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