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 |
#ifndef __P2TC_P2T_SHAPES_H__
|
37 |
#define __P2TC_P2T_SHAPES_H__
|
38 |
|
39 |
#include <stddef.h>
|
40 |
#include <stdio.h>
|
41 |
#include <assert.h>
|
42 |
#include <math.h>
|
43 |
#include "poly2tri-private.h"
|
44 |
#include "cutils.h"
|
45 |
|
46 |
|
47 |
|
48 |
// --------EXCEPTIONS-------
|
49 |
|
50 |
#include <setjmp.h>
|
51 |
|
52 |
// defined in maptool.h !!
|
53 |
extern jmp_buf ex_buf__;
|
54 |
extern void (*func_global)(int);
|
55 |
long long stack_pt;
|
56 |
|
57 |
#define STACKPTMAX 12000
|
58 |
|
59 |
#define THROW(x) longjmp(ex_buf__, x)
|
60 |
#define MAPTOOL_00001_EXCEPTION (1)
|
61 |
|
62 |
// --------EXCEPTIONS-------
|
63 |
|
64 |
|
65 |
|
66 |
|
67 |
/**
|
68 |
* P2tPoint:
|
69 |
* @x: The x coordinate of the point
|
70 |
* @y: The y coordinate of the point
|
71 |
* @edge_list: The edges this point constitutes an upper ending point
|
72 |
*
|
73 |
* A struct to represent 2D points with double precision, and to keep track
|
74 |
* of the edges this point constitutes an upper ending point
|
75 |
*/
|
76 |
struct _P2tPoint
|
77 |
{
|
78 |
/*< public >*/
|
79 |
P2tEdgePtrArray edge_list;
|
80 |
double x, y;
|
81 |
};
|
82 |
|
83 |
/**
|
84 |
* p2t_point_init_dd:
|
85 |
* @THIS: The #P2tPoint to initialize
|
86 |
* @x: The desired x coordinate of the point
|
87 |
* @y: The desired y coordinate of the point
|
88 |
*
|
89 |
* A function to initialize a #P2tPoint struct with the given coordinates. The
|
90 |
* struct must later be finalized by a call to #p2t_point_destroy
|
91 |
*/
|
92 |
void p2t_point_init_dd (P2tPoint* THIS, double x, double y);
|
93 |
|
94 |
/**
|
95 |
* p2t_point_new_dd:
|
96 |
* @x: The desired x coordinate of the point
|
97 |
* @y: The desired y coordinate of the point
|
98 |
*
|
99 |
* A utility function to alloacte and initialize a #P2tPoint.
|
100 |
* See #p2t_point_init_dd. Note that when finished using the point, it must be
|
101 |
* freed by a call to #p2t_point_free and can not be freed like regular memory.
|
102 |
*
|
103 |
* Returns: The allocated and initialized point
|
104 |
*/
|
105 |
P2tPoint* p2t_point_new_dd (double x, double y);
|
106 |
|
107 |
/**
|
108 |
* p2t_point_init:
|
109 |
* @THIS: The #P2tPoint to initialize
|
110 |
*
|
111 |
* A function to initialize a #P2tPoint struct to (0,0). The struct must later
|
112 |
* be finalized by a call to #p2t_point_destroy
|
113 |
*/
|
114 |
void p2t_point_init (P2tPoint* THIS);
|
115 |
|
116 |
/**
|
117 |
* p2t_point_new:
|
118 |
*
|
119 |
* A utility function to alloacte and initialize a #P2tPoint.
|
120 |
* See #p2t_point_init. Note that when finished using the point, it must be
|
121 |
* freed by a call to #p2t_point_free and can not be freed like regular memory.
|
122 |
*/
|
123 |
P2tPoint* p2t_point_new ();
|
124 |
|
125 |
/**
|
126 |
* p2t_point_destroy:
|
127 |
* @THIS: The #P2tPoint whose resources should be freed
|
128 |
*
|
129 |
* This function will free all the resources allocated by a #P2tPoint, without
|
130 |
* freeing the #P2tPoint pointed by @THIS
|
131 |
*/
|
132 |
void p2t_point_destroy (P2tPoint* THIS);
|
133 |
|
134 |
/**
|
135 |
* p2t_point_free:
|
136 |
* @THIS: The #P2tPoint to free
|
137 |
*
|
138 |
* This function will free all the resources allocated by a #P2tPoint, and will
|
139 |
* also free the #P2tPoint pointed by @THIS
|
140 |
*/
|
141 |
void p2t_point_free (P2tPoint* THIS);
|
142 |
|
143 |
/**
|
144 |
* P2tEdge:
|
145 |
* @p: The top right point of the edge
|
146 |
* @q: The bottom left point of the edge
|
147 |
*
|
148 |
* Represents a simple polygon's edge
|
149 |
*/
|
150 |
struct _P2tEdge
|
151 |
{
|
152 |
P2tPoint *p, *q;
|
153 |
};
|
154 |
|
155 |
/**
|
156 |
* p2t_edge_init:
|
157 |
* @THIS: The #P2tEdge to initialize
|
158 |
* @p1: One of the two points that form the edge
|
159 |
* @p2: The other point of the two points that form the edge
|
160 |
*
|
161 |
* A function to initialize a #P2tEdge struct from the given points. The
|
162 |
* struct must later be finalized by a call to #p2t_point_destroy.
|
163 |
*
|
164 |
* Warning: The points must be geometrically not-equal! This means that they
|
165 |
* must differ by at least one of their coordinates. Otherwise, a runtime error
|
166 |
* would be raised!
|
167 |
*/
|
168 |
void p2t_edge_init (P2tEdge* THIS, P2tPoint* p1, P2tPoint* p2);
|
169 |
|
170 |
/**
|
171 |
* p2t_edge_new:
|
172 |
*
|
173 |
* A utility function to alloacte and initialize a #P2tEdge.
|
174 |
* See #p2t_edge_init. Note that when finished using the point, it must be freed
|
175 |
* by a call to #p2t_point_free and can not be freed like regular memory.
|
176 |
*
|
177 |
* Returns: The allocated and initialized edge
|
178 |
*/
|
179 |
P2tEdge* p2t_edge_new (P2tPoint* p1, P2tPoint* p2);
|
180 |
|
181 |
/**
|
182 |
* p2t_edge_destroy:
|
183 |
* @THIS: The #P2tEdge whose resources should be freed
|
184 |
*
|
185 |
* This function will free all the resources allocated by a #P2tEdge, without
|
186 |
* freeing the #P2tPoint pointed by @THIS
|
187 |
*/
|
188 |
void p2t_edge_destroy (P2tEdge* THIS);
|
189 |
|
190 |
/**
|
191 |
* p2t_edge_free:
|
192 |
* @THIS: The #P2tEdge to free
|
193 |
*
|
194 |
* This function will free all the resources allocated by a #P2tEdge, and will
|
195 |
* also free the #P2tEdge pointed by @THIS
|
196 |
*/
|
197 |
void p2t_edge_free (P2tEdge* THIS);
|
198 |
|
199 |
|
200 |
/* Triangle-based data structures are know to have better performance than quad-edge structures
|
201 |
* See: J. Shewchuk, "Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator"
|
202 |
* "Triangulations in CGAL"
|
203 |
*/
|
204 |
|
205 |
/**
|
206 |
* P2tTriangle:
|
207 |
* @constrained_edge: Flags to determine if an edge is a Constrained edge
|
208 |
* @delaunay_edg: Flags to determine if an edge is a Delauney edge
|
209 |
* @points_: Triangle points
|
210 |
* @neighbors_: Neighbor list
|
211 |
* @interior_: Has this triangle been marked as an interior triangle?
|
212 |
*
|
213 |
* A data structure for representing a triangle, while keeping information about
|
214 |
* neighbor triangles, etc.
|
215 |
*/
|
216 |
struct _P2tTriangle
|
217 |
{
|
218 |
/*< public >*/
|
219 |
gboolean constrained_edge[3];
|
220 |
gboolean delaunay_edge[3];
|
221 |
|
222 |
/*< private >*/
|
223 |
P2tPoint * points_[3];
|
224 |
struct _P2tTriangle * neighbors_[3];
|
225 |
gboolean interior_;
|
226 |
};
|
227 |
|
228 |
P2tTriangle* p2t_triangle_new (P2tPoint* a, P2tPoint* b, P2tPoint* c);
|
229 |
void p2t_triangle_init (P2tTriangle* THIS, P2tPoint* a, P2tPoint* b, P2tPoint* c);
|
230 |
P2tPoint* p2t_triangle_get_point (P2tTriangle* THIS, const int index);
|
231 |
P2tPoint* p2t_triangle_point_cw (P2tTriangle* THIS, P2tPoint* point);
|
232 |
P2tPoint* p2t_triangle_point_ccw (P2tTriangle* THIS, P2tPoint* point);
|
233 |
P2tPoint* p2t_triangle_opposite_point (P2tTriangle* THIS, P2tTriangle* t, P2tPoint* p);
|
234 |
|
235 |
P2tTriangle* p2t_triangle_get_neighbor (P2tTriangle* THIS, const int index);
|
236 |
void p2t_triangle_mark_neighbor_pt_pt_tr (P2tTriangle* THIS, P2tPoint* p1, P2tPoint* p2, P2tTriangle* t);
|
237 |
void p2t_triangle_mark_neighbor_tr (P2tTriangle* THIS, P2tTriangle *t);
|
238 |
|
239 |
void p2t_triangle_mark_constrained_edge_i (P2tTriangle* THIS, const int index);
|
240 |
void p2t_triangle_mark_constrained_edge_ed (P2tTriangle* THIS, P2tEdge* edge);
|
241 |
void p2t_triangle_mark_constrained_edge_pt_pt (P2tTriangle* THIS, P2tPoint* p, P2tPoint* q);
|
242 |
|
243 |
int p2t_triangle_index (P2tTriangle* THIS, const P2tPoint* p);
|
244 |
int p2t_triangle_edge_index (P2tTriangle* THIS, const P2tPoint* p1, const P2tPoint* p2);
|
245 |
|
246 |
P2tTriangle* p2t_triangle_neighbor_cw (P2tTriangle* THIS, P2tPoint* point);
|
247 |
P2tTriangle* p2t_triangle_neighbor_ccw (P2tTriangle* THIS, P2tPoint* point);
|
248 |
gboolean p2t_triangle_get_constrained_edge_ccw (P2tTriangle* THIS, P2tPoint* p);
|
249 |
gboolean p2t_triangle_get_constrained_edge_cw (P2tTriangle* THIS, P2tPoint* p);
|
250 |
void p2t_triangle_set_constrained_edge_ccw (P2tTriangle* THIS, P2tPoint* p, gboolean ce);
|
251 |
void p2t_triangle_set_constrained_edge_cw (P2tTriangle* THIS, P2tPoint* p, gboolean ce);
|
252 |
gboolean p2t_triangle_get_delunay_edge_ccw (P2tTriangle* THIS, P2tPoint* p);
|
253 |
gboolean p2t_triangle_get_delunay_edge_cw (P2tTriangle* THIS, P2tPoint* p);
|
254 |
void p2t_triangle_set_delunay_edge_ccw (P2tTriangle* THIS, P2tPoint* p, gboolean e);
|
255 |
void p2t_triangle_set_delunay_edge_cw (P2tTriangle* THIS, P2tPoint* p, gboolean e);
|
256 |
|
257 |
gboolean p2t_triangle_contains_pt (P2tTriangle* THIS, P2tPoint* p);
|
258 |
gboolean p2t_triangle_contains_ed (P2tTriangle* THIS, const P2tEdge* e);
|
259 |
gboolean p2t_triangle_contains_pt_pt (P2tTriangle* THIS, P2tPoint* p, P2tPoint* q);
|
260 |
void p2t_triangle_legalize_pt (P2tTriangle* THIS, P2tPoint* point);
|
261 |
void p2t_triangle_legalize_pt_pt (P2tTriangle* THIS, P2tPoint* opoint, P2tPoint* npoint);
|
262 |
/**
|
263 |
* Clears all references to all other triangles and points
|
264 |
*/
|
265 |
void p2t_triangle_clear (P2tTriangle* THIS);
|
266 |
void p2t_triangle_clear_neighbor_tr (P2tTriangle* THIS, P2tTriangle *triangle);
|
267 |
void p2t_triangle_clear_neighbors (P2tTriangle* THIS);
|
268 |
void p2t_triangle_clear_delunay_edges (P2tTriangle* THIS);
|
269 |
|
270 |
gboolean p2t_triangle_is_interior (P2tTriangle* THIS);
|
271 |
void p2t_triangle_is_interior_b (P2tTriangle* THIS, gboolean b);
|
272 |
|
273 |
P2tTriangle* p2t_triangle_neighbor_across (P2tTriangle* THIS, P2tPoint* opoint);
|
274 |
|
275 |
void p2t_triangle_debug_print (P2tTriangle* THIS);
|
276 |
|
277 |
gint p2t_point_cmp (gconstpointer a, gconstpointer b);
|
278 |
|
279 |
/* gboolean operator == (const Point& a, const Point& b); */
|
280 |
gboolean p2t_point_equals (const P2tPoint* a, const P2tPoint* b);
|
281 |
|
282 |
#endif
|
283 |
|
284 |
|