Работа с триангуляцией в программе

[zcorvid]

Имеется следующая ситуация. Есть прямоугольник примерно 2500 на 2000 (это на самом деле пиксели изображения), его нужно триангулировать (необязательно треугольниками, главное чтобы полигоны триангуляции были выпуклыми, как такую "триангуляцию" называют я не знаю, поэтому прошу прощения за неточность терминологии). Триангуляция у нас входной параметр, то есть её будет задавать пользователь вручную. Нужно как-то организовать её хранение в памяти компьютера, при этом требуется, чтобы можно было (относительно) быстро узнавать, в каком полигоне лежит точка с заданными координатами. Посоветуйте, пожалуйста, как можно организовать такую структуру данных.

Триангуляцию можно хранить либо как граф на плоскости (список точек-вершин, и списки рёбер, рёбра на плоскости представляются прямолинейными отрезками), либо списком полигонов (в этом случае получится некоторое дублирование информации - каждое ребро будет помещено в память дважды). Для быстрого определения полигона, в который попадает точка с заданными координатами я пока не могу придумать ничего лучше, кроме как предрассчитать эту информацию для всех точек изображения, запомнив для каждой точки указатель на соответствующий полигон (или его ID). Но это адский объём информации, кроме того даже малое изменение триангуляции повлечёт за собой либо полный пересчёт этой информации (это займёт много времени), либо придётся создавать специальные алгоритмы пересчёта для разных ситуация изменения триангуляции, что также может оказаться не очень просто (и снова, скорее всего, займёт много времени для не очень больших триангуляций).

[Eimrine]

Если бы ваши полигоны не были бы гарантированно выпуклыми, то скорее всего, ваш вариант был бы самым лучшим. Что если попробовать для каждого полигона просчитать 4 крайних точки (верх/низ/лево/право), а потом для каждого заданного пикселя поискать, какие полигоны ему точно не подойдут? Предполагаю, что останется только один.

upd: Думаю, это можно делать и на лету.

[arseniiv]

Eimrine в сообщении #1150159 писал(а):

Что если попробовать для каждого полигона просчитать 4 крайних точки (верх/низ/лево/право), а потом для каждого заданного пикселя поискать, какие полигоны ему точно не подойдут? Предполагаю, что останется только один.

Видно, что не всегда один; пример — разделите прямоугольник диагональю. Зато вашу идею можно модифицировать — разбить полигоны на прямоугольники и прямоугольные треугольники.

-- Пт сен 09, 2016 00:06:40 --

…со сторонами, параллельными одним и тем же для всей картинки прямым. Однако это не всегда возможно.

-- Пт сен 09, 2016 00:08:43 --

Но, конечно, нужная модификация проверки будет — придётся просто иногда смотреть, если точка входит в одну область, не входит ли она при этом ещё в одну.

[slavav]

Для представления прямолинейных планарных графов годится DCEL/РСДС: https://en.wikipedia.org/wiki/Doubly_co ... _edge_list
Для локализации точек за $\log N$, где $N$ - число рёбер, можно использовать алгоритм детализации триангуляции Киркпатрика (он сложный) или метод полос (он простой, но может потребовать $N^2$ памяти).

Ещё можно попытать счастья с quadtree: https://en.wikipedia.org/wiki/Quadtree . Это простая универсальная структура, но её сложность и скорость работы зависят от структуры триангуляции. Поиск всегда будет не хуже чем $\log$ числа пикселей.

[wrest]

Eimrine в сообщении #1150159 писал(а):

Предполагаю, что останется только один.

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

[slavav]

Забыл ещё одну структуру поисковую: BSP (https://ru.wikipedia.org/wiki/%D0%94%D0 ... 0%B2%D0%B0).
Её применение аналогично применению quadtree. Начинаем со всей картинки. Режем прямоугольник поперёк длинной стороны по границе между пикселями. Каждый узел дерева хранит список многоугольников, который с ним пересекаются, двух детей и разделяющую прямую. Разбиение останавливается когда в узле остался только один многоугольник (как вариант - некоторое небольшое количество многоугольников) или когда узел ограничивает только один пиксель (как вариант - некоторое небольшое количество пикселей). Локализация состоит в спуске по дереву. Когда попадаем в лист и в листе не один многоугольник, надо сделать локализацию относительно этих многоугольников. Итого $\log N + \log M$, $N$ - число рёбер, $M$ - число пикселей.
Сложность построения BSP и объём памяти могут быть большими. Это зависит от триангуляции. К счастью структура простая и можно поставить эксперимент.
Это только один способ. А ведь можно BSP строить проводя прямые по рёбрам триангуляции. Выбирать ребро можно случайно. Почти всегда будет получаться дерево с высотой $O(\log N)$. Полагаю что построится оно за $O(N\log N)$ и займёт $O(N)$ памяти. Собственно локализация немного сложнее чем двоичный поиск. Среднее время поиска $O(\log N)$.