Найти треугольник [решено]

[Igors]

Добрый день

Есть контейнер вершин связанных ребрами (граф). Каждая вершина хранит список вершин с которыми она образует ребро. Есть ф-ция которая умеет для любой точки p возвращать список ближайших вершин. При этом запросная точка p может совпадать с одной из вершин или нет.

Задача: для произвольной точки p (нарисована покрупнее) найти треугольник в котором она находится, т.е. три вершины (p0, p1, p2)  соединенные ребрами.  

Спасибо

[alexman]

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

Пока писал еще в голову пришло:
1. Строим р-дерево с привязкой бинов к треугольникам. (Один раз строится). UPDATE р-дерево даже излишне. Достаточно просто сетки, где каждый бин связан со списком треугольников.
2. Находим нужный бин. А далее просто перебор или процедура выше.

ЗЫ 100% все нюансы не учтены.

[Blackwanderer]

Вершины знают свои координаты? Искать нужно для одной точки или для многих?

[Igors]

Вершины знают свои координаты? Искать нужно для одной точки или для многих?

Ну конечно координаты есть (иначе не нарисовать аттач). Искать нужно для многих (намного больше чем число вершин) и как можно быстрее. Поиск ближайших вершин (дерево) уже реализован, Теперь надо найти ячейку (треугольник)

[Blackwanderer]

Поиск ближайших вершин (дерево) уже реализован, Теперь надо найти ячейку (треугольник)

Не совсем понятно, что вы имеете ввиду. Если вы уже локализовали область поиска (нашли ближайшие точки) то дальше только полным перебором по этой локальной области (для каждой ближайшей точки формируются и проверяются все треугольники с вершиной в этой точке). А вообще, какая-то неудобная структура данных для такой задачи.
По списку треугольников такой поиск можно выполнять со сложностью O(1) в среднем:
1) Накрываем триангуляцию прямоугольной сеткой;
2) Заносим ссылку на каждый треугольник в те прямоугольники, в которых он лежит хотя бы частично;
3) Для произвольной точки проверяем на попадание только те треугольники, которые записаны в прямоугольник, в который попала точка.

[Igors]

По списку треугольников такой поиск можно выполнять со сложностью O(1) в среднем:
1) Накрываем триангуляцию прямоугольной сеткой;
2) Заносим ссылку на каждый треугольник в те прямоугольники, в которых он лежит хотя бы частично;
3) Для произвольной точки проверяем на попадание только те треугольники, которые записаны в прямоугольник, в который попала точка.

Так в один прямоугольник может попасть много а в другой почти ничего. Поэтому по-хорошему надо делать сетку адаптивной (прямоугольник хранит дочерние (меньшие) прямоугольники). Эта структура называется multi-resolution OcTree (кстати именно она реализована для поиска вершин).

Ну что сказать.. да, это будет работать, но реализация и объем нужной памяти (еще одно дерево) не маленькие, да и O(1) там совсем не пахнет. Накладно получается, нет ли решения попроще? 

[alexman]

Есть ф-ция которая умеет для любой точки p возвращать список ближайших вершин.

Блин, сразу не увидел. Мимо ушей...

Можно анализировать пересечение вертикальной линии, проходящей через точку, со всеми ребрами ближайших вершин. Ну и найти два ближайших к точке ребра, которые пересекает вертикальная линия и выходят из одной вершины. Время О(число ребер ближайших вершин).

[Blackwanderer]

А вам принципиально представление триангуляции именно узлами? На мой взгляд для этой задачи это крайне неудачная структура. Она порождает слишком много неоднозначностей, а следовательно - слишком много проверок, что усложняет разработку алгоритма.

да и O(1) там совсем не пахнет

Ну O(C) в среднем если вам это так принципиально

[Igors]

А вам принципиально представление триангуляции именно узлами? На мой взгляд для этой задачи это крайне неудачная структура. Она порождает слишком много неоднозначностей, а следовательно - слишком много проверок, что усложняет разработку алгоритма.

Пожалуйста, предлагайте лучшую организацию данных (но без жирных дополнительных структур, сеток и.т.п.)

[alexman]

Как всегда две крайности: либо память, либо время

[Igors]

Можно анализировать пересечение вертикальной линии, проходящей через точку, со всеми ребрами ближайших вершин. Ну и найти два ближайших к точке ребра, которые пересекает вертикальная линия и выходят из одной вершины. Время О(число ребер ближайших вершин).

Не гарантируется что поверхность замкнута (т.е. каждое ребро входит в 2 - и только 2 треугольника). Поэтому ближайшими могут оказаться ребра разных треугольников. Да и расчетов многовато. Напр дерево выдало 10-15 ближайших вершин, у каждой примерно 6 ребер. Понятно что многие будут повторяться, но все же..

[Blackwanderer]

Пожалуйста, предлагайте лучшую организацию данных (но без жирных дополнительных структур, сеток и.т.п.)

Я использую два двумерных массива (в том числе и при решении вашей задачи):
xy: вещественный размеров nx2 для хранения координат вершин
nvtr: целочисленный mx3 для хранения треугольников (вершины треугольников хранятся в виде индексов элементов массива xy)

[alexman]

Не гарантируется что поверхность замкнута (т.е. каждое ребро входит в 2 - и только 2 треугольника). Поэтому ближайшими могут оказаться ребра разных треугольников.

Ну здесь достаточно дополнительной проверки.

Да и расчетов многовато.

Что-нить наколдовать.

[Igors]

Я использую два двумерных массива (в том числе и при решении вашей задачи):
xy: вещественный размеров nx2 для хранения координат вершин
nvtr: целочисленный mx3 для хранения треугольников (вершины треугольников хранятся в виде индексов элементов массива xy)

Это обычная полигонная модель (mesh), но зная индекс вертекса (вершины) мы ничего не можем сказать о треугольниках в которые он входит. Для быстрого поиска нужны еще данные,

[Blackwanderer]

Для быстрого поиска нужны еще данные

Двумерный массив списков. Каждый список - номера треугольников (из nvtr), которые попадают в соответствующий прямоугольник. У меня сетка достаточно равномерная, так что в адаптивной прямоугольной сетке нужды не было. Если нужна адаптивная - например список списков. Первые k*p элементов символизируют первичную прямоугольную сетку. Если в этих элементах содержатся положительные числа - то это индексы из nvtr, если отрицательные - то это четыре элемента списка (с индексом больше чем k*p) являющиеся четырьмя прямоугольниками, на которые разбит первичный четырехугольник ну и дальше по рекурсии.