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

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

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

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

Дано - порядка сотни невыпуклых полигонов, которые частично перекрываются
Между полигонами может оставаться свободное пространство, не занятое ни одним полигоном.
Задача - определить площадь свободного пространства (внутренних белых многоугольников)
ИзображениеИзображение

Пишу на js. На данный момент использую эту библиотеку https://github.com/voidqk/polybooljs
Работает очень медленно для моих нужд (нужно иметь возможность запускать скрипт сотни раз в секунду). Буду рад рекомендации какой-нибудь ОЧЕНЬ быстрой библиотечки аналогичной этой  (необязательно js, если крутой алгоритм, то перепишу или запущу на сервере).

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


#1
14:41, 20 фев. 2019

А чёнить с BSP намутить пробовал? Или эти либы то дже самое делают?

#2
15:04, 20 фев. 2019

Конкретно эта библиотека - не использует BSP

+ Показать

а с BSP с какой стороны подойти к этой задаче? Можно подробнее?

#3
15:07, 20 фев. 2019

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

#4
15:18, 20 фев. 2019

grea
> Задача - определить площадь свободного пространства (внутренних белых
> многоугольников)
Многоугольники покрывают всю площадь? Или важно найти такие вот дырки только в конкретной группе многоугольников?
Есть ли возможность использовать GPU?

grea
> Например, какой нибудь трюк со сканирующим лучом
Собственно да, самый простой вариант, ищешь пересечение многоугольников со сканирующим лучом, сортируешь их по оси Х (с сохранением ID многоугольника), и дальше - остается попарно посчитать количество пересечений. Там где количество пересечений для всех ID будет четным - будет дырка, "ширина" дырки - расстояние между этими точками.

Если количество многоугольников порядка сотни, да еще и хранить для каждого его min/max, чтоб сразу откинуть лишние, количество проверок будет вполне приемлемым.

Если на GPU - можно как распараллелить этот процесс, так и явно посчитать оставшееся пространство через тот же glBeginQuery/glEndQuery.

#5
15:30, 20 фев. 2019

если не планируется поддержка утюгов, то я бы посмотрел в сторону чего-нибудь clipper-подобного и wasm.
например https://www.npmjs.com/package/js-angusj-clipper

#6
15:30, 20 фев. 2019

1 frag / 2 deaths
Мне придется строить BSP дерево каждый раз, потому что геометрия полигонов непрерывно меняется. Выиграю ли я что-то тогда в скорости алгоритма?

Fantom09
область подсчета ограничивается параллелограммом, он большей частью находится внутри полигонов но нет гарантий, что свободная область не будет с ним граничить в какой-то момент времени.

Я так понимаю GPU мне выдаст количество незакрашеных пикселей? Я хотел бы получить большую точность, хотя бы семь значащих цифр

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

#7
15:34, 20 фев. 2019

iKest
Интересная штука, но жаль что целочисленная, мне нужно иметь хорошую чуткость алгоритма даже к микроскопическим изменениям геометрии.

#8
15:37, 20 фев. 2019

ну можно в принципе заморочиться с созданием нативного аддона для node на базе того-же клиппера. это если server-side планируется...

#9
15:43, 20 фев. 2019

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

#10
15:48, 20 фев. 2019

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

#11
15:50, 20 фев. 2019

А откуда они взялись - сотни полигонов? Может проще их изначально расставлять правильно?
Полигоны могут быть абсолютно любыми? Или есть некие универсальные правила? На картинке они весьма симметричные и не пустые в центре. Этим можно попробовать воспользоваться.

#12
15:56, 20 фев. 2019

Dmitrrr
Все полигоны примерно одного размера, без дырок внутри, похожи на скругленный равносторонний треугольник, но граница на каждой итерации немного меняется. Иногда возникает небольшое самопересечение ( В принципе это можно детектить и не допускать, но боюсь дополнительно потерять в производительности, само по себе это не сильно важно для вычислений)

#13
15:59, 20 фев. 2019

grea
> По сканирующему лучу - я получу некоторое количество точек, которые находятся
> на границе свободной области. Как теперь определить порядок их обхода и
> связность, чтобы правильно посчитать площадь и количество полигонов?
У тебя задача посчитать площадь или построить многоугольник, описывающий эту дырку?
если площадь, то там все просто. Возьмем твой рисунок:
Пересечение полигонов со сканирущим лучом | Быстрый алгоритм нахождения дырок между полигонами
Там у луча 6 пересечений с тремя многоугольниками A,B и C
Пулучаем такую схему, после сортировки по Х:
1B, 2A, 3B, 4A, 5C, 6C

1B, 2A, 3B, 4A - здесь пересекаются полигоны A и B, но в точке 4 - для обоих полигонов  у нас четное количество пересечений - 1B - 3B - полигон закрыт, 2А - 4А - полигон закрыт

Дальше у нас идет 5С - 6С, тоже полигон закрыт
итого - имеем дырку между 4А и 5С
ширина разрыва S[y]= 5C.x-4A.x
Сканирующий луч идет по вертикальной оси, суммируешь все разрывы - получаешь общую площадь всех пересечений.
Добавив триггер - были пересечения/не были - можешь даже локализовать эту площадь.

Точность - это уже более сложный вопрос, во-первых - нужно точно определять пересечения луча с полигонами, с учетом всех граничных случаев. Неплохо разобрано здесь:
https://www.inf.usi.ch/hormann/papers/Hormann.2001.TPI.pdf

Длины отрезков по оси Х будет равны вычислительной точности
А вот сканирование по вертикали - это уже регулируемая точность, зависит от того, с каким шагов ты собираешься это делать, если у тебя размер картинки 1024 пикселя и тебе нужна точность "хотя бы семь значащих цифр", то это нужно уменьшать шаг по оси Y.

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

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

Можно попробовать прикрутить glut tessellation. По идее, там можно все инвертировать так, что оно тебе сразу отдаст треугольники, относящиеся к дыркам.

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

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