Russian Qt Forum

Добрый день

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

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

Спасибо

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

:) Я сам заядлый велосипедист, но здесь - не стоит, octree сильнее (и его не нужно будет бесконечно латать). У меня расчет начинается с облака точек, по ним я строю треугольники, поэтому дерево для поиска вертексов у меня по-любому есть. Строить еще одно дерево - жаба давит. Неужели нельзя обойтись одним? Давайте-ка подумаем, а то как что нешаблонное - так сразу уж и "неудобная структура данных"  :)

(Следующий параграф слабонервным лучше не читать)
Объем данных не фиксирован. Т.е. если получен отказ на malloc -  надо парить по частям. Так что сажать (кучерявые) деревья почем зря в мои планы не входит   

Под какую ось пишешь?

OcTree используется только для поиска вершин? Или еще для чего то? (Просто интересно)

А зачем вам дерево для поиска вертексов? У вас логическая единица задачи - треугольник.
Проблемы вашей структуры данных следующие:
1) Сборка треугольника из вертексов - это дополнительная подзадача, к тому же с кучей if-ов.
2) Понятие ближайшей точки субъективно. Что такое ближайшая точка?
Какие у вашей структуры данных преимущества?

OSX + (злополучное) Вындоуз

Наоборот, треугольники в данном случае играют вспомогательную роль. Упрощенно: сначала создается облако вертексов, у каждого есть "зона захвата/влияния" которая многократно корректируется в процессе расчета. Если один вертекс влияет на другой - образуется ребро. Какие-то вертексы могут не иметь ребер, в каких-то (пусть редких) случаях треугольников может вообще не быть.

Igors, есть какое-то решение? Или хотите посмотреть варианты?

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

Задумка простая: сначала (предрасчет) для каждого вертекса рассортировать все выходящие из него ребра "по углу". Тогда треугольники будут (почти) готовы

Чисто к сведению: на юникс-лайк системах malloc/new не всегда возвращает NULL (или генерит bad_alloc в случае new), а возвращает "корректный" адрес на участок памяти. При первом обращении к такому участку памяти получаем краш. Так что проверки на NULL, ловля bad_alloc, установка new handler бесполезны. Все это связано с memory overcommit. (http://"http://opsmonkey.blogspot.com/2007/01/linux-memory-overcommit.html"). Думаю будет полезно ознакомиться.

Сорри за оффтоп.

Это я для простоты так сказал "отказ malloc". На самом деле в этом проекте все выделения памяти перекрыты и NULL возвращается если общее кол-во выделенной памяти превысило предел заданный пользователем. Дальше начинается (довольно мучительное) выяснение какие данные снести на диск (чтобы затем опять подгрузить). Это я к тому что с деревьями особо не разогнаться.

Пастор, Вы стали много читать  :)

В общем сделал, все оказалось легко. Для каждого вертекса сортирую исходящие из него ребра по углу. На поиске просто перебираю ребра, каждое образует треугольник с предыдущим. Плюс 2 дополнительные проверки

- проверка угла между ребрами на < 180
- проверка "треугольник уже был рассмотрен". Реализовал незатейливым массивом и линейным просмотром