Пересечение, объединение и разность многоугольников

Такая ситуация не возможна, если у нас CD делится сплитером UK (почему UK, кстати? Ведь отрезок UF после деления сплиттером 0E должен распасться на два (UK и KF), и сплиттер UK должен попать в другую половину дерева, а здесь должен работать сплиттер KF), то положительные элементы после разделения сплиттером должны обрабатыватся дальше безымянным сплиттером F? (? - самая правая вершина на рисунке), точнее не им, а его половиной, которая образовалась, когда его на первом шаге рассек сплиттер 0E. А вот он уже классифицирует CH как лежащий внутри многоугольника.
Проверь, похоже тут из дерева пропал сплиттер F?.

Или покажи BSP-дерево для многоугольника EGUF... желательно, с подписанными буковками, а то набор чисел не воспринимается абсолютно.

Спасибо

Цитата

Проверь, похоже тут из дерева пропал сплиттер F?.

Да, именно так. Его не было в BSP - я его выкидывала так как t1 = 0.003... а у меня стояла погрешность на 0.005!
Правда все равно есть глюки:( Буду дальше разбираться, что не так делаю...

может кто что нибудь сказать про тип данных vec2 ..какой файл для него надо подключать.?

Цитата icetnt @ 02.09.08, 17:34

может кто что нибудь сказать про тип данных vec2 ..какой файл для него надо подключать.?

Никакой. Возьми и сам напиши реализацию

albom ясно значит просто обычная структура с 2мя полями как бе =)

Добавлено 02.09.08, 17:56
хотя скорее класс.

Именно так, просто точка на плоскости + пара вспомогательных функций.

а может уважаемый albom подкинет листинг vec2 ?

При всем уважении, но я бы не советовал вам браться за эту задачу. Если вы даже пять строчек самостоятельно написать не можете, то и реализация vec2 вам не поможет

Злой вы
проблема только в d1 ^ d2. Как называется эта операция над векторами?

Цитата VG54 @ 27.09.08, 15:40

d1 ^ d2. Как называется эта операция над векторами?

Векторрное произведение, вроде. Собственно, проверить легко, всё равно она тут только в одном месте затесалась, а именно взять уравнение прямой a+t*d, где a - точка на прямой, d - вектор, параллельный прямой, t - скаляр, взять аналогичное уравнение для второй, и решить

Цитата VG54 @ 27.09.08, 15:40

Злой вы

Увы, увы

Цитата

Векторрное произведение

Если я правильно поняла, то d₁ и d₂ - направляющие вектора отрезков, для которых ищется точка пересечения. У коллинеарных векторов векторное произведение равно 0, и функция возвращает false.

Да, всё задумывалось именно так.

2albom
Совпадающие(в т.ч. частично) грани многоугольников алгоритм считает коллинеарными и выкидывает в положит. полуплоскость, т.е. в итоговых результатах (например в polygonIntersection) их не показывает. Это бага или фича?

Сообщение отредактировано: VG54 - 29.09.08, 18:56

Как минимум, это неинтересное с точки зрения алгоритма обстоятельство. Если критично, поразбирай самостоятельно возможные случаи - это же просто техническая проблема.

Добавлено 29.09.08, 19:30

Цитата VG54 @ 29.09.08, 18:39

Это бага или фича?

Фича. Посмотри на функцию split(), условие вполне ясно показывает, как в данном случае реализация себя ведет.

Скажите, пожалуйста, а если многоугольники касаются в одной точке или по стороне, подойдут ли для операции объединения/пересечения bsp-деревья?
И еще один вопрос (я не очень поняла) если одна из сторон многоугольника совпадает со сплиттером, то она в дерево уже не идет на данной этапе?