Алгоритм выявления принадлежности точки треугольнику.

oleg1966

На плоскости задано множество исходных точек.
(у всех известны координаты)
Эти точки образуют множество треугольников.
Как на следующем рисунке:

Есть еще точка (на рисунке она с координатами (x,z координаты которой тоже известны.
Необходимо выявить, какому из треугольников она принадлежит (то есть найти координаты вершин того из треугольников, которому она принадлежит) на рисунке x1,z1x2,z2x3,z3
Кто-нибудь может знает такой алгоритм? и еще:
Возможен ли в данном случае быстрый алгоритм поиска?
Заранее спасибо за советы.
PS модераторам: этот же пост помещен в раздел программирование. Прошу меня извинить, не мог точно определить, куда запостить. Если удалите пост - никаких обид с моей стороны.

Airat1734

Помню я в каком-то журнале видел более эффективный алгоритм, чем проверка выше или ниже прямой лежит точка. Яндекс тебе поможет.

spiritmc

Думаю, эта область называется "computational geometry."
В FAQ глядел?
---
...Я работаю антинаучным аферистом...

natunchik

Кодовое слово - BSP (binary space partitioning). Можешь заюзать движок первой кваки для решения этой проблемы =)

kachokslava

Как проверить, что точка внутри конкретного треугольника?
Подставить её координаты в функции формы. Все три значения должны быть из интервала [0..1]
И перебрать все треугольники.
Чёткого алгоритма ускорения перебора нет.
Есть хитрые хаки типа кластеризации всей плоскости.
Смысл в следующем: разбиваем используемый участок плоскости на квадраты (например, 16 штук) и ведём индексы принадлежности треугольников квадратам.
Далее, когда ищем точку - сначала смотрим, в какой квадрат она попадает (это БЫСТРО далее - перебираем все треугольники внутри квадрата (их в среднем в 16 раз меньше).
Можно проводить дальнейшую кластеризацию - если счёт треугольников идёт на десятки тысяч - то разбиение плоскости сначала на 16 квадратов, потом каждый - на ещё 16 штук - то поиск ускоряется в среднем в 256 раз.

kachokslava

Кстати, просто координат точек недостаточно. на одной и той же сетке может быть очень много различных триангуляций. К примеру - возьми любой четырёхугольник, образованный двумя треугольниками в твоей триангуляции.
Их общаяя сторона - диагональ четырёхугольника. Если выкинуть эту диагональ и провести другую - получится ДРУГАЯ триангуляция на ТОЙ ЖЕ сетке.
Оптимально считается триангуляция, у которой сумма длин рёбер минимальна. Построение такой - NP-полная задача.
Строят близкую по оптимальности - т.н. триангуляцию Делоне - такую что в описанную окружность любого треугольника не попадает ни одна вершина сетки.

oleg1966

Кстати, просто координат точек недостаточно. на одной и той же сетке может быть очень много различных триангуляций. К примеру - возьми любой четырёхугольник, образованный двумя треугольниками в твоей триангуляции.
Их общаяя сторона - диагональ четырёхугольника. Если выкинуть эту диагональ и провести другую - получится ДРУГАЯ триангуляция на ТОЙ ЖЕ сетке.
Я не совсем математик.... сорри, конечно!, это так, то что ты говоришь.
Запостил в прогерстве еще один такой пост только с таким пояснением:
typedef struct {
float x, y, z;
} VERTEX;
typedef struct {
VERTEX vertex[3];
} TRIANGLE;
(то есть, треугольники все-таки имеются, и они конкретно обозначены)

oleg1966

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