Tessellate a plane of point

Question

У меня есть файл, заполненный 3d-пунктами. Точки образуют плоскость. Вот пример файла:

25 
1 -1 0 
1 -0.5 0 
1 0 0 
1 0.5 0 
1 1 0 
0.5 -1 0 
0.5 -0.5 0 
0.5 0 0 
0.5 0.5 0 
0.5 1 0 
0 -1 0 
0 -0.5 0 
0 0 0 
0 0.5 0 
0 1 0 
-0.5 -1 0 
-0.5 -0.5 0 
-0.5 0 0 
-0.5 0.5 0 
-0.5 1 0 
-1 -1 0 
-1 -0.5 0 
-1 0 0 
-1 0.5 0 
-1 1 0 

Редактировать: Поскольку мой пример набора точек был слишком простым, вот более сложный пример.

30 
-0.298858 -0.816497 1.11536 
0.0546949 -0.816497 0.761802 
0.408248 -0.816497 0.408248 
0.761802 -0.816497 0.0546949 
1.11536 -0.816497 -0.298858 
-0.462158 -0.489898 0.952056 
-0.108604 -0.489898 0.598502 
0.244949 -0.489898 0.244949 
0.598502 -0.489898 -0.108604 
0.952056 -0.489898 -0.462158 
-0.625457 -0.163299 0.788756 
-0.271904 -0.163299 0.435203 
0.0816497 -0.163299 0.0816497 
0.435203 -0.163299 -0.271904 
0.788756 -0.163299 -0.625457 
-0.788756 0.163299 0.625457 
-0.435203 0.163299 0.271904 
-0.0816497 0.163299 -0.0816497 
0.271904 0.163299 -0.435203 
0.625457 0.163299 -0.788756 
-0.952056 0.489898 0.462158 
-0.598502 0.489898 0.108604 
-0.244949 0.489898 -0.244949 
0.108604 0.489898 -0.598502 
0.462158 0.489898 -0.952056 
-1.11536 0.816497 0.298858 
-0.761802 0.816497 -0.0546949 
-0.408248 0.816497 -0.408248 
-0.0546949 0.816497 -0.761802 
0.298858 0.816497 -1.11536 

Эти точки наносятся следующим образом:

Этот файл указывает, что существует 25 точек на плоскости, а также перечислены пункты. Точки находятся на регулярной основе. Основываясь на этой информации, как я мог бы сформировать треугольники из данных точек и хранить его в std::vector<Tri> где Tri является

struct Tri 
{ 
    double x1, y1, z1; 
    double x2, y2, z2; 
    double x3, y3, z3; 
}; 

Обратите также внимание: Проблема ограничения: Внешние библиотеки не допускаются. Использование C++ 0X запрещено (компилятор: g ++ 4.5.2).

Answer 1

прочитайте первую строчку, назовите ее N. Прочитайте остальные точки в массиве A.

Point xdir = A[1] - A[0]; 
int xdim = 2; 
while (A[xdim] - A[xdim-1] == xdir) xdim++; 
int ydim = N/xdim; 
for (int y = 0; y < ydim-1; y++) { 
    for (int x = 0; x < xdim-1; x++) { 
     addTriangle(A[y*xdim+x],A[(y+1)*xdim+x],A[(y+1)*xdim+(x+1)]); 
     addTriangle(A[y*xdim+x],A[y*xdim+(x+1)],A[(y+1)*xdim+(x+1)]); 
    } 
} 

Конечно, предполагается, что вы действительно получаете все свои очки в режиме сетки. Если нет, сначала отберите их.

Answer 2

Отделите сетку от плоскости на множество линий. Тесселяция дается путем принятия каждой пары соседних точек на линии и добавления ближайшей точки каждого члена пары в смежных строках к паре.

Вы можете разделить плоскость на линии с помощью векторной арифметики. Возьмите первую точку в файле как основание плоскости, а вектор ко второй точке - как ось X. Проецируйте вектор из первой точки в любую точку вектора оси X и используйте длину проекции в виде координат Х. Поскольку вы принимаете правильную сетку, эти значения должны быть равны 0, 1, 2, 3 и т. Д., Прямо разделяя точки на линии.

Answer 3

Может быть, Delaunay Triangulation поможет вам? В этом link приведены некоторые алгоритмы получения треугольника Delaunay.

Дается еще один алгоритм here.

Answer 4

Для алгоритма тесселяции попробуйте создать и нажать на вектор, правые треугольники соседних точек (без их перекрытия). Предполагая, что вы сохранили все точки в m x n матрицы в правильном порядке, вы можете создать этот набор треугольников:

• {(i,j),(i+1,j),(i+1,j+1)} для 0 < i < m-1 и 0 < j < n-1.
• {(i,j+1), (i+1,j+1), (i,j) для 0 < i < m-1 и 0 < j < n-1.

Я использовал форму {p1, p2, p3} для треугольника и (x, y) для пары указателей точки в матрице. В вашем случае также эти переменные m и n равны 5.

Answer 5

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

Но мой подход вероятно, будет выглядеть примерно так:

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

2. Напишите алгоритмы для использования этого нормального вектора для определения некоторых распространенных вопросов плоскости, таких как «Является ли точка D внутри треугольника ABC?» и «Пересекаются ли сегменты AB и CD?» (в плоскости проекции).

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

Если вы просто хотите, чтобы получить какой-либо набор непересекающихся треугольников, tesselate выпуклой оболочки:

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

2. Если новая точка для добавления находится внутри существующего треугольника, замените этот треугольник тремя подтреуголами.

3. В противном случае определите, какие отрезки линии N (N> = 2) от граничных многоугольников до новой точки не пересекаются с граничным многоугольником. Добавьте (N-1) новые треугольники. Новая точка заменяет (N-2) старые точки как новую вершину в граничном многоугольнике.

4. Предполагая, что это хорошо, чтобы избежать почти коллинеарных треугольников и ненужных длинных сегментов: проведите по краям треугольника, которые не находятся на границе, и проверьте, выпуклый ли четырехугольник, покрытый двумя смежными треугольниками, и другая диагональ (значительно) короче, чем исследуемый общий фронт треугольника. Если это так, замените эти два треугольника. Повторяйте до тех пор, пока не будут сделаны такие замены. (Этот цикл должен заканчиваться, так как общая длина кромок всегда уменьшается, и существует конечное число tesselations.)