Horizon
delaunay.h
1 #ifndef H_DELAUNAY
2 #define H_DELAUNAY
3 
4 #include "vector2.h"
5 #include "edge.h"
6 #include "triangle.h"
7 
8 #include <vector>
9 #include <algorithm>
10 namespace delaunay {
11 template <class T>
12 class Delaunay
13 {
14  public:
15  using TriangleType = Triangle<T>;
16  using EdgeType = Edge<T>;
17  using VertexType = Vector2<T>;
18 
19  const std::vector<TriangleType>& triangulate(std::vector<VertexType> &vertices)
20  {
21  // Store the vertices localy
22  _vertices = vertices;
23 
24  // Determinate the super triangle
25  float minX = vertices[0].x;
26  float minY = vertices[0].y;
27  float maxX = minX;
28  float maxY = minY;
29 
30  for(std::size_t i = 0; i < vertices.size(); ++i)
31  {
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;
36  }
37 
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;
43 
44  VertexType p1(midx - 20 * deltaMax, midy - deltaMax);
45  VertexType p2(midx, midy + 20 * deltaMax);
46  VertexType p3(midx + 20 * deltaMax, midy - deltaMax);
47 
48  //std::cout << "Super triangle " << std::endl << Triangle(p1, p2, p3) << std::endl;
49 
50  // Create a list of triangles, and add the supertriangle in it
51  _triangles.push_back(TriangleType(p1, p2, p3));
52 
53  for(auto p = begin(vertices); p != end(vertices); p++)
54  {
55  //std::cout << "Traitement du point " << *p << std::endl;
56  //std::cout << "_triangles contains " << _triangles.size() << " elements" << std::endl;
57 
58  std::vector<TriangleType> badTriangles;
59  std::vector<EdgeType> polygon;
60 
61  for(auto t = begin(_triangles); t != end(_triangles); t++)
62  {
63  //std::cout << "Processing " << std::endl << *t << std::endl;
64 
65  if(t->circumCircleContains(*p))
66  {
67  //std::cout << "Pushing bad triangle " << *t << std::endl;
68  badTriangles.push_back(*t);
69  polygon.push_back(t->e1);
70  polygon.push_back(t->e2);
71  polygon.push_back(t->e3);
72  }
73  else
74  {
75  //std::cout << " does not contains " << *p << " in his circum center" << std::endl;
76  }
77  }
78 
79  _triangles.erase(std::remove_if(begin(_triangles), end(_triangles), [badTriangles](TriangleType &t){
80  for(auto bt = begin(badTriangles); bt != end(badTriangles); bt++)
81  {
82  if(*bt == t)
83  {
84  //std::cout << "Removing bad triangle " << std::endl << *bt << " from _triangles" << std::endl;
85  return true;
86  }
87  }
88  return false;
89  }), end(_triangles));
90 
91  std::vector<EdgeType> badEdges;
92  for(auto e1 = begin(polygon); e1 != end(polygon); e1++)
93  {
94  for(auto e2 = begin(polygon); e2 != end(polygon); e2++)
95  {
96  if(e1 == e2)
97  continue;
98 
99  if(*e1 == *e2)
100  {
101  badEdges.push_back(*e1);
102  badEdges.push_back(*e2);
103  }
104  }
105  }
106 
107  polygon.erase(std::remove_if(begin(polygon), end(polygon), [badEdges](EdgeType &e){
108  for(auto it = begin(badEdges); it != end(badEdges); it++)
109  {
110  if(*it == e)
111  return true;
112  }
113  return false;
114  }), end(polygon));
115 
116  for(auto e = begin(polygon); e != end(polygon); e++)
117  _triangles.push_back(TriangleType(e->p1, e->p2, *p));
118 
119  }
120 
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));
124 
125  for(auto t = begin(_triangles); t != end(_triangles); t++)
126  {
127  _edges.push_back(t->e1);
128  _edges.push_back(t->e2);
129  _edges.push_back(t->e3);
130  }
131 
132  return _triangles;
133  }
134 
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; };
138 
139  private:
140  std::vector<TriangleType> _triangles;
141  std::vector<EdgeType> _edges;
142  std::vector<VertexType> _vertices;
143 };
144 }
145 #endif