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

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

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

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

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


#16
16:08, 20 фев. 2019

Fantom09
Такое решение не подойдет. Слишком малый шаг тогда будет по оси Y для требуемой точности, значит много итераций и ничего не выиграется по производительности. Это полувекторно-полурастровое решение, а нужно чисто векторное.

#17
16:11, 20 фев. 2019

grea
> Это полувекторно-полурастровое решение, а нужно чисто векторное.
Нужно было с этого начинать, что решение должно быть аналитическим с точностью в 7 знаков, работать на джава скрипте, топология непрерывно обновляется и нужно находить решение 100 раз в секунду :)

#18
16:14, 20 фев. 2019

Fantom09
если получится 1000 раз в секунду находить, будет еще круче)

#19
16:36, 20 фев. 2019

Тут можно попробовать с другой стороны зайти, вместо поиска дырок и вычисления их площади - объединить все полигоны в один, посчитать его площади и вычесть ее из площади параллелограмма, остаток и будет искомая площадь. Но от этого задачка не становится проще :)
Это что-то типа:
http://www.cs.man.ac.uk/~toby/alan/software/gpc.html

#20
16:37, 20 фев. 2019

grea
> Мне придется строить BSP дерево каждый раз, потому что геометрия полигонов
> непрерывно меняется. Выиграю ли я что-то тогда в скорости алгоритма?
Всех полигонов, или только одного-двух в кадр? Можно кешировать ноды.

#21
17:06, 20 фев. 2019

Fantom09
Собственно сейчас так и делаю с помощью той библиотечки, которую указал в первом посте, но быстродействие ее совершенно не устраивает. iKest предложил быструю библиотеку, жаль что целочисленная, но оставлю ее на крайний случай, если не найдется какого-то другого решения.

#22
17:06, 20 фев. 2019

1 frag / 2 deaths
Абсолютно все двигается, какие-то узлы медленно, какие-то быстро.

#23
17:24, 20 фев. 2019

Пока попробую эту библиотеку прикрутить
https://sourceforge.net/projects/jsclipper/
На моем компе она показала в бенчмарках одинаковую скорость как для целых так, для вещественных параметров.

#24
17:33, 20 фев. 2019

Fantom09
> А вот сканирование по вертикали - это уже регулируемая точность, зависит от того, с каким шагов ты собираешься это делать
Шагать по Y надо по точкам исходных многоугольников.
А площадь считать с учетом получающихся трапеций.

#25
17:39, 20 фев. 2019

grea
> Абсолютно все двигается, какие-то узлы медленно, какие-то быстро.
Ну, может быть не очень быстро, да.

#26
17:40, 20 фев. 2019

}:+()___ [Smile]
> Шагать по Y надо по точкам исходных многоугольников.
> А площадь считать с учетом получающихся трапеций.
В принципе да, алгоритм слегка изменится, но в целом решаемо.
Я вообще хотел предложить итерационный метод, но так пожалуй лучше :)

#27
17:45, 20 фев. 2019

}:+()___ [Smile]
Допустим, нашел точки пересечения полигонов и отсортировал их с узлами. Не очень представляю как в итоге получить правильный список трапеций, чтобы наконец все просуммировать. Так то это логично, но не понял как к этому подступиться.

#28
17:48, 20 фев. 2019

Надо каким-то образом получить замкнутый контур дырки, а дальше считать обычным методом интегрирования трапеций (калькулятор площади меня уже есть, проблема - получить контур с правильным порядком точек)

#29
18:00, 20 фев. 2019

grea
> проблема - получить контур с правильным порядком точек
там не нужен контур
у тебя будет две вершины, с координатами Yi и Yi+1, и соответственно точки пересечения всех многоугольников, с линией проходящими через Yi и Yi+1. Дальше тот же принцип - считаешь парность, чтоб найти незамкнутую область. В итоге имеешь в рамках одной области - 4 точки пересечения, образующие трапецию. Считаешь площадь трапеции (по формуле) и дальше накапливаешь ее.

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

следующая итерация будет считаться для Yi+1, Yi+2, потому разрывов не будет, и необходимости в построении контура нет, по сути ты разбиваешь многоугольник пустой области на набор трапеций, и дальше считаешь его площадь как сумму площадей этих трапеций

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

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