/[zanavi_public1]/navit/navit/maptool/refine/cdt.h
ZANavi

Contents of /navit/navit/maptool/refine/cdt.h

Parent Directory Parent Directory | Revision Log Revision Log


Revision 31 - (show annotations) (download)
Mon Feb 4 17:41:59 2013 UTC (11 years, 1 month ago) by zoff99
File MIME type: text/plain
File size: 5182 byte(s)
new map version, lots of fixes and experimental new features
1 /*
2 * This file is a part of Poly2Tri-C
3 * (c) Barak Itkin <lightningismyname@gmail.com>
4 * http://code.google.com/p/poly2tri-c/
5 *
6 * All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without modification,
9 * are permitted provided that the following conditions are met:
10 *
11 * * Redistributions of source code must retain the above copyright notice,
12 * this list of conditions and the following disclaimer.
13 * * Redistributions in binary form must reproduce the above copyright notice,
14 * this list of conditions and the following disclaimer in the documentation
15 * and/or other materials provided with the distribution.
16 * * Neither the name of Poly2Tri nor the names of its contributors may be
17 * used to endorse or promote products derived from this software without specific
18 * prior written permission.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
23 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
24 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
25 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
26 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
27 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
28 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
29 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
30 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 */
32
33 #ifndef __P2TC_REFINE_CDT_H__
34 #define __P2TC_REFINE_CDT_H__
35
36 #include <p2t/poly2tri.h>
37 #include "mesh.h"
38 #include "pslg.h"
39
40 typedef struct
41 {
42 P2trMesh *mesh;
43 P2trPSLG *outline;
44 } P2trCDT;
45
46 /**
47 * Create a new P2trCDT from an existing P2tCDT. The resulting P2trCDT
48 * does not depend on the original P2tCDT which can be freed
49 * @param cdt A P2tCDT Constrained Delaunay Triangulation
50 * @return A P2trCDT Constrained Delaunay Triangulation
51 */
52 P2trCDT* p2tr_cdt_new (P2tCDT *cdt);
53
54 void p2tr_cdt_free (P2trCDT *cdt);
55
56 void p2tr_cdt_free_full (P2trCDT *cdt, gboolean clear_mesh);
57
58 /**
59 * Test whether there is a path from the point @ref p to the edge @e
60 * so that the path does not cross any segment of the CDT
61 */
62 gboolean p2tr_cdt_visible_from_edge (P2trCDT *self,
63 P2trEdge *e,
64 P2trVector2 *p);
65
66 /**
67 * Make sure that all edges either have two triangles (one on each side)
68 * or that they are constrained. The reason for that is that the
69 * triangulation domain of the CDT is defined by a closed PSLG.
70 */
71 void p2tr_cdt_validate_edges (P2trCDT *self);
72
73 void p2tr_cdt_validate_unused (P2trCDT* self);
74
75 /**
76 * Make sure the constrained empty circum-circle property holds,
77 * meaning that each triangles circum-scribing circle is either empty
78 * or only contains points which are not "visible" from the edges of
79 * the triangle.
80 */
81 void p2tr_cdt_validate_cdt (P2trCDT *self);
82
83 #if P2TR_CDT_VALIDATE
84 #define P2TR_CDT_VALIDATE_EDGES(CDT) p2tr_cdt_validate_edges(CDT)
85 #define P2TR_CDT_VALIDATE_UNUSED(CDT) p2tr_cdt_validate_unused(CDT)
86 #define P2TR_CDT_VALIDATE_CDT(CDT) p2tr_cdt_validate_cdt(CDT)
87 #else
88 #define P2TR_CDT_VALIDATE_EDGES(CDT) G_STMT_START { } G_STMT_END
89 #define P2TR_CDT_VALIDATE_UNUSED(CDT) G_STMT_START { } G_STMT_END
90 #define P2TR_CDT_VALIDATE_CDT(CDT) G_STMT_START { } G_STMT_END
91 #endif
92
93 /**
94 * Insert a point into the triangulation while preserving the
95 * constrained delaunay property
96 * @param self The CDT into which the point should be inserted
97 * @param pc The point to insert
98 * @param point_location_guess A triangle which may be near the
99 * area containing the point (or maybe even contains the point).
100 * The better the guess is, the faster the insertion will be. If
101 * such a triangle is unknown, NULL may be passed.
102 */
103 P2trPoint* p2tr_cdt_insert_point (P2trCDT *self,
104 const P2trVector2 *pc,
105 P2trTriangle *point_location_guess);
106
107 /**
108 * Similar to @ref p2tr_cdt_insert_point, but assumes that the point to
109 * insert is located inside the area of the given triangle
110 */
111 void p2tr_cdt_insert_point_into_triangle (P2trCDT *self,
112 P2trPoint *pt,
113 P2trTriangle *tri);
114
115 /**
116 * Insert a point so that is splits an existing edge, while preserving
117 * the constrained delaunay property. This function assumes that the
118 * point is on the edge itself and between its end-points.
119 * If the edge being split is constrained, then the function returns a
120 * list containing both parts resulted from the splitting. In that case,
121 * THE RETURNED EDGES MUST BE UNREFERENCED!
122 */
123 GList* p2tr_cdt_split_edge (P2trCDT *self,
124 P2trEdge *e,
125 P2trPoint *C);
126
127 #endif

   
Visit the ZANavi Wiki