sweep.h 8.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285
  1. /*
  2. * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors
  3. * http://code.google.com/p/poly2tri/
  4. *
  5. * All rights reserved.
  6. *
  7. * Redistribution and use in source and binary forms, with or without modification,
  8. * are permitted provided that the following conditions are met:
  9. *
  10. * * Redistributions of source code must retain the above copyright notice,
  11. * this list of conditions and the following disclaimer.
  12. * * Redistributions in binary form must reproduce the above copyright notice,
  13. * this list of conditions and the following disclaimer in the documentation
  14. * and/or other materials provided with the distribution.
  15. * * Neither the name of Poly2Tri nor the names of its contributors may be
  16. * used to endorse or promote products derived from this software without specific
  17. * prior written permission.
  18. *
  19. * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  20. * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  21. * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  22. * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
  23. * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  24. * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  25. * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  26. * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
  27. * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  28. * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  29. * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  30. */
  31. /**
  32. * Sweep-line, Constrained Delauney Triangulation (CDT) See: Domiter, V. and
  33. * Zalik, B.(2008)'Sweep-line algorithm for constrained Delaunay triangulation',
  34. * International Journal of Geographical Information Science
  35. *
  36. * "FlipScan" Constrained Edge Algorithm invented by Thomas ?hl?n, thahlen@gmail.com
  37. */
  38. #ifndef SWEEP_H
  39. #define SWEEP_H
  40. #include <vector>
  41. namespace p2t {
  42. class SweepContext;
  43. struct Node;
  44. struct Point;
  45. struct Edge;
  46. class Triangle;
  47. class Sweep
  48. {
  49. public:
  50. /**
  51. * Triangulate
  52. *
  53. * @param tcx
  54. */
  55. void Triangulate(SweepContext& tcx);
  56. /**
  57. * Destructor - clean up memory
  58. */
  59. ~Sweep();
  60. private:
  61. /**
  62. * Start sweeping the Y-sorted point set from bottom to top
  63. *
  64. * @param tcx
  65. */
  66. void SweepPoints(SweepContext& tcx);
  67. /**
  68. * Find closes node to the left of the new point and
  69. * create a new triangle. If needed new holes and basins
  70. * will be filled to.
  71. *
  72. * @param tcx
  73. * @param point
  74. * @return
  75. */
  76. Node& PointEvent(SweepContext& tcx, Point& point);
  77. /**
  78. *
  79. *
  80. * @param tcx
  81. * @param edge
  82. * @param node
  83. */
  84. void EdgeEvent(SweepContext& tcx, Edge* edge, Node* node);
  85. void EdgeEvent(SweepContext& tcx, Point& ep, Point& eq, Triangle* triangle, Point& point);
  86. /**
  87. * Creates a new front triangle and legalize it
  88. *
  89. * @param tcx
  90. * @param point
  91. * @param node
  92. * @return
  93. */
  94. Node& NewFrontTriangle(SweepContext& tcx, Point& point, Node& node);
  95. /**
  96. * Adds a triangle to the advancing front to fill a hole.
  97. * @param tcx
  98. * @param node - middle node, that is the bottom of the hole
  99. */
  100. void Fill(SweepContext& tcx, Node& node);
  101. /**
  102. * Returns true if triangle was legalized
  103. */
  104. bool Legalize(SweepContext& tcx, Triangle& t);
  105. /**
  106. * <b>Requirement</b>:<br>
  107. * 1. a,b and c form a triangle.<br>
  108. * 2. a and d is know to be on opposite side of bc<br>
  109. * <pre>
  110. * a
  111. * +
  112. * / \
  113. * / \
  114. * b/ \c
  115. * +-------+
  116. * / d \
  117. * / \
  118. * </pre>
  119. * <b>Fact</b>: d has to be in area B to have a chance to be inside the circle formed by
  120. * a,b and c<br>
  121. * d is outside B if orient2d(a,b,d) or orient2d(c,a,d) is CW<br>
  122. * This preknowledge gives us a way to optimize the incircle test
  123. * @param a - triangle point, opposite d
  124. * @param b - triangle point
  125. * @param c - triangle point
  126. * @param d - point opposite a
  127. * @return true if d is inside circle, false if on circle edge
  128. */
  129. bool Incircle(const Point& pa, const Point& pb, const Point& pc, const Point& pd) const;
  130. /**
  131. * Rotates a triangle pair one vertex CW
  132. *<pre>
  133. * n2 n2
  134. * P +-----+ P +-----+
  135. * | t /| |\ t |
  136. * | / | | \ |
  137. * n1| / |n3 n1| \ |n3
  138. * | / | after CW | \ |
  139. * |/ oT | | oT \|
  140. * +-----+ oP +-----+
  141. * n4 n4
  142. * </pre>
  143. */
  144. void RotateTrianglePair(Triangle& t, Point& p, Triangle& ot, Point& op) const;
  145. /**
  146. * Fills holes in the Advancing Front
  147. *
  148. *
  149. * @param tcx
  150. * @param n
  151. */
  152. void FillAdvancingFront(SweepContext& tcx, Node& n);
  153. // Decision-making about when to Fill hole.
  154. // Contributed by ToolmakerSteve2
  155. bool LargeHole_DontFill(const Node* node) const;
  156. bool AngleExceeds90Degrees(const Point* origin, const Point* pa, const Point* pb) const;
  157. bool AngleExceedsPlus90DegreesOrIsNegative(const Point* origin, const Point* pa, const Point* pb) const;
  158. double Angle(const Point* origin, const Point* pa, const Point* pb) const;
  159. /**
  160. *
  161. * @param node - middle node
  162. * @return the angle between 3 front nodes
  163. */
  164. double HoleAngle(const Node& node) const;
  165. /**
  166. * The basin angle is decided against the horizontal line [1,0]
  167. */
  168. double BasinAngle(const Node& node) const;
  169. /**
  170. * Fills a basin that has formed on the Advancing Front to the right
  171. * of given node.<br>
  172. * First we decide a left,bottom and right node that forms the
  173. * boundaries of the basin. Then we do a reqursive fill.
  174. *
  175. * @param tcx
  176. * @param node - starting node, this or next node will be left node
  177. */
  178. void FillBasin(SweepContext& tcx, Node& node);
  179. /**
  180. * Recursive algorithm to fill a Basin with triangles
  181. *
  182. * @param tcx
  183. * @param node - bottom_node
  184. * @param cnt - counter used to alternate on even and odd numbers
  185. */
  186. void FillBasinReq(SweepContext& tcx, Node* node);
  187. bool IsShallow(SweepContext& tcx, Node& node);
  188. bool IsEdgeSideOfTriangle(Triangle& triangle, Point& ep, Point& eq);
  189. void FillEdgeEvent(SweepContext& tcx, Edge* edge, Node* node);
  190. void FillRightAboveEdgeEvent(SweepContext& tcx, Edge* edge, Node* node);
  191. void FillRightBelowEdgeEvent(SweepContext& tcx, Edge* edge, Node& node);
  192. void FillRightConcaveEdgeEvent(SweepContext& tcx, Edge* edge, Node& node);
  193. void FillRightConvexEdgeEvent(SweepContext& tcx, Edge* edge, Node& node);
  194. void FillLeftAboveEdgeEvent(SweepContext& tcx, Edge* edge, Node* node);
  195. void FillLeftBelowEdgeEvent(SweepContext& tcx, Edge* edge, Node& node);
  196. void FillLeftConcaveEdgeEvent(SweepContext& tcx, Edge* edge, Node& node);
  197. void FillLeftConvexEdgeEvent(SweepContext& tcx, Edge* edge, Node& node);
  198. void FlipEdgeEvent(SweepContext& tcx, Point& ep, Point& eq, Triangle* t, Point& p);
  199. /**
  200. * After a flip we have two triangles and know that only one will still be
  201. * intersecting the edge. So decide which to contiune with and legalize the other
  202. *
  203. * @param tcx
  204. * @param o - should be the result of an orient2d( eq, op, ep )
  205. * @param t - triangle 1
  206. * @param ot - triangle 2
  207. * @param p - a point shared by both triangles
  208. * @param op - another point shared by both triangles
  209. * @return returns the triangle still intersecting the edge
  210. */
  211. Triangle& NextFlipTriangle(SweepContext& tcx, int o, Triangle& t, Triangle& ot, Point& p, Point& op);
  212. /**
  213. * When we need to traverse from one triangle to the next we need
  214. * the point in current triangle that is the opposite point to the next
  215. * triangle.
  216. *
  217. * @param ep
  218. * @param eq
  219. * @param ot
  220. * @param op
  221. * @return
  222. */
  223. Point& NextFlipPoint(Point& ep, Point& eq, Triangle& ot, Point& op);
  224. /**
  225. * Scan part of the FlipScan algorithm<br>
  226. * When a triangle pair isn't flippable we will scan for the next
  227. * point that is inside the flip triangle scan area. When found
  228. * we generate a new flipEdgeEvent
  229. *
  230. * @param tcx
  231. * @param ep - last point on the edge we are traversing
  232. * @param eq - first point on the edge we are traversing
  233. * @param flipTriangle - the current triangle sharing the point eq with edge
  234. * @param t
  235. * @param p
  236. */
  237. void FlipScanEdgeEvent(SweepContext& tcx, Point& ep, Point& eq, Triangle& flip_triangle, Triangle& t, Point& p);
  238. void FinalizationPolygon(SweepContext& tcx);
  239. std::vector<Node*> nodes_;
  240. };
  241. }
  242. #endif