Russian Qt Forum
Ноябрь 23, 2024, 04:42 *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

Войти
 
  Начало   Форум  WIKI (Вики)FAQ Помощь Поиск Войти Регистрация  

Russian Qt Forum > Forum > Программирование > Алгоритмы > Найти треугольник [решено]
Страниц: [1] 2   Вниз
« предыдущая тема следующая тема »
  Печать  
Автор Тема: Найти треугольник [решено]  (Прочитано 15516 раз)
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« : Январь 29, 2012, 17:51 »
Добрый день

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

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

Спасибо
« Последнее редактирование: Февраль 03, 2012, 10:18 от Igors » Записан
alexman
Гость
« Ответ #1 : Январь 29, 2012, 18:26 »
Ну если опустить перебор, то пока в голову приходит следующее:
1. Завести новую структуру данных-граф: каждый треугольник есть вершина графа, а ребра смежных треугольников есть совпадающие стороны. (Один раз строится. Возможно, это лишнее).
2. Провести из точки вертикальный луч (не важно). Найти самый верхний треугольник (тут просто: пересечение двух перпендикулярных прямых + найти соответствующий треугольник).
3. Далее добраться по новому графу до треугольника.

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

ЗЫ 100% все нюансы не учтены.
« Последнее редактирование: Январь 29, 2012, 18:34 от alexman » Записан
Blackwanderer
Гость
« Ответ #2 : Январь 29, 2012, 20:33 »
Вершины знают свои координаты? Искать нужно для одной точки или для многих?
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #3 : Январь 30, 2012, 08:39 »
Цитата: Черный Странник от Январь 29, 2012,  20:33
Вершины знают свои координаты? Искать нужно для одной точки или для многих?
Ну конечно координаты есть (иначе не нарисовать аттач). Искать нужно для многих (намного больше чем число вершин) и как можно быстрее. Поиск ближайших вершин (дерево) уже реализован, Теперь надо найти ячейку (треугольник)
Записан
Blackwanderer
Гость
« Ответ #4 : Январь 30, 2012, 10:53 »
Цитата: Igors от Январь 30, 2012,  08:39
Поиск ближайших вершин (дерево) уже реализован, Теперь надо найти ячейку (треугольник)
Не совсем понятно, что вы имеете ввиду. Если вы уже локализовали область поиска (нашли ближайшие точки) то дальше только полным перебором по этой локальной области (для каждой ближайшей точки формируются и проверяются все треугольники с вершиной в этой точке). А вообще, какая-то неудобная структура данных для такой задачи.
По списку треугольников такой поиск можно выполнять со сложностью O(1) в среднем:
1) Накрываем триангуляцию прямоугольной сеткой;
2) Заносим ссылку на каждый треугольник в те прямоугольники, в которых он лежит хотя бы частично;
3) Для произвольной точки проверяем на попадание только те треугольники, которые записаны в прямоугольник, в который попала точка.
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #5 : Январь 30, 2012, 11:15 »
Цитата: Черный Странник от Январь 30, 2012,  10:53
По списку треугольников такой поиск можно выполнять со сложностью O(1) в среднем:
1) Накрываем триангуляцию прямоугольной сеткой;
2) Заносим ссылку на каждый треугольник в те прямоугольники, в которых он лежит хотя бы частично;
3) Для произвольной точки проверяем на попадание только те треугольники, которые записаны в прямоугольник, в который попала точка.
Так в один прямоугольник может попасть много а в другой почти ничего. Поэтому по-хорошему надо делать сетку адаптивной (прямоугольник хранит дочерние (меньшие) прямоугольники). Эта структура называется multi-resolution OcTree (кстати именно она реализована для поиска вершин).

Ну что сказать.. да, это будет работать, но реализация и объем нужной памяти (еще одно дерево) не маленькие, да и O(1) там совсем не пахнет. Накладно получается, нет ли решения попроще? 
Записан
alexman
Гость
« Ответ #6 : Январь 30, 2012, 11:42 »
Цитировать
Есть ф-ция которая умеет для любой точки p возвращать список ближайших вершин.
Блин, сразу не увидел. Мимо ушей...

