15 using TriangleType = Triangle<T>;
16 using EdgeType = Edge<T>;
17 using VertexType = Vector2<T>;
19 const std::vector<TriangleType>& triangulate(std::vector<VertexType> &vertices)
25 float minX = vertices[0].x;
26 float minY = vertices[0].y;
30 for(std::size_t i = 0; i < vertices.size(); ++i)
32 if (vertices[i].x < minX) minX = vertices[i].x;
33 if (vertices[i].y < minY) minY = vertices[i].y;
34 if (vertices[i].x > maxX) maxX = vertices[i].x;
35 if (vertices[i].y > maxY) maxY = vertices[i].y;
38 float dx = maxX - minX;
39 float dy = maxY - minY;
40 float deltaMax = std::max(dx, dy);
41 float midx = (minX + maxX) / 2.f;
42 float midy = (minY + maxY) / 2.f;
44 VertexType p1(midx - 20 * deltaMax, midy - deltaMax);
45 VertexType p2(midx, midy + 20 * deltaMax);
46 VertexType p3(midx + 20 * deltaMax, midy - deltaMax);
51 _triangles.push_back(TriangleType(p1, p2, p3));
53 for(
auto p = begin(vertices); p != end(vertices); p++)
58 std::vector<TriangleType> badTriangles;
59 std::vector<EdgeType> polygon;
61 for(
auto t = begin(_triangles); t != end(_triangles); t++)
65 if(t->circumCircleContains(*p))
68 badTriangles.push_back(*t);
69 polygon.push_back(t->e1);
70 polygon.push_back(t->e2);
71 polygon.push_back(t->e3);
79 _triangles.erase(std::remove_if(begin(_triangles), end(_triangles), [badTriangles](TriangleType &t){
80 for(
auto bt = begin(badTriangles); bt != end(badTriangles); bt++)
91 std::vector<EdgeType> badEdges;
92 for(
auto e1 = begin(polygon); e1 != end(polygon); e1++)
94 for(
auto e2 = begin(polygon); e2 != end(polygon); e2++)
101 badEdges.push_back(*e1);
102 badEdges.push_back(*e2);
107 polygon.erase(std::remove_if(begin(polygon), end(polygon), [badEdges](EdgeType &e){
108 for(
auto it = begin(badEdges); it != end(badEdges); it++)
116 for(
auto e = begin(polygon); e != end(polygon); e++)
117 _triangles.push_back(TriangleType(e->p1, e->p2, *p));
121 _triangles.erase(std::remove_if(begin(_triangles), end(_triangles), [p1, p2, p3](TriangleType &t){
122 return t.containsVertex(p1) || t.containsVertex(p2) || t.containsVertex(p3);
123 }), end(_triangles));
125 for(
auto t = begin(_triangles); t != end(_triangles); t++)
127 _edges.push_back(t->e1);
128 _edges.push_back(t->e2);
129 _edges.push_back(t->e3);
135 const std::vector<TriangleType>& getTriangles()
const {
return _triangles; };
136 const std::vector<EdgeType>& getEdges()
const {
return _edges; };
137 const std::vector<VertexType>& getVertices()
const {
return _vertices; };
140 std::vector<TriangleType> _triangles;
141 std::vector<EdgeType> _edges;
142 std::vector<VertexType> _vertices;