Delaunay.h
上传用户:shlanyl88
上传日期:2013-03-14
资源大小:147k
文件大小:7k
源码类别:

3D图形编程

开发平台:

Visual C++

  1. /********************************************************************************
  2. Copyright (C) 2004-2005 Sjaak Priester
  3. This is free software; you can redistribute it and/or modify
  4. it under the terms of the GNU General Public License as published by
  5. the Free Software Foundation; either version 2 of the License, or
  6. (at your option) any later version.
  7. This file is distributed in the hope that it will be useful,
  8. but WITHOUT ANY WARRANTY; without even the implied warranty of
  9. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  10. GNU General Public License for more details.
  11. You should have received a copy of the GNU General Public License
  12. along with this application; if not, write to the Free Software
  13. Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  14. ********************************************************************************/
  15. // Delaunay
  16. // Class to perform Delaunay triangulation on a set of vertices
  17. //
  18. // Version 1.2 (C) 2005, Sjaak Priester, Amsterdam.
  19. // - Removed stupid bug in SetY; function wasn't used, so no consequences. Thanks to squat.
  20. //
  21. // Version 1.1 (C) 2005, Sjaak Priester, Amsterdam.
  22. // - Removed bug which gave incorrect results for co-circular vertices.
  23. //
  24. // Version 1.0 (C) 2004, Sjaak Priester, Amsterdam.
  25. // mailto:sjaak@sjaakpriester.nl
  26. #pragma once
  27. #include <set>
  28. #include <algorithm>
  29. #include <math.h>
  30. using namespace std;
  31. #ifndef _GDIPLUS_H
  32. // I designed this with GDI+ in mind. However, this particular code doesn't
  33. // use GDI+ at all, only some of it's variable types.
  34. // These definitions are substitutes for those of GDI+. 
  35. typedef float REAL;
  36. struct PointF
  37. {
  38. PointF() : X(0), Y(0) {}
  39. PointF(const PointF& p) : X(p.X), Y(p.Y) {}
  40. PointF(REAL x, REAL y) : X(x), Y(y) {}
  41. PointF operator+(const PointF& p) const { return PointF(X + p.X, Y + p.Y); }
  42. PointF operator-(const PointF& p) const { return PointF(X - p.X, Y - p.Y); }
  43. REAL X;
  44. REAL Y;
  45. };
  46. const REAL REAL_EPSILON = 1.192092896e-07F; // = 2^-23; I've no idea why this is a good value, but GDI+ has it.
  47. #endif // _GDIPLUS_H
  48. ///////////////////
  49. // vertex
  50. class vertex
  51. {
  52. public:
  53. vertex() : m_Pnt(0.0F, 0.0F) {}
  54. vertex(const vertex& v) : m_Pnt(v.m_Pnt) {}
  55. vertex(const PointF& pnt) : m_Pnt(pnt) {}
  56. vertex(REAL x, REAL y) : m_Pnt(x, y) {}
  57. vertex(int x, int y) : m_Pnt((REAL) x, (REAL) y) {}
  58. bool operator<(const vertex& v) const
  59. {
  60. if (m_Pnt.X == v.m_Pnt.X) return m_Pnt.Y < v.m_Pnt.Y;
  61. return m_Pnt.X < v.m_Pnt.X;
  62. }
  63. bool operator==(const vertex& v) const
  64. {
  65. return m_Pnt.X == v.m_Pnt.X && m_Pnt.Y == v.m_Pnt.Y;
  66. }
  67. REAL GetX() const { return m_Pnt.X; }
  68. REAL GetY() const { return m_Pnt.Y; }
  69. void SetX(REAL x) { m_Pnt.X = x; }
  70. void SetY(REAL y) { m_Pnt.Y = y; }
  71. const PointF& GetPoint() const { return m_Pnt; }
  72. protected:
  73. PointF m_Pnt;
  74. };
  75. typedef set<vertex> vertexSet;
  76. typedef set<vertex>::iterator vIterator;
  77. typedef set<vertex>::const_iterator cvIterator;
  78. ///////////////////
  79. // triangle
  80. class triangle
  81. {
  82. public:
  83. triangle(const triangle& tri)
  84. : m_Center(tri.m_Center)
  85. , m_R(tri.m_R)
  86. , m_R2(tri.m_R2)
  87. {
  88. for (int i = 0; i < 3; i++) m_Vertices[i] = tri.m_Vertices[i];
  89. }
  90. triangle(const vertex * p0, const vertex * p1, const vertex * p2)
  91. {
  92. m_Vertices[0] = p0;
  93. m_Vertices[1] = p1;
  94. m_Vertices[2] = p2;
  95. SetCircumCircle();
  96. }
  97. triangle(const vertex * pV)
  98. {
  99. for (int i = 0; i < 3; i++) m_Vertices[i] = pV++;
  100. SetCircumCircle();
  101. }
  102. bool operator<(const triangle& tri) const
  103. {
  104. if (m_Center.X == tri.m_Center.X) return m_Center.Y < tri.m_Center.Y;
  105. return m_Center.X < tri.m_Center.X;
  106. }
  107. const vertex * GetVertex(int i) const
  108. {
  109. ASSERT(i >= 0);
  110. ASSERT(i < 3);
  111. return m_Vertices[i];
  112. }
  113. bool IsLeftOf(cvIterator itVertex) const
  114. {
  115. // returns true if * itVertex is to the right of the triangle's circumcircle
  116. return itVertex->GetPoint().X > (m_Center.X + m_R);
  117. }
  118. bool CCEncompasses(cvIterator itVertex) const
  119. {
  120. // Returns true if * itVertex is in the triangle's circumcircle.
  121. // A vertex exactly on the circle is also considered to be in the circle.
  122. // These next few lines look like optimisation, however in practice they are not.
  123. // They even seem to slow down the algorithm somewhat.
  124. // Therefore, I've commented them out.
  125. // First check boundary box.
  126. // REAL x = itVertex->GetPoint().X;
  127. //
  128. // if (x > (m_Center.X + m_R)) return false;
  129. // if (x < (m_Center.X - m_R)) return false;
  130. //
  131. // REAL y = itVertex->GetPoint().Y;
  132. //
  133. // if (y > (m_Center.Y + m_R)) return false;
  134. // if (y < (m_Center.Y - m_R)) return false;
  135. PointF dist = itVertex->GetPoint() - m_Center; // the distance between v and the circle center
  136. REAL dist2 = dist.X * dist.X + dist.Y * dist.Y; // squared
  137. return dist2 <= m_R2; // compare with squared radius
  138. }
  139. protected:
  140. const vertex * m_Vertices[3]; // the three triangle vertices
  141. PointF m_Center; // center of circumcircle
  142. REAL m_R; // radius of circumcircle
  143. REAL m_R2; // radius of circumcircle, squared
  144. void SetCircumCircle();
  145. };
  146. // Changed in verion 1.1: collect triangles in a multiset.
  147. // In version 1.0, I used a set, preventing the creation of multiple
  148. // triangles with identical center points. Therefore, more than three
  149. // co-circular vertices yielded incorrect results. Thanks to Roger Labbe.
  150. typedef multiset<triangle> triangleSet;
  151. typedef multiset<triangle>::iterator tIterator;
  152. typedef multiset<triangle>::const_iterator ctIterator;
  153. ///////////////////
  154. // edge
  155. class edge
  156. {
  157. public:
  158. edge(const edge& e) : m_pV0(e.m_pV0), m_pV1(e.m_pV1) {}
  159. edge(const vertex * pV0, const vertex * pV1)
  160. : m_pV0(pV0), m_pV1(pV1)
  161. {
  162. }
  163. bool operator<(const edge& e) const
  164. {
  165. if (m_pV0 == e.m_pV0) return * m_pV1 < * e.m_pV1;
  166. return * m_pV0 < * e.m_pV0;
  167. }
  168. const vertex * m_pV0;
  169. const vertex * m_pV1;
  170. };
  171. typedef set<edge> edgeSet;
  172. typedef set<edge>::iterator edgeIterator;
  173. typedef set<edge>::const_iterator cedgeIterator;
  174. ///////////////////
  175. // Delaunay
  176. class Delaunay
  177. {
  178. public:
  179. // Calculate the Delaunay triangulation for the given set of vertices.
  180. void Triangulate(const vertexSet& vertices, triangleSet& output);
  181. // Put the edges of the triangles in an edgeSet, eliminating double edges.
  182. // This comes in useful for drawing the triangulation.
  183. void TrianglesToEdges(const triangleSet& triangles, edgeSet& edges);
  184. protected:
  185. void HandleEdge(const vertex * p0, const vertex * p1, edgeSet& edges);
  186. };