Алгоритм для преобразования набора ребер в набор треугольников - PullRequest
Новая
       54

Алгоритм для преобразования набора ребер в набор треугольников

0 голосов
/ 08 июля 2019

Я реализовал алгоритм триангуляции полигонов в моей программе.Алгоритм сначала берет простой многоугольник , описанный как 2D точки / вершины, и разбивает его на y-монотонных кусочков .После этого алгоритм берет каждую монотонную часть многоугольника и разбивает ее на треугольные части.

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

Однако в этом наборе ребер нет особого порядка, и мне нужно, чтобы вывод представлял собой массив типа полоса треугольника или массив, в котором каждый треугольникпросто описывается тремя вершинами (пример: [a1, a2, a3, b1, b2, b3] , поскольку у нас есть треугольник a и треугольник b ),

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

Вот пример псевдокода программы, используемой для лучшего понимания моего вопроса: 

class Vertex {
 var point;
 var index;
 init(x,y,index){
   point = (x,y)
   self.index = index
 }
}

class Edge {
 var from; // of type Vertex
 var to; // of type Vertex
 init(from, to){
  self.from = from
  self.to = to
 }
}

Вызов функции getMonotonePiecesOfPolygon(polygon) может сгенерировать одну из множества монотонных частей многоугольника, которые будут иметь эти вершины и ребра: 

var vertex0 = Vertex(x0,y0,0)
var vertex1 = Vertex(x1,y1,1)
var vertex2 = Vertex(x2,y2,2)
var vertex3 = Vertex(x3,y3,3)

var edge0 = Edge(vertex0, vertex1)
var edge1 = Edge(vertex1, vertex2)
var edge2 = Edge(vertex2, vertex3)
var edge3 = Edge(vertex3, vertex4)

Это может соответствовать прямоугольнику, подобному этому: 

         edge0
       0------1
       |      |
 edge3 |      | edge1
       |      |
       3------2 
         edge2

Затем мы можем предоставить эти ребра в массиве и разделить многоугольник на треугольники с помощью метода триангуляции 'makeMonotonePolygonIntoTrianglePieces ()' 

var edgesArray = [edge0,edge1,edge2,edge3]  
var edgesArray = makePolygonIntoTrianglePieces(edgesArray)

Теперь edgesArray может выглядеть так: 

edgesArray == [edge0,edge1,edge2,edge3,newEdge1]

где 

newEdge1.from == vertex0
newEdge1.to == vertex2

, который бы соответствовал такому многоугольнику, если бы мы рисовали каждое ребро: 

         edge0
       0------1
       |\     |
 edge3 |  \   | edge1
       |    \ |
       3------2 
         edge2

Теперь вот часть моего вопросастремясь решить.Мне нужен массив, который будет выглядеть следующим образом: 

var triangles = [
                 vertex0,vertex3,vertex2, 
                 vertex0,vertex2,vertex1
                ]

или с использованием полос треугольника (каждый треугольник описывается одной новой вершиной и двумя вершинами из предыдущего треугольника): 

var triangles = [
                 vertex3, vertex2, vertex0,
                 vertex1
                ]
...