Войти
ПрограммированиеФорумГрафика

Быстрый алгоритм нахождения дырок между полигонами (3 стр)

Advanced: Тема повышенной сложности или важная.

Страницы: 1 2 3 4 5 Следующая »
#30
18:05, 20 фев. 2019

grea
> Не очень представляю как в итоге получить правильный список трапеций, чтобы наконец все просуммировать.
Ну вот ты перешел от Y1 к Y2, а размер дырки изменился от L1 к L2. Тогда добавленная площадь дырки будет (L1 + L2) × (Y2 − Y2) / 2.

Хотя тут будет проблема с определением, относится ли отрезок к дырке, или это кусок внешнего окружения.

Контур получить тоже просто: соединяешь нетривиальные точки дырки в списки, потом обходишь.
Кстати, пересечения полигонов заранее считать и сортировать не надо.
Просто хранишь скорость движения точек при движении сканирующей линии и считаешь время столкновения всех соседей.


#31
18:27, 20 фев. 2019

Fantom09
точка может лежать внутри одного, двух или трех разных полигонов одновременно.
Думаю, тут будут большие проблемы с парностью

#32
18:36, 20 фев. 2019

Хотя нет, можно проверить с каждым полигоном по отдельности, и выбрать те, которые не лежат внутри ни одного. Тогда действительно можем получить набор отрезков, распределить их по связности и отдельно просчитать. В принципе, должно получиться.

#33
19:54, 20 фев. 2019

grea
> Наверное, если бы авторы смогли обойти ограничения целочисленности, они бы так
> и сделали
Ты просто пока еще не осознал, что целочисленность в данном алгоритме - благо. Целочисленность дает фиксированную погрешность вне зависимости от того, где находится точка. А не так, как флоат, что в районе нуля у нас маленькая погрешность, а где-то далеко - гигантская.

grea
> мне нужно иметь хорошую чуткость алгоритма даже к микроскопическим изменениям
> геометрии.
Просто умножь свои координаты на большое число, чтобы в целых числах это были скажем десятки миллионов и округли. Погрешность будет маленькая. Затем используй эту библиотеку, а результат клиппинга потом раздели на это большое число.

#34
20:45, 20 фев. 2019

Хорошая разминка ума на самом деле... Алгоритмов можно придумать много, но все они весьма сложные и значит не быстрые. Без тестов не понять какой быстрее. А сложность их такая, что код можно неделю писать. Не лень?

Мне даже описывать и детально продумывать эти алгоритмы лень))

Ладно, совсем кратко:
Алгоритм 1.
Для начала находишь все точки пересечения граней полигонов (можно рассматривать только более менее близкие, раз у тебя нет особо вытянутых и разных по габаритам форм)
Так же разбиваешь каждый полигон на треугольники.
Потом берёшь любой узел на границе конкретного полигона и идёшь по его контура по всем сторонам, узлам и точкам пересечения. По пути рассматриваешь каждый отрезок между характерными точками (узлами или точками пересечения). Для каждого отрезка рассматриваешь 2 точки на 0,0000001 справа и слева от середины (твоя точность). И проверяешь попадают ли эти 2 точки хотя бы в одни из треугольников полигонов. Если точка не попадает ни в один из полигонов, то запоминаешь её, как координату дырки.
Повторяешь это со всеми полигонами.
Теперь ты имеешь в каждой дырке координату хотя бы одной произвольной точки.
Остаётся только построить лучи до соседних точек и проверить лежат ли отрезки целиком в дыре или нет (проверяешь точку в 0,0000001 от второй точки). После этого построить лучи из вторичных точек и опять проверить. Так можно нащупать размеры каждой дыры.

Алгоритм 2.
Опять найти координаты всех пересечений граней полинона.
После этого разбить всю твою зону на треугольники так, чтобы каждый узел и каждая очка пересечения являлась вершиной нескольких треугольников. Гугли алгоритмы триангуляции.
После этого останется определить для каждого треугольника принадлежит ли он хотя бы одному полигону или нет. Это тоже не просто, но решаемо.
Ну и в конце взять сумму ничейных треугольников.

Можно и другие придумать, но они получаются не менее наворочены.

#35
23:31, 20 фев. 2019

Dmitrrr
сканирующий луч с идеей Смайла (про то что не надо пересечения считать) выглядит очень быстрым.

#36
23:51, 20 фев. 2019

Горизонтальная сканлиния (уже предлагали)
Движется снизу вверх по вершинам полигонов, в порядке возрастания Y. При этом два исходящих из вершины отрезка (стороны полигона) добавляются/удаляются, в зависимости от ориентации, в список активных сторон, которые сортированы по X точки пересечения сканлинией. Список реализован как сбалансированное дерево (rb-tree / b-tree / avl-tree) для быстрых поиска/вставки/удаления. Для каждой пары соседних отрезков запоминаем событие их пересечения - и помещаем в heap, сортированный по Y, там же и события прохождения вершин.
Между двумя последовательными событиями имеем набор непересекающихся трапеций, для которого несложно подсчитать площадь. Учтем, что событие меняет 1-2 трапеции, а у прочих ширина сечения меняется линейно, можно сократить вычисления и свести время к O(N*log(N))

#37
3:56, 21 фев. 2019

а просто растеризовать это, отрендерив на видюхе и посчитав количество незакрашенных пикселей -- слишком просто?

#38
6:59, 21 фев. 2019

Suslik
Автор хочет точность 10^-7 и скорость

Любопытно, зачем все это?

#39
7:08, 21 фев. 2019

}:+()___ [Smile]
> Хотя тут будет проблема с определением, относится ли отрезок к
> дырке, или это кусок внешнего окружения
Действительно, если две полигона в форме буквы Л при пересечении формируют замкнутое кольцо или не формируют - придется строить внешнюю оболочку

#40
9:35, 21 фев. 2019

kipar
> сканирующий луч с идеей Смайла
Да, хороший вариант (особенно в том, что можно рассматривать не все подряд лучи, а только пересекающие характерные точки, пусть их и будет десяток тясяч). Возможно, он самый простой и понятный. Но он тоже потребует:
1. нахождения всех точек пересечения полигонов друг с другом (это тоже характерные точки, через которые надо проводить лучи)
2. Нахождения точек пересечения всех тысяч лучей со всеми полигонами
3. Алгоритма проверки нахождения точек внутри полигонов (а это на предварительный взгляд возможно только предварительно разбив все полигоны на треугольники)

И в сумме это опять получится куча вычислений не меньше, чем в других вариантах.

#41
9:51, 21 фев. 2019

Aslan
Меня в сканлинии беспокоят самопересечения, после которых меняется ориентация отрезка.
Точность нужна, чтобы считать дельту площади между соседними итерациями и оценить эффективность шага.

MrShoor, спасибо, обдумаю, проэкспериментирую)

Dmitrrr
Триангуляцию придется делать каждую итерацию. В принципе в каждом полигоне два-три десяток узлов, должно довольно быстро считаться, надо экспериментировать.

Всем
использую сейчас вот эту штуку
http://jsclipper.sourceforge.net/6.4.2.2/main_demo.html
Version  :  6.4.2.2 (FPoint)                         
Date      :  8 September 2017 

Оказалась намного шустрее других библиотек. Пока более-менее пригодно. Интуитивно кажется, что самая быстрая реализация увеличит скорость в пару раз, а не на порядок. Так что пока её использую, чтобы процесс на месте не стоял.

#42
9:58, 21 фев. 2019

Dmitrrr
> 1. нахождения всех точек пересечения полигонов друг с другом (это тоже
> характерные точки, через которые надо проводить лучи)
не потребуется. В том и крутизна идеи. Берем луч проходящий через вершины, находим все его пересечения с отрезками, дальше зная наклон отрезков можем понять, когда соседние точки пересекутся, если какое-то пересечение будет раньше следующей вершины - рассматриваем его.
> 2. Нахождения точек пересечения всех тысяч лучей со всеми полигонами
со всем отрезками. т.е. это всего две проверки - x<xmax&&x>xmin. Но да, в худшем случае квадратичная сложность от числа точек. В остальных алгоритмах эта квадратичная сложность легко может получиться еще на поиске точек пересечения.
> 3. Алгоритма проверки нахождения точек внутри полигонов
не потребуется. просто считаем четное ли число раз мы пересекали стороны.

#43
10:02, 21 фев. 2019

kipar
Одна точка может лежать хоть внутри двух, хоть в трех других полигонах. Может получиться ложная четность

#44
10:11, 21 фев. 2019

grea
> Меня в сканлинии беспокоят самопересечения, после которых
> меняется ориентация отрезка
Проблема не в пересечениях, а на рисунке
1 | Быстрый алгоритм нахождения дырок между полигонами
Слева дырки нет, справа есть
И эти случаи не различить, не построив внешнюю границу

> Одна точка может лежать хоть внутри двух, хоть в трех других
> полигонах. Может получиться ложная четность
Считать глубину - когда внешняя нормаль полигона смотрит влево +1, вправо -1, глубина>0 - внутри когото

Страницы: 1 2 3 4 5 Следующая »
ПрограммированиеФорумГрафика

Тема в архиве.