Создание поверхности треугольников из набора 2D точек

Question

У меня есть множество точек, и мне нужно, чтобы преобразовать множество в (непересекающихся) треугольников (или большой полигон, если эквивалент) ...

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

X   X     *---------*      *---------* 
           | \ /| \      |   \ 
           | \/ | \     |    \ 
    X   x  =>  | * | *  = or =>  |    * 
           | /\ | /     |   /
           |/ \ |/     |   /
X   X     *---------*      *---------* 

есть простой способ сделать или I нужно PhD, чтобы закодировать его?

Или с огромным полигоном? Я нашел http://en.wikipedia.org/wiki/Point_in_polygon

Thx, JD

Answer 1

Это фактически будет легче вычислить конечный многоугольник, чем строительство полигона из треугольников.

Что вы ищете, это convex hull из множества точек. Для этого существует множество different algorithms.

В классе моих алгоритмов мы изучили gift-wrapping algorithm (a.k.a .: The Jarvis March). Это довольно просто, но существуют более быстрые решения.

Если вы хотите построить полный polygon mesh, вам нужно будет запустить алгоритм triangulation, такой как Delaunay triangulation.

Answer 2

Использование Delaunay triangulation или другое.

Answer 3

Ваш текст вопроса и название вопроса указывают нам в самых разных направлениях. Вы хотите выяснить:

• триангуляция из набора точек (Google для триангуляции Delauny); или

• многоугольник, который охватывает ваше множество точек (выпуклая оболочка) или

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

Нет, вам не нужно PhD, чтобы кодировать это, все они достаточно хорошо документированы в вычислительной геометрии. Вы сможете найти программное обеспечение с открытым исходным кодом для всего вышеперечисленного. Ваша самая большая проблема, вероятно, будет найти полигональное представление каждой интересующей вас страны.

Answer 4

Для выполнения этой работы есть библиотека под названием qhull (http://www.qhull.org/). Он достаточно прочен для использования в Blender, OGRE3D и других приложениях, которые серьезно используются, и имеет API для более чем просто C/C++. Его можно даже использовать в командной строке с помощью простых текстовых файлов данных для ручного экспериментирования.

Нет необходимости для кандидата, только разрешение на установку 8D

Есть и другие, но в основном полезны для исследователей или для специальных применений.