1 /* 2 * Poly2Tri Copyright (c) 2009-2018, Poly2Tri Contributors 3 * https://github.com/jhasse/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 39 #ifndef SWEEP_H 40 #define SWEEP_H 41 42 #include <vector> 43 44 namespace p2t { 45 46 class SweepContext; 47 struct Node; 48 struct Point; 49 struct Edge; 50 class Triangle; 51 52 class Sweep 53 { 54 public: 55 56 /** 57 * Triangulate 58 * 59 * @param tcx 60 */ 61 void Triangulate(SweepContext& tcx); 62 63 /** 64 * Destructor - clean up memory 65 */ 66 ~Sweep(); 67 68 private: 69 70 /** 71 * Start sweeping the Y-sorted point set from bottom to top 72 * 73 * @param tcx 74 */ 75 void SweepPoints(SweepContext& tcx); 76 77 /** 78 * Find closes node to the left of the new point and 79 * create a new triangle. If needed new holes and basins 80 * will be filled to. 81 * 82 * @param tcx 83 * @param point 84 * @return 85 */ 86 Node& PointEvent(SweepContext& tcx, Point& point); 87 88 /** 89 * 90 * 91 * @param tcx 92 * @param edge 93 * @param node 94 */ 95 void EdgeEvent(SweepContext& tcx, Edge* edge, Node* node); 96 97 void EdgeEvent(SweepContext& tcx, Point& ep, Point& eq, Triangle* triangle, Point& point); 98 99 /** 100 * Creates a new front triangle and legalize it 101 * 102 * @param tcx 103 * @param point 104 * @param node 105 * @return 106 */ 107 Node& NewFrontTriangle(SweepContext& tcx, Point& point, Node& node); 108 109 /** 110 * Adds a triangle to the advancing front to fill a hole. 111 * @param tcx 112 * @param node - middle node, that is the bottom of the hole 113 */ 114 void Fill(SweepContext& tcx, Node& node); 115 116 /** 117 * Returns true if triangle was legalized 118 */ 119 bool Legalize(SweepContext& tcx, Triangle& t); 120 121 /** 122 * <b>Requirement</b>:<br> 123 * 1. a,b and c form a triangle.<br> 124 * 2. a and d is know to be on opposite side of bc<br> 125 * <pre> 126 * a 127 * + 128 * / \ 129 * / \ 130 * b/ \c 131 * +-------+ 132 * / d \ 133 * / \ 134 * </pre> 135 * <b>Fact</b>: d has to be in area B to have a chance to be inside the circle formed by 136 * a,b and c<br> 137 * d is outside B if orient2d(a,b,d) or orient2d(c,a,d) is CW<br> 138 * This preknowledge gives us a way to optimize the incircle test 139 * @param a - triangle point, opposite d 140 * @param b - triangle point 141 * @param c - triangle point 142 * @param d - point opposite a 143 * @return true if d is inside circle, false if on circle edge 144 */ 145 bool Incircle(const Point& pa, const Point& pb, const Point& pc, const Point& pd) const; 146 147 /** 148 * Rotates a triangle pair one vertex CW 149 *<pre> 150 * n2 n2 151 * P +-----+ P +-----+ 152 * | t /| |\ t | 153 * | / | | \ | 154 * n1| / |n3 n1| \ |n3 155 * | / | after CW | \ | 156 * |/ oT | | oT \| 157 * +-----+ oP +-----+ 158 * n4 n4 159 * </pre> 160 */ 161 void RotateTrianglePair(Triangle& t, Point& p, Triangle& ot, Point& op) const; 162 163 /** 164 * Fills holes in the Advancing Front 165 * 166 * 167 * @param tcx 168 * @param n 169 */ 170 void FillAdvancingFront(SweepContext& tcx, Node& n); 171 172 // Decision-making about when to Fill hole. 173 // Contributed by ToolmakerSteve2 174 bool LargeHole_DontFill(const Node* node) const; 175 bool AngleExceeds90Degrees(const Point* origin, const Point* pa, const Point* pb) const; 176 bool AngleExceedsPlus90DegreesOrIsNegative(const Point* origin, const Point* pa, const Point* pb) const; 177 double Angle(const Point* origin, const Point* pa, const Point* pb) const; 178 179 /** 180 * 181 * @param node - middle node 182 * @return the angle between 3 front nodes 183 */ 184 double HoleAngle(const Node& node) const; 185 186 /** 187 * The basin angle is decided against the horizontal line [1,0] 188 */ 189 double BasinAngle(const Node& node) const; 190 191 /** 192 * Fills a basin that has formed on the Advancing Front to the right 193 * of given node.<br> 194 * First we decide a left,bottom and right node that forms the 195 * boundaries of the basin. Then we do a reqursive fill. 196 * 197 * @param tcx 198 * @param node - starting node, this or next node will be left node 199 */ 200 void FillBasin(SweepContext& tcx, Node& node); 201 202 /** 203 * Recursive algorithm to fill a Basin with triangles 204 * 205 * @param tcx 206 * @param node - bottom_node 207 * @param cnt - counter used to alternate on even and odd numbers 208 */ 209 void FillBasinReq(SweepContext& tcx, Node* node); 210 211 bool IsShallow(SweepContext& tcx, Node& node); 212 213 bool IsEdgeSideOfTriangle(Triangle& triangle, Point& ep, Point& eq); 214 215 void FillEdgeEvent(SweepContext& tcx, Edge* edge, Node* node); 216 217 void FillRightAboveEdgeEvent(SweepContext& tcx, Edge* edge, Node* node); 218 219 void FillRightBelowEdgeEvent(SweepContext& tcx, Edge* edge, Node& node); 220 221 void FillRightConcaveEdgeEvent(SweepContext& tcx, Edge* edge, Node& node); 222 223 void FillRightConvexEdgeEvent(SweepContext& tcx, Edge* edge, Node& node); 224 225 void FillLeftAboveEdgeEvent(SweepContext& tcx, Edge* edge, Node* node); 226 227 void FillLeftBelowEdgeEvent(SweepContext& tcx, Edge* edge, Node& node); 228 229 void FillLeftConcaveEdgeEvent(SweepContext& tcx, Edge* edge, Node& node); 230 231 void FillLeftConvexEdgeEvent(SweepContext& tcx, Edge* edge, Node& node); 232 233 void FlipEdgeEvent(SweepContext& tcx, Point& ep, Point& eq, Triangle* t, Point& p); 234 235 /** 236 * After a flip we have two triangles and know that only one will still be 237 * intersecting the edge. So decide which to contiune with and legalize the other 238 * 239 * @param tcx 240 * @param o - should be the result of an orient2d( eq, op, ep ) 241 * @param t - triangle 1 242 * @param ot - triangle 2 243 * @param p - a point shared by both triangles 244 * @param op - another point shared by both triangles 245 * @return returns the triangle still intersecting the edge 246 */ 247 Triangle& NextFlipTriangle(SweepContext& tcx, int o, Triangle& t, Triangle& ot, Point& p, Point& op); 248 249 /** 250 * When we need to traverse from one triangle to the next we need 251 * the point in current triangle that is the opposite point to the next 252 * triangle. 253 * 254 * @param ep 255 * @param eq 256 * @param ot 257 * @param op 258 * @return 259 */ 260 Point& NextFlipPoint(Point& ep, Point& eq, Triangle& ot, Point& op); 261 262 /** 263 * Scan part of the FlipScan algorithm<br> 264 * When a triangle pair isn't flippable we will scan for the next 265 * point that is inside the flip triangle scan area. When found 266 * we generate a new flipEdgeEvent 267 * 268 * @param tcx 269 * @param ep - last point on the edge we are traversing 270 * @param eq - first point on the edge we are traversing 271 * @param flipTriangle - the current triangle sharing the point eq with edge 272 * @param t 273 * @param p 274 */ 275 void FlipScanEdgeEvent(SweepContext& tcx, Point& ep, Point& eq, Triangle& flip_triangle, Triangle& t, Point& p); 276 277 void FinalizationPolygon(SweepContext& tcx); 278 279 std::vector<Node*> nodes_; 280 281 }; 282 283 } 284 285 #endif 286