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

Question

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

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

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

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

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

Thx, JD

Answer 1

Было бы проще вычислить конечный многоугольник, чем построить многоугольник из треугольников.

То, что вы ищете, это выпуклая оболочка набора точек. Для этого существует множество различных алгоритмов .

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

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

Answer 2

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

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

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

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

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

Answer 3

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

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

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

Answer 4

Использование Триангуляция Делоне или др.