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 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(Point& pa, Point& pb, Point& pc, Point& pd); 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); 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 /** 173 * 174 * @param node - middle node 175 * @return the angle between 3 front nodes 176 */ 177 float HoleAngle(Node& node); 178 179 /** 180 * The basin angle is decided against the horizontal line [1,0] 181 */ 182 float BasinAngle(Node& node); 183 184 /** 185 * Fills a basin that has formed on the Advancing Front to the right 186 * of given node.<br> 187 * First we decide a left,bottom and right node that forms the 188 * boundaries of the basin. Then we do a reqursive fill. 189 * 190 * @param tcx 191 * @param node - starting node, this or next node will be left node 192 */ 193 void FillBasin(SweepContext& tcx, Node& node); 194 195 /** 196 * Recursive algorithm to fill a Basin with triangles 197 * 198 * @param tcx 199 * @param node - bottom_node 200 * @param cnt - counter used to alternate on even and odd numbers 201 */ 202 void FillBasinReq(SweepContext& tcx, Node* node); 203 204 bool IsShallow(SweepContext& tcx, Node& node); 205 206 bool IsEdgeSideOfTriangle(Triangle& triangle, Point& ep, Point& eq); 207 208 void FillEdgeEvent(SweepContext& tcx, Edge* edge, Node* node); 209 210 void FillRightAboveEdgeEvent(SweepContext& tcx, Edge* edge, Node* node); 211 212 void FillRightBelowEdgeEvent(SweepContext& tcx, Edge* edge, Node& node); 213 214 void FillRightConcaveEdgeEvent(SweepContext& tcx, Edge* edge, Node& node); 215 216 void FillRightConvexEdgeEvent(SweepContext& tcx, Edge* edge, Node& node); 217 218 void FillLeftAboveEdgeEvent(SweepContext& tcx, Edge* edge, Node* node); 219 220 void FillLeftBelowEdgeEvent(SweepContext& tcx, Edge* edge, Node& node); 221 222 void FillLeftConcaveEdgeEvent(SweepContext& tcx, Edge* edge, Node& node); 223 224 void FillLeftConvexEdgeEvent(SweepContext& tcx, Edge* edge, Node& node); 225 226 void FlipEdgeEvent(SweepContext& tcx, Point& ep, Point& eq, Triangle* t, Point& p); 227 228 /** 229 * After a flip we have two triangles and know that only one will still be 230 * intersecting the edge. So decide which to contiune with and legalize the other 231 * 232 * @param tcx 233 * @param o - should be the result of an orient2d( eq, op, ep ) 234 * @param t - triangle 1 235 * @param ot - triangle 2 236 * @param p - a point shared by both triangles 237 * @param op - another point shared by both triangles 238 * @return returns the triangle still intersecting the edge 239 */ 240 Triangle& NextFlipTriangle(SweepContext& tcx, int o, Triangle& t, Triangle& ot, Point& p, Point& op); 241 242 /** 243 * When we need to traverse from one triangle to the next we need 244 * the point in current triangle that is the opposite point to the next 245 * triangle. 246 * 247 * @param ep 248 * @param eq 249 * @param ot 250 * @param op 251 * @return 252 */ 253 Point& NextFlipPoint(Point& ep, Point& eq, Triangle& ot, Point& op); 254 255 /** 256 * Scan part of the FlipScan algorithm<br> 257 * When a triangle pair isn't flippable we will scan for the next 258 * point that is inside the flip triangle scan area. When found 259 * we generate a new flipEdgeEvent 260 * 261 * @param tcx 262 * @param ep - last point on the edge we are traversing 263 * @param eq - first point on the edge we are traversing 264 * @param flipTriangle - the current triangle sharing the point eq with edge 265 * @param t 266 * @param p 267 */ 268 void FlipScanEdgeEvent(SweepContext& tcx, Point& ep, Point& eq, Triangle& flip_triangle, Triangle& t, Point& p); 269 270 void FinalizationPolygon(SweepContext& tcx); 271 272 std::vector<Node*> nodes_; 273 274 }; 275 276 } 277 278 #endif 279