Алгоритм выявления принадлежности точки треугольнику
Я так понимаю на координату Y можно вообще забить?
Точка P лежит внутри треугольника ABC <=> ориентированные площади треугольников PAB, PBC, PCA одного знака. Лежит на стороне треугольника, когда одна из площадей ноль, а другие одного знака. И является одной из вершин, когда две площади равны нулю.
Ориентированная площадь треугольника (x1,z1 (x2, z2 (x3, z3) — половина определителя 2x2:
Стоит для себя решить несколько вопросов:
1) Надо ли проверить всего одну единственную точку, или их будет очень много?
2) Если их будет много, то будет ли при этом меняться конфигурация треугольной сетки (добавление новых треугольников / изменение старых)?
3) Является ли сетка конформной?
Точка P лежит внутри треугольника ABC <=> ориентированные площади треугольников PAB, PBC, PCA одного знака. Лежит на стороне треугольника, когда одна из площадей ноль, а другие одного знака. И является одной из вершин, когда две площади равны нулю.
Ориентированная площадь треугольника (x1,z1 (x2, z2 (x3, z3) — половина определителя 2x2:
| x1-x3 x2-x3 |Чтобы не перебирать все треугольники подряд, придется использовать какую-нибудь более продвинутую структуру для их хранения.
| z1-z3 z2-z3 |
Стоит для себя решить несколько вопросов:
1) Надо ли проверить всего одну единственную точку, или их будет очень много?
2) Если их будет много, то будет ли при этом меняться конфигурация треугольной сетки (добавление новых треугольников / изменение старых)?
3) Является ли сетка конформной?
у меня есть мешер неплохой 
поищи мои посты со словами "триангуляция"
поищи мои посты со словами "триангуляция"
Дерево, например
Чтобы не перебирать все треугольники подряд, придется использовать какую-нибудь более продвинутую структуру для их хранения.
Возможен ли в данном случае быстрый алгоритм поиска?Чувак, это была не шутка, я абсолютно серьёзен. Алгоритм называется BSP, и возможно проще всего окажется заботать QuakeC и использовать движок первой кваки.
Чувак, это была не шутка, я абсолютно серьёзен. Алгоритм называется BSP, и возможно проще всего окажется заботать QuakeC и использовать движок первой кваки.спасибо за совет!
если ты столкнешься с такой же (или похожей на эту) проблемой, интересно, как ты отнесешься к рекомендации:"прочти исходники counter strike" ?
думаю, ты очень долго про себя будешь материться....
просили алгоритм, а дали "ГУГЛ+ ВИКИПЕДИЯ, сынок..."
ну, спасибо, блин, за совет....
Сообщение удалил
ага - все - спасибо!
Оставить комментарий
markyzz
На плоскости задано множество исходных точек.(у всех известны координаты)
Эти точки образуют множество треугольников.
На Си это задано примерно так:
typedef struct {
float x, y, z;
} VERTEX;
typedef struct {
VERTEX vertex[3];
} TRIANGLE;
Как на следующем рисунке:
Есть еще точка (на рисунке она с координатами (x,z координаты которой тоже известны.
Необходимо выявить, какому из треугольников она принадлежит (то есть найти координаты вершин того из треугольников, которому она принадлежит) на рисунке x1,z1x2,z2x3,z3
Кто-нибудь может знает такой алгоритм? и еще:
Возможен ли в данном случае быстрый алгоритм поиска?
Заранее спасибо за советы.
PS модераторам: этот же пост помещен в раздел Study. Прошу меня извинить, не мог точно определить, куда запостить. Если удалите пост - никаких обид с моей стороны.