Можно анализировать пересечение вертикальной линии, проходящей через точку, со всеми ребрами ближайших вершин. Ну и найти два ближайших к точке ребра, которые пересекает вертикальная линия и выходят из одной вершины. Время О(число ребер ближайших вершин).
Записан
Blackwanderer
Гость
« Ответ #7 : Январь 30, 2012, 13:47 »
А вам принципиально представление триангуляции именно узлами? На мой взгляд для этой задачи это крайне неудачная структура. Она порождает слишком много неоднозначностей, а следовательно - слишком много проверок, что усложняет разработку алгоритма.

Цитата: Igors от Январь 30, 2012,  11:15
да и O(1) там совсем не пахнет
Ну O(C) в среднем если вам это так принципиально
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #8 : Январь 30, 2012, 15:24 »
Цитата: Черный Странник от Январь 30, 2012,  13:47
А вам принципиально представление триангуляции именно узлами? На мой взгляд для этой задачи это крайне неудачная структура. Она порождает слишком много неоднозначностей, а следовательно - слишком много проверок, что усложняет разработку алгоритма.
Пожалуйста, предлагайте лучшую организацию данных (но без жирных дополнительных структур, сеток и.т.п.)
Записан
alexman
Гость
« Ответ #9 : Январь 30, 2012, 15:25 »
Как всегда две крайности: либо память, либо время Улыбающийся
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #10 : Январь 30, 2012, 15:32 »
Цитата: alexman от Январь 30, 2012,  11:42
Можно анализировать пересечение вертикальной линии, проходящей через точку, со всеми ребрами ближайших вершин. Ну и найти два ближайших к точке ребра, которые пересекает вертикальная линия и выходят из одной вершины. Время О(число ребер ближайших вершин).
Не гарантируется что поверхность замкнута (т.е. каждое ребро входит в 2 - и только 2 треугольника). Поэтому ближайшими могут оказаться ребра разных треугольников. Да и расчетов многовато. Напр дерево выдало 10-15 ближайших вершин, у каждой примерно 6 ребер. Понятно что многие будут повторяться, но все же..
Записан
Blackwanderer
Гость
« Ответ #11 : Январь 30, 2012, 15:39 »
Цитата: Igors от Январь 30, 2012,  15:24
Пожалуйста, предлагайте лучшую организацию данных (но без жирных дополнительных структур, сеток и.т.п.)
Я использую два двумерных массива (в том числе и при решении вашей задачи):
xy: вещественный размеров nx2 для хранения координат вершин
nvtr: целочисленный mx3 для хранения треугольников (вершины треугольников хранятся в виде индексов элементов массива xy)
Записан
alexman
Гость
« Ответ #12 : Январь 30, 2012, 15:44 »
Цитировать
Не гарантируется что поверхность замкнута (т.е. каждое ребро входит в 2 - и только 2 треугольника). Поэтому ближайшими могут оказаться ребра разных треугольников.
Ну здесь достаточно дополнительной проверки.

Цитировать
Да и расчетов многовато.
Что-нить наколдовать.
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #13 : Январь 30, 2012, 15:52 »
Цитата: Черный Странник от Январь 30, 2012,  15:39
Я использую два двумерных массива (в том числе и при решении вашей задачи):
xy: вещественный размеров nx2 для хранения координат вершин
nvtr: целочисленный mx3 для хранения треугольников (вершины треугольников хранятся в виде индексов элементов массива xy)
Это обычная полигонная модель (mesh), но зная индекс вертекса (вершины) мы ничего не можем сказать о треугольниках в которые он входит. Для быстрого поиска нужны еще данные,
Записан
Blackwanderer
Гость
« Ответ #14 : Январь 30, 2012, 16:51 »
Цитата: Igors от Январь 30, 2012,  15:52
Для быстрого поиска нужны еще данные
Двумерный массив списков. Каждый список - номера треугольников (из nvtr), которые попадают в соответствующий прямоугольник. У меня сетка достаточно равномерная, так что в адаптивной прямоугольной сетке нужды не было. Если нужна адаптивная - например список списков. Первые k*p элементов символизируют первичную прямоугольную сетку. Если в этих элементах содержатся положительные числа - то это индексы из nvtr, если отрицательные - то это четыре элемента списка (с индексом больше чем k*p) являющиеся четырьмя прямоугольниками, на которые разбит первичный четырехугольник ну и дальше по рекурсии.
Записан
Страниц: [1] 2   Вверх
  Печать  
« предыдущая тема следующая тема »
 
Перейти в:  


Страница сгенерирована за 0.132 секунд. Запросов: 22.