From 78a22e6d6ef3120e8fb7c3793ded4bfdfc80fbc9 Mon Sep 17 00:00:00 2001 From: Barak Itkin Date: Fri, 20 Apr 2012 19:09:52 +0300 Subject: [PATCH 1/1] Import the code (only) from the GEGL soc-2011-seamless-clone branch The poly2tri-c code was developped inside the GEGL repository as part of the Google Summer of Code 2011 project. It is time to seperate the repositories and to make poly2tri-c an independent library. The code checked in in this commit is from commit 6ae8521387 of GEGL. --- common/cutils.h | 39 + common/poly2tri-private.h | 34 + common/shapes.c | 736 ++++++++++++++++++ common/shapes.h | 262 +++++++ common/utils.c | 95 +++ common/utils.h | 63 ++ main.c | 260 +++++++ poly2tri.h | 39 + refine/refine.c | 706 ++++++++++++++++++ refine/refine.h | 29 + refine/triangulation.c | 1494 +++++++++++++++++++++++++++++++++++++ refine/triangulation.h | 323 ++++++++ refine/utils.h | 71 ++ render/mesh-render.c | 354 +++++++++ render/mesh-render.h | 73 ++ render/svg-plot.c | 330 ++++++++ render/svg-plot.h | 98 +++ sweep/advancing_front.c | 224 ++++++ sweep/advancing_front.h | 88 +++ sweep/cdt.c | 90 +++ sweep/cdt.h | 101 +++ sweep/sweep.c | 932 +++++++++++++++++++++++ sweep/sweep.h | 270 +++++++ sweep/sweep_context.c | 313 ++++++++ sweep/sweep_context.h | 133 ++++ 25 files changed, 7157 insertions(+) create mode 100755 common/cutils.h create mode 100755 common/poly2tri-private.h create mode 100755 common/shapes.c create mode 100755 common/shapes.h create mode 100755 common/utils.c create mode 100755 common/utils.h create mode 100755 main.c create mode 100755 poly2tri.h create mode 100755 refine/refine.c create mode 100755 refine/refine.h create mode 100755 refine/triangulation.c create mode 100755 refine/triangulation.h create mode 100755 refine/utils.h create mode 100755 render/mesh-render.c create mode 100755 render/mesh-render.h create mode 100755 render/svg-plot.c create mode 100755 render/svg-plot.h create mode 100755 sweep/advancing_front.c create mode 100755 sweep/advancing_front.h create mode 100755 sweep/cdt.c create mode 100755 sweep/cdt.h create mode 100755 sweep/sweep.c create mode 100755 sweep/sweep.h create mode 100755 sweep/sweep_context.c create mode 100755 sweep/sweep_context.h diff --git a/common/cutils.h b/common/cutils.h new file mode 100755 index 0000000..1fcb2cd --- /dev/null +++ b/common/cutils.h @@ -0,0 +1,39 @@ +/* + * File: cutils.h + * Author: user + * + * Created on 28 מאי 2011, 02:24 + */ + +#ifndef CUTILS_H +#define CUTILS_H + +#include +#include "poly2tri-private.h" + +#ifdef __cplusplus +extern "C" +{ +#endif + +#define DEBUG FALSE + + typedef GPtrArray* P2tEdgePtrArray; +#define edge_index(array,index_) ((P2tEdge*)g_ptr_array_index(array,index_)) + typedef GPtrArray* P2tPointPtrArray; +#define point_index(array,index_) ((P2tPoint*)g_ptr_array_index(array,index_)) + typedef GPtrArray* P2tTrianglePtrArray; +#define triangle_index(array,index_) ((P2tTriangle*)g_ptr_array_index(array,index_)) + typedef GPtrArray* P2tNodePtrArray; +#define node_index(array,index_) ((P2tNode*)g_ptr_array_index(array,index_)) + typedef GList* P2tTrianglePtrList; +#define triangle_val(list) ((P2tTriangle*)((list)->data)) + +#define g_ptr_array_index_cyclic(array,index_) g_ptr_array_index(array,(index_)%((array)->len)) + +#ifdef __cplusplus +} +#endif + +#endif /* CUTILS_H */ + diff --git a/common/poly2tri-private.h b/common/poly2tri-private.h new file mode 100755 index 0000000..abdb29b --- /dev/null +++ b/common/poly2tri-private.h @@ -0,0 +1,34 @@ +/* + * File: poly2tri-private.h + * Author: user + * + * Created on 4 יוני 2011, 13:22 + */ + +#ifndef POLY2TRI_PRIVATE_H +#define POLY2TRI_PRIVATE_H + +#ifdef __cplusplus +extern "C" +{ +#endif + +typedef struct _P2tNode P2tNode; +typedef struct AdvancingFront_ P2tAdvancingFront; +typedef struct CDT_ P2tCDT; +typedef struct _P2tEdge P2tEdge; +typedef struct _P2tPoint P2tPoint; +typedef struct _P2tTriangle P2tTriangle; +typedef struct SweepContext_ P2tSweepContext; +typedef struct Sweep_ P2tSweep; + +typedef struct P2tSweepContextBasin_ P2tSweepContextBasin; +typedef struct P2tSweepContextEdgeEvent_ P2tSweepContextEdgeEvent; + + +#ifdef __cplusplus +} +#endif + +#endif /* POLY2TRI_PRIVATE_H */ + diff --git a/common/shapes.c b/common/shapes.c new file mode 100755 index 0000000..f211148 --- /dev/null +++ b/common/shapes.c @@ -0,0 +1,736 @@ +/* + * This file is a part of Poly2Tri-C - The C port of the Poly2Tri library + * Porting to C done by (c) Barak Itkin + * http://code.google.com/p/poly2tri-c/ + * + * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors + * http://code.google.com/p/poly2tri/ + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without modification, + * are permitted provided that the following conditions are met: + * + * * Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * * Neither the name of Poly2Tri nor the names of its contributors may be + * used to endorse or promote products derived from this software without specific + * prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ +#include "shapes.h" +#include +#include + +/// Default constructor does nothing (for performance). + +void +p2t_point_init (P2tPoint* THIS) +{ + THIS->x = 0; + THIS->y = 0; + THIS->edge_list = g_ptr_array_new (); +} + +P2tPoint* +p2t_point_new () +{ + P2tPoint* THIS = g_slice_new (P2tPoint); + p2t_point_init (THIS); + return THIS; +} + +/// Construct using coordinates. + +void +p2t_point_init_dd (P2tPoint* THIS, double x, double y) +{ + THIS->x = x; + THIS->y = y; + THIS->edge_list = g_ptr_array_new (); +} + +P2tPoint* +p2t_point_new_dd (double x, double y) +{ + P2tPoint* THIS = g_slice_new (P2tPoint); + p2t_point_init_dd (THIS, x, y); + return THIS; +} + +void +p2t_point_destroy (P2tPoint* THIS) +{ + g_ptr_array_free (THIS->edge_list, TRUE); +} + +void +p2t_point_free (P2tPoint* THIS) +{ + p2t_point_destroy (THIS); + g_slice_free (P2tPoint, THIS); +} + +/// Constructor + +void +p2t_edge_init (P2tEdge* THIS, P2tPoint* p1, P2tPoint* p2) +{ + THIS->p = p1; + THIS->q = p2; + if (p1->y > p2->y) + { + THIS->q = p1; + THIS->p = p2; + } + else if (p1->y == p2->y) + { + if (p1->x > p2->x) + { + THIS->q = p1; + THIS->p = p2; + } + else if (p1->x == p2->x) + { + // Repeat points + assert (FALSE); + } + } + + g_ptr_array_add (THIS->q->edge_list, THIS); +} + +P2tEdge* +p2t_edge_new (P2tPoint* p1, P2tPoint* p2) +{ + P2tEdge* THIS = g_slice_new (P2tEdge); + p2t_edge_init (THIS, p1, p2); + return THIS; +} + +void +p2t_edge_destroy (P2tEdge* THIS) { } + +void +p2t_edge_free (P2tEdge* THIS) +{ + p2t_edge_destroy (THIS); + g_slice_free (P2tEdge, THIS); +} + +P2tTriangle* +p2t_triangle_new (P2tPoint* a, P2tPoint* b, P2tPoint* c) +{ + P2tTriangle *tr = g_new (P2tTriangle, 1); + p2t_triangle_init (tr, a, b, c); + return tr; +} + +void +p2t_triangle_init (P2tTriangle* THIS, P2tPoint* a, P2tPoint* b, P2tPoint* c) +{ + THIS->points_[0] = a; + THIS->points_[1] = b; + THIS->points_[2] = c; + THIS->neighbors_[0] = NULL; + THIS->neighbors_[1] = NULL; + THIS->neighbors_[2] = NULL; + THIS->constrained_edge[0] = THIS->constrained_edge[1] = THIS->constrained_edge[2] = FALSE; + THIS->delaunay_edge[0] = THIS->delaunay_edge[1] = THIS->delaunay_edge[2] = FALSE; + THIS->interior_ = FALSE; + +} +// Update neighbor pointers + +void +p2t_triangle_mark_neighbor_pt_pt_tr (P2tTriangle* THIS, P2tPoint* p1, P2tPoint* p2, P2tTriangle* t) +{ + if ((p1 == THIS->points_[2] && p2 == THIS->points_[1]) || (p1 == THIS->points_[1] && p2 == THIS->points_[2])) + THIS->neighbors_[0] = t; + else if ((p1 == THIS->points_[0] && p2 == THIS->points_[2]) || (p1 == THIS->points_[2] && p2 == THIS->points_[0])) + THIS->neighbors_[1] = t; + else if ((p1 == THIS->points_[0] && p2 == THIS->points_[1]) || (p1 == THIS->points_[1] && p2 == THIS->points_[0])) + THIS->neighbors_[2] = t; + else + assert (0); +} + +// Exhaustive search to update neighbor pointers + +void +p2t_triangle_mark_neighbor_tr (P2tTriangle* THIS, P2tTriangle *t) +{ + if (p2t_triangle_contains_pt_pt (t, THIS->points_[1], THIS->points_[2])) + { + THIS->neighbors_[0] = t; + p2t_triangle_mark_neighbor_pt_pt_tr (t, THIS->points_[1], THIS->points_[2], THIS); + } + else if (p2t_triangle_contains_pt_pt (t, THIS->points_[0], THIS->points_[2])) + { + THIS->neighbors_[1] = t; + p2t_triangle_mark_neighbor_pt_pt_tr (t, THIS->points_[0], THIS->points_[2], THIS); + } + else if (p2t_triangle_contains_pt_pt (t, THIS->points_[0], THIS->points_[1])) + { + THIS->neighbors_[2] = t; + p2t_triangle_mark_neighbor_pt_pt_tr (t, THIS->points_[0], THIS->points_[1], THIS); + } +} + +/** + * Clears all references to all other triangles and points + */ +void +p2t_triangle_clear (P2tTriangle* THIS) +{ + int i; + P2tTriangle *t; + for (i = 0; i < 3; i++) + { + t = THIS->neighbors_[i]; + if (t != NULL) + { + p2t_triangle_clear_neighbor_tr (t, THIS); + } + } + p2t_triangle_clear_neighbors (THIS); + THIS->points_[0] = THIS->points_[1] = THIS->points_[2] = NULL; +} + +void +p2t_triangle_clear_neighbor_tr (P2tTriangle* THIS, P2tTriangle *triangle) +{ + if (THIS->neighbors_[0] == triangle) + { + THIS->neighbors_[0] = NULL; + } + else if (THIS->neighbors_[1] == triangle) + { + THIS->neighbors_[1] = NULL; + } + else + { + THIS->neighbors_[2] = NULL; + } +} + +void +p2t_triangle_clear_neighbors (P2tTriangle* THIS) +{ + THIS->neighbors_[0] = NULL; + THIS->neighbors_[1] = NULL; + THIS->neighbors_[2] = NULL; +} + +void +p2t_triangle_clear_delunay_edges (P2tTriangle* THIS) +{ + THIS->delaunay_edge[0] = THIS->delaunay_edge[1] = THIS->delaunay_edge[2] = FALSE; +} + +P2tPoint* +p2t_triangle_opposite_point (P2tTriangle* THIS, P2tTriangle* t, P2tPoint* p) +{ + P2tPoint *cw = p2t_triangle_point_cw (t, p); + double x = cw->x; + double y = cw->y; + x = p->x; + y = p->y; + P2tPoint* ham = p2t_triangle_point_cw (THIS, cw); + return p2t_triangle_point_cw (THIS, cw); +} + +// Legalized triangle by rotating clockwise around point(0) + +void +p2t_triangle_legalize_pt (P2tTriangle* THIS, P2tPoint *point) +{ + THIS->points_[1] = THIS->points_[0]; + THIS->points_[0] = THIS->points_[2]; + THIS->points_[2] = point; +} + +// Legalize triagnle by rotating clockwise around oPoint + +void +p2t_triangle_legalize_pt_pt (P2tTriangle* THIS, P2tPoint *opoint, P2tPoint *npoint) +{ + if (opoint == THIS->points_[0]) + { + THIS->points_[1] = THIS->points_[0]; + THIS->points_[0] = THIS->points_[2]; + THIS->points_[2] = npoint; + } + else if (opoint == THIS->points_[1]) + { + THIS->points_[2] = THIS->points_[1]; + THIS->points_[1] = THIS->points_[0]; + THIS->points_[0] = npoint; + } + else if (opoint == THIS->points_[2]) + { + THIS->points_[0] = THIS->points_[2]; + THIS->points_[2] = THIS->points_[1]; + THIS->points_[1] = npoint; + } + else + { + assert (0); + } +} + +int +p2t_triangle_index (P2tTriangle* THIS, const P2tPoint* p) +{ + if (p == THIS->points_[0]) + { + return 0; + } + else if (p == THIS->points_[1]) + { + return 1; + } + else if (p == THIS->points_[2]) + { + return 2; + } + assert (0); +} + +int +p2t_triangle_edge_index (P2tTriangle* THIS, const P2tPoint* p1, const P2tPoint* p2) +{ + if (THIS->points_[0] == p1) + { + if (THIS->points_[1] == p2) + { + return 2; + } + else if (THIS->points_[2] == p2) + { + return 1; + } + } + else if (THIS->points_[1] == p1) + { + if (THIS->points_[2] == p2) + { + return 0; + } + else if (THIS->points_[0] == p2) + { + return 2; + } + } + else if (THIS->points_[2] == p1) + { + if (THIS->points_[0] == p2) + { + return 1; + } + else if (THIS->points_[1] == p2) + { + return 0; + } + } + return -1; +} + +void +p2t_triangle_mark_constrained_edge_i (P2tTriangle* THIS, const int index) +{ + THIS->constrained_edge[index] = TRUE; +} + +void +p2t_triangle_mark_constrained_edge_ed (P2tTriangle* THIS, P2tEdge* edge) +{ + p2t_triangle_mark_constrained_edge_pt_pt (THIS, edge->p, edge->q); +} + +// Mark edge as constrained + +void +p2t_triangle_mark_constrained_edge_pt_pt (P2tTriangle* THIS, P2tPoint* p, P2tPoint* q) +{ + if ((q == THIS->points_[0] && p == THIS->points_[1]) || (q == THIS->points_[1] && p == THIS->points_[0])) + { + THIS->constrained_edge[2] = TRUE; + } + else if ((q == THIS->points_[0] && p == THIS->points_[2]) || (q == THIS->points_[2] && p == THIS->points_[0])) + { + THIS->constrained_edge[1] = TRUE; + } + else if ((q == THIS->points_[1] && p == THIS->points_[2]) || (q == THIS->points_[2] && p == THIS->points_[1])) + { + THIS->constrained_edge[0] = TRUE; + } +} + +// The point counter-clockwise to given point + +P2tPoint* +p2t_triangle_point_cw (P2tTriangle* THIS, P2tPoint* point) +{ + if (point == THIS->points_[0]) + { + return THIS->points_[2]; + } + else if (point == THIS->points_[1]) + { + return THIS->points_[0]; + } + else if (point == THIS->points_[2]) + { + return THIS->points_[1]; + } + assert (0); +} + +// The point counter-clockwise to given point + +P2tPoint* +p2t_triangle_point_ccw (P2tTriangle* THIS, P2tPoint* point) +{ + if (point == THIS->points_[0]) + { + return THIS->points_[1]; + } + else if (point == THIS->points_[1]) + { + return THIS->points_[2]; + } + else if (point == THIS->points_[2]) + { + return THIS->points_[0]; + } + assert (0); +} + +// The neighbor clockwise to given point + +P2tTriangle* +p2t_triangle_neighbor_cw (P2tTriangle* THIS, P2tPoint* point) +{ + if (point == THIS->points_[0]) + { + return THIS->neighbors_[1]; + } + else if (point == THIS->points_[1]) + { + return THIS->neighbors_[2]; + } + return THIS->neighbors_[0]; +} + +// The neighbor counter-clockwise to given point + +P2tTriangle* +p2t_triangle_neighbor_ccw (P2tTriangle* THIS, P2tPoint* point) +{ + if (point == THIS->points_[0]) + { + return THIS->neighbors_[2]; + } + else if (point == THIS->points_[1]) + { + return THIS->neighbors_[0]; + } + return THIS->neighbors_[1]; +} + +gboolean +p2t_triangle_get_constrained_edge_ccw (P2tTriangle* THIS, P2tPoint* p) +{ + if (p == THIS->points_[0]) + { + return THIS->constrained_edge[2]; + } + else if (p == THIS->points_[1]) + { + return THIS->constrained_edge[0]; + } + return THIS->constrained_edge[1]; +} + +gboolean +p2t_triangle_get_constrained_edge_cw (P2tTriangle* THIS, P2tPoint* p) +{ + if (p == THIS->points_[0]) + { + return THIS->constrained_edge[1]; + } + else if (p == THIS->points_[1]) + { + return THIS->constrained_edge[2]; + } + return THIS->constrained_edge[0]; +} + +void +p2t_triangle_set_constrained_edge_ccw (P2tTriangle* THIS, P2tPoint* p, gboolean ce) +{ + if (p == THIS->points_[0]) + { + THIS->constrained_edge[2] = ce; + } + else if (p == THIS->points_[1]) + { + THIS->constrained_edge[0] = ce; + } + else + { + THIS->constrained_edge[1] = ce; + } +} + +void +p2t_triangle_set_constrained_edge_cw (P2tTriangle* THIS, P2tPoint* p, gboolean ce) +{ + if (p == THIS->points_[0]) + { + THIS->constrained_edge[1] = ce; + } + else if (p == THIS->points_[1]) + { + THIS->constrained_edge[2] = ce; + } + else + { + THIS->constrained_edge[0] = ce; + } +} + +gboolean +p2t_triangle_get_delunay_edge_ccw (P2tTriangle* THIS, P2tPoint* p) +{ + if (p == THIS->points_[0]) + { + return THIS->delaunay_edge[2]; + } + else if (p == THIS->points_[1]) + { + return THIS->delaunay_edge[0]; + } + return THIS->delaunay_edge[1]; +} + +gboolean +p2t_triangle_get_delunay_edge_cw (P2tTriangle* THIS, P2tPoint* p) +{ + if (p == THIS->points_[0]) + { + return THIS->delaunay_edge[1]; + } + else if (p == THIS->points_[1]) + { + return THIS->delaunay_edge[2]; + } + return THIS->delaunay_edge[0]; +} + +void +p2t_triangle_set_delunay_edge_ccw (P2tTriangle* THIS, P2tPoint* p, gboolean e) +{ + if (p == THIS->points_[0]) + { + THIS->delaunay_edge[2] = e; + } + else if (p == THIS->points_[1]) + { + THIS->delaunay_edge[0] = e; + } + else + { + THIS->delaunay_edge[1] = e; + } +} + +void +p2t_triangle_set_delunay_edge_cw (P2tTriangle* THIS, P2tPoint* p, gboolean e) +{ + if (p == THIS->points_[0]) + { + THIS->delaunay_edge[1] = e; + } + else if (p == THIS->points_[1]) + { + THIS->delaunay_edge[2] = e; + } + else + { + THIS->delaunay_edge[0] = e; + } +} + +// The neighbor across to given point + +P2tTriangle* +p2t_triangle_neighbor_across (P2tTriangle* THIS, P2tPoint* opoint) +{ + if (opoint == THIS->points_[0]) + { + return THIS->neighbors_[0]; + } + else if (opoint == THIS->points_[1]) + { + return THIS->neighbors_[1]; + } + return THIS->neighbors_[2]; +} + +void +p2t_triangle_debug_print (P2tTriangle* THIS) +{ + printf ("%f,%f ", THIS->points_[0]->x, THIS->points_[0]->y); + printf ("%f,%f ", THIS->points_[1]->x, THIS->points_[1]->y); + printf ("%f,%f\n", THIS->points_[2]->x, THIS->points_[2]->y); +} + +// WARNING! the function for sorting a g_ptr_array expects to recieve +// pointers to the pointers (double indirection)! + +gint +p2t_point_cmp (gconstpointer a, gconstpointer b) +{ + P2tPoint *ap = *((P2tPoint**) a), *bp = *((P2tPoint**) b); + if (ap->y < bp->y) + { + return -1; + } + else if (ap->y == bp->y) + { + // Make sure q is point with greater x value + if (ap->x < bp->x) + { + return -1; + } + else if (ap->x == bp->x) + return 0; + } + return 1; +} + +// /// Add two points_ component-wise. +// +// Point operator + (const Point& a, const Point& b) +// { +// return Point (a.x + b.x, a.y + b.y); +// } +// +// /// Subtract two points_ component-wise. +// +// Point operator - (const Point& a, const Point& b) +// { +// return Point (a.x - b.x, a.y - b.y); +// } +// +// /// Multiply point by scalar +// +// Point operator * (double s, const Point& a) +// { +// return Point (s * a.x, s * a.y); +// } + +// gboolean operator == (const Point& a, const Point& b) + +gboolean +p2t_point_equals (const P2tPoint* a, const P2tPoint* b) +{ + return a->x == b->x && a->y == b->y; +} +// +// gboolean operator != (const Point& a, const Point& b) +// { +// return a.x != b.x && a.y != b.y; +// } + +// /// Peform the dot product on two vectors. +// +// double +// Dot (const Point& a, const Point& b) +// { +// return a.x * b.x + a.y * b.y; +// } +// +// /// Perform the cross product on two vectors. In 2D this produces a scalar. +// +// double +// Cross (const Point& a, const Point& b) +// { +// return a.x * b.y - a.y * b.x; +// } +// +// /// Perform the cross product on a point and a scalar. In 2D this produces +// /// a point. +// +// Point +// Cross (const Point& a, double s) +// { +// return Point (s * a.y, -s * a.x); +// } +// +// /// Perform the cross product on a scalar and a point. In 2D this produces +// /// a point. +// +// Point +// Cross (const double s, const Point& a) +// { +// return Point (-s * a.y, s * a.x); +// } + +P2tPoint* +p2t_triangle_get_point (P2tTriangle* THIS, const int index) +{ + return THIS->points_[index]; +} + +P2tTriangle* +p2t_triangle_get_neighbor (P2tTriangle* THIS, const int index) +{ + return THIS->neighbors_[index]; +} + +gboolean +p2t_triangle_contains_pt (P2tTriangle* THIS, P2tPoint* p) +{ + return p == THIS->points_[0] || p == THIS->points_[1] || p == THIS->points_[2]; +} + +gboolean +p2t_triangle_contains_ed (P2tTriangle* THIS, const P2tEdge* e) +{ + return p2t_triangle_contains_pt (THIS, e->p) && p2t_triangle_contains_pt (THIS, e->q); +} + +gboolean +p2t_triangle_contains_pt_pt (P2tTriangle* THIS, P2tPoint* p, P2tPoint* q) +{ + return p2t_triangle_contains_pt (THIS, p) && p2t_triangle_contains_pt (THIS, q); +} + +gboolean +p2t_triangle_is_interior (P2tTriangle* THIS) +{ + return THIS->interior_; +} + +void +p2t_triangle_is_interior_b (P2tTriangle* THIS, gboolean b) +{ + THIS->interior_ = b; +} diff --git a/common/shapes.h b/common/shapes.h new file mode 100755 index 0000000..6287e9a --- /dev/null +++ b/common/shapes.h @@ -0,0 +1,262 @@ +/* + * This file is a part of Poly2Tri-C - The C port of the Poly2Tri library + * Porting to C done by (c) Barak Itkin + * http://code.google.com/p/poly2tri-c/ + * + * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors + * http://code.google.com/p/poly2tri/ + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without modification, + * are permitted provided that the following conditions are met: + * + * * Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * * Neither the name of Poly2Tri nor the names of its contributors may be + * used to endorse or promote products derived from this software without specific + * prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef __SHAPES_H__ +#define __SHAPES_H__ + +#include +#include +#include +#include "poly2tri-private.h" +#include "cutils.h" + +/** + * P2tPoint: + * @x: The x coordinate of the point + * @y: The y coordinate of the point + * @edge_list: The edges this point constitutes an upper ending point + * + * A struct to represent 2D points with double precision, and to keep track + * of the edges this point constitutes an upper ending point + */ +struct _P2tPoint +{ + /*< public >*/ + P2tEdgePtrArray edge_list; + double x, y; +}; + +/** + * p2t_point_init_dd: + * @THIS: The #P2tPoint to initialize + * @x: The desired x coordinate of the point + * @y: The desired y coordinate of the point + * + * A function to initialize a #P2tPoint struct with the given coordinates. The + * struct must later be finalized by a call to #p2t_point_destroy + */ +void p2t_point_init_dd (P2tPoint* THIS, double x, double y); + +/** + * p2t_point_new_dd: + * @x: The desired x coordinate of the point + * @y: The desired y coordinate of the point + * + * A utility function to alloacte and initialize a #P2tPoint. + * See #p2t_point_init_dd. Note that when finished using the point, it must be + * freed by a call to #p2t_point_free and can not be freed like regular memory. + * + * Returns: The allocated and initialized point + */ +P2tPoint* p2t_point_new_dd (double x, double y); + +/** + * p2t_point_init: + * @THIS: The #P2tPoint to initialize + * + * A function to initialize a #P2tPoint struct to (0,0). The struct must later + * be finalized by a call to #p2t_point_destroy + */ +void p2t_point_init (P2tPoint* THIS); + +/** + * p2t_point_new: + * + * A utility function to alloacte and initialize a #P2tPoint. + * See #p2t_point_init. Note that when finished using the point, it must be + * freed by a call to #p2t_point_free and can not be freed like regular memory. + */ +P2tPoint* p2t_point_new (); + +/** + * p2t_point_destroy: + * @THIS: The #P2tPoint whose resources should be freed + * + * This function will free all the resources allocated by a #P2tPoint, without + * freeing the #P2tPoint pointed by @THIS + */ +void p2t_point_destroy (P2tPoint* THIS); + +/** + * p2t_point_free: + * @THIS: The #P2tPoint to free + * + * This function will free all the resources allocated by a #P2tPoint, and will + * also free the #P2tPoint pointed by @THIS + */ +void p2t_point_free (P2tPoint* THIS); + +/** + * P2tEdge: + * @p: The top right point of the edge + * @q: The bottom left point of the edge + * + * Represents a simple polygon's edge + */ +struct _P2tEdge +{ + P2tPoint *p, *q; +}; + +/** + * p2t_edge_init: + * @THIS: The #P2tEdge to initialize + * @p1: One of the two points that form the edge + * @p2: The other point of the two points that form the edge + * + * A function to initialize a #P2tEdge struct from the given points. The + * struct must later be finalized by a call to #p2t_point_destroy. + * + * Warning: The points must be geometrically not-equal! This means that they + * must differ by at least one of their coordinates. Otherwise, a runtime error + * would be raised! + */ +void p2t_edge_init (P2tEdge* THIS, P2tPoint* p1, P2tPoint* p2); + +/** + * p2t_edge_new: + * + * A utility function to alloacte and initialize a #P2tEdge. + * See #p2t_edge_init. Note that when finished using the point, it must be freed + * by a call to #p2t_point_free and can not be freed like regular memory. + * + * Returns: The allocated and initialized edge + */ +P2tEdge* p2t_edge_new (P2tPoint* p1, P2tPoint* p2); + +/** + * p2t_edge_destroy: + * @THIS: The #P2tEdge whose resources should be freed + * + * This function will free all the resources allocated by a #P2tEdge, without + * freeing the #P2tPoint pointed by @THIS + */ +void p2t_edge_destroy (P2tEdge* THIS); + +/** + * p2t_edge_free: + * @THIS: The #P2tEdge to free + * + * This function will free all the resources allocated by a #P2tEdge, and will + * also free the #P2tEdge pointed by @THIS + */ +void p2t_edge_free (P2tEdge* THIS); + + +/* Triangle-based data structures are know to have better performance than quad-edge structures + * See: J. Shewchuk, "Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator" + * "Triangulations in CGAL" + */ + +/** + * P2tTriangle: + * @constrained_edge: Flags to determine if an edge is a Constrained edge + * @delaunay_edg: Flags to determine if an edge is a Delauney edge + * @points_: Triangle points + * @neighbors_: Neighbor list + * @interior_: Has this triangle been marked as an interior triangle? + * + * A data structure for representing a triangle, while keeping information about + * neighbor triangles, etc. + */ +struct _P2tTriangle +{ + /*< public >*/ + gboolean constrained_edge[3]; + gboolean delaunay_edge[3]; + + /*< private >*/ + P2tPoint * points_[3]; + struct _P2tTriangle * neighbors_[3]; + gboolean interior_; +}; + +P2tTriangle* p2t_triangle_new (P2tPoint* a, P2tPoint* b, P2tPoint* c); +void p2t_triangle_init (P2tTriangle* THIS, P2tPoint* a, P2tPoint* b, P2tPoint* c); +P2tPoint* p2t_triangle_get_point (P2tTriangle* THIS, const int index); +P2tPoint* p2t_triangle_point_cw (P2tTriangle* THIS, P2tPoint* point); +P2tPoint* p2t_triangle_point_ccw (P2tTriangle* THIS, P2tPoint* point); +P2tPoint* p2t_triangle_opposite_point (P2tTriangle* THIS, P2tTriangle* t, P2tPoint* p); + +P2tTriangle* p2t_triangle_get_neighbor (P2tTriangle* THIS, const int index); +void p2t_triangle_mark_neighbor_pt_pt_tr (P2tTriangle* THIS, P2tPoint* p1, P2tPoint* p2, P2tTriangle* t); +void p2t_triangle_mark_neighbor_tr (P2tTriangle* THIS, P2tTriangle *t); + +void p2t_triangle_mark_constrained_edge_i (P2tTriangle* THIS, const int index); +void p2t_triangle_mark_constrained_edge_ed (P2tTriangle* THIS, P2tEdge* edge); +void p2t_triangle_mark_constrained_edge_pt_pt (P2tTriangle* THIS, P2tPoint* p, P2tPoint* q); + +int p2t_triangle_index (P2tTriangle* THIS, const P2tPoint* p); +int p2t_triangle_edge_index (P2tTriangle* THIS, const P2tPoint* p1, const P2tPoint* p2); + +P2tTriangle* p2t_triangle_neighbor_cw (P2tTriangle* THIS, P2tPoint* point); +P2tTriangle* p2t_triangle_neighbor_ccw (P2tTriangle* THIS, P2tPoint* point); +gboolean p2t_triangle_get_constrained_edge_ccw (P2tTriangle* THIS, P2tPoint* p); +gboolean p2t_triangle_get_constrained_edge_cw (P2tTriangle* THIS, P2tPoint* p); +void p2t_triangle_set_constrained_edge_ccw (P2tTriangle* THIS, P2tPoint* p, gboolean ce); +void p2t_triangle_set_constrained_edge_cw (P2tTriangle* THIS, P2tPoint* p, gboolean ce); +gboolean p2t_triangle_get_delunay_edge_ccw (P2tTriangle* THIS, P2tPoint* p); +gboolean p2t_triangle_get_delunay_edge_cw (P2tTriangle* THIS, P2tPoint* p); +void p2t_triangle_set_delunay_edge_ccw (P2tTriangle* THIS, P2tPoint* p, gboolean e); +void p2t_triangle_set_delunay_edge_cw (P2tTriangle* THIS, P2tPoint* p, gboolean e); + +gboolean p2t_triangle_contains_pt (P2tTriangle* THIS, P2tPoint* p); +gboolean p2t_triangle_contains_ed (P2tTriangle* THIS, const P2tEdge* e); +gboolean p2t_triangle_contains_pt_pt (P2tTriangle* THIS, P2tPoint* p, P2tPoint* q); +void p2t_triangle_legalize_pt (P2tTriangle* THIS, P2tPoint* point); +void p2t_triangle_legalize_pt_pt (P2tTriangle* THIS, P2tPoint* opoint, P2tPoint* npoint); +/** + * Clears all references to all other triangles and points + */ +void p2t_triangle_clear (P2tTriangle* THIS); +void p2t_triangle_clear_neighbor_tr (P2tTriangle* THIS, P2tTriangle *triangle); +void p2t_triangle_clear_neighbors (P2tTriangle* THIS); +void p2t_triangle_clear_delunay_edges (P2tTriangle* THIS); + +gboolean p2t_triangle_is_interior (P2tTriangle* THIS); +void p2t_triangle_is_interior_b (P2tTriangle* THIS, gboolean b); + +P2tTriangle* p2t_triangle_neighbor_across (P2tTriangle* THIS, P2tPoint* opoint); + +void p2t_triangle_debug_print (P2tTriangle* THIS); + +gint p2t_point_cmp (gconstpointer a, gconstpointer b); + +// gboolean operator == (const Point& a, const Point& b); +gboolean p2t_point_equals (const P2tPoint* a, const P2tPoint* b); + +#endif + + diff --git a/common/utils.c b/common/utils.c new file mode 100755 index 0000000..24ce71b --- /dev/null +++ b/common/utils.c @@ -0,0 +1,95 @@ + +/* + * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors + * http://code.google.com/p/poly2tri/ + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without modification, + * are permitted provided that the following conditions are met: + * + * * Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * * Neither the name of Poly2Tri nor the names of its contributors may be + * used to endorse or promote products derived from this software without specific + * prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include +#include "utils.h" + +/** + * Forumla to calculate signed area
+ * Positive if CCW
+ * Negative if CW
+ * 0 if collinear
+ * 
+ * A[P1,P2,P3]  =  (x1*y2 - y1*x2) + (x2*y3 - y2*x3) + (x3*y1 - y3*x1)
+ *              =  (x1-x3)*(y2-y3) - (y1-y3)*(x2-x3)
+ *
+ */ +P2tOrientation +p2t_orient2d (P2tPoint* pa, P2tPoint* pb, P2tPoint* pc) +{ + double detleft = (pa->x - pc->x) * (pb->y - pc->y); + double detright = (pa->y - pc->y) * (pb->x - pc->x); + double val = detleft - detright; + if (val > -EPSILON && val < EPSILON) + { + return COLLINEAR; + } + else if (val > 0) + { + return CCW; + } + return CW; +} + +gboolean +p2t_utils_in_scan_area (P2tPoint* pa, P2tPoint* pb, P2tPoint* pc, P2tPoint* pd) +{ + double pdx = pd->x; + double pdy = pd->y; + double adx = pa->x - pdx; + double ady = pa->y - pdy; + double bdx = pb->x - pdx; + double bdy = pb->y - pdy; + + double adxbdy = adx * bdy; + double bdxady = bdx * ady; + double oabd = adxbdy - bdxady; + + if (oabd <= EPSILON) + { + return FALSE; + } + + double cdx = pc->x - pdx; + double cdy = pc->y - pdy; + + double cdxady = cdx * ady; + double adxcdy = adx * cdy; + double ocad = cdxady - adxcdy; + + if (ocad <= EPSILON) + { + return FALSE; + } + + return TRUE; +} diff --git a/common/utils.h b/common/utils.h new file mode 100755 index 0000000..18d42b9 --- /dev/null +++ b/common/utils.h @@ -0,0 +1,63 @@ +/* + * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors + * http://code.google.com/p/poly2tri/ + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without modification, + * are permitted provided that the following conditions are met: + * + * * Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * * Neither the name of Poly2Tri nor the names of its contributors may be + * used to endorse or promote products derived from this software without specific + * prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef UTILS_H +#define UTILS_H + +#include +#include "poly2tri-private.h" +#include "cutils.h" +#include "shapes.h" + +#define PI_3div4 (3 * M_PI / 4) +#define EPSILON (1e-6) + +typedef enum +{ + CW, CCW, COLLINEAR +} P2tOrientation; + +/** + * Forumla to calculate signed area
+ * Positive if CCW
+ * Negative if CW
+ * 0 if collinear
+ * 
+ * A[P1,P2,P3]  =  (x1*y2 - y1*x2) + (x2*y3 - y2*x3) + (x3*y1 - y3*x1)
+ *              =  (x1-x3)*(y2-y3) - (y1-y3)*(x2-x3)
+ *
+ */ +P2tOrientation p2t_orient2d (P2tPoint* pa, P2tPoint* pb, P2tPoint* pc); + +gboolean p2t_utils_in_scan_area (P2tPoint* pa, P2tPoint* pb, P2tPoint* pc, P2tPoint* pd); + +#endif + diff --git a/main.c b/main.c new file mode 100755 index 0000000..e3f6c73 --- /dev/null +++ b/main.c @@ -0,0 +1,260 @@ +/* + * Poly2Tri Copyright (c) 2009-2011, Poly2Tri Contributors + * http://code.google.com/p/poly2tri/ + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without modification, + * are permitted provided that the following conditions are met: + * + * * Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * * Neither the name of Poly2Tri nor the names of its contributors may be + * used to endorse or promote products derived from this software without specific + * prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include +#include +#include + +#include "poly2tri.h" + +#include "refine/triangulation.h" +#include "render/svg-plot.h" +#include "refine/refine.h" + +#include "render/mesh-render.h" + +#include + + +static gint refine_max_steps = 1000; +static gboolean debug_print = TRUE; +static gboolean verbose = TRUE; +static gchar *input_file = NULL; +static gchar *output_file = NULL; + +static GOptionEntry entries[] = +{ + { "refine-max-steps", 'r', 0, G_OPTION_ARG_INT, &refine_max_steps, "Set maximal refinement steps to N", "N" }, + { "verbose", 'v', 0, G_OPTION_ARG_NONE, &verbose, "Print output?", NULL }, + { "debug", 'd', 0, G_OPTION_ARG_NONE, &debug_print, "Enable debug printing", NULL }, + { "input", 'i', 0, G_OPTION_ARG_FILENAME, &input_file, "Use input file at FILE_IN", "FILE_IN" }, + { "output", 'o', 0, G_OPTION_ARG_FILENAME, &output_file, "Use output file at FILE_OUT", "FILE_OUT" }, + { NULL } +}; + +typedef gfloat Color3f[3]; +typedef gfloat Point2f[2]; + +/** + * read_points_file: + * @path: The path to the points & colors file + * @points: An pointer to an array of pointers to #P2RrPoint will be returned + * here. NULL can be passed. + * @colors: An pointer to an array of colors will be returned here. NULL can be + * passed. + * + * + */ +void +read_points_file (const gchar *path, + GPtrArray **points, + GArray **colors) +{ + FILE *f = fopen (path, "r"); + gint countPts = 0, countCls = 0; + + if (f == NULL) + { + g_print ("Error! Could not read input file!"); + exit (1); + } + + if (verbose) + g_print ("Now parsing \"%s\"\n", path); + + if (points != NULL) *points = g_ptr_array_new (); + if (colors != NULL) *colors = g_array_new (FALSE, FALSE, sizeof (Color3f)); + + if (debug_print && points == NULL) g_print ("Points will not be kept\n"); + if (debug_print && colors == NULL) g_print ("Colors will not be kept\n"); + + while (! feof (f)) + { + Color3f col = { 0, 0, 0 }; + Point2f ptc = { 0, 0 }; + gboolean foundCol = FALSE, foundPt = FALSE; + + /* Read only while we have valid points */ + gint readSize = fscanf (f, "@ %f %f ", &ptc[0], &ptc[1]); + + if (readSize > 0) + { + if (readSize != 2) + { + g_error ("Error! %d is an unexpected number of floats after point '@' declaration!\n", readSize); + exit (1); + } + + foundPt = TRUE; + + if (points != NULL) + { + g_ptr_array_add (*points, p2tr_point_new (ptc[0], ptc[1])); + countPts++; + } + } + + readSize = fscanf (f, "# %f %f %f ", &col[0], &col[1], &col[2]); + + if (readSize > 0) + { + if (readSize != 1 && readSize != 3) + { + g_error ("Error! %d is an unexpected number of floats after color '#' declaration!\n", readSize); + exit (1); + } + + foundCol = TRUE; + + /* Did we read Gray color information? */ + if (readSize == 1) + col[1] = col[2] = col[0]; + + if (colors != NULL) + { + g_array_append_val (*colors, ptc); + countCls++; + } + } + + if (!foundCol && !foundPt) + break; + } + + fclose (f); + + if (verbose) + g_print ("Read %d points and %d colors\n", countPts, countCls); +} + +/* In order to find the maximal length of a filename path, most + * platforms have either the macro MAX_PATH, or PATH_MAX. This is a + * guess which tries them both */ + +#ifdef MAX_PATH +#define P2TC_MAX_PATH MAX_PATH +#else +#define P2TC_MAX_PATH PATH_MAX +#endif + +gint main (int argc, char *argv[]) +{ + FILE *out; + GError *error = NULL; + GOptionContext *context; + + GPtrArray *pts; + GArray *colors; + + P2tRTriangulation *T; + + gint i; + gchar buf[P2TC_MAX_PATH+1]; + gfloat *im; + + context = g_option_context_new ("- Create a fine mesh from a given PSLG"); + g_option_context_add_main_entries (context, entries, NULL); + +// g_option_context_add_group (context, gtk_get_option_group (TRUE)); + + if (!g_option_context_parse (context, &argc, &argv, &error)) + { + g_print ("option parsing failed: %s\n", error->message); + exit (1); + } + + if (input_file == NULL) + { + g_print ("No input file given. Stop."); + exit (1); + } + + if (! g_file_test (input_file, G_FILE_TEST_EXISTS)) + { + g_print ("Input file does not exist. Stop."); + exit (1); + } + + if (output_file == NULL) + { + g_print ("No output file given. Stop."); + exit (1); + } + + if ((out = fopen (output_file, "w")) == NULL) + { + g_print ("Can't open the output file. Stop."); + exit (1); + } + + read_points_file (input_file, &pts, &colors); + + T = p2tr_triangulate_and_refine (pts, refine_max_steps); + + p2tr_plot_svg (T,out); + + fclose (out); + + sprintf (buf, "%s.ppm", output_file); + + if ((out = fopen (buf, "w")) == NULL) + { + g_print ("Can't open the output ppm file. Stop."); + exit (1); + } + + P2tRImageConfig imc; + + imc.cpp = 4; + imc.min_x = imc.min_y = 0; + imc.step_x = imc.step_y = 0.2; + imc.x_samples = imc.y_samples = 500; + + im = g_new (gfloat, imc.cpp * imc.x_samples * imc.y_samples); + + p2tr_mesh_render_scanline (T, im, &imc, p2tr_test_point_to_color, NULL); + + p2tr_write_ppm (out, im, &imc); + fclose (out); + + g_free (im); + + p2tr_triangulation_free (T); + + for (i = 0; i < pts->len; i++) + { + p2tr_point_unref ((P2tRPoint*) g_ptr_array_index (pts, i)); + } + + g_ptr_array_free (pts, TRUE); + g_array_free (colors, TRUE); + +} diff --git a/poly2tri.h b/poly2tri.h new file mode 100755 index 0000000..487755e --- /dev/null +++ b/poly2tri.h @@ -0,0 +1,39 @@ +/* + * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors + * http://code.google.com/p/poly2tri/ + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without modification, + * are permitted provided that the following conditions are met: + * + * * Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * * Neither the name of Poly2Tri nor the names of its contributors may be + * used to endorse or promote products derived from this software without specific + * prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef POLY2TRI_H +#define POLY2TRI_H + +#include "common/shapes.h" +#include "sweep/cdt.h" + +#endif + diff --git a/refine/refine.c b/refine/refine.c new file mode 100755 index 0000000..df99d6a --- /dev/null +++ b/refine/refine.c @@ -0,0 +1,706 @@ +#include + +#include "triangulation.h" + +/* Place holder function. In the future, this should be replaced by some search + * tree, such as a quad tree. + */ +P2tRTriangle * +p2tr_triangulation_locate_point (P2tRTriangulation *T, P2tRPoint *X) +{ + P2trHashSetIter iter; + P2tRTriangle *result; + + p2tr_hash_set_iter_init (&iter, T->tris); + + while (p2tr_hash_set_iter_next(&iter, (gpointer*)&result)) + { + if (p2tr_triangle_contains_pt (result, X)) + return result; + } + + return NULL; +} + +gboolean +p2tr_points_are_same (P2tRPoint *pt1, P2tRPoint *pt2) +{ + return p2tr_math_edge_len_sq (pt1->x, pt1->y, pt2->x, pt2->y) < EPSILON2; +} + +/* As the algorithm paper states, an edge can only be encroached by the + * point opposite to it in one of the triangles it's a part of. + * We can deduce from that that a point may only encroach upon edges that form + * the triangle in/on which it is located. + * which are opposite to it in some triangle, and that it may encroach free + * points (points which are not a part of any triangles) + * We can find the list of triangles in which a point it a part, by iterating + * over the .tri property of the out going edges. + * NOTE: If there is a triangle formed by edges, but without a real triangle + * there, then we are dealing with the edges of the domain which have to + * be constrained! Therefore, we can ignore these edges and not return them + */ +P2tRHashSet * +p2tr_triangulation_get_encroaches_upon (P2tRPoint *pt, P2tRTriangulation *T) +{ + GList *iter; + P2tRTriangle *Tri = p2tr_triangulation_locate_point (T, pt); + P2tRPoint *p; + P2tRHashSet *E = p2tr_hash_set_set_new (g_direct_hash, g_direct_equal, NULL); + gint i; + + if (Tri == NULL) + return E; + + for (i = 0; i < 3; i++) + { + /* If the point is the same as any of the points of the triangle, then it + * is inside the diametral circle of all the edges that connect to that + * point. In that case, add all the edges of the point to the list of + * encroahced edges. + * TODO: check if you can break after finding one in this case + */ + if (p2tr_points_are_same (pt, p = p2tr_edge_get_end (Tri->edges[i]))) + foreach (iter, p->edges) + p2tr_hash_set_insert (E, (P2tREdge*) iter->data); + + /* Now, check if any of the edges contains the point inside it's diametral + * circle */ + if (p2tr_edge_diametral_circle_contains (Tri->edges[i], pt)) + p2tr_hash_set_insert (E, Tri->edges[i]); + + /* TODO: add a check for the case where the point is actually on one of the + * edges */ + } + + return E; +} + + +/** + * Split an edge at a given point. If the point is at the same location as one + * of the sides, the edge will not be split in order to avoid zero lengthed edges. + * + * @param e the edge to split + * @param pt the point to add + * @param T the triangulation to maintain + * @param patchHoles Whethe the holes created by removing the original edge + * should be patched + * @param dest An array where the results of the split are to be stored. The + * array should be of size 2, and it will contain one edge if no split + * occured or two edges if a split did in fact occur. + * + * @return The amount of edges resulting from the split - 1 if no split, 2 if a + * split occured + */ +gint +p2tr_split_edge (P2tREdge *e, + P2tRPoint *pt, + P2tRTriangulation *T, + gboolean patchHoles, + P2tREdge *dest[2], + gboolean flipFix) +{ + /* A + * / \ + * / | \ + * / \ + * / | \ + * / \ + * S---- pt----E ===> This is edge e, and pt is the point we insert + * \ | / + * \ / + * \ | / + * \ / + * \ | / + * \ / + * B + * + * Each of these edges may need flip fixing! + */ + P2tRPoint *S = p2tr_edge_get_start (e); + P2tRPoint *E = p2tr_edge_get_end (e); + P2tRPoint *A = NULL, *B = NULL; + + P2tRTriangle *SptA = NULL, *ptEA = NULL, *SptB = NULL, *ptEB = NULL; + + gboolean constrained = e->constrained; + /* TODO: T remove me */ + p2tr_validate_edge (e); + + P2tREdge *Spt, *ptE; + + p2tr_debug ("Checking if can split\n"); + + if (p2tr_points_are_same (pt, S) || p2tr_points_are_same (pt, E)) + { + dest[0] = e; + dest[1] = NULL; + return 1; + } + + p2tr_debug ("Splitting!\nAdding (%f,%f) between (%f,%f) and (%f,%f)\n", pt->x,pt->y,S->x,S->y,E->x,E->y); + + if (patchHoles) + { + if (e->tri != NULL) + A = p2tr_triangle_opposite_point (e->tri, e); + + if (e->mirror->tri != NULL) + B = p2tr_triangle_opposite_point (e->mirror->tri, e); + } + + p2tr_edge_remove (e, T); + + Spt = p2tr_edge_new (S, pt); + ptE = p2tr_edge_new (pt,E); + + p2tr_edge_set_constrained (Spt, constrained); + p2tr_edge_set_constrained (ptE, constrained); + + if (patchHoles) + { + if (A != NULL) + { + P2tREdge *ptA = p2tr_point_edge_to (pt, A); + P2tRTriangle *SptA = p2tr_triangle_new (Spt, ptA, p2tr_point_edge_to (A, S), T); + P2tRTriangle *ptEA = p2tr_triangle_new (ptE, p2tr_point_edge_to (E, A), ptA->mirror,T); + } + + if (B != NULL) + { + P2tREdge* ptB = p2tr_point_edge_to (pt, B); + P2tRTriangle *SptB = p2tr_triangle_new (Spt, ptB, p2tr_point_edge_to (B, S), T); + P2tRTriangle *ptEB = p2tr_triangle_new (ptE, p2tr_point_edge_to (E, B), ptB->mirror,T); + } + } + + if (flipFix) + { + P2tREdge *temp; + + /* We do not want the edges resulting from the split to be flipped! */ + p2tr_edge_set_delaunay (Spt, TRUE); + p2tr_edge_set_delaunay (ptE, TRUE); + + if (A != NULL) + { + p2tr_triangulation_legalize (T, SptA); + p2tr_triangulation_legalize (T, ptEA); + } + if (B != NULL) + { + p2tr_triangulation_legalize (T, SptB); + p2tr_triangulation_legalize (T, ptEB); + } + + p2tr_edge_set_delaunay (Spt, FALSE); + p2tr_edge_set_delaunay (ptE, FALSE); + } + + // Error - if the triangles were remove, unreffing them would cause problems + // So for now, I'm commenting these out + // TODO: FIXME! +// p2tr_triangle_unref (SptA); +// p2tr_triangle_unref (ptEA); + +// p2tr_triangle_unref (SptB); +// p2tr_triangle_unref (ptEB); + + if (dest != NULL) + { + /* We shouldn't decrese the reference to Spt and ptE, since it's 1 + * right now, and we pass the reference to them back to the caller through + * dest */ + dest[0] = Spt; + dest[1] = ptE; + } + else + { + p2tr_edge_unref (Spt); + p2tr_edge_unref (ptE); + } + return 2; +} + +/** + * Insert a point into a triangulation. If it's outside of the triangulation or + * if it merges with an existing point it will not be inserted. If it's on an + * existing edge, the edge will be split and then there will be a flipfix to + * make the triangulation CDT again. If it's inside a triangle, the triangle + * will be subdivided and flipfixing will be applied to maintain the CDT + * property. + * + * @param pt the point to insert + * @param T the triangulation to insert into + * + * @return TRUE if the point was inserted, FALSE otherwise + */ +gboolean +p2tr_triangulation_insert_pt (P2tRPoint *pt, P2tRTriangulation *T) +{ + p2tr_debug ("@insertPt\n"); + P2tRTriangle *Tri = p2tr_triangulation_locate_point (T, pt); + + gint i; + P2tREdge *temp; + + p2tr_validate_triangulation (T); + if (Tri == NULL) + { + p2tr_debug ("Warning - tried to insert point outside of domain\n"); + return FALSE; + } + + P2tREdge *ab = Tri->edges[0]; + P2tREdge *bc = Tri->edges[1]; + P2tREdge *ca = Tri->edges[2]; + + P2tRPoint *a = p2tr_edge_get_end (ca); + P2tRPoint *b = p2tr_edge_get_end (ab); + P2tRPoint *c = p2tr_edge_get_end (bc); + + if (p2tr_points_are_same (pt, a) + || p2tr_points_are_same (pt, b) + || p2tr_points_are_same (pt, c)) + { + p2tr_debug ("Not inserting point on existing point!\n"); + return FALSE; + } + + p2tr_validate_triangulation (T); + /* Check if the point is on any of the edges */ + for (i = 0; i < 3; i++) + { + P2tRPoint *S = p2tr_edge_get_start (Tri->edges[i]); + P2tRPoint *E = p2tr_edge_get_end (Tri->edges[i]); + + /* Is the point on the edge? */ + if (p2tr_math_orient2d (pt,S,E) == COLLINEAR) + { + gint j; + gint splitCount; + P2tREdge *splits[2]; + + /* If so, flip the edge */ + p2tr_validate_triangulation (T); + splitCount = p2tr_split_edge (Tri->edges[i], pt, T, TRUE, splits, TRUE); + p2tr_validate_triangulation (T); + /* Then, flipfix each of the resulting edges */ + for (j = 0; j < splitCount; j++) + { + p2tr_triangulation_flip_fix (splits[j], T); + /* We don't use the edge after this point, so unref */ + p2tr_edge_unref (splits[j]); + } + + /* If the point is on one edge then it's not on any other edge (unless + * it is in fact one of the triangle vertices but we already fixed + * that case earlier). So by splitting the edge and flipfixing the + * result, we are in fact done. */ + return TRUE; + } + } + + /* If reached here, then the point was not on any of the edges. So just + * insert it into the triangle */ + + p2tr_validate_triangulation (T); + p2tr_triangle_subdivide (Tri, pt, T, NULL); + p2tr_validate_triangulation (T); + + /* IMPORTANT: YOU CAN NOT FLIP AB/BC/CA BECAUSE THEY MAY NOT EXIST! + * Even if there is an edge from a to b for example, it may not be ab we got + * earlier! It can be there as a result of different flip fixing which + * deleted and then created it! So, take the edge returned from has_edge_to + * (which is the updated one) and flip-fix if it exists. + */ + if ((temp = p2tr_point_has_edge_to (a,b)) != NULL) + p2tr_triangulation_flip_fix (temp, T); + p2tr_validate_triangulation (T); + + if ((temp = p2tr_point_has_edge_to (b,c)) != NULL) + p2tr_triangulation_flip_fix (temp, T); + p2tr_validate_triangulation (T); + + if ((temp = p2tr_point_has_edge_to (c,a)) != NULL) + p2tr_triangulation_flip_fix (temp, T); + p2tr_validate_triangulation (T); + + return TRUE; +} + +typedef gboolean (*deltafunc) (P2tRTriangle *); + + +/* + * This function returns negative if triangle a is uglier than b, 0 if same, and + * 1 if b is uglier + */ +gint +ugliness_comparision (gconstpointer a, + gconstpointer b, + gpointer ignored) +{ + if (a == b) + return 0; // Fast path exit + + gdouble shortestA = p2tr_triangle_shortest_edge_len ((P2tRTriangle*)a); + gdouble shortestB = p2tr_triangle_shortest_edge_len ((P2tRTriangle*)b); + + gdouble longestA = p2tr_triangle_longest_edge_len ((P2tRTriangle*)a); + gdouble longestB = p2tr_triangle_longest_edge_len ((P2tRTriangle*)b); + + gdouble smallestA = p2tr_triangle_smallest_non_seperating_angle ((P2tRTriangle*)a); + gdouble smallestB = p2tr_triangle_smallest_non_seperating_angle ((P2tRTriangle*)b); + +// Bad +// return (gint) ((smallestA - smallestB) / M_PI) ;//+ (longestA - longestB) / MAX (longestA, longestB); + +// Seems Good + return (gint) (1 - longestA/longestB + ((smallestA - smallestB) / M_PI)); + +// Not sure? +// return (gint) (longestB/shortestB - longestA/shortestA); + +// Trivial, reasonable +// return (gint) (smallestA - smallestB); +} + + +void +NewVertex (P2tRPoint *v, gdouble theta, deltafunc delta, + GQueue *Qs, GSequence *Qt) +{ + GList *iter; + + p2tr_debug ("NewVertex: After inserting "); + p2tr_debug_point (v, TRUE); + + foreach (iter, v->edges) + { + P2tREdge *ed = (P2tREdge*) iter->data; + P2tRTriangle *t = ed->tri; + + if (t != NULL) + { + p2tr_debug ("NewVertex: Checking tri "); + p2tr_debug_tri (t, TRUE); + + P2tREdge *e = p2tr_triangle_opposite_edge (t, v); + if (e->mirror->tri == NULL && p2tr_edge_is_encroached_by (e, v)) + g_queue_push_tail (Qs, e); + else if (delta (t) || p2tr_triangle_smallest_non_seperating_angle (t) < theta) + g_sequence_insert_sorted (Qt, t, ugliness_comparision, NULL); + } + } +} + +void +SplitEncroachedSubsegments (gdouble theta, + deltafunc delta, + P2tRTriangulation *T, + GQueue *Qs, + GSequence *Qt) +{ + while (! g_queue_is_empty (Qs)) + { + p2tr_debug ("Handling edge\n"); + P2tREdge *s = g_queue_pop_head (Qs); + gboolean isin = FALSE; + + P2trHashSetIter iter; + P2tRTriangle *t; + p2tr_hash_set_iter_init (&iter, T->tris); + + while (p2tr_hash_set_iter_next (&iter, (gpointer*)&t)) + { + if (t->edges[0] == s || t->edges[1] == s || t->edges[2] == s) + { + isin = TRUE; + break; + } + } + + if (isin) + { + if (p2tr_edge_len_sq (s) >= 1) + { + P2tRPoint *v = p2tr_edge_concentric_center (s); + P2tREdge *splits[2]; + gint splitCount = p2tr_split_edge (s, v, T, TRUE, splits, TRUE), i; + + for (i = 0; i < splitCount; i++) + { + p2tr_triangulation_flip_fix (splits[i], T); + } + + NewVertex (v, theta, delta, Qs, Qt); + for (i = 0; i < splitCount; i++) + { + if (p2tr_edge_is_encroached (splits[i])) + g_queue_push_tail (Qs, splits[i]); + } + } + } + } +} + + +gboolean +p2tr_false_delta (P2tRTriangle *t) +{ + return FALSE; +} + +const gdouble POW2_EPS = 0; +const gdouble LENGTHSQ_EPS = 0; + +gboolean +SplitPermitted (P2tREdge *s, gdouble d) +{ + p2tr_debug ("@SplitPermitted\n"); + if (! (p2tr_point_is_in_cluster (p2tr_edge_get_start(s), s) ^ p2tr_point_is_in_cluster (p2tr_edge_get_end(s), s->mirror))) + { + p2tr_debug ("Criteria 1\n"); + return TRUE; + } + gdouble l = p2tr_edge_len_sq (s); + gdouble temp = log2 (l) / 2; + if (ABS (round (temp) - temp) < POW2_EPS) + { + p2tr_debug ("Criteria 2\n"); + return TRUE; + } + + gdouble phi_min; + GList *S = p2tr_point_get_cluster (p2tr_edge_get_start (s), s, &phi_min); + GList *s1; + + foreach(s1, S) + { + if (p2tr_edge_len_sq ((P2tREdge*)s1->data) < 1 * (1 + LENGTHSQ_EPS)) + { + p2tr_debug ("Criteria 3\n"); + return TRUE; + } + } + + gdouble r_min = sqrt(l) * sin (phi_min / 2); + + if (r_min >= d) + { + p2tr_debug ("Criteria 4\n"); + return TRUE; + } + + p2tr_debug ("Split not permitted\n"); + return FALSE; +} + +#define MIN_MAX_EDGE_LEN 0 + +void +DelaunayTerminator (P2tRTriangulation *T, + GList *XEs, + gdouble theta, + deltafunc delta, + int max_refine_steps) +{ + const gint STEPS = max_refine_steps; + GSequence *Qt; + GQueue Qs; + + GList *Liter, Liter2; + P2trHashSetIter Hiter; + + p2tr_debug("Max refine point count is %d\n", max_refine_steps); + + p2tr_validate_triangulation (T); + + P2tRTriangle *t; + + g_queue_init (&Qs); + Qt = g_sequence_new (NULL); + + if (STEPS == 0) + return; + + foreach (Liter, XEs) + { + P2tREdge *s = (P2tREdge*) (Liter->data); + if (p2tr_edge_is_encroached (s)) + { + g_queue_push_tail (&Qs, s); + } + } + + SplitEncroachedSubsegments(0, p2tr_false_delta,T,&Qs,Qt); + + p2tr_validate_triangulation (T); + + p2tr_hash_set_iter_init (&Hiter, T->tris); + while (p2tr_hash_set_iter_next (&Hiter, (gpointer*)&t)) + if (delta (t) || p2tr_triangle_smallest_non_seperating_angle (t) < theta) + g_sequence_insert_sorted (Qt, t, ugliness_comparision, NULL); + + gint STOP = STEPS - 1; /* The above split was a step */ + + while (g_sequence_get_length (Qt) > 0 && STOP > 0) + { + p2tr_validate_triangulation (T); + p2tr_debug ("Restarting main loop\n"); + STOP--; + + do + { + GSequenceIter *siter = g_sequence_get_begin_iter (Qt); + t = g_sequence_get (siter); + g_sequence_remove (siter); + if (g_sequence_get_length (Qt) == 0) break; + } + while (! p2tr_hash_set_contains (T->tris, t)); + if (g_sequence_get_length (Qt) == 0) break; + + if (p2tr_triangle_longest_edge_len (t) < MIN_MAX_EDGE_LEN) + { + continue; + } + + /* Possibly make more efficient by adding an "erased" field */ + if (p2tr_hash_set_contains (T->tris, t)) + { + P2tRCircle cc; + P2tRPoint *c; + P2tRHashSet *E; + + p2tr_debug ("Found a triangle that still needs fixing\n"); + + p2tr_triangle_circumcircle (t, &cc); + c = p2tr_point_new (cc.x,cc.y); + + E = p2tr_triangulation_get_encroaches_upon (c, T); + p2tr_validate_triangulation (T); + + if (g_hash_table_size (E) == 0) + { + p2tr_debug ("It's circumcircle encraoches upon nothing!\n"); + /* Check if the point is in the domain and inserted OK */ + if (p2tr_triangulation_insert_pt (c, T)) + { + p2tr_validate_triangulation (T); + NewVertex (c,theta,delta,&Qs,Qt); + p2tr_validate_triangulation (T); + } + else + { + int k; + /* In the other cases, split the edge crossing the + * line to the point + */ + g_assert (! p2tr_triangle_contains_pt (t, c)); + P2tRPoint *M = p2tr_triangle_median_pt (t); + P2tREdge *MC = p2tr_point_edge_to (M, c); + p2tr_validate_triangulation (T); + for (k = 0; k < 3; k++) + { + P2tREdge *e = t->edges[k]; + if (p2tr_edges_intersect (e, MC)) + { + P2tREdge *splits[2]; + P2tRPoint *splitPoint = p2tr_edge_concentric_center (e); + gint count = p2tr_split_edge (e, splitPoint, T, TRUE, splits, TRUE); + p2tr_validate_triangulation (T); + gint j; + + for (j = 0; j < count; j++) + { + p2tr_triangulation_flip_fix (splits[j], T); + p2tr_validate_triangulation (T); + } + + p2tr_point_unref (splitPoint); + break; + } + } + } + } + else + { + P2tREdge *s; + p2tr_debug ("It's circumcircle encraoches %d edges\n", g_hash_table_size (E)); + gdouble d = p2tr_triangle_shortest_edge_len (t); + + p2tr_hash_set_iter_init (&Hiter, E); + while (p2tr_hash_set_iter_next (&Hiter, (gpointer*)&s)) + { + if (delta (t) || SplitPermitted(s,d)) + { + p2tr_debug ("Appending an edge for splitting\n"); + g_queue_push_tail (&Qs, s); + } + } + if (! g_queue_is_empty (&Qs)) + { + g_sequence_insert_sorted (Qt, t, ugliness_comparision, NULL); + p2tr_debug ("Will now try splitting\n"); + SplitEncroachedSubsegments(theta,delta,T,&Qs,Qt); + } + } + + p2tr_point_unref (c); + } + + // Why not to legalize here: + // 1. Because it should have no effect if we did maintain the CDT + // 2. Because if it does have an effect, since legalizations checks only + // vialoations with adjacent neighbours, it may simply violate the CDT + // property with remote ones! + + // Flip fixing actually adds more triangles that may have to be fixed. + // Untill we do it preoperly, add them here: + /* + P2trHashSetIter triter; + P2tRTriangle *trit; + + p2tr_hash_set_iter_init (&triter,T->tris); + while (p2tr_hash_set_iter_next (&triter, (gpointer*)&trit)) + { + if (p2tr_triangle_smallest_non_seperating_angle (trit) < theta) + g_sequence_insert_sorted (Qt, t, ugliness_comparision, NULL); + } + */ + } +} + +/* + * Input must be a GPtrArray of P2tRPoint* + */ +P2tRTriangulation* +p2tr_triangulate_and_refine (GPtrArray *pts, int max_refine_steps) +{ + gint i, N = pts->len; + GList *XEs = NULL, *iter; + P2tRTriangulation *T; + + for (i = 0; i < pts->len; i++) + { + P2tREdge *E = p2tr_point_edge_to ((P2tRPoint*)g_ptr_array_index_cyclic (pts, i), + (P2tRPoint*)g_ptr_array_index_cyclic (pts, i+1)); + p2tr_edge_set_constrained (E, TRUE); + XEs = g_list_prepend (XEs, E); + } + + T = p2tr_triangulateA ((P2tRPoint**)pts->pdata ,pts->len); + DelaunayTerminator (T,XEs,M_PI/6,p2tr_false_delta, max_refine_steps); + + foreach (iter, XEs) + { + P2tREdge *E = (P2tREdge*) iter->data; + p2tr_edge_unref (E); + } + + g_list_free (XEs); + + return T; +} diff --git a/refine/refine.h b/refine/refine.h new file mode 100755 index 0000000..8c95493 --- /dev/null +++ b/refine/refine.h @@ -0,0 +1,29 @@ +/* + * File: refine.h + * Author: Barak + * + * Created on 29 יולי 2011, 04:52 + */ + +#ifndef REFINE_H +#define REFINE_H + +#include +#include "triangulation.h" + +#ifdef __cplusplus +extern "C" +{ +#endif + +P2tRTriangulation* +p2tr_triangulate_and_refine (GPtrArray *pts, int max_refine_steps); + + + +#ifdef __cplusplus +} +#endif + +#endif /* REFINE_H */ + diff --git a/refine/triangulation.c b/refine/triangulation.c new file mode 100755 index 0000000..73e78e5 --- /dev/null +++ b/refine/triangulation.c @@ -0,0 +1,1494 @@ +#include + +#include "../common/utils.h" +#include "triangulation.h" +#include "../poly2tri.h" + +static void p2tr_edge_init (P2tREdge *self, P2tRPoint *start, P2tRPoint *end); + +static void p2tr_edge_init_private (P2tREdge *self, P2tRPoint *start, P2tRPoint *end, gboolean mirror); + +static void p2tr_edge_remove_private (P2tREdge *self, P2tRTriangulation *T); + +static void p2tr_point_init (P2tRPoint *self, gdouble x, gdouble y); + +static void p2tr_point_add_edge (P2tRPoint *self, P2tREdge *edge); + + +/* ########################################################################## */ +/* Common math */ +/* ########################################################################## */ +gdouble +p2tr_math_normalize_angle (gdouble angle) +{ + while (angle < -M_PI) + angle += 2 * M_PI_2; + while (angle > M_PI) + angle -= 2 * M_PI; + return angle; +} + +/* NOTE: exact copy of p2t_orient2d, with different EPSILON2 + * TODO: merge somehow + */ +P2tROrientation +p2tr_math_orient2d (P2tRPoint* pa, + P2tRPoint* pb, + P2tRPoint* pc) +{ + double detleft = (pa->x - pc->x) * (pb->y - pc->y); + double detright = (pa->y - pc->y) * (pb->x - pc->x); + double val = detleft - detright; +// p2tr_debug ("orient2d val is %f\n",val); + if (val > -EPSILON2 && val < EPSILON2) + { +// p2tr_debug ("COLLINEAR!\n"); + return COLLINEAR; + } + else if (val > 0) + { +// p2tr_debug ("CCW!\n"); + return CCW; + } +// p2tr_debug ("CW!\n"); + return CW; +} + +/* TODO: check relation with p2t_utils_in_scan_area */ +/* This function is based on an article by Jonathan Richard Shewchuk + * "Robust Adaptive Floating-Point Geometric Predicates" + * + * | ax-dx ay-dy (ax-dx)^2+(ay-dy)^2 | + * | bx-dx by-dy (bx-dx)^2+(by-dy)^2 | + * | cx-dx cy-dy (cx-dx)^2+(cy-dy)^2 | + * + * A, B AND C MUST BE IN CCW ORDER! + */ +P2tRInCircle +p2tr_math_incircle (P2tRPoint* a, + P2tRPoint* b, + P2tRPoint* c, + P2tRPoint* d) +{ + gdouble ad_dx = a->x - d->x; + gdouble ad_dy = a->y - d->y; + gdouble ad_dsq = ad_dx * ad_dx + ad_dy * ad_dy; + + gdouble bd_dx = b->x - d->x; + gdouble bd_dy = b->y - d->y; + gdouble bd_dsq = bd_dx * bd_dx + bd_dy * bd_dy; + + gdouble cd_dx = c->x - d->x; + gdouble cd_dy = c->y - d->y; + gdouble cd_dsq = cd_dx * cd_dx + cd_dy * cd_dy; + + gdouble calc = + ad_dx * (bd_dy * cd_dsq - cd_dy * bd_dsq) + - ad_dy * (bd_dx * cd_dsq - cd_dx * bd_dsq) + + ad_dsq * (bd_dx * cd_dy - cd_dx * bd_dy); + + if (calc > EPSILON2) + return INCIRCLE_INSIDE; + else if (calc < EPSILON2) + return INCIRCLE_OUTSIDE; + else + return INCIRCLE_ON; +} + +gdouble +p2tr_math_edge_len_sq (gdouble x1, gdouble y1, gdouble x2, gdouble y2) +{ + gdouble dx = x2 - x1; + gdouble dy = y2 - y1; + return dx * dx + dy * dy; +} + +/* ########################################################################## */ +/* Triangulation struct */ +/* ########################################################################## */ + +void +p2tr_triangulation_remove_pt (P2tRTriangulation *self, P2tRPoint *pt) +{ + if (p2tr_hash_set_remove (self->pts, pt)) + p2tr_point_unref (pt); +} + +void +p2tr_triangulation_remove_ed (P2tRTriangulation *self, P2tREdge *ed) +{ + if (p2tr_hash_set_remove (self->edges, ed)) + p2tr_edge_unref (ed); +} + +void +p2tr_triangulation_remove_tr (P2tRTriangulation *self, P2tRTriangle *tr) +{ + if (p2tr_hash_set_remove (self->tris, tr)) + p2tr_triangle_unref (tr); +} + +void +p2tr_triangulation_add_pt (P2tRTriangulation *self, P2tRPoint *pt) +{ + if (p2tr_hash_set_contains (self->pts, pt)) + return; + + p2tr_hash_set_insert (self->pts, pt); + p2tr_point_ref (pt); +} +void +p2tr_triangulation_add_ed (P2tRTriangulation *self, P2tREdge *ed) +{ + if (p2tr_hash_set_contains (self->edges, ed)) + return; + + p2tr_hash_set_insert (self->edges, ed); + p2tr_edge_ref (ed); +} +void +p2tr_triangulation_add_tr (P2tRTriangulation *self, P2tRTriangle *tr) +{ + if (p2tr_hash_set_contains (self->tris, tr)) + return; + + p2tr_hash_set_insert (self->tris, tr); + p2tr_triangle_ref (tr); +} + +void +p2tr_triangulation_get_points (P2tRTriangulation *self, GPtrArray *dest) +{ + P2trHashSetIter iter; + P2tRTriangle *tr; + P2tRHashSet *pts = p2tr_hash_set_set_new (g_direct_hash, g_direct_equal, NULL); + gint i; + + p2tr_hash_set_iter_init (&iter, self->tris); + while (p2tr_hash_set_iter_next (&iter, (gpointer*)&tr)) + { + for (i = 0; i < 3; i++) + { + P2tRPoint *pt = p2tr_edge_get_end (tr->edges[i]); + if (! p2tr_hash_set_contains (pts, pt)) + { + p2tr_point_ref (pt); + g_ptr_array_add (dest, pt); + p2tr_hash_set_insert (pts, pt); + } + } + } + + g_hash_table_destroy (pts); +} +/* ########################################################################## */ +/* Point struct */ +/* ########################################################################## */ + +static void +p2tr_point_init (P2tRPoint *self, + gdouble x, + gdouble y) +{ + self->x = x; + self->y = y; + self->edges = NULL; + self->_refcount = 1; +} + +P2tRPoint* +p2tr_point_new (gdouble x, + gdouble y) +{ + P2tRPoint *self = g_slice_new (P2tRPoint); + p2tr_point_init (self, x, y); + return self; +} + +static void +p2tr_point_destroy (P2tRPoint *self) +{ + GList *iter; + + g_assert (self->_refcount == 0); + + foreach (iter, self->edges) + { + P2tREdge *e = (P2tREdge*) iter->data; + p2tr_edge_unref (e); + } + + g_list_free (self->edges); +} + +void +p2tr_point_free (P2tRPoint *self) +{ + p2tr_point_destroy (self); + g_slice_free (P2tRPoint, self); +} +/* DBG: Differs from original + * + * THIS FUNCTION SHOULD NOT BE USED DIRECTLY! IT IS JUST A CONVINIENCE FUNCTION + * USED BY THE CONSTRUCTOR OF THE EDGE OBJECT TO ACTUALLY REFERENCE THE EDGE + * FROM THE POINT! + */ +static void +p2tr_point_add_edge (P2tRPoint *self, + P2tREdge *edge) +{ + GList *iter = self->edges; + for (iter = self->edges; iter != NULL; iter = iter->next) + { + if (!(P2TR_EDGE(iter->data)->angle < edge->angle)) + break; + } + + /* Inserting before NULL will insert at the end of the list */ + self->edges = g_list_insert_before (self->edges, iter, edge); + + /* We now hold a reference to the edge! */ + p2tr_edge_ref (edge); +} + +void +p2tr_point_remove_edge (P2tRPoint *self, + P2tREdge *edge) +{ + p2tr_assert_and_explain (g_list_find (self->edges, edge) != NULL, "can't remove non existing edge"); + self->edges = g_list_remove (self->edges, edge); + p2tr_edge_unref (edge); +} + +void +p2tr_point_remove (P2tRPoint *self, + P2tRTriangulation *T) +{ + GList *iter = self->edges; + for (iter = self->edges; iter != NULL; iter = iter->next) + { + p2tr_edge_remove (P2TR_EDGE(iter->data), T); + } + p2tr_triangulation_remove_pt (T, self); +} + +/* This function will return an edge from the current + * point to a given other point. If no such edge exists, + * it will be created + */ +P2tREdge* +p2tr_point_edge_to (P2tRPoint *self, P2tRPoint *end) +{ + GList *iter = self->edges; + + for (iter = self->edges; iter != NULL; iter = iter->next) + if (P2TR_EDGE(iter->data)->end == end) + { + p2tr_edge_ref (P2TR_EDGE(iter->data)); + return P2TR_EDGE (iter->data); + } + + /* Don't decrease reference - this is returned to someone else */ + return p2tr_edge_new (self, end); +} + +P2tREdge* +p2tr_point_has_edge_to (P2tRPoint *self, P2tRPoint *end) +{ + GList *iter = self->edges; + + for (iter = self->edges; iter != NULL; iter = iter->next) + if (P2TR_EDGE(iter->data)->end == end) + return P2TR_EDGE(iter->data); + + return NULL; +} + +P2tREdge* +p2tr_point_edgeccw (P2tRPoint *self, P2tREdge *edge) +{ + GList *index = g_list_find (self->edges, edge); + return p2tr_edgelist_ccw (self->edges, index); +} + +P2tREdge* +p2tr_point_edgecw (P2tRPoint *self, P2tREdge *edge) +{ + GList *index = g_list_find (self->edges, edge); + return p2tr_edgelist_cw (self->edges, index); +} + +/* + * ^ e1 = CCW Neighbor of e + * / + * / e1.tri + * / + * P *------> e + * \ + * \ e.tri + * \ + * v e2 = CW Neighbor of e + * + * e is in a cluster defined by P, if any of the + * following conditions hold: + * - The angle between e and e2 is less than 60 degrees, + * and the triangle of e1 is not None (i.e. the area + * between the edges is in the triangulation domain) + * - Same with e and e1 + */ +gboolean +p2tr_point_is_in_cluster (P2tRPoint *self, P2tREdge *e) +{ + /* TODO: make more efficient instead of two searches */ + GList *eL = g_list_find (self->edges, e); + P2tREdge *e1 = p2tr_edgelist_ccw (self->edges, eL); + P2tREdge *e2 = p2tr_edgelist_cw (self->edges, eL); + + gdouble Ae1e = p2tr_math_normalize_angle (e1->angle - e->angle); + gdouble Aee2 = p2tr_math_normalize_angle (e->angle - e2->angle); + + return (e1->tri != NULL && ABS (Ae1e) <= M_PI/3) + || (e->tri != NULL && ABS (Aee2) <= M_PI/3); +} + +/* + * DBG: different from original + */ +GList* +p2tr_point_get_cluster (P2tRPoint *self, P2tREdge *e, gdouble *angle) +{ + gdouble A = M_PI, a; + GList *eI = g_list_find (self->edges, e); + GList *temp; + + GList *S = g_list_append (NULL, e); + + GList *ePrev = g_list_cyclic_prev (self->edges,eI); + GList *eNext = g_list_cyclic_next (self->edges,eI); + + a = p2tr_math_normalize_angle (e->angle - P2TR_EDGE (ePrev->data)->angle); + while (a <= M_PI / 3 && ePrev != eI) + { + A = MIN(a, A); + S = g_list_prepend (S, P2TR_EDGE (ePrev->data)); + temp = ePrev; + ePrev = g_list_cyclic_prev (self->edges, ePrev); + a = p2tr_math_normalize_angle (P2TR_EDGE (temp->data)->angle - P2TR_EDGE (ePrev->data)->angle); + } + + a = p2tr_math_normalize_angle (P2TR_EDGE (eNext->data)->angle - e->angle); + while (a <= M_PI / 3 && eNext->data != S->data) + { + A = MIN(a, A); + S = g_list_append (S, P2TR_EDGE (eNext->data)); + temp = eNext; + eNext = g_list_cyclic_next (self->edges, eNext); + a = p2tr_math_normalize_angle (P2TR_EDGE (eNext->data)->angle - P2TR_EDGE (temp->data)->angle); + } + + if (angle != NULL) + *angle = A; + + return S; +} + +gboolean +p2tr_point_is_fully_in_domain (P2tRPoint *self) +{ + GList *iter = self->edges; + + for (iter = self->edges; iter != NULL; iter = iter->next) + if (P2TR_EDGE(iter->data)->end == NULL) + return FALSE; + + return TRUE; +} + +/* ########################################################################## */ +/* Edge struct */ +/* ########################################################################## */ + +P2tREdge* +p2tr_edge_new (P2tRPoint *start, P2tRPoint *end) +{ + return p2tr_edge_new_private (start, end, FALSE); +} + +P2tREdge* +p2tr_edge_new_private (P2tRPoint *start, P2tRPoint *end, gboolean mirror) +{ + P2tREdge *self = g_slice_new (P2tREdge); + p2tr_edge_init_private (self, start, end, mirror); + return self; +} + +static void +p2tr_edge_init (P2tREdge *self, P2tRPoint *start, P2tRPoint *end) +{ + p2tr_edge_init_private (self, start, end, FALSE); +} + +static void +p2tr_edge_init_private (P2tREdge *self, P2tRPoint *start, P2tRPoint *end, gboolean mirror) +{ + self->_refcount = 0; + self->removed = FALSE; + self->end = end; + self->tri = NULL; + + self->angle = atan2 (end->y - start->y, end->x - start->x); + + self->delaunay = FALSE; + self->constrained = FALSE; + + /* Important! Add the edge only once we have an angle! + * This function also adds a reference to the edge, since the point now points + * at the edge. */ + p2tr_point_add_edge (start, self); + + if (!mirror) + { + self->mirror = p2tr_edge_new_private (end, start, TRUE); + self->mirror->mirror = self; + } + + /* The edge that was created should have it's reference count increased by 1, + * since it will be returned (so mark the person who gets it holds a ref). + * Note that we don't count the reference loop between two mirror edges */ + if (!mirror) + p2tr_edge_ref (self); + + /* Finally, the edge now references it's end point */ + p2tr_point_ref (self->end); + + p2tr_assert_and_explain (p2tr_point_has_edge_to (start, end), "edge connectivity"); + p2tr_assert_and_explain (p2tr_point_has_edge_to (end, start), "edge connectivity"); +} + +/* Note that you can't really free one edge - since the edge and it's mirror are + * tightly coupled. By freeing one of them, you will also free the other - so + * beware of double freeing! + * + * The best way is not to free directly, but to use the unref function. + * + * TODO: Merge some logic and fill in missing part with the edge_remove function + */ +void +p2tr_edge_free (P2tREdge *self) +{ + g_assert (self->_refcount == 0); + + if (self->mirror->_refcount != 0) + return; + + self->removed = self->mirror->removed = TRUE; + + p2tr_point_unref (self->mirror->end); + p2tr_point_unref (self->end); + + p2tr_triangle_unref (self->mirror->tri); + p2tr_triangle_unref (self->tri); + + g_slice_free (P2tREdge, self->mirror); + g_slice_free (P2tREdge, self); +} + +/* You can't remove just one edge from a triangulation. When you remove an edge, + * it's mirror is also removed! Calling this will also remove the edge from the + * points that form the edge. + * + * TODO: Merge some logic and fill in missing part with the edge_free function + */ +void +p2tr_edge_remove (P2tREdge *self, P2tRTriangulation *T) +{ + p2tr_edge_remove_private (self, T); + p2tr_validate_triangulation (T); +} + +static void +p2tr_edge_remove_private (P2tREdge *self, P2tRTriangulation *T) +{ + P2tREdge *mir = self->mirror; + + if (self->removed) + return; + + if (self->tri != NULL) + p2tr_triangle_remove (self->tri, T); + p2tr_validate_triangulation (T); + + if (mir->tri != NULL) + p2tr_triangle_remove (mir->tri, T); + p2tr_validate_triangulation (T); + + self->removed = mir->removed = TRUE; + + p2tr_validate_triangulation (T); + p2tr_point_remove_edge (p2tr_edge_get_start (self), self); + p2tr_validate_triangulation (T); + p2tr_point_remove_edge (p2tr_edge_get_start (mir), mir); + p2tr_validate_triangulation (T); + + p2tr_triangulation_remove_ed (T, self); + p2tr_triangulation_remove_ed (T, mir); +} + +/* + * DBG: different from source + */ +gboolean +p2tr_edge_is_encroached_by (P2tREdge *self, P2tRPoint *other) +{ + if (p2tr_edge_diametral_circle_contains (self, other)) + { + p2tr_debug ("The point "); + p2tr_debug_point (other, FALSE); + p2tr_debug (" encroaches "); + p2tr_debug_edge (self, TRUE); + return TRUE; + } + return FALSE; +} + +/* + * DBG: different from source + */ +gboolean +p2tr_edge_is_encroached (P2tREdge *self) +{ + if (self->tri != NULL) + { + P2tRPoint *w = p2tr_triangle_opposite_point (self->tri, self); + if (p2tr_edge_is_encroached_by (self, w)) + return TRUE; + } + + if (self->mirror->tri != NULL) + { + P2tRPoint *w = p2tr_triangle_opposite_point (self->mirror->tri, self); + if (p2tr_edge_is_encroached_by (self, w)) + return TRUE; + } + + p2tr_debug ("The edge "); + p2tr_debug_edge (self, FALSE); + p2tr_debug (" is not encroached!\n"); + + return FALSE; +} + +gboolean +p2tr_edge_diametral_circle_contains (P2tREdge *self, P2tRPoint *pt) +{ + /* a-----O-----b + * / + * / + * pt + * + * pt is in the diametral circle only if it's distance from O (the center of + * a and b) is equal/less than a's distance from O (that's the radius). + */ + P2tRPoint *a = p2tr_edge_get_start (self); + P2tRPoint *b = p2tr_edge_get_end (self); + + gdouble Ox = (a->x + b->x) / 2; + gdouble Oy = (a->y + b->y) / 2; + + return (Ox - a->x) * (Ox - a->x) + (Oy - a->y) * (Oy - a->y) + >= (Ox - pt->x) * (Ox - pt->x) + (Oy - pt->y) * (Oy - pt->y); + /* + return (pt->y - a->y) * (pt->x - a->x) + * (pt->y - b->y) * (pt->x - b->x) <= 0; + */ +} + +gboolean +p2tr_edge_diametral_lens_contains (P2tREdge *self, P2tRPoint *W) +{ + /* + * W + * /|\ + * / | \ + * /60|60\ + * / | \ + * /30 | 30\ + * X-----O-----Y + * L L + * + * Non-Efficient: Calculate XW, and XO=YO + * + * |XO| ===> |XO| sqrt(3) ===> |XO|^2 3 + * Make sure asin (----) >= 60° ===> ---- >= ------- ===> ------ >= - + * |XW| ===> |XW| 2 ===> |XW|^2 4 + * + * |YO| ===> |YO| sqrt(3) ===> |YO|^2 3 + * Make sure asin (----) >= 60° ===> ---- >= ------- ===> ------ >= - + * |YW| ===> |YW| 2 ===> |YW|^2 4 + */ + + P2tRPoint *X = p2tr_edge_get_start (self); + P2tRPoint *Y = p2tr_edge_get_end (self); + + gdouble XO2 = p2tr_edge_len_sq (self) / 4, YO2 = XO2; + + gdouble XW2 = p2tr_math_edge_len_sq (X->x, X->y, W->x, W->y); + gdouble YW2 = p2tr_math_edge_len_sq (Y->x, Y->y, W->x, W->y); + + return (XO2 / XW2 >= 0.75) && (YO2 / YW2 >= 0.75); +} + +gdouble +p2tr_edge_len_sq (P2tREdge *self) +{ + P2tRPoint *S = p2tr_edge_get_start (self); + P2tRPoint *E = p2tr_edge_get_end (self); + return p2tr_math_edge_len_sq (S->x,S->y,E->x,E->y); +} + +void +p2tr_edge_set_constrained (P2tREdge *self, gboolean b) +{ + self->constrained = self->mirror->constrained = b; +} + +void +p2tr_edge_set_delaunay (P2tREdge *self, gboolean b) +{ + self->delaunay = self->mirror->delaunay = b; +} + +/* a = abs(E1.angle) + * b = abs(E2.angle) + * + * A is the angle we wish to find. Note the fact that we want + * to find the angle so that the edges go CLOCKWISE around it. + * + * Case 1: Signs of E1.angle and | Case 2: Signs of E1.angle and + * E2.angle agree | E2.angle disagree + * | + * A=a'+b=180-a+b | A=180-a-b + * + * ^^ | + * E2 // | * + * // | ^^ \\ + * // \ | // A \\ + * * A| | E1 // \_/ \\ E2 + * /^^ / | // \\ + * / || | //a vv + * / || E1 | ------------------ + * / || | \b + * /b a'||a | \ + * -------------- | \ + * PRECONDITION: e1.getEnd() == e2.getStart() + */ +gdouble +p2tr_angle_between (P2tREdge *e1, P2tREdge *e2) +{ + gdouble RET; + + g_assert (p2tr_edge_get_end (e1) == p2tr_edge_get_start (e2)); + + if (e1->angle < 0) + { + if (e2->angle > 0) + return ABS (e1->angle) + ABS (e2->angle) - M_PI; + else + return ABS (e1->angle) - (ABS (e2->angle) - M_PI); + } + else + { + if (e2->angle > 0) + return M_PI - ABS (e1->angle) + ABS (e2->angle); + else + return M_PI - ABS (e1->angle) - ABS (e2->angle); + } + + /* g_assert (RET + EPSILON2 >= 0 && RET <= M_PI + EPSILON2); */ + + return RET; +} + +void +p2tr_triangle_init (P2tRTriangle *self, P2tREdge *e1, P2tREdge *e2, P2tREdge *e3, P2tRTriangulation *T) +{ + P2tRPoint *A = p2tr_edge_get_end (e1); + P2tRPoint *B = p2tr_edge_get_end (e2); + P2tRPoint *C = p2tr_edge_get_end (e3); + + /* Assert that edges do form a loop! */ + p2tr_assert_and_explain (A == p2tr_edge_get_start (e2) + && B == p2tr_edge_get_start (e3) + && C == p2tr_edge_get_start (e1), "Edges form a loop!"); + + P2tROrientation o = p2tr_math_orient2d (A, B, C); + + /* + * ^ + * | \ | ^ \ + * a | \ c ==> | a' | \ c' + * v \ | | \ + * -----> | <--- v + * b | b' + * + * When found a CCW triangle with edges a-b-c, change it to + * a'-c'-b' and not a'-b'-c' !!! + */ + + p2tr_assert_and_explain (o != COLLINEAR, "No support for collinear points!"); + + if (o == CCW) + { + self->edges[0] = e1->mirror; + self->edges[1] = e3->mirror; + self->edges[2] = e2->mirror; + } + else + { + self->edges[0] = e1; + self->edges[1] = e2; + self->edges[2] = e3; + } + + /* The triangle is now referenced by the person who requested it, and also by + * 3 edges. Also, the 3 edges are now referenced by the triangle. + */ + self->edges[0]->tri = self->edges[1]->tri = self->edges[2]->tri = self; + self->_refcount = 4; + p2tr_edge_ref (self->edges[0]); + p2tr_edge_ref (self->edges[1]); + p2tr_edge_ref (self->edges[2]); + + if (T != NULL) + { + p2tr_triangulation_add_tr (T, self); + } +} + +P2tRTriangle* +p2tr_triangle_new (P2tREdge *e1, P2tREdge *e2, P2tREdge *e3, P2tRTriangulation *T) +{ + P2tRTriangle *self = g_slice_new (P2tRTriangle); + p2tr_triangle_init (self, e1, e2, e3, T); + return self; +} + +/* TODO: merge logic with the remove function */ +void +p2tr_triangle_free (P2tRTriangle *self) +{ + g_assert (self->_refcount == 0); + + p2tr_edge_unref (self->edges[0]); + p2tr_edge_unref (self->edges[1]); + p2tr_edge_unref (self->edges[2]); + + g_slice_free (P2tRTriangle, self); +} + +/* + * e0.end + * ^ + * | \ + * | \ e0 <=> e1.end + * e0 | \ e1 e1 <=> e2.end + * | \ e2 <=> e0.end + * <---- v + * e2.end e2 e1.end + */ +P2tRPoint* +p2tr_triangle_opposite_point (P2tRTriangle *self, P2tREdge *e) +{ + if (self->edges[0] == e || self->edges[0] == e->mirror) + return p2tr_edge_get_end (self->edges[1]); + else if (self->edges[1] == e || self->edges[1] == e->mirror) + return p2tr_edge_get_end (self->edges[2]); + else if (self->edges[2] == e || self->edges[2] == e->mirror) + return p2tr_edge_get_end (self->edges[0]); + + p2tr_assert_and_explain (FALSE, "Edge not in in triangle!"); +} + +P2tREdge* +p2tr_triangle_opposite_edge (P2tRTriangle *self, P2tRPoint *pt) +{ + if (p2tr_edge_get_end (self->edges[0]) == pt) + return self->edges[2]; + else if (p2tr_edge_get_end (self->edges[1]) == pt) + return self->edges[0]; + else if (p2tr_edge_get_end (self->edges[2]) == pt) + return self->edges[1]; + + p2tr_assert_and_explain (FALSE, "Point not in in triangle!"); +} + +/* Return the smallest angle not seperating two input segments (Input segments + * can not be disconnected, so we can't fix a small angle between them) + */ +gdouble +p2tr_triangle_smallest_non_seperating_angle (P2tRTriangle *self) +{ + gdouble minA = M_PI; + + P2tREdge *e0 = self->edges[0]; + P2tREdge *e1 = self->edges[1]; + P2tREdge *e2 = self->edges[2]; + + if (! e0->mirror->constrained && ! e1->mirror->constrained) + minA = MIN (minA, p2tr_angle_between(self->edges[0], self->edges[1])); + + if (! e1->mirror->constrained && ! e2->mirror->constrained) + minA = MIN (minA, p2tr_angle_between(self->edges[1], self->edges[2])); + + if (! e2->mirror->constrained && ! e0->mirror->constrained) + minA = MIN (minA, p2tr_angle_between(self->edges[2], self->edges[0])); + + return minA; +} + +gdouble +p2tr_triangle_shortest_edge_len (P2tRTriangle *self) +{ + gdouble l0 = p2tr_edge_len_sq (self->edges[0]); + gdouble l1 = p2tr_edge_len_sq (self->edges[1]); + gdouble l2 = p2tr_edge_len_sq (self->edges[2]); + + return sqrt (MIN (l0, MIN (l1, l2))); +} + +gdouble +p2tr_triangle_longest_edge_len (P2tRTriangle *self) +{ + gdouble l0 = p2tr_edge_len_sq (self->edges[0]); + gdouble l1 = p2tr_edge_len_sq (self->edges[1]); + gdouble l2 = p2tr_edge_len_sq (self->edges[2]); + + return sqrt (MAX (l0, MAX (l1, l2))); +} + +void +p2tr_triangle_angles (P2tRTriangle *self, gdouble dest[3]) +{ + dest[0] = p2tr_angle_between(self->edges[0], self->edges[1]); + dest[1] = p2tr_angle_between(self->edges[1], self->edges[2]); + dest[2] = p2tr_angle_between(self->edges[2], self->edges[0]); +} + +gdouble +p2tr_triangle_get_angle_at (P2tRTriangle *self, P2tRPoint* pt) +{ + if (pt == self->edges[0]->end) + return p2tr_angle_between(self->edges[0], self->edges[1]); + else if (pt == self->edges[1]->end) + return p2tr_angle_between(self->edges[1], self->edges[2]); + else if (pt == self->edges[2]->end) + return p2tr_angle_between(self->edges[2], self->edges[0]); + else + p2tr_assert_and_explain (FALSE, "Trying to get the angle at a point not in the tri!\n"); +} + +/* + * TODO: merge logic with the free function + */ +void +p2tr_triangle_remove (P2tRTriangle *self, P2tRTriangulation *T) +{ + p2tr_debug ("Removing a triangle\n"); + + if (T != NULL) + p2tr_triangulation_remove_tr (T, self); + + self->edges[0]->tri = NULL; + p2tr_triangle_unref (self); + + self->edges[1]->tri = NULL; + p2tr_triangle_unref (self); + + self->edges[2]->tri = NULL; + p2tr_triangle_unref (self); + +} + +void +p2tr_triangle_circumcircle (P2tRTriangle *self, P2tRCircle *dest) +{ + P2tRPoint *A = p2tr_edge_get_end (self->edges[2]); + P2tRPoint *B = p2tr_edge_get_end (self->edges[0]); + P2tRPoint *C = p2tr_edge_get_end (self->edges[1]); + + gdouble Anorm = A->x * A->x + A->y * A->y; + gdouble Bnorm = B->x * B->x + B->y * B->y; + gdouble Cnorm = C->x * C->x + C->y * C->y; + + gdouble D = 2*(A->x * (B->y - C->y) + B->x * (C->y - A->y) + C->x * (A->y - B->y)); + + dest->x = (Anorm * (B->y - C->y) + Bnorm * (C->y - A->y) + Cnorm * (A->y - B->y)) / D; + dest->y = -(Anorm * (B->x - C->x) + Bnorm * (C->x - A->x) + Cnorm * (A->x - B->x)) / D; + + dest->radius = sqrt (p2tr_math_edge_len_sq (A->x, A->y, dest->x, dest->y)); +} + +gboolean +p2tr_triangle_is_circumcenter_inside (P2tRTriangle *self) +{ + gdouble angles[3]; + + p2tr_triangle_angles (self, angles); + + return MAX (angles[0], MAX (angles[1], angles[2])) < M_PI / 2; +} + + +/* + * P0 + * ^ \ + * / \ + * e2/ \e0 + * / *C \ + * / v + * P2 <------- P1 + * e1 + * + * DBG: different from source + */ +void +p2tr_triangle_subdivide (P2tRTriangle *self, P2tRPoint *C, P2tRTriangulation *T, P2tRTriangle *dest_new[3]) +{ + P2tREdge *e0 = self->edges[0]; + P2tREdge *e1 = self->edges[1]; + P2tREdge *e2 = self->edges[2]; + + P2tREdge *CP0, *CP1, *CP2; + + P2tRPoint *P0 = p2tr_edge_get_end (e2); + P2tRPoint *P1 = p2tr_edge_get_end (e0); + P2tRPoint *P2 = p2tr_edge_get_end (e1); + + P2tRTriangle *t0, *t1, *t2; + + if (C == NULL) + { + P2tRCircle cc; + p2tr_triangle_circumcircle (self, &cc); + C = p2tr_point_new (cc.x, cc.y); + } + + g_assert (p2tr_triangle_contains_pt (self, C)); + + p2tr_validate_triangulation (T); + p2tr_triangle_remove (self, T); + p2tr_validate_triangulation (T); + + CP0 = p2tr_point_edge_to (C, P0); + CP1 = p2tr_point_edge_to (C, P1); + CP2 = p2tr_point_edge_to (C, P2); + + t0 = p2tr_triangle_new (CP0, e0, CP1->mirror, T); + p2tr_validate_triangulation (T); + t1 = p2tr_triangle_new (CP1, e1, CP2->mirror, T); + p2tr_validate_triangulation (T); + t2 = p2tr_triangle_new (CP2, e2, CP0->mirror, T); + p2tr_validate_triangulation (T); + + if (dest_new != NULL) + { + dest_new[0] = t0; + dest_new[1] = t1; + dest_new[2] = t2; + } + else + { + p2tr_triangle_unref (t0); + p2tr_triangle_unref (t1); + p2tr_triangle_unref (t2); + } +} + +/* Based on http://www.blackpawn.com/texts/pointinpoly/default.html */ +gboolean +p2tr_triangle_contains_pt (P2tRTriangle *self, P2tRPoint *P) +{ + P2tRPoint *A = p2tr_edge_get_end (self->edges[2]); + P2tRPoint *B = p2tr_edge_get_end (self->edges[0]); + P2tRPoint *C = p2tr_edge_get_end (self->edges[1]); + + gdouble v0x = C->x - A->x; + gdouble v0y = C->y - A->y; + gdouble v1x = B->x - A->x; + gdouble v1y = B->y - A->y; + gdouble v2x = P->x - A->x; + gdouble v2y = P->y - A->y; + + /* Compute dot products */ + gdouble dot00 = v0x * v0x + v0y * v0y; + gdouble dot01 = v0x * v1x + v0y * v1y; + gdouble dot02 = v0x * v2x + v0y * v2y; + gdouble dot11 = v1x * v1x + v1y * v1y; + gdouble dot12 = v1x * v2x + v1y * v2y; + + /* Compute barycentric coordinates */ + gdouble invDenom = 1 / (dot00 * dot11 - dot01 * dot01); + gdouble u = (dot11 * dot02 - dot01 * dot12) * invDenom; + gdouble v = (dot00 * dot12 - dot01 * dot02) * invDenom; + + /* Check if point is in triangle */ + return (u > -EPSILON2) && (v > -EPSILON2) && (u + v < 1 + EPSILON2); +} + + +gboolean +p2tr_triangulation_legalize (P2tRTriangulation *T, + P2tRTriangle *tr) +{ + /* Remember! Edges in each triangle are ordered counter clockwise! + * q + * *-----------*a shared_tr = p->q = tr->edges[i] + * |\ / shared_ot = q->p = tr->edges[i]->mirror + * | \ / ot = shared_ot->tri + * | \ tr / + * | \ / + * | ot \ / + * *-----* + * b p + * + * Also note that we can not flip in cases of concave quads! We must check + * that the angles at p and at q are both smaller than 180°. + */ + gint i; + + /* First, make sure this triangle still exists */ + if (! p2tr_hash_set_contains (T->tris, tr)) + return FALSE; + + /* To legalize a triangle we start by finding if any of the three edges + * violate the Delaunay condition + */ + for (i = 0; i < 3; i++) + { + P2tREdge *shared_tr = tr->edges[i]; + P2tREdge *shared_ot = shared_tr->mirror; + P2tRTriangle* ot = shared_ot->tri; + + // If this is a Constrained Edge or a Delaunay Edge (only during + // recursive legalization) then we should not try to legalize + if (shared_tr->delaunay || shared_tr->constrained) + continue; + + if (ot) + { + P2tRPoint* p = p2tr_edge_get_end (shared_ot); + P2tRPoint* q = p2tr_edge_get_end (shared_tr); + P2tRPoint* a = p2tr_triangle_opposite_point (tr, shared_tr); + P2tRPoint* b = p2tr_triangle_opposite_point (ot, shared_ot); + // We already checked if it's constrained or delaunay for the case of + // skipping this tri + + // Check for concave quads + if (p2tr_triangle_get_angle_at (tr, p) + p2tr_triangle_get_angle_at (ot, p) >= M_PI + || p2tr_triangle_get_angle_at (tr, q) + p2tr_triangle_get_angle_at (ot, q) >= M_PI) + continue; + + gboolean inside = p2tr_math_incircle (p, a, q, b); + + if (inside) + { + P2tREdge *ab; + P2tREdge *bq, *qa, *pb, *ap; + P2tRTriangle *abq, *pba; + + // First of all, remove the edge + p2tr_edge_remove (shared_tr, T); + + // Create a new matching rotated edge + ab = p2tr_edge_new (a, b); + + // Mark it as Delaunay + p2tr_edge_set_delaunay (ab, TRUE); + + // Create the triangles + bq = p2tr_point_edge_to (b,q); + qa = p2tr_point_edge_to (q,a); + abq = p2tr_triangle_new (ab, bq, qa, T); + + pb = p2tr_point_edge_to (p,b); + ap = p2tr_point_edge_to (a,p); + pba = p2tr_triangle_new (pb, ab->mirror, ap, T); + + // Unref stuff + p2tr_edge_unref (bq); + p2tr_edge_unref (qa); + + p2tr_edge_unref (pb); + p2tr_edge_unref (ap); + + // Now, legalize these two triangles: + p2tr_triangulation_legalize (T, abq); + p2tr_triangle_unref (abq); + + // Legalization may have killed the other triangle, but that's OK + // since legalization makes sure the triangle exists + p2tr_triangulation_legalize (T, pba); + p2tr_triangle_unref (pba); + + // Reset the Delaunay edges, since they only are valid Delaunay edges + // until we add a new triangle or point. + // XXX: need to think about this. Can these edges be tried after we + // return to previous recursive level? + p2tr_edge_set_delaunay (ab, FALSE); + + // If triangle have been legalized no need to check the other edges since + // the recursive legalization will handles those so we can end here. + return TRUE; + } + } + } + return FALSE; +} + +/* * A2 + * / \ + * / \ + * / T2 \ + * B *------>* C e = B->C + * ^ T1 / + * \ / + * \ v + * * A1 + */ +void +p2tr_triangulation_flip_fix (P2tREdge *e, P2tRTriangulation *T) +{ + P2tRTriangle *T1 = e->tri; + P2tRTriangle *T2 = e->mirror->tri; + + /* Removed edges do not need fixing, constrained edges can not be flipped, and + * edges that were already flipped should not be flipped again. + * + * Finally, edges must have a triangle on both sides of them (such a situation + * can occur during the execution of the algorithms, without the edge being + * constrained) in order to be flipped + */ + if (e->removed || e->constrained || e->delaunay || T1 == NULL || T2 == NULL) + return; + + P2tRPoint *A1 = p2tr_triangle_opposite_point (T1, e); + P2tRPoint *A2 = p2tr_triangle_opposite_point (T2, e); + P2tRPoint *B = p2tr_edge_get_start (e); + P2tRPoint *C = p2tr_edge_get_end (e); + + /* We can't do a flip fix in cases where the two triangles form together a + * concave quad! + * + * To check this, see if the sum of the two angles at any of the edges is + * larger than 180 degress. + */ + P2tREdge *BC = p2tr_point_edge_to (B, C); + + p2tr_validate_triangulation (T); + P2tREdge *CA2 = p2tr_point_edge_to (C, A2); + p2tr_validate_triangulation (T); + P2tREdge *CA1 = p2tr_point_edge_to (C, A1); + p2tr_validate_triangulation (T); + + P2tREdge *BA2 = p2tr_point_edge_to (B, A2); + p2tr_validate_triangulation (T); + P2tREdge *BA1 = p2tr_point_edge_to (B, A1); + p2tr_validate_triangulation (T); + + gdouble BCA2 = p2tr_angle_between (CA2->mirror,BC->mirror); + gdouble BCA1 = p2tr_angle_between (BC,CA1); + + gdouble CBA2 = p2tr_angle_between (BC->mirror,BA2); + gdouble CBA1 = p2tr_angle_between (BA1->mirror,BC); + + if (BCA2 + BCA1 > M_PI - EPSILON2 || CBA2 + CBA1 > M_PI - EPSILON2) + { + p2tr_debug ("Won't fix concave quads!\n"); + + /* In the case of concave quads, mark the edge as non flip-able */ + p2tr_edge_set_delaunay (BC, TRUE); + + /* Now fix the other edges */ + p2tr_triangulation_flip_fix (BA2,T); + p2tr_triangulation_flip_fix (BA1,T); + p2tr_triangulation_flip_fix (CA2,T); + p2tr_triangulation_flip_fix (CA1,T); + + /* Restore */ + p2tr_edge_set_delaunay (BC, FALSE); + } + + /* Check if empty circle property does not hold */ + else if (p2tr_math_incircle (A1,C,B,A2) != INCIRCLE_OUTSIDE + || p2tr_math_incircle (A2,B,C,A1) != INCIRCLE_OUTSIDE) + { + P2tREdge *A2A1; + P2tRTriangle *Tn1, *Tn2; + + p2tr_validate_triangulation (T); + p2tr_edge_remove (e, T); + p2tr_validate_triangulation (T); + + A2A1 = p2tr_point_edge_to (A2, A1); + p2tr_validate_triangulation (T); + + Tn1 = p2tr_triangle_new (A2A1, BA1->mirror, BA2, T); + p2tr_validate_triangulation (T); + Tn2 = p2tr_triangle_new (A2A1, CA1->mirror, CA2, T); + p2tr_validate_triangulation (T); + + p2tr_edge_set_delaunay (A2A1, TRUE); + + p2tr_triangulation_flip_fix (BA2,T); + p2tr_triangulation_flip_fix (CA2,T); + + p2tr_triangulation_flip_fix (BA1->mirror,T); + p2tr_triangulation_flip_fix (CA1->mirror,T); + + p2tr_edge_set_delaunay (A2A1, FALSE); + } +} + +/* TODO: UNEFFICIENT LIKE HELL! */ +gboolean +p2tr_edges_intersect (P2tREdge *e1, P2tREdge *e2) +{ + P2tRPoint *e1S = p2tr_edge_get_start (e1); + P2tRPoint *e1E = p2tr_edge_get_end (e1); + P2tRPoint *e2S = p2tr_edge_get_start (e1); + P2tRPoint *e2E = p2tr_edge_get_end (e1); + + return p2tr_math_orient2d (e1S,e1E,e2S) != p2tr_math_orient2d (e1S,e1E,e2E) + && p2tr_math_orient2d (e2S,e2E,e1S) != p2tr_math_orient2d (e2S,e2E,e1E); +} + +P2tRPoint * +p2tr_triangle_median_pt (P2tRTriangle *self) +{ + P2tRPoint *A = p2tr_edge_get_end (self->edges[2]); + P2tRPoint *B = p2tr_edge_get_end (self->edges[0]); + P2tRPoint *C = p2tr_edge_get_end (self->edges[1]); + + return p2tr_point_new ((A->x+B->x+C->x)/3,(A->y+B->y+C->y)/3); +} + +/* TODO: this computation can be much optimized using math rules! */ +P2tRPoint * +p2tr_edge_concentric_center (P2tREdge *e) +{ + gdouble x0 = p2tr_edge_get_start(e)->x, y0 = p2tr_edge_get_start(e)->y; + gdouble x1 = p2tr_edge_get_end(e)->x, y1 = p2tr_edge_get_end(e)->y; + gdouble fraction; + + gdouble l = sqrt (p2tr_edge_len_sq (e)); + /* Note that in the braces below, it's L and not 1 */ + gdouble lPart = pow (2, round (log2 (l/2))); + + while (lPart >= l) + lPart /= 2 + ; + fraction = lPart / l; + + return p2tr_point_new (x0 + fraction * (x1 - x0), y0 + fraction * (y1 - y0)); +} + +P2tRTriangulation* +p2tr_triangulate (GList *p2trpoints) +{ + P2tPointPtrArray D = g_ptr_array_new (); + GList *iter; + + P2tRTriangulation *T = p2tr_triangulation_new (); + + GHashTable *map = g_hash_table_new_full (g_direct_hash, g_direct_equal, NULL, NULL); + + foreach (iter, p2trpoints) + { + P2tRPoint *pt = (P2tRPoint*) iter->data; + P2tPoint *opt = p2t_point_new_dd (pt->x, pt->y); + + g_hash_table_insert (map, opt, pt); + g_ptr_array_add (D, opt); + } + + P2tCDT *cdt = p2t_cdt_new (D); + p2t_cdt_triangulate (cdt); + + P2tTrianglePtrArray pt = p2t_cdt_get_triangles (cdt); + int i; + for (i = 0; i < pt->len; i++) + { + P2tTriangle *t = triangle_index (pt,i); + P2tRPoint *p0 = g_hash_table_lookup (map, p2t_triangle_get_point (t, 0)); + P2tRPoint *p1 = g_hash_table_lookup (map, p2t_triangle_get_point (t, 1)); + P2tRPoint *p2 = g_hash_table_lookup (map, p2t_triangle_get_point (t, 2)); + p2tr_triangle_new (p2tr_point_edge_to (p0, p1), + p2tr_point_edge_to (p1, p2), + p2tr_point_edge_to (p2, p0), T); + } + + p2t_cdt_free (cdt); + + for (i = 0; i < D->len; i++) + p2t_point_free (point_index (D, i)); + + g_ptr_array_free (D, TRUE); + + g_hash_table_destroy (map); + + return T; + +} + +P2tRTriangulation * +p2tr_triangulation_new () +{ + P2tRTriangulation *self = g_slice_new (P2tRTriangulation); + self->tris = p2tr_hash_set_set_new (g_direct_hash, g_direct_equal, NULL); + self->pts = p2tr_hash_set_set_new (g_direct_hash, g_direct_equal, NULL); + self->edges = p2tr_hash_set_set_new (g_direct_hash, g_direct_equal, NULL); + return self; +} + +P2tRTriangulation* +p2tr_triangulation_free (P2tRTriangulation *self) +{ + P2trHashSetIter siter; + + P2tRTriangle *tr; + P2tREdge *ed; + P2tRPoint *pt; + + p2tr_hash_set_iter_init (&siter, self->tris); + while (p2tr_hash_set_iter_next (&siter, (gpointer*) &tr)) + { + p2tr_triangle_unref (tr); + } + + p2tr_hash_set_iter_init (&siter, self->edges); + while (p2tr_hash_set_iter_next (&siter, (gpointer*) &ed)) + { + p2tr_edge_unref (ed); + } + + p2tr_hash_set_iter_init (&siter, self->pts); + while (p2tr_hash_set_iter_next (&siter, (gpointer*) &pt)) + { + p2tr_point_unref (pt); + } + + g_hash_table_destroy (self->tris); + g_hash_table_destroy (self->edges); + g_hash_table_destroy (self->pts); + + g_slice_free (P2tRTriangulation, self); +} + +P2tRTriangulation* +p2tr_triangulateA (P2tRPoint **p2trpoints, gint count) +{ + GList *A = NULL; + P2tRTriangulation *T; + int i; + for (i = 0; i < count; i++) + { + A = g_list_prepend (A, p2trpoints[count-i-1]); + } + + T = p2tr_triangulate (A); + + g_list_free (A); + + return T; + +} + +#define DEBUG FALSE +gboolean +p2tr_validate_triangulation (P2tRTriangulation* T) +{ +#if DEBUG + P2trHashSetIter iter; + GList *L; + P2tRTriangle *t; + + p2tr_hash_set_iter_init (&iter, T->tris); + + while (p2tr_hash_set_iter_next (&iter, (gpointer*)&t)) + { + int i; + for (i = 0; i < 3; i++) + { + P2tRPoint *S = p2tr_edge_get_start (t->edges[i]); + P2tRPoint *E = p2tr_edge_get_end (t->edges[i]); + + p2tr_assert_and_explain (p2tr_point_has_edge_to (S, E), "edge connectivity"); + p2tr_assert_and_explain (p2tr_point_has_edge_to (E, S), "edge connectivity"); + p2tr_assert_and_explain (t->edges[i]->tri == t, "triangle <-> edge"); + } + } +#endif + return TRUE; + +} + +gboolean +p2tr_validate_edge (P2tREdge* e) +{ + if (e->constrained != e->mirror->constrained) + { + G_BREAKPOINT(); + g_assert (FALSE); + } + if (e->tri == NULL && ! e->constrained) + { + G_BREAKPOINT(); + g_assert (FALSE); + } + + if (e->mirror->constrained != e->mirror->mirror->constrained) + { + G_BREAKPOINT(); + g_assert (FALSE); + } + if (e->mirror->tri == NULL && ! e->mirror->constrained) + { + G_BREAKPOINT(); + g_assert (FALSE); + } + + return TRUE; + +} + + +void +p2tr_debug_point (P2tRPoint* pt, gboolean newline) +{ + p2tr_debug ("@PT(%g,%g)", pt->x, pt->y); + if (newline) p2tr_debug ("\n"); +} + +void +p2tr_debug_edge (P2tREdge* ed, gboolean newline) +{ + p2tr_debug ("@ED("); + p2tr_debug_point (p2tr_edge_get_start (ed), FALSE); + p2tr_debug ("->"); + p2tr_debug_point (p2tr_edge_get_end (ed), FALSE); + p2tr_debug (")"); + if (newline) p2tr_debug ("\n"); +} + +void +p2tr_debug_tri (P2tRTriangle* tr, gboolean newline) +{ + p2tr_debug ("@TR("); + p2tr_debug_edge (tr->edges[0], FALSE); + p2tr_debug ("~"); + p2tr_debug_edge (tr->edges[1], FALSE); + p2tr_debug ("~"); + p2tr_debug_edge (tr->edges[2], FALSE); + p2tr_debug (")"); + if (newline) p2tr_debug ("\n"); +} + diff --git a/refine/triangulation.h b/refine/triangulation.h new file mode 100755 index 0000000..10a2b36 --- /dev/null +++ b/refine/triangulation.h @@ -0,0 +1,323 @@ +/* + * This file is a part of Poly2Tri-C - The C port of the Poly2Tri library + * Porting to C done by (c) Barak Itkin + * http://code.google.com/p/poly2tri-c/ + * + * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors + * http://code.google.com/p/poly2tri/ + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without modification, + * are permitted provided that the following conditions are met: + * + * * Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * * Neither the name of Poly2Tri nor the names of its contributors may be + * used to endorse or promote products derived from this software without specific + * prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ +#ifndef __POLY2TRI_C_REFINE_TRIANGULATION_H__ +#define __POLY2TRI_C_REFINE_TRIANGULATION_H__ + +#ifdef __cplusplus +extern "C" +{ +#endif + +#include +#include "../common/utils.h" +#include "utils.h" +#include + +#define EPSILON2 (1e-6) + +#define p2tr_debug //g_printerr + +#define p2tr_assert_and_explain(expr,err) \ +do { \ + if (!(expr)) \ + { \ + g_warning (err); \ + g_assert (FALSE); \ + } \ +} while (FALSE) + + +typedef struct P2tRTriangle_ P2tRTriangle; +typedef struct P2tREdge_ P2tREdge; +typedef struct P2tRPoint_ P2tRPoint; +typedef struct P2tRTriangulation_ P2tRTriangulation; +typedef struct P2tRCircle_ P2tRCircle; + +/* ########################################################################## */ +/* Common math */ +/* ########################################################################## */ + +gdouble p2tr_math_normalize_angle (gdouble angle); + +/* TODO: try to somehow merge with the matching functions in utils.c */ +typedef P2tOrientation P2tROrientation; + +typedef enum +{ + INCIRCLE_ON, + INCIRCLE_INSIDE, + INCIRCLE_OUTSIDE +} P2tRInCircle; + +P2tROrientation p2tr_math_orient2d (P2tRPoint* pa, P2tRPoint* pb, P2tRPoint* pc); + +P2tRInCircle p2tr_math_incircle (P2tRPoint* a, P2tRPoint* b, P2tRPoint* c, P2tRPoint* d); + +gdouble p2tr_math_edge_len_sq (gdouble x1, gdouble y1, gdouble x2, gdouble y2); + +/* ########################################################################## */ +/* Triangulation struct */ +/* ########################################################################## */ + +struct P2tRTriangulation_ +{ + P2tRHashSet *pts; + P2tRHashSet *edges; + P2tRHashSet *tris; +}; + +void p2tr_triangulation_remove_pt (P2tRTriangulation *self, P2tRPoint *pt); +void p2tr_triangulation_remove_ed (P2tRTriangulation *self, P2tREdge *ed); +void p2tr_triangulation_remove_tr (P2tRTriangulation *self, P2tRTriangle *tr); + +void p2tr_triangulation_add_pt (P2tRTriangulation *self, P2tRPoint *pt); +void p2tr_triangulation_add_ed (P2tRTriangulation *self, P2tREdge *ed); +void p2tr_triangulation_add_tr (P2tRTriangulation *self, P2tRTriangle *tr); + +void p2tr_triangulation_get_points (P2tRTriangulation *self, GPtrArray *dest); + + +/* ########################################################################## */ +/* Point struct */ +/* ########################################################################## */ + +struct P2tRPoint_ +{ + gdouble x; + gdouble y; + GList *edges; + guint _refcount; +}; + +P2tRPoint* p2tr_point_new (gdouble x, gdouble y); + +void p2tr_point_remove_edge (P2tRPoint *self, P2tREdge *edge); + +void p2tr_point_remove (P2tRPoint *self, P2tRTriangulation *T); + +P2tREdge* p2tr_point_edge_to (P2tRPoint *self, P2tRPoint *end); + +P2tREdge* p2tr_point_has_edge_to (P2tRPoint *self, P2tRPoint *end); + +P2tREdge* p2tr_point_edgeccw (P2tRPoint *self, P2tREdge *edge); + +P2tREdge* p2tr_point_edgecw (P2tRPoint *self, P2tREdge *edge); + +gboolean p2tr_point_is_in_cluster (P2tRPoint *self, P2tREdge *e); + +GList* p2tr_point_get_cluster (P2tRPoint *self, P2tREdge *e, gdouble *angle); + +gboolean p2tr_point_is_fully_in_domain (P2tRPoint *self); + +void p2tr_point_free (P2tRPoint *self); + +#define p2tr_point_ref(pt) ((pt)->_refcount++) + +#define p2tr_point_unref(pt) \ +do { \ + if ((--(pt)->_refcount) == 0) \ + { \ + p2tr_point_free ((pt)); \ + } \ +} while (FALSE) + + +/* ########################################################################## */ +/* Edge struct */ +/* ########################################################################## */ + +#define P2TR_EDGE(e) ((P2tREdge*)(e)) + +struct P2tREdge_ +{ + P2tRPoint *end; + gdouble angle; + + P2tREdge *mirror; + P2tRTriangle *tri; + + gboolean delaunay; + gboolean constrained; + + gboolean removed; + + /* Note that this count does not include the pointing from the mirror edge */ + guint _refcount; +}; + +P2tREdge* p2tr_edge_new (P2tRPoint *start, P2tRPoint *end); + +P2tREdge* p2tr_edge_new_private (P2tRPoint *start, P2tRPoint *end, gboolean mirror); + +void p2tr_edge_remove (P2tREdge *self, P2tRTriangulation *T); + +gboolean p2tr_edge_is_encroached_by (P2tREdge *self, P2tRPoint *other); + +gboolean p2tr_edge_is_encroached (P2tREdge *self); + +gboolean p2tr_edge_diametral_lens_contains (P2tREdge *self, P2tRPoint *W); + +gboolean p2tr_edge_diametral_circle_contains (P2tREdge *self, P2tRPoint *pt); + +gdouble p2tr_edge_len_sq (P2tREdge *self); + +void p2tr_edge_set_constrained (P2tREdge *self, gboolean b); + +void p2tr_edge_set_delaunay (P2tREdge *self, gboolean b); + +/* Note that you can't really free one edge; Freeing will happen when both + * have no references to + */ +void p2tr_edge_free (P2tREdge *self); + +#define p2tr_edge_ref(ed) ((ed)->_refcount++) + +#define p2tr_edge_unref(ed) \ +do { \ + if ((--(ed)->_refcount) == 0) \ + { \ + p2tr_edge_free ((ed)); \ + } \ +} while (FALSE) + +#define p2tr_edgelist_ccw(elist,e) P2TR_EDGE(g_list_cyclic_next((elist),(e))->data) +#define p2tr_edgelist_cw(elist,e) P2TR_EDGE(g_list_cyclic_prev((elist),(e))->data) + +#define p2tr_edge_get_start(e) ((e)->mirror->end) +#define p2tr_edge_get_end(e) ((e)->end) + +/* ########################################################################## */ +/* Triangle struct */ +/* ########################################################################## */ + +struct P2tRTriangle_ +{ + P2tREdge *edges[3]; + guint _refcount; +}; + +struct P2tRCircle_ +{ + gdouble x; + gdouble y; + + gdouble radius; +}; + +gdouble p2tr_angle_between (P2tREdge *e1, P2tREdge *e2); + +void p2tr_triangle_init (P2tRTriangle *self, P2tREdge *e1, P2tREdge *e2, P2tREdge *e3, P2tRTriangulation *T); + +P2tRTriangle* p2tr_triangle_new (P2tREdge *e1, P2tREdge *e2, P2tREdge *e3, P2tRTriangulation *T); + +void p2tr_triangle_free (P2tRTriangle *self); + +P2tRPoint* p2tr_triangle_opposite_point (P2tRTriangle *self, P2tREdge *e); + +P2tREdge* p2tr_triangle_opposite_edge (P2tRTriangle *self, P2tRPoint *pt); + +gdouble p2tr_triangle_smallest_non_seperating_angle (P2tRTriangle *self); + +gdouble p2tr_triangle_shortest_edge_len (P2tRTriangle *self); + +gdouble p2tr_triangle_longest_edge_len (P2tRTriangle *self); + +void p2tr_triangle_angles (P2tRTriangle *self, gdouble dest[3]); + +gdouble p2tr_triangle_get_angle_at (P2tRTriangle *self, P2tRPoint* pt); + +void p2tr_triangle_remove (P2tRTriangle *self, P2tRTriangulation *T); + +void p2tr_triangle_circumcircle (P2tRTriangle *self, P2tRCircle *dest); + +gboolean p2tr_triangle_is_circumcenter_inside (P2tRTriangle *self); + +void p2tr_triangle_subdivide (P2tRTriangle *self, P2tRPoint *C, P2tRTriangulation *T, P2tRTriangle *dest_new[3]); + +gboolean p2tr_triangle_contains_pt (P2tRTriangle *self, P2tRPoint *P); + +void p2tr_triangulation_flip_fix (P2tREdge *e, P2tRTriangulation *T); + +gboolean p2tr_edges_intersect (P2tREdge *e1, P2tREdge *e2); + +P2tRPoint *p2tr_triangle_median_pt (P2tRTriangle *self); + +P2tRPoint *p2tr_edge_concentric_center (P2tREdge *e); + +P2tRTriangulation* p2tr_triangulate (GList *p2trpoints); + +P2tRTriangulation* p2tr_triangulateA (P2tRPoint **p2trpoints, gint count); + +gboolean p2tr_validate_triangulation (P2tRTriangulation* T); + +gboolean p2tr_validate_edge (P2tREdge* e); + +gboolean p2tr_false_delta (P2tRTriangle *t); + +#define p2tr_triangle_ref(tr) ((tr)->_refcount++) + +#define p2tr_triangle_unref(tr) \ +do { \ + if ((--(tr)->_refcount) == 0) \ + { \ + p2tr_triangle_free ((tr)); \ + } \ +} while (FALSE) + + + + + +P2tRTriangulation* +p2tr_triangulation_free (P2tRTriangulation *self); + +P2tRTriangulation* +p2tr_triangulation_new (); + + + + +void p2tr_debug_point (P2tRPoint* pt, gboolean newline); + +void p2tr_debug_edge (P2tREdge* ed, gboolean newline); + +void p2tr_debug_tri (P2tRTriangle* tr, gboolean newline); + + +#ifdef __cplusplus +} +#endif + +#endif /* TRIANGULATION_H */ diff --git a/refine/utils.h b/refine/utils.h new file mode 100755 index 0000000..a846155 --- /dev/null +++ b/refine/utils.h @@ -0,0 +1,71 @@ +/* + * This file is a part of Poly2Tri-C - The C port of the Poly2Tri library + * Porting to C done by (c) Barak Itkin + * http://code.google.com/p/poly2tri-c/ + * + * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors + * http://code.google.com/p/poly2tri/ + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without modification, + * are permitted provided that the following conditions are met: + * + * * Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * * Neither the name of Poly2Tri nor the names of its contributors may be + * used to endorse or promote products derived from this software without specific + * prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef __POLY2TRI_C_REFINE_UTILS_H__ +#define __POLY2TRI_C_REFINE_UTILS_H__ + +#ifdef __cplusplus +extern "C" +{ +#endif + +#include + + /* The code for the Hash Set is partially based on the example given at + * http://developer.gnome.org/glib/2.29/glib-Hash-Tables.html + */ + + typedef GHashTable P2tRHashSet; + typedef GHashTableIter P2trHashSetIter; + +#define p2tr_hash_set_set_new(hash_func, equal_func, destroy) g_hash_table_new_full ((hash_func), (equal_func), (destroy),NULL) +#define p2tr_hash_set_insert(set,element) g_hash_table_insert ((set), (element), (element)) +#define p2tr_hash_set_contains(set,element) g_hash_table_lookup_extended ((set), (element), NULL, NULL) +#define p2tr_hash_set_remove(set,element) g_hash_table_remove ((set), (element)) + +#define p2tr_hash_set_iter_init(iter,hash_set) g_hash_table_iter_init ((iter),(hash_set)) +#define p2tr_hash_set_iter_next(iter,val) g_hash_table_iter_next ((iter),(val),NULL) +#define p2tr_hash_set_iter_remove(iter) g_hash_table_iter_remove ((iter)) + +#define g_list_cyclic_prev(list,elem) (((elem)->prev != NULL) ? (elem)->prev : g_list_last ((elem))) +#define g_list_cyclic_next(list,elem) (((elem)->next != NULL) ? (elem)->next : g_list_first ((elem))) + +#define foreach(iter,list) for ((iter) = (list); (iter) != NULL; (iter) = (iter)->next) + +#ifdef __cplusplus +} +#endif + +#endif /* UTILS_H */ diff --git a/render/mesh-render.c b/render/mesh-render.c new file mode 100755 index 0000000..6d8e3ca --- /dev/null +++ b/render/mesh-render.c @@ -0,0 +1,354 @@ +#include +#include +#include +#include "../refine/triangulation.h" +#include "mesh-render.h" + +/* Most computations using the Barycentric Coordinates are Based on + * http://www.blackpawn.com/texts/pointinpoly/default.html */ + +/* This function is simply to make sure the code is consitant */ +void +p2tr_triangle_barycentric_get_points (P2tRTriangle *self, + P2tRPoint **A, + P2tRPoint **B, + P2tRPoint **C) +{ + *A = p2tr_edge_get_end (self->edges[2]); + *B = p2tr_edge_get_end (self->edges[0]); + *C = p2tr_edge_get_end (self->edges[1]); +} + +#define USE_BARYCENTRIC(u,v,A,B,C) ((A) + (v)*((B)-(A)) + (u)*((C)-(A))) + +gboolean +p2tr_triangle_compute_barycentric_coords (P2tRTriangle *tr, + gdouble Px, + gdouble Py, + gdouble *u_out, + gdouble *v_out) +{ + P2tRPoint *A, *B, *C; + + gdouble u, v; + gdouble v0x, v0y, v1x, v1y, v2x, v2y; + gdouble dot00, dot01, dot02, dot11, dot12; + gdouble invDenom; + + p2tr_triangle_barycentric_get_points (tr, &A, &B, &C); + + /* v0 = C-A */ + v0x = C->x - A->x; + v0y = C->y - A->y; + /* v1 = B-A */ + v1x = B->x - A->x; + v1y = B->y - A->y; + /* v2 = P-A */ + v2x = Px - A->x; + v2y = Py - A->y; + + /* Compute dot products */ + dot00 = v0x * v0x + v0y * v0y; + dot01 = v0x * v1x + v0y * v1y; + dot02 = v0x * v2x + v0y * v2y; + dot11 = v1x * v1x + v1y * v1y; + dot12 = v1x * v2x + v1y * v2y; + + /* Compute barycentric coordinates */ + invDenom = 1 / (dot00 * dot11 - dot01 * dot01); + + /* P = A + v*(B-A) + u*(C-A) */ + *u_out = u = (dot11 * dot02 - dot01 * dot12) * invDenom; + *v_out = v = (dot00 * dot12 - dot01 * dot02) * invDenom; + + /* Check if point is in triangle */ + return (u > -EPSILON2) && (v > -EPSILON2) && (u + v < 1 + EPSILON2); + +} + +/* This function implements box logic to see if a point is contained in a + * triangles bounding box. This is very useful for cases where there are many + * triangles to test against a single point, and most of them aren't even near + * it. + * + * Instead of finding the Xmin, Xmax, Ymin, Ymax and checking if the the point + * is outside, just check if the point is on the SAME SIDE compared to all the + * points of the triangle. + * See http://lightningismyname.blogspot.com/2011/08/quickboxa-quick-point-in-triangle-test.html + */ +gboolean +p2tr_triangule_quick_box_test (P2tRTriangle *self, + gdouble Px, + gdouble Py) +{ + P2tRPoint *A = p2tr_edge_get_end (self->edges[2]); + P2tRPoint *B = p2tr_edge_get_end (self->edges[0]); + P2tRPoint *C = p2tr_edge_get_end (self->edges[1]); + + register gboolean xPBorder = B->x <= Px; + register gboolean yPBorder = B->y <= Py; + + return (((A->x <= Px) == xPBorder) && (xPBorder == (C->x <= Px))) + || (((A->y <= Py) == yPBorder) && (yPBorder == (C->y <= Py))); +} +/** + * p2tr_triangulation_locate_point2: + * @T: A triangulation object + * @X: The point to locate + * @guess: Some triangle near the point, or NULL if not known. + * WARNING! The triangle must be inside the same continuos region as the + * point! If not, this function may return wrong values! + * + * Returns: A triangle containing the point, or NULL if the point is outside the + * triangulation domain. + */ +P2tRTriangle* +p2tr_triangulation_locate_point2 (P2tRTriangulation *T, + gdouble Px, + gdouble Py, + P2tRTriangle *guess, + gdouble *u, + gdouble *v) +{ + if (guess == NULL || ! p2tr_hash_set_contains (T->tris, guess)) + { + /* If we have nothing, check all the triangles. + * TODO: This can probably be improved by sampling several triangles at + * random, picking the closest and using it as a guess.*/ + P2tRTriangle *tr = NULL; + P2trHashSetIter iter; + p2tr_hash_set_iter_init (&iter, T->tris); + while (p2tr_hash_set_iter_next (&iter, (gpointer*)&tr)) + { + if (p2tr_triangule_quick_box_test (tr, Px, Py)) + continue; + else if (p2tr_triangle_compute_barycentric_coords (tr, Px, Py, u, v)) + return tr; + } + return NULL; + } + else + { + /* Maintain a set of checked triangles, and a queue of ones to check. + * For each triangle in the queue, check if it has the point, and if not + * then add it's neighbors at the end of the queue. This also gaurantess + * to some level a search that starts local around the triangles and only + * goes farther if needed. */ + P2tRHashSet *checked = p2tr_hash_set_set_new (g_direct_hash, g_direct_equal, NULL); + P2tRTriangle *result = NULL, *current = NULL; + GQueue tris; + gint i; + + g_queue_init (&tris); + g_queue_push_tail (&tris, guess); + + while (! g_queue_is_empty (&tris)) + { + current = (P2tRTriangle*) g_queue_pop_head (&tris); + if (p2tr_triangle_compute_barycentric_coords (current, Px, Py, u, v)) + { + result = current; + break; + } + else for (i = 0; i < 3; i++) + { + P2tRTriangle *neighbor = current->edges[i]->mirror->tri; + if (neighbor != NULL && ! p2tr_hash_set_contains (checked, neighbor)) + g_queue_push_tail (&tris, current->edges[i]->mirror->tri); + } + + p2tr_hash_set_insert (checked, current); + } + + /* If the queue is empty, then we have nothing to free. It's struct is + * allocated directly on the stack and it has nothing dynamic in it. */ + + g_hash_table_destroy (checked); + + return result; + } +} + +void p2tr_test_point_to_color (P2tRPoint* point, gfloat *dest, gpointer user_data) +{ +/* + GRand* sr = g_rand_new_with_seed ((*((guchar*)&point->x)) ^ (*((guchar*)&point->y))); + gfloat temp; + + temp = (gfloat) g_rand_double (sr); + dest[0] = ABS (temp); + + temp = (gfloat) g_rand_double (sr); + dest[1] = ABS (temp); + + temp = (gfloat) g_rand_double (sr); + dest[2] = ABS (temp); + + dest[3] = 1; +*/ + dest[0] = 0; + dest[1] = 0.5; + dest[2] = 1; +} + +#define uvt3_u(ptr) (((ptr)+0)->u) +#define uvt3_v(ptr) (((ptr)+1)->v) +#define uvt3_t(ptr) (((ptr)+2)->tri) + +void +p2tr_mesh_render_cache_uvt (P2tRTriangulation *T, + P2tRuvt *dest, + P2tRImageConfig *config) +{ + p2tr_mesh_render_cache_uvt_exact (T, dest, config->x_samples * config->y_samples, config); +} + +void +p2tr_mesh_render_cache_uvt_exact (P2tRTriangulation *T, + P2tRuvt *dest, + gint dest_len, + P2tRImageConfig *config) +{ + gint x, y, n = dest_len; + P2tRuvt *uvt = dest; + P2tRTriangle *tr_prev = NULL; + + uvt3_t(uvt) = p2tr_triangulation_locate_point2 (T, config->min_x, config->min_y, NULL, &uvt3_u(uvt), &uvt3_v(uvt)); + tr_prev = uvt3_t(uvt); + + for (y = 0; y < config->y_samples; y++) + for (x = 0; x < config->x_samples; x++) + { + if (n-- == 0) return; + gdouble Px = config->min_x + x * config->step_x; + gdouble Py = config->min_y + y * config->step_y; + uvt3_t(uvt) = p2tr_triangulation_locate_point2 (T, Px, Py, tr_prev, &uvt3_u(uvt), &uvt3_v(uvt)); + tr_prev = uvt3_t(uvt); + uvt += 3; + } +} + + +void +p2tr_mesh_render_scanline (P2tRTriangulation *T, + gfloat *dest, + P2tRImageConfig *config, + P2tRPointToColorFunc pt2col, + gpointer pt2col_user_data) +{ + P2tRuvt *uvt_cache = g_new (P2tRuvt, 3 * config->x_samples * config->y_samples); + GTimer *timer = g_timer_new (); + + g_timer_start (timer); + p2tr_mesh_render_cache_uvt (T, uvt_cache, config); + g_timer_stop (timer); + g_debug ("Mesh preprocessing took %f seconds\n", g_timer_elapsed (timer, NULL)); + + g_timer_start (timer); + p2tr_mesh_render_scanline2 (uvt_cache, dest, config, pt2col, pt2col_user_data); + g_timer_stop (timer); + g_debug ("Mesh rendering took %f seconds\n", g_timer_elapsed (timer, NULL)); + + g_timer_destroy (timer); + g_free (uvt_cache); + +} + + +void +p2tr_mesh_render_scanline2 (P2tRuvt *uvt_cache, + gfloat *dest, + P2tRImageConfig *config, + P2tRPointToColorFunc pt2col, + gpointer pt2col_user_data) +{ + P2tRuvt *uvt_p = uvt_cache; + + gdouble u, v; + P2tRTriangle *tr_prev = NULL, *tr_now; + + gint x, y; + + P2tRPoint *A = NULL, *B = NULL, *C = NULL; + + gfloat *col = g_new (gfloat, config->cpp); + gfloat *colA = g_new (gfloat, config->cpp); + gfloat *colB = g_new (gfloat, config->cpp); + gfloat *colC = g_new (gfloat, config->cpp); + + gfloat *pixel = dest; + + for (y = 0; y < config->y_samples; y++) + for (x = 0; x < config->x_samples; x++) + { + u = uvt3_u (uvt_p); + v = uvt3_v (uvt_p); + tr_now = uvt3_t (uvt_p); + + uvt_p += 3; + + /* If we are outside of the triangulation, set alpha to zero and + * continue */ + if (tr_now == NULL) + { + pixel[3] = 0; + pixel += 4; + } + else + { + /* If the triangle hasn't changed since the previous pixel, + * then don't sample the color at the vertices again, since + * that is an expensive process! */ + if (tr_now != tr_prev) + { + /* Get the points of the triangle in some fixed order, + * just to make sure that the computation goes the same + * everywhere */ + p2tr_triangle_barycentric_get_points (tr_now, &A, &B, &C); + /* At each point X sample the color into colX */ + pt2col (A, colA, pt2col_user_data); + pt2col (B, colB, pt2col_user_data); + pt2col (C, colC, pt2col_user_data); + /* Set the current triangle */ + tr_now = tr_prev; + } + + /* Interpolate the color using barycentric coodinates */ + *pixel++ = USE_BARYCENTRIC (u,v,colA[0],colB[0],colC[0]); + *pixel++ = USE_BARYCENTRIC (u,v,colA[1],colB[1],colC[1]); + *pixel++ = USE_BARYCENTRIC (u,v,colA[2],colB[2],colC[2]); + /* Finally, set as opaque since we are inside the mesh */ + *pixel++ = 1; + } + } +} + +void +p2tr_write_ppm (FILE *f, + gfloat *dest, + P2tRImageConfig *config) +{ + gint x, y; + fprintf (f, "P3\n"); + fprintf (f, "%d %d\n", config->x_samples, config->y_samples); + fprintf (f, "255\n"); + + gfloat *pixel = dest; + + for (y = 0; y < config->y_samples; y++) + { + for (x = 0; x < config->x_samples; x++) + { + if (pixel[3] <= 0.5) + fprintf (f, " 0 0 0"); + else + fprintf (f, "%3d %3d %3d", (guchar)(pixel[0] * 255), (guchar)(pixel[1] * 255), (guchar)(pixel[2] * 255)); + + if (x != config->x_samples - 1) + fprintf (f, " "); + + pixel += 4; + } + fprintf (f, "\n"); + } +} diff --git a/render/mesh-render.h b/render/mesh-render.h new file mode 100755 index 0000000..907d41f --- /dev/null +++ b/render/mesh-render.h @@ -0,0 +1,73 @@ +/* + * File: mesh-render.h + * Author: Barak + * + * Created on 1 אוגוסט 2011, 15:37 + */ + +#ifndef MESH_RENDER_H +#define MESH_RENDER_H + +#ifdef __cplusplus +extern "C" +{ +#endif + +typedef struct { + /* Minimal X and Y coordinates to start sampling at */ + gdouble min_x, min_y; + /* Size of a step in each axis */ + gdouble step_x, step_y; + /* The amount of samples desired in each axis */ + guint x_samples, y_samples; + /* The amount of channels per pixel, both in destination buffer and in the + * colors returned from the matching point-to-color function */ + guint cpp; +} P2tRImageConfig; + +typedef void (*P2tRPointToColorFunc) (P2tRPoint* point, gfloat *dest, gpointer user_data); + +typedef union { + P2tRTriangle *tri; + gdouble u; + gdouble v; +} P2tRuvt; + +void p2tr_test_point_to_color (P2tRPoint* point, gfloat *dest, gpointer user_data); + +void +p2tr_mesh_render_cache_uvt (P2tRTriangulation *T, + P2tRuvt *dest, + P2tRImageConfig *config); + +/* Like the regular version, but cache only the specified amount of + * pixels */ +void +p2tr_mesh_render_cache_uvt_exact (P2tRTriangulation *T, + P2tRuvt *dest, + gint dest_len, + P2tRImageConfig *config); + +void +p2tr_mesh_render_scanline (P2tRTriangulation *T, + gfloat *dest, + P2tRImageConfig *config, + P2tRPointToColorFunc pt2col, + gpointer pt2col_user_data); + +void +p2tr_mesh_render_scanline2 (P2tRuvt *uvt_cache, + gfloat *dest, + P2tRImageConfig *config, + P2tRPointToColorFunc pt2col, + gpointer pt2col_user_data); + + + + +#ifdef __cplusplus +} +#endif + +#endif /* MESH_RENDER_H */ + diff --git a/render/svg-plot.c b/render/svg-plot.c new file mode 100755 index 0000000..d716ace --- /dev/null +++ b/render/svg-plot.c @@ -0,0 +1,330 @@ +#include +#include +#include +#include + +#include "../refine/triangulation.h" + +#include "svg-plot.h" + +void +p2tr_plot_svg_plot_group_start (const gchar *Name, FILE *outfile) +{ + if (Name == NULL) + fprintf (outfile, "" "\n"); + else + fprintf (outfile, "" "\n", Name); +} + +void +p2tr_plot_svg_plot_group_end (FILE *outfile) +{ + fprintf (outfile, "" "\n"); +} + +void +p2tr_plot_svg_plot_line (gdouble x1, gdouble y1, gdouble x2, gdouble y2, const gchar *color, FILE *outfile) +{ + fprintf (outfile, "" "\n", color, PLOT_LINE_WIDTH); + fprintf (outfile, "" "\n"); +} + +void +p2tr_plot_svg_plot_arrow (gdouble x1, gdouble y1, gdouble x2, gdouble y2, const gchar* color, FILE *outfile) +{ + p2tr_plot_svg_plot_line (x1, y1, x2, y2, color, outfile); + + gdouble dy = y2 - y1; + gdouble dx = x2 - x1; + gdouble angle = atan2 (dy, dx); + + gdouble temp = angle - ARROW_SIDE_ANGLE; + p2tr_plot_svg_plot_line (x2, y2, x2 - ARROW_HEAD_SIZE * cos (temp), y2 - ARROW_HEAD_SIZE * sin (temp), color, outfile); + + temp = angle + ARROW_SIDE_ANGLE; + p2tr_plot_svg_plot_line (x2, y2, x2 - ARROW_HEAD_SIZE * cos (temp), y2 - ARROW_HEAD_SIZE * sin (temp), color, outfile); +} + +void +p2tr_plot_svg_fill_triangle (gdouble x1, gdouble y1, gdouble x2, gdouble y2, gdouble x3, gdouble y3, const gchar *color, FILE *outfile) +{ + fprintf (outfile, "" "\n", color); + fprintf (outfile, "" "\n"); +} + +void +p2tr_plot_svg_fill_point (gdouble x1, gdouble y1, const gchar* color, FILE *outfile) +{ + fprintf (outfile, "" "\n", color); + fprintf (outfile, "" "\n"); +} + +void +p2tr_plot_svg_plot_circle (gdouble xc, gdouble yc, gdouble R, const gchar* color, FILE *outfile) +{ + fprintf (outfile, "" "\n", color, PLOT_LINE_WIDTH); + fprintf (outfile, "" "\n"); +} + +void +p2tr_plot_svg_plot_end (FILE *outfile) +{ + fprintf (outfile, "" "\n"); + fprintf (outfile, "" "\n"); +} + +void +p2tr_plot_svg_plot_init (FILE *outfile) +{ + fprintf (outfile, "" "\n"); + fprintf (outfile, "" "\n"); + fprintf (outfile, "" "\n"); + fprintf (outfile, "" "\n"); + fprintf (outfile, "" "\n"); + fprintf (outfile, " " "\n"); + fprintf (outfile, "" "\n"); + fprintf (outfile, " " "\n"); + fprintf (outfile, " " "\n"); + fprintf (outfile, "" "\n"); + fprintf (outfile, "" "\n"); + fprintf (outfile, "" "\n", X_TRANSLATE, Y_TRANSLATE, X_SCALE, Y_SCALE); + + p2tr_plot_svg_plot_arrow (-20, 0, 100, 0, "black", outfile); + p2tr_plot_svg_plot_arrow (0, -20, 0, 100, "black", outfile); +} + +void +p2tr_plot_svg_plot_edge (P2tREdge *self, const gchar* color, FILE* outfile) +{ + gdouble x1 = p2tr_edge_get_start (self)->x; + gdouble y1 = p2tr_edge_get_start (self)->y; + gdouble x2 = p2tr_edge_get_end (self)->x; + gdouble y2 = p2tr_edge_get_end (self)->y; + gdouble R = sqrt ((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)) / 2; + + p2tr_plot_svg_plot_line (x1, y1, x2, y2, color, outfile); + + +// if (p2tr_edge_is_encroached (self)) +// p2tr_plot_svg_plot_circle ((x1 + x2) / 2, (y1 + y2) / 2, R, "red", outfile); +} + +void +p2tr_plot_svg_plot_triangle (P2tRTriangle *self, const gchar* color, FILE* outfile) +{ + P2tRCircle c; + p2tr_triangle_circumcircle (self, &c); + p2tr_plot_svg_plot_edge (self->edges[0], color, outfile); + p2tr_plot_svg_plot_edge (self->edges[1], color, outfile); + p2tr_plot_svg_plot_edge (self->edges[2], color, outfile); + p2tr_plot_svg_plot_circle (c.x, c.y, c.radius, "green", outfile); + p2tr_plot_svg_fill_point (self->edges[0]->end->x, self->edges[0]->end->y, "blue", outfile); + p2tr_plot_svg_fill_point (self->edges[1]->end->x, self->edges[1]->end->y, "blue", outfile); + p2tr_plot_svg_fill_point (self->edges[2]->end->x, self->edges[2]->end->y, "blue", outfile); +} + +void +CCWTest (FILE* outfile) +{ + P2tRPoint *A = p2tr_point_new (50, 50); + gdouble C[8][2] = { + {0, 0}, + {50, 0}, + {100, 0}, + {100, 50}, + {100, 100}, + {50, 100}, + {0, 100}, + {0, 50} + }; + + gint lenC = sizeof (C) / (2 * sizeof (gdouble)); + + gint j; + for (j = 0; j < lenC; j++) + { + gint k; + do + { + k = rand () % lenC; + } + while (C[k][0] == INFINITY && C[k][1] == INFINITY); + + gdouble *h = C[k]; + + p2tr_point_edge_to (A, p2tr_point_new (h[0], h[1])); + + h[0] = h[1] = INFINITY; + } + + gint i = 0; + GList *iter; + + foreach (iter, A->edges) + { + gchar color[18]; + P2tREdge *e = (P2tREdge*) iter->data; + gint val = i * 255 / lenC; + + sprintf (color, "#%02x%02x%02x", val, val, val); + p2tr_plot_svg_plot_edge (e, color, outfile); + i++; + } +} + +void +TriangleClockwiseTest (FILE* outfile) +{ + + const gchar * ecolors[3] = {"#ff0000", "#00ff00", "#0000ff"}; + const gchar * mecolors[3] = {"#770000", "#007700", "#000077"}; + const gchar * ptcolors[3] = {"#ff00ff", "#ffff00", "#00ffff"}; + + const gchar * names[3] = {"A", "B", "C"}; + + P2tRPoint * pts[3]; + int i; + for (i = 0; i < 3; i++) + { + pts[i] = p2tr_point_new (r (), r ()); + } + + P2tREdge * edges[3]; + for (i = 0; i < 3; i++) + { + edges[i] = p2tr_edge_new (pts[i], pts[(i + 1) % 3]); + } + + P2tRTriangle *tri = p2tr_triangle_new (edges[0], edges[1], edges[2], NULL); + + for (i = 0; i < 3; i++) + { + p2tr_plot_svg_plot_edge (tri->edges[i]->mirror, mecolors[i], outfile); + } + + for (i = 0; i < 3; i++) + { + p2tr_plot_svg_plot_edge (tri->edges[i], ecolors[i], outfile); + } + + for (i = 0; i < 3; i++) + { + P2tRPoint *P = p2tr_edge_get_start (tri->edges[i]); + p2tr_plot_svg_fill_point (P->x, P->y, ptcolors[i], outfile); + } +} + +void +refineTest(FILE* outfile) +{ + /* + gdouble RAW[5][2] = {{10,10},{50,50},{55,130},{0,100},{30,50}}; + P2tRPoint *X[5]; + gint N = 5; + */ + gdouble RAW[10][2] = {{10,10},{30,30},{50,50},{52.5,90},{55,130},{27.5,115},{0,100},{15,75},{30,50},{20,30}}; + P2tRPoint *X[10]; + gint N = 10; + + GList *XEs = NULL; + int i; + + for (i = 0; i < N; i++) + { + X[i] = p2tr_point_new (RAW[i][0], RAW[i][1]); + p2tr_plot_svg_fill_point (RAW[i][0], RAW[i][1], "blue", outfile); + } + + fprintf (stderr, "Preparing to work on %d points\n", N); + for (i = 0; i < N; i++) + { + P2tREdge *E = p2tr_edge_new (X[N-i-1], X[N-1-((i+1)%N)]); + XEs = g_list_prepend (XEs, E); + p2tr_edge_set_constrained (E, TRUE); + } + + P2tRTriangulation *T = p2tr_triangulateA (X,N); + + { + GList *liter; + foreach (liter, XEs) + p2tr_validate_edge ((P2tREdge*)liter->data); + } + + DelaunayTerminator (T,XEs,M_PI/6,p2tr_false_delta); + + { + P2trHashSetIter iter; + P2tRTriangle *t; + p2tr_hash_set_iter_init (&iter, T->tris); + while (p2tr_hash_set_iter_next (&iter, (gpointer*)&t)) + { + p2tr_assert_and_explain (t != NULL, "NULL triangle found!\n"); + p2tr_assert_and_explain (t->edges[0] != NULL && t->edges[1] != NULL && t->edges[2] != NULL, + "Removed triangle found!\n"); + p2tr_plot_svg_plot_triangle (t, "black", outfile); + + p2tr_validate_edge (t->edges[0]); + p2tr_validate_edge (t->edges[1]); + p2tr_validate_edge (t->edges[2]); + + } + } + +#if FALSE + GPtrArray* points = mvc_findEdgePoints (T); + //PlotPoints (points); + + P2tRPoint *testX = p2tr_point_new (40, 45); + p2tr_plot_svg_fill_point (testX->x, testX->y, "red"); + /* Give special care for the part after the last point - it may have less + * points than other parts */ + gint div = points->len / 16; + P2tRHashSet *allPts = p2tr_hash_set_set_new (g_direct_hash, g_direct_equal, NULL); + for (i = 0; i < 16; i++) + { + gint index1 = i * div; + gint index2 = MIN ((i + 1) * div, points->len); /* In the last iteration, take the last */ + mvc_makePtList (testX, points, index1, index2, allPts); + } + + { + gint count = 0; + P2trHashSetIter iter; + P2tRPoint *pt; + p2tr_hash_set_iter_init (&iter, allPts); + while (p2tr_hash_set_iter_next (&iter, (gpointer*)&pt)) + { + p2tr_plot_svg_fill_point (pt->x, pt->y, "orange"); + count++; + } + fprintf (stderr, "In total, had %d sample points\n", count); + } +#endif +} + + +void +p2tr_plot_svg (P2tRTriangulation *T, FILE *outfile) +{ + P2trHashSetIter siter; + P2tRTriangle *tr; + + p2tr_debug ("Starting to write SVG output\n"); + p2tr_plot_svg_plot_init (outfile); + + p2tr_hash_set_iter_init (&siter, T->tris); + while (p2tr_hash_set_iter_next (&siter, (gpointer*)&tr)) + p2tr_plot_svg_plot_triangle (tr, "black", outfile); + + p2tr_plot_svg_plot_end (outfile); + p2tr_debug ("Finished writing SVG output\n"); +} \ No newline at end of file diff --git a/render/svg-plot.h b/render/svg-plot.h new file mode 100755 index 0000000..20d7050 --- /dev/null +++ b/render/svg-plot.h @@ -0,0 +1,98 @@ +/* + * This file is a part of Poly2Tri-C - The C port of the Poly2Tri library + * Porting to C done by (c) Barak Itkin + * http://code.google.com/p/poly2tri-c/ + * + * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors + * http://code.google.com/p/poly2tri/ + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without modification, + * are permitted provided that the following conditions are met: + * + * * Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * * Neither the name of Poly2Tri nor the names of its contributors may be + * used to endorse or promote products derived from this software without specific + * prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef SVG_PLOT_H +#define SVG_PLOT_H + +#ifdef __cplusplus +extern "C" +{ +#endif + +#include "../refine/refine.h" + +#define PLOT_LINE_WIDTH 0.40 +#define ARROW_SIDE_ANGLE (M_PI / 180 * 30) +#define ARROW_HEAD_SIZE 2.0 + +#define X_SCALE 3. +#define Y_SCALE 3. +#define X_TRANSLATE 500. +#define Y_TRANSLATE 500. + +void +p2tr_plot_svg_plot_group_start (const gchar *Name, FILE* outfile); + +void +p2tr_plot_svg_plot_group_end (FILE* outfile); + +void +p2tr_plot_svg_plot_line (gdouble x1, gdouble y1, gdouble x2, gdouble y2, const gchar *color, FILE* outfile); + +void +p2tr_plot_svg_plot_arrow (gdouble x1, gdouble y1, gdouble x2, gdouble y2, const gchar* color, FILE* outfile); + +void +p2tr_plot_svg_fill_triangle (gdouble x1, gdouble y1, gdouble x2, gdouble y2, gdouble x3, gdouble y3, const gchar *color, FILE* outfile); + +void +p2tr_plot_svg_fill_point (gdouble x1, gdouble y1, const gchar* color, FILE* outfile); + +void +p2tr_plot_svg_plot_circle (gdouble xc, gdouble yc, gdouble R, const gchar* color, FILE* outfile); + +void +p2tr_plot_svg_plot_end (FILE* outfile); + +void +p2tr_plot_svg_plot_init (FILE* outfile); + +void +p2tr_plot_svg_plot_edge (P2tREdge *self, const gchar* color, FILE* outfile); + +void +p2tr_plot_svg_plot_triangle (P2tRTriangle *self, const gchar* color, FILE* outfile); + +#define r() (10+(rand () % 91)) + +void +p2tr_plot_svg (P2tRTriangulation *T, FILE* outfile); + +#ifdef __cplusplus +} +#endif + +#endif /* SVG_PLOT_H */ + diff --git a/sweep/advancing_front.c b/sweep/advancing_front.c new file mode 100755 index 0000000..ca3c993 --- /dev/null +++ b/sweep/advancing_front.c @@ -0,0 +1,224 @@ +/* + * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors + * http://code.google.com/p/poly2tri/ + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without modification, + * are permitted provided that the following conditions are met: + * + * * Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * * Neither the name of Poly2Tri nor the names of its contributors may be + * used to endorse or promote products derived from this software without specific + * prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ +#include "advancing_front.h" + +void +p2t_node_init_pt (P2tNode* THIS, P2tPoint* p) +{ + THIS->point = p; + THIS->triangle = NULL; + THIS->value = p->x; + THIS->next = NULL; + THIS->prev = NULL; +} + +P2tNode* +p2t_node_new_pt (P2tPoint* p) +{ + P2tNode* THIS = g_slice_new (P2tNode); + p2t_node_init_pt (THIS, p); + return THIS; +} + +void +p2t_node_init_pt_tr (P2tNode* THIS, P2tPoint* p, P2tTriangle* t) +{ + THIS->point = p; + THIS->triangle = t; + THIS->value = p->x; + THIS->next = NULL; + THIS->prev = NULL; +} + +P2tNode* +p2t_node_new_pt_tr (P2tPoint* p, P2tTriangle* t) +{ + P2tNode* THIS = g_slice_new (P2tNode); + p2t_node_init_pt_tr (THIS, p, t); + return THIS; +} + +void p2t_node_destroy (P2tNode* THIS) +{ +} +void p2t_node_free (P2tNode* THIS) +{ + p2t_node_destroy (THIS); + g_slice_free (P2tNode, THIS); +} + +void +p2t_advancingfront_init (P2tAdvancingFront* THIS, P2tNode* head, P2tNode* tail) +{ + THIS->head_ = head; + THIS->tail_ = tail; + THIS->search_node_ = head; +} + +P2tAdvancingFront* +p2t_advancingfront_new (P2tNode* head, P2tNode* tail) +{ + P2tAdvancingFront* THIS = g_slice_new (P2tAdvancingFront); + p2t_advancingfront_init (THIS, head, tail); + return THIS; +} + +void +p2t_advancingfront_destroy (P2tAdvancingFront* THIS) { } + +void +p2t_advancingfront_free (P2tAdvancingFront* THIS) +{ + p2t_advancingfront_destroy (THIS); + g_slice_free (P2tAdvancingFront, THIS); +} + +P2tNode* +p2t_advancingfront_locate_node (P2tAdvancingFront *THIS, const double x) +{ + P2tNode* node = THIS->search_node_; + + if (x < node->value) + { + while ((node = node->prev) != NULL) + { + if (x >= node->value) + { + THIS->search_node_ = node; + return node; + } + } + } + else + { + while ((node = node->next) != NULL) + { + if (x < node->value) + { + THIS->search_node_ = node->prev; + return node->prev; + } + } + } + return NULL; +} + +P2tNode* +p2t_advancingfront_find_search_node (P2tAdvancingFront *THIS, const double x) +{ + // TODO: implement BST index + return THIS->search_node_; +} + +P2tNode* +p2t_advancingfront_locate_point (P2tAdvancingFront *THIS, const P2tPoint* point) +{ + const double px = point->x; + P2tNode* node = p2t_advancingfront_find_search_node (THIS, px); + const double nx = node->point->x; + + if (px == nx) + { + if (point != node->point) + { + // We might have two nodes with same x value for a short time + if (point == node->prev->point) + { + node = node->prev; + } + else if (point == node->next->point) + { + node = node->next; + } + else + { + assert (0); + } + } + } + else if (px < nx) + { + while ((node = node->prev) != NULL) + { + if (point == node->point) + { + break; + } + } + } + else + { + while ((node = node->next) != NULL) + { + if (point == node->point) + break; + } + } + if (node) THIS->search_node_ = node; + return node; +} + +P2tNode* +p2t_advancingfront_head (P2tAdvancingFront *THIS) +{ + return THIS->head_; +} + +void +AdvancingFront_set_head (P2tAdvancingFront *THIS, P2tNode* node) +{ + THIS->head_ = node; +} + +P2tNode* +p2t_advancingfront_tail (P2tAdvancingFront *THIS) +{ + return THIS->tail_; +} + +void +p2t_advancingfront_set_tail (P2tAdvancingFront *THIS, P2tNode* node) +{ + THIS->tail_ = node; +} + +P2tNode* +p2t_advancingfront_search (P2tAdvancingFront *THIS) +{ + return THIS->search_node_; +} + +void +p2t_advancingfront_set_search (P2tAdvancingFront *THIS, P2tNode* node) +{ + THIS->search_node_ = node; +} + diff --git a/sweep/advancing_front.h b/sweep/advancing_front.h new file mode 100755 index 0000000..44ef55e --- /dev/null +++ b/sweep/advancing_front.h @@ -0,0 +1,88 @@ +/* + * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors + * http://code.google.com/p/poly2tri/ + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without modification, + * are permitted provided that the following conditions are met: + * + * * Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * * Neither the name of Poly2Tri nor the names of its contributors may be + * used to endorse or promote products derived from this software without specific + * prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef ADVANCED_FRONT_H +#define ADVANCED_FRONT_H + +#include "../common/poly2tri-private.h" +#include "../common/shapes.h" + +// Advancing front node + +struct _P2tNode +{ + P2tPoint* point; + P2tTriangle* triangle; + + struct _P2tNode* next; + struct _P2tNode* prev; + + double value; +}; + +void p2t_node_init_pt (P2tNode* THIS, P2tPoint* p); +P2tNode* p2t_node_new_pt (P2tPoint* p); +void p2t_node_init_pt_tr (P2tNode* THIS, P2tPoint* p, P2tTriangle* t); +P2tNode* p2t_node_new_pt_tr (P2tPoint* p, P2tTriangle* t); +void p2t_node_destroy (P2tNode* THIS); +void p2t_node_free (P2tNode* THIS); + +// Advancing front + +struct AdvancingFront_ +{ + //private: + + P2tNode* head_, *tail_, *search_node_; + +}; + +void p2t_advancingfront_init (P2tAdvancingFront* THIS, P2tNode* head, P2tNode* tail); +P2tAdvancingFront* p2t_advancingfront_new (P2tNode* head, P2tNode* tail); + +void p2t_advancingfront_destroy (P2tAdvancingFront* THIS); +void p2t_advancingfront_free (P2tAdvancingFront* THIS); + +P2tNode* p2t_advancingfront_head (P2tAdvancingFront *THIS); +void AdvancingFront_set_head (P2tAdvancingFront *THIS, P2tNode* node); +P2tNode* p2t_advancingfront_tail (P2tAdvancingFront *THIS); +void p2t_advancingfront_set_tail (P2tAdvancingFront *THIS, P2tNode* node); +P2tNode* p2t_advancingfront_search (P2tAdvancingFront *THIS); +void p2t_advancingfront_set_search (P2tAdvancingFront *THIS, P2tNode* node); + +/// Locate insertion point along advancing front +P2tNode* p2t_advancingfront_locate_node (P2tAdvancingFront *THIS, const double x); + +P2tNode* p2t_advancingfront_locate_point (P2tAdvancingFront *THIS, const P2tPoint* point); + +P2tNode* p2t_advancingfront_find_search_node (P2tAdvancingFront *THIS, const double x); + +#endif diff --git a/sweep/cdt.c b/sweep/cdt.c new file mode 100755 index 0000000..49785e6 --- /dev/null +++ b/sweep/cdt.c @@ -0,0 +1,90 @@ +/* + * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors + * http://code.google.com/p/poly2tri/ + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without modification, + * are permitted provided that the following conditions are met: + * + * * Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * * Neither the name of Poly2Tri nor the names of its contributors may be + * used to endorse or promote products derived from this software without specific + * prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ +#include "cdt.h" + +void +p2t_cdt_init (P2tCDT* THIS, P2tPointPtrArray polyline) +{ + THIS->sweep_context_ = p2t_sweepcontext_new (polyline); + THIS->sweep_ = p2t_sweep_new (); +} + +P2tCDT* +p2t_cdt_new (P2tPointPtrArray polyline) +{ + P2tCDT* THIS = g_slice_new (P2tCDT); + p2t_cdt_init (THIS, polyline); + return THIS; +} + +void +p2t_cdt_destroy (P2tCDT* THIS) +{ + p2t_sweepcontext_delete (THIS->sweep_context_); + p2t_sweep_free (THIS->sweep_); +} + +void +p2t_cdt_free (P2tCDT* THIS) +{ + p2t_cdt_destroy (THIS); + g_slice_free (P2tCDT, THIS); +} + +void +p2t_cdt_add_hole (P2tCDT *THIS, P2tPointPtrArray polyline) +{ + p2t_sweepcontext_add_hole (THIS->sweep_context_, polyline); +} + +void +p2t_cdt_add_point (P2tCDT *THIS, P2tPoint* point) +{ + p2t_sweepcontext_add_point (THIS->sweep_context_, point); +} + +void +p2t_cdt_triangulate (P2tCDT *THIS) +{ + p2t_sweep_triangulate (THIS->sweep_, THIS->sweep_context_); +} + +P2tTrianglePtrArray +p2t_cdt_get_triangles (P2tCDT *THIS) +{ + return p2t_sweepcontext_get_triangles (THIS->sweep_context_); +} + +P2tTrianglePtrList +p2t_cdt_get_map (P2tCDT *THIS) +{ + return p2t_sweepcontext_get_map (THIS->sweep_context_); +} diff --git a/sweep/cdt.h b/sweep/cdt.h new file mode 100755 index 0000000..bd40198 --- /dev/null +++ b/sweep/cdt.h @@ -0,0 +1,101 @@ +/* + * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors + * http://code.google.com/p/poly2tri/ + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without modification, + * are permitted provided that the following conditions are met: + * + * * Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * * Neither the name of Poly2Tri nor the names of its contributors may be + * used to endorse or promote products derived from this software without specific + * prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef CDT_H +#define CDT_H + +#include "../common/poly2tri-private.h" +#include "advancing_front.h" +#include "sweep_context.h" +#include "sweep.h" + +/** + * + * @author Mason Green + * + */ + +struct CDT_ +{ + //private: + + /** + * Internals + */ + + P2tSweepContext* sweep_context_; + P2tSweep* sweep_; + +}; +/** + * Constructor - add polyline with non repeating points + * + * @param polyline + */ +void p2t_cdt_init (P2tCDT* THIS, P2tPointPtrArray polyline); +P2tCDT* p2t_cdt_new (P2tPointPtrArray polyline); + +/** + * Destructor - clean up memory + */ +void p2t_cdt_destroy (P2tCDT* THIS); +void p2t_cdt_free (P2tCDT* THIS); + +/** + * Add a hole + * + * @param polyline + */ +void p2t_cdt_add_hole (P2tCDT *THIS, P2tPointPtrArray polyline); + +/** + * Add a steiner point + * + * @param point + */ +void p2t_cdt_add_point (P2tCDT *THIS, P2tPoint* point); + +/** + * Triangulate - do this AFTER you've added the polyline, holes, and Steiner points + */ +void p2t_cdt_triangulate (P2tCDT *THIS); + +/** + * Get CDT triangles + */ +P2tTrianglePtrArray p2t_cdt_get_triangles (P2tCDT *THIS); + +/** + * Get triangle map + */ +P2tTrianglePtrList p2t_cdt_get_map (P2tCDT *THIS); + +#endif diff --git a/sweep/sweep.c b/sweep/sweep.c new file mode 100755 index 0000000..147191c --- /dev/null +++ b/sweep/sweep.c @@ -0,0 +1,932 @@ +/* + * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors + * http://code.google.com/p/poly2tri/ + * + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without modification, + * are permitted provided that the following conditions are met: + * + * * Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * * Neither the name of Poly2Tri nor the names of its contributors may be + * used to endorse or promote products derived from this software without specific + * prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ +#include "sweep.h" +#include "sweep_context.h" +#include "advancing_front.h" +#include "../common/utils.h" +#include "../common/shapes.h" + +void +p2t_sweep_init (P2tSweep* THIS) +{ + THIS->nodes_ = g_ptr_array_new (); +} + +P2tSweep* +p2t_sweep_new () +{ + P2tSweep* THIS = g_new (P2tSweep, 1); + p2t_sweep_init (THIS); + return THIS; +} + +/** + * Destructor - clean up memory + */ +void +p2t_sweep_destroy (P2tSweep* THIS) +{ + int i; + // Clean up memory + for (i = 0; i < THIS->nodes_->len; i++) + { + p2t_node_free (node_index (THIS->nodes_, i)); + } + + g_ptr_array_free (THIS->nodes_, TRUE); +} + +void +p2t_sweep_free (P2tSweep* THIS) +{ + p2t_sweep_destroy (THIS); + g_free (THIS); +} + +// Triangulate simple polygon with holes + +void +p2t_sweep_triangulate (P2tSweep *THIS, P2tSweepContext *tcx) +{ + p2t_sweepcontext_init_triangulation (tcx); + p2t_sweepcontext_create_advancingfront (tcx, THIS->nodes_); + // Sweep points; build mesh + p2t_sweep_sweep_points (THIS, tcx); + // Clean up + p2t_sweep_finalization_polygon (THIS, tcx); +} + +void +p2t_sweep_sweep_points (P2tSweep *THIS, P2tSweepContext *tcx) +{ + int i, j; + for (i = 1; i < p2t_sweepcontext_point_count (tcx); i++) + { + P2tPoint* point = p2t_sweepcontext_get_point (tcx, i); + P2tNode* node = p2t_sweep_point_event (THIS, tcx, point); + for (j = 0; j < point->edge_list->len; j++) + { + p2t_sweep_edge_event_ed_n (THIS, tcx, edge_index (point->edge_list, j), node); + } + } +} + +void +p2t_sweep_finalization_polygon (P2tSweep *THIS, P2tSweepContext *tcx) +{ + // Get an Internal triangle to start with + P2tTriangle* t = p2t_advancingfront_head (p2t_sweepcontext_front (tcx))->next->triangle; + P2tPoint* p = p2t_advancingfront_head (p2t_sweepcontext_front (tcx))->next->point; + while (!p2t_triangle_get_constrained_edge_cw (t, p)) + { + t = p2t_triangle_neighbor_ccw (t, p); + } + + // Collect interior triangles constrained by edges + p2t_sweepcontext_mesh_clean (tcx, t); +} + +P2tNode* +p2t_sweep_point_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tPoint* point) +{ + P2tNode* node = p2t_sweepcontext_locate_node (tcx, point); + P2tNode* new_node = p2t_sweep_new_front_triangle (THIS, tcx, point, node); + + // Only need to check +epsilon since point never have smaller + // x value than node due to how we fetch nodes from the front + if (point->x <= node->point->x + EPSILON) + { + p2t_sweep_fill (THIS, tcx, node); + } + + //tcx.AddNode(new_node); + + p2t_sweep_fill_advancingfront (THIS, tcx, new_node); + return new_node; +} + +void +p2t_sweep_edge_event_ed_n (P2tSweep *THIS, P2tSweepContext *tcx, P2tEdge* edge, P2tNode* node) +{ + tcx->edge_event.constrained_edge = edge; + tcx->edge_event.right = (edge->p->x > edge->q->x); + + if (p2t_sweep_is_edge_side_of_triangle (THIS, node->triangle, edge->p, edge->q)) + { + return; + } + + // For now we will do all needed filling + // TODO: integrate with flip process might give some better performance + // but for now this avoid the issue with cases that needs both flips and fills + p2t_sweep_fill_edge_event (THIS, tcx, edge, node); + p2t_sweep_edge_event_pt_pt_tr_pt (THIS, tcx, edge->p, edge->q, node->triangle, edge->q); +} + +void +p2t_sweep_edge_event_pt_pt_tr_pt (P2tSweep *THIS, P2tSweepContext *tcx, P2tPoint* ep, P2tPoint* eq, P2tTriangle* triangle, P2tPoint* point) +{ + if (p2t_sweep_is_edge_side_of_triangle (THIS, triangle, ep, eq)) + { + return; + } + + P2tPoint* p1 = p2t_triangle_point_ccw (triangle, point); + P2tOrientation o1 = p2t_orient2d (eq, p1, ep); + if (o1 == COLLINEAR) + { + if (p2t_triangle_contains_pt_pt (triangle, eq, p1)) + { + p2t_triangle_mark_constrained_edge_pt_pt (triangle, eq, p1); + // We are modifying the constraint maybe it would be better to + // not change the given constraint and just keep a variable for the new constraint + tcx->edge_event.constrained_edge->q = p1; + triangle = p2t_triangle_neighbor_across (triangle, point); + p2t_sweep_edge_event_pt_pt_tr_pt (THIS, tcx, ep, p1, triangle, p1); + } + else + { + g_error ("EdgeEvent - collinear points not supported"); + } + return; + } + + P2tPoint* p2 = p2t_triangle_point_cw (triangle, point); + P2tOrientation o2 = p2t_orient2d (eq, p2, ep); + if (o2 == COLLINEAR) + { + if (p2t_triangle_contains_pt_pt (triangle, eq, p2)) + { + p2t_triangle_mark_constrained_edge_pt_pt (triangle, eq, p2); + // We are modifying the constraint maybe it would be better to + // not change the given constraint and just keep a variable for the new constraint + tcx->edge_event.constrained_edge->q = p2; + triangle = p2t_triangle_neighbor_across (triangle, point); + p2t_sweep_edge_event_pt_pt_tr_pt (THIS, tcx, ep, p2, triangle, p2); + } + else + { + g_error ("EdgeEvent - collinear points not supported"); + } + return; + } + + if (o1 == o2) + { + // Need to decide if we are rotating CW or CCW to get to a triangle + // that will cross edge + if (o1 == CW) + { + triangle = p2t_triangle_neighbor_ccw (triangle, point); + } + else + { + triangle = p2t_triangle_neighbor_cw (triangle, point); + } + p2t_sweep_edge_event_pt_pt_tr_pt (THIS, tcx, ep, eq, triangle, point); + } + else + { + // This triangle crosses constraint so lets flippin start! + p2t_sweep_flip_edge_event (THIS, tcx, ep, eq, triangle, point); + } +} + +gboolean +p2t_sweep_is_edge_side_of_triangle (P2tSweep *THIS, P2tTriangle *triangle, P2tPoint* ep, P2tPoint* eq) +{ + int index = p2t_triangle_edge_index (triangle, ep, eq); + + if (index != -1) + { + p2t_triangle_mark_constrained_edge_i (triangle, index); + P2tTriangle* t = p2t_triangle_get_neighbor (triangle, index); + if (t) + { + p2t_triangle_mark_constrained_edge_pt_pt (t, ep, eq); + } + return TRUE; + } + return FALSE; +} + +P2tNode* +p2t_sweep_new_front_triangle (P2tSweep *THIS, P2tSweepContext *tcx, P2tPoint* point, P2tNode *node) +{ + P2tTriangle* triangle = p2t_triangle_new (point, node->point, node->next->point); + + p2t_triangle_mark_neighbor_tr (triangle, node->triangle); + p2t_sweepcontext_add_to_map (tcx, triangle); + + P2tNode* new_node = p2t_node_new_pt (point); + g_ptr_array_add (THIS->nodes_, new_node); + + new_node->next = node->next; + new_node->prev = node; + node->next->prev = new_node; + node->next = new_node; + + if (!p2t_sweep_legalize (THIS, tcx, triangle)) + { + p2t_sweepcontext_map_triangle_to_nodes (tcx, triangle); + } + + return new_node; +} + +void +p2t_sweep_fill (P2tSweep *THIS, P2tSweepContext *tcx, P2tNode* node) +{ + P2tTriangle* triangle = p2t_triangle_new (node->prev->point, node->point, node->next->point); + + // TODO: should copy the constrained_edge value from neighbor triangles + // for now constrained_edge values are copied during the legalize + p2t_triangle_mark_neighbor_tr (triangle, node->prev->triangle); + p2t_triangle_mark_neighbor_tr (triangle, node->triangle); + + p2t_sweepcontext_add_to_map (tcx, triangle); + + // Update the advancing front + node->prev->next = node->next; + node->next->prev = node->prev; + + // If it was legalized the triangle has already been mapped + if (!p2t_sweep_legalize (THIS, tcx, triangle)) + { + p2t_sweepcontext_map_triangle_to_nodes (tcx, triangle); + } + +} + +void +p2t_sweep_fill_advancingfront (P2tSweep *THIS, P2tSweepContext *tcx, P2tNode* n) +{ + + // Fill right holes + P2tNode* node = n->next; + + while (node->next) + { + double angle = p2t_sweep_hole_angle (THIS, node); + if (angle > M_PI_2 || angle < -M_PI_2) break; + p2t_sweep_fill (THIS, tcx, node); + node = node->next; + } + + // Fill left holes + node = n->prev; + + while (node->prev) + { + double angle = p2t_sweep_hole_angle (THIS, node); + if (angle > M_PI_2 || angle < -M_PI_2) break; + p2t_sweep_fill (THIS, tcx, node); + node = node->prev; + } + + // Fill right basins + if (n->next && n->next->next) + { + double angle = p2t_sweep_basin_angle (THIS, n); + if (angle < PI_3div4) + { + p2t_sweep_fill_basin (THIS, tcx, n); + } + } +} + +double +p2t_sweep_basin_angle (P2tSweep *THIS, P2tNode* node) +{ + double ax = node->point->x - node->next->next->point->x; + double ay = node->point->y - node->next->next->point->y; + return atan2 (ay, ax); +} + +double +p2t_sweep_hole_angle (P2tSweep *THIS, P2tNode* node) +{ + /* Complex plane + * ab = cosA +i*sinA + * ab = (ax + ay*i)(bx + by*i) = (ax*bx + ay*by) + i(ax*by-ay*bx) + * atan2(y,x) computes the principal value of the argument function + * applied to the complex number x+iy + * Where x = ax*bx + ay*by + * y = ax*by - ay*bx + */ + double ax = node->next->point->x - node->point->x; + double ay = node->next->point->y - node->point->y; + double bx = node->prev->point->x - node->point->x; + double by = node->prev->point->y - node->point->y; + return atan2 (ax * by - ay * bx, ax * bx + ay * by); +} + +gboolean +p2t_sweep_legalize (P2tSweep *THIS, P2tSweepContext *tcx, P2tTriangle *t) +{ + int i; + // To legalize a triangle we start by finding if any of the three edges + // violate the Delaunay condition + for (i = 0; i < 3; i++) + { + if (t->delaunay_edge[i]) + continue; + + P2tTriangle* ot = p2t_triangle_get_neighbor (t, i); + + if (ot) + { + P2tPoint* p = p2t_triangle_get_point (t, i); + P2tPoint* op = p2t_triangle_opposite_point (ot, t, p); + int oi = p2t_triangle_index (ot, op); + + // If this is a Constrained Edge or a Delaunay Edge(only during recursive legalization) + // then we should not try to legalize + if (ot->constrained_edge[oi] || ot->delaunay_edge[oi]) + { + t->constrained_edge[i] = ot->constrained_edge[oi]; + continue; + } + + gboolean inside = p2t_sweep_incircle (THIS, p, p2t_triangle_point_ccw (t, p), p2t_triangle_point_cw (t, p), op); + + if (inside) + { + // Lets mark this shared edge as Delaunay + t->delaunay_edge[i] = TRUE; + ot->delaunay_edge[oi] = TRUE; + + // Lets rotate shared edge one vertex CW to legalize it + p2t_sweep_rotate_triangle_pair (THIS, t, p, ot, op); + + // We now got one valid Delaunay Edge shared by two triangles + // This gives us 4 new edges to check for Delaunay + + // Make sure that triangle to node mapping is done only one time for a specific triangle + gboolean not_legalized = !p2t_sweep_legalize (THIS, tcx, t); + if (not_legalized) + { + p2t_sweepcontext_map_triangle_to_nodes (tcx, t); + } + + not_legalized = !p2t_sweep_legalize (THIS, tcx, ot); + if (not_legalized) + p2t_sweepcontext_map_triangle_to_nodes (tcx, ot); + + // Reset the Delaunay edges, since they only are valid Delaunay edges + // until we add a new triangle or point. + // XXX: need to think about this. Can these edges be tried after we + // return to previous recursive level? + t->delaunay_edge[i] = FALSE; + ot->delaunay_edge[oi] = FALSE; + + // If triangle have been legalized no need to check the other edges since + // the recursive legalization will handles those so we can end here. + return TRUE; + } + } + } + return FALSE; +} + +gboolean +p2t_sweep_incircle (P2tSweep *THIS, P2tPoint* pa, P2tPoint* pb, P2tPoint* pc, P2tPoint* pd) +{ + double adx = pa->x - pd->x; + double ady = pa->y - pd->y; + double bdx = pb->x - pd->x; + double bdy = pb->y - pd->y; + + double adxbdy = adx * bdy; + double bdxady = bdx * ady; + double oabd = adxbdy - bdxady; + + if (oabd <= 0) + return FALSE; + + double cdx = pc->x - pd->x; + double cdy = pc->y - pd->y; + + double cdxady = cdx * ady; + double adxcdy = adx * cdy; + double ocad = cdxady - adxcdy; + + if (ocad <= 0) + return FALSE; + + double bdxcdy = bdx * cdy; + double cdxbdy = cdx * bdy; + + double alift = adx * adx + ady * ady; + double blift = bdx * bdx + bdy * bdy; + double clift = cdx * cdx + cdy * cdy; + + double det = alift * (bdxcdy - cdxbdy) + blift * ocad + clift * oabd; + + return det > 0; +} + +void +p2t_sweep_rotate_triangle_pair (P2tSweep *THIS, P2tTriangle *t, P2tPoint* p, P2tTriangle *ot, P2tPoint* op) +{ + P2tTriangle* n1, *n2, *n3, *n4; + n1 = p2t_triangle_neighbor_ccw (t, p); + n2 = p2t_triangle_neighbor_cw (t, p); + n3 = p2t_triangle_neighbor_ccw (ot, op); + n4 = p2t_triangle_neighbor_cw (ot, op); + + gboolean ce1, ce2, ce3, ce4; + ce1 = p2t_triangle_get_constrained_edge_ccw (t, p); + ce2 = p2t_triangle_get_constrained_edge_cw (t, p); + ce3 = p2t_triangle_get_constrained_edge_ccw (ot, op); + ce4 = p2t_triangle_get_constrained_edge_cw (ot, op); + + gboolean de1, de2, de3, de4; + de1 = p2t_triangle_get_delunay_edge_ccw (t, p); + de2 = p2t_triangle_get_delunay_edge_cw (t, p); + de3 = p2t_triangle_get_delunay_edge_ccw (ot, op); + de4 = p2t_triangle_get_delunay_edge_cw (ot, op); + + p2t_triangle_legalize_pt_pt (t, p, op); + p2t_triangle_legalize_pt_pt (ot, op, p); + + // Remap delaunay_edge + p2t_triangle_set_delunay_edge_ccw (ot, p, de1); + p2t_triangle_set_delunay_edge_cw (t, p, de2); + p2t_triangle_set_delunay_edge_ccw (t, op, de3); + p2t_triangle_set_delunay_edge_cw (ot, op, de4); + + // Remap constrained_edge + p2t_triangle_set_constrained_edge_ccw (ot, p, ce1); + p2t_triangle_set_constrained_edge_cw (t, p, ce2); + p2t_triangle_set_constrained_edge_ccw (t, op, ce3); + p2t_triangle_set_constrained_edge_cw (ot, op, ce4); + + // Remap neighbors + // XXX: might optimize the markNeighbor by keeping track of + // what side should be assigned to what neighbor after the + // rotation. Now mark neighbor does lots of testing to find + // the right side. + p2t_triangle_clear_neighbors (t); + p2t_triangle_clear_neighbors (ot); + if (n1) p2t_triangle_mark_neighbor_tr (ot, n1); + if (n2) p2t_triangle_mark_neighbor_tr (t, n2); + if (n3) p2t_triangle_mark_neighbor_tr (t, n3); + if (n4) p2t_triangle_mark_neighbor_tr (ot, n4); + p2t_triangle_mark_neighbor_tr (t, ot); +} + +void +p2t_sweep_fill_basin (P2tSweep *THIS, P2tSweepContext *tcx, P2tNode* node) +{ + if (p2t_orient2d (node->point, node->next->point, node->next->next->point) == CCW) + { + tcx->basin.left_node = node->next->next; + } + else + { + tcx->basin.left_node = node->next; + } + + // Find the bottom and right node + tcx->basin.bottom_node = tcx->basin.left_node; + while (tcx->basin.bottom_node->next + && tcx->basin.bottom_node->point->y >= tcx->basin.bottom_node->next->point->y) + { + tcx->basin.bottom_node = tcx->basin.bottom_node->next; + } + if (tcx->basin.bottom_node == tcx->basin.left_node) + { + // No valid basin + return; + } + + tcx->basin.right_node = tcx->basin.bottom_node; + while (tcx->basin.right_node->next + && tcx->basin.right_node->point->y < tcx->basin.right_node->next->point->y) + { + tcx->basin.right_node = tcx->basin.right_node->next; + } + if (tcx->basin.right_node == tcx->basin.bottom_node) + { + // No valid basins + return; + } + + tcx->basin.width = tcx->basin.right_node->point->x - tcx->basin.left_node->point->x; + tcx->basin.left_highest = tcx->basin.left_node->point->y > tcx->basin.right_node->point->y; + + p2t_sweep_fill_basin_req (THIS, tcx, tcx->basin.bottom_node); +} + +void +p2t_sweep_fill_basin_req (P2tSweep *THIS, P2tSweepContext *tcx, P2tNode* node) +{ + // if shallow stop filling + if (p2t_sweep_is_shallow (THIS, tcx, node)) + { + return; + } + + p2t_sweep_fill (THIS, tcx, node); + + if (node->prev == tcx->basin.left_node && node->next == tcx->basin.right_node) + { + return; + } + else if (node->prev == tcx->basin.left_node) + { + P2tOrientation o = p2t_orient2d (node->point, node->next->point, node->next->next->point); + if (o == CW) + { + return; + } + node = node->next; + } + else if (node->next == tcx->basin.right_node) + { + P2tOrientation o = p2t_orient2d (node->point, node->prev->point, node->prev->prev->point); + if (o == CCW) + { + return; + } + node = node->prev; + } + else + { + // Continue with the neighbor node with lowest Y value + if (node->prev->point->y < node->next->point->y) + { + node = node->prev; + } + else + { + node = node->next; + } + } + + p2t_sweep_fill_basin_req (THIS, tcx, node); +} + +gboolean +p2t_sweep_is_shallow (P2tSweep *THIS, P2tSweepContext *tcx, P2tNode* node) +{ + double height; + + if (tcx->basin.left_highest) + { + height = tcx->basin.left_node->point->y - node->point->y; + } + else + { + height = tcx->basin.right_node->point->y - node->point->y; + } + + // if shallow stop filling + if (tcx->basin.width > height) + { + return TRUE; + } + return FALSE; +} + +void +p2t_sweep_fill_edge_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tEdge* edge, P2tNode* node) +{ + if (tcx->edge_event.right) + { + p2t_sweep_fill_right_above_edge_event (THIS, tcx, edge, node); + } + else + { + p2t_sweep_fill_left_above_edge_event (THIS, tcx, edge, node); + } +} + +void +p2t_sweep_fill_right_above_edge_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tEdge* edge, P2tNode* node) +{ + while (node->next->point->x < edge->p->x) + { + // Check if next node is below the edge + if (p2t_orient2d (edge->q, node->next->point, edge->p) == CCW) + { + p2t_sweep_fill_right_below_edge_event (THIS, tcx, edge, node); + } + else + { + node = node->next; + } + } +} + +void +p2t_sweep_fill_right_below_edge_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tEdge* edge, P2tNode* node) +{ + if (node->point->x < edge->p->x) + { + if (p2t_orient2d (node->point, node->next->point, node->next->next->point) == CCW) + { + // Concave + p2t_sweep_fill_right_concave_edge_event (THIS, tcx, edge, node); + } + else + { + // Convex + p2t_sweep_fill_right_convex_edge_event (THIS, tcx, edge, node); + // Retry this one + p2t_sweep_fill_right_below_edge_event (THIS, tcx, edge, node); + } + } +} + +void +p2t_sweep_fill_right_concave_edge_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tEdge* edge, P2tNode* node) +{ + p2t_sweep_fill (THIS, tcx, node->next); + if (node->next->point != edge->p) + { + // Next above or below edge? + if (p2t_orient2d (edge->q, node->next->point, edge->p) == CCW) + { + // Below + if (p2t_orient2d (node->point, node->next->point, node->next->next->point) == CCW) + { + // Next is concave + p2t_sweep_fill_right_concave_edge_event (THIS, tcx, edge, node); + } + else + { + // Next is convex + } + } + } + +} + +void +p2t_sweep_fill_right_convex_edge_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tEdge* edge, P2tNode* node) +{ + // Next concave or convex? + if (p2t_orient2d (node->next->point, node->next->next->point, node->next->next->next->point) == CCW) + { + // Concave + p2t_sweep_fill_right_concave_edge_event (THIS, tcx, edge, node->next); + } + else + { + // Convex + // Next above or below edge? + if (p2t_orient2d (edge->q, node->next->next->point, edge->p) == CCW) + { + // Below + p2t_sweep_fill_right_convex_edge_event (THIS, tcx, edge, node->next); + } + else + { + // Above + } + } +} + +void +p2t_sweep_fill_left_above_edge_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tEdge* edge, P2tNode* node) +{ + while (node->prev->point->x > edge->p->x) + { + // Check if next node is below the edge + if (p2t_orient2d (edge->q, node->prev->point, edge->p) == CW) + { + p2t_sweep_fill_left_below_edge_event (THIS, tcx, edge, node); + } + else + { + node = node->prev; + } + } +} + +void +p2t_sweep_fill_left_below_edge_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tEdge* edge, P2tNode* node) +{ + if (node->point->x > edge->p->x) + { + if (p2t_orient2d (node->point, node->prev->point, node->prev->prev->point) == CW) + { + // Concave + p2t_sweep_fill_left_concave_edge_event (THIS, tcx, edge, node); + } + else + { + // Convex + p2t_sweep_fill_left_convex_edge_event (THIS, tcx, edge, node); + // Retry this one + p2t_sweep_fill_left_below_edge_event (THIS, tcx, edge, node); + } + } +} + +void +p2t_sweep_fill_left_convex_edge_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tEdge* edge, P2tNode* node) +{ + // Next concave or convex? + if (p2t_orient2d (node->prev->point, node->prev->prev->point, node->prev->prev->prev->point) == CW) + { + // Concave + p2t_sweep_fill_left_concave_edge_event (THIS, tcx, edge, node->prev); + } + else + { + // Convex + // Next above or below edge? + if (p2t_orient2d (edge->q, node->prev->prev->point, edge->p) == CW) + { + // Below + p2t_sweep_fill_left_convex_edge_event (THIS, tcx, edge, node->prev); + } + else + { + // Above + } + } +} + +void +p2t_sweep_fill_left_concave_edge_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tEdge* edge, P2tNode* node) +{ + p2t_sweep_fill (THIS, tcx, node->prev); + if (node->prev->point != edge->p) + { + // Next above or below edge? + if (p2t_orient2d (edge->q, node->prev->point, edge->p) == CW) + { + // Below + if (p2t_orient2d (node->point, node->prev->point, node->prev->prev->point) == CW) + { + // Next is concave + p2t_sweep_fill_left_concave_edge_event (THIS, tcx, edge, node); + } + else + { + // Next is convex + } + } + } + +} + +void +p2t_sweep_flip_edge_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tPoint* ep, P2tPoint* eq, P2tTriangle* t, P2tPoint* p) +{ + P2tTriangle* ot = p2t_triangle_neighbor_across (t, p); + P2tPoint* op = p2t_triangle_opposite_point (ot, t, p); + + if (ot == NULL) + { + // If we want to integrate the fillEdgeEvent do it here + // With current implementation we should never get here + //throw new RuntimeException( "[BUG:FIXME] FLIP failed due to missing triangle"); + assert (0); + } + + if (p2t_utils_in_scan_area (p, p2t_triangle_point_ccw (t, p), p2t_triangle_point_cw (t, p), op)) + { + // Lets rotate shared edge one vertex CW + p2t_sweep_rotate_triangle_pair (THIS, t, p, ot, op); + p2t_sweepcontext_map_triangle_to_nodes (tcx, t); + p2t_sweepcontext_map_triangle_to_nodes (tcx, ot); + + if (p == eq && op == ep) + { + if (p2t_point_equals (eq, tcx->edge_event.constrained_edge->q) && p2t_point_equals (ep, tcx->edge_event.constrained_edge->p)) + { + p2t_triangle_mark_constrained_edge_pt_pt (t, ep, eq); + p2t_triangle_mark_constrained_edge_pt_pt (ot, ep, eq); + p2t_sweep_legalize (THIS, tcx, t); + p2t_sweep_legalize (THIS, tcx, ot); + } + else + { + // XXX: I think one of the triangles should be legalized here? + } + } + else + { + P2tOrientation o = p2t_orient2d (eq, op, ep); + t = p2t_sweep_next_flip_triangle (THIS, tcx, (int) o, t, ot, p, op); + p2t_sweep_flip_edge_event (THIS, tcx, ep, eq, t, p); + } + } + else + { + P2tPoint* newP = p2t_sweep_next_flip_point (THIS, ep, eq, ot, op); + p2t_sweep_flip_scan_edge_event (THIS, tcx, ep, eq, t, ot, newP); + p2t_sweep_edge_event_pt_pt_tr_pt (THIS, tcx, ep, eq, t, p); + } +} + +P2tTriangle* +p2t_sweep_next_flip_triangle (P2tSweep *THIS, P2tSweepContext *tcx, int o, P2tTriangle *t, P2tTriangle *ot, P2tPoint* p, P2tPoint* op) +{ + if (o == CCW) + { + // ot is not crossing edge after flip + int edge_index = p2t_triangle_edge_index (ot, p, op); + ot->delaunay_edge[edge_index] = TRUE; + p2t_sweep_legalize (THIS, tcx, ot); + p2t_triangle_clear_delunay_edges (ot); + return t; + } + + // t is not crossing edge after flip + int edge_index = p2t_triangle_edge_index (t, p, op); + + t->delaunay_edge[edge_index] = TRUE; + p2t_sweep_legalize (THIS, tcx, t); + p2t_triangle_clear_delunay_edges (t); + return ot; +} + +P2tPoint* +p2t_sweep_next_flip_point (P2tSweep *THIS, P2tPoint* ep, P2tPoint* eq, P2tTriangle *ot, P2tPoint* op) +{ + P2tOrientation o2d = p2t_orient2d (eq, op, ep); + if (o2d == CW) + { + // Right + return p2t_triangle_point_ccw (ot, op); + } + else if (o2d == CCW) + { + // Left + return p2t_triangle_point_cw (ot, op); + } + else + { + //throw new RuntimeException("[Unsupported] Opposing point on constrained edge"); + assert (0); + } +} + +void +p2t_sweep_flip_scan_edge_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tPoint* ep, P2tPoint* eq, P2tTriangle *flip_triangle, + P2tTriangle *t, P2tPoint* p) +{ + P2tTriangle* ot = p2t_triangle_neighbor_across (t, p); + P2tPoint* op = p2t_triangle_opposite_point (ot, t, p); + + if (p2t_triangle_neighbor_across (t, p) == NULL) + { + // If we want to integrate the fillEdgeEvent do it here + // With current implementation we should never get here + //throw new RuntimeException( "[BUG:FIXME] FLIP failed due to missing triangle"); + assert (0); + } + + if (p2t_utils_in_scan_area (eq, p2t_triangle_point_ccw (flip_triangle, eq), p2t_triangle_point_cw (flip_triangle, eq), op)) + { + // flip with new edge op->eq + p2t_sweep_flip_edge_event (THIS, tcx, eq, op, ot, op); + // TODO: Actually I just figured out that it should be possible to + // improve this by getting the next ot and op before the the above + // flip and continue the flipScanEdgeEvent here + // set new ot and op here and loop back to inScanArea test + // also need to set a new flip_triangle first + // Turns out at first glance that this is somewhat complicated + // so it will have to wait. + } + else + { + P2tPoint* newP = p2t_sweep_next_flip_point (THIS, ep, eq, ot, op); + p2t_sweep_flip_scan_edge_event (THIS, tcx, ep, eq, flip_triangle, ot, newP); + } +} diff --git a/sweep/sweep.h b/sweep/sweep.h new file mode 100755 index 0000000..cf33169 --- /dev/null +++ b/sweep/sweep.h @@ -0,0 +1,270 @@ +/* + * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors + * http://code.google.com/p/poly2tri/ + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without modification, + * are permitted provided that the following conditions are met: + * + * * Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * * Neither the name of Poly2Tri nor the names of its contributors may be + * used to endorse or promote products derived from this software without specific + * prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ +/** + * Sweep-line, Constrained Delauney Triangulation (CDT) See: Domiter, V. and + * Zalik, B.(2008)'Sweep-line algorithm for constrained Delaunay triangulation', + * International Journal of Geographical Information Science + * + * "FlipScan" Constrained Edge Algorithm invented by Thomas �hl�n, thahlen@gmail.com + */ + +#ifndef SWEEP_H +#define SWEEP_H + +#include "../common/poly2tri-private.h" +#include "../common/shapes.h" + +struct Sweep_ +{ +//private: +P2tNodePtrArray nodes_; + +}; + +void p2t_sweep_init (P2tSweep* THIS); +P2tSweep* p2t_sweep_new (); + +/** + * Destructor - clean up memory + */ +void p2t_sweep_destroy (P2tSweep* THIS); +void p2t_sweep_free (P2tSweep* THIS); + +/** + * Triangulate + * + * @param tcx + */ +void p2t_sweep_triangulate (P2tSweep *THIS, P2tSweepContext *tcx); + +/** + * Start sweeping the Y-sorted point set from bottom to top + * + * @param tcx + */ +void p2t_sweep_sweep_points (P2tSweep *THIS, P2tSweepContext *tcx); + +/** + * Find closes node to the left of the new point and + * create a new triangle. If needed new holes and basins + * will be filled to. + * + * @param tcx + * @param point + * @return + */ +P2tNode* p2t_sweep_point_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tPoint* point); + +/** + * + * + * @param tcx + * @param edge + * @param node + */ +void p2t_sweep_edge_event_ed_n (P2tSweep *THIS, P2tSweepContext *tcx, P2tEdge* edge, P2tNode* node); + +void p2t_sweep_edge_event_pt_pt_tr_pt (P2tSweep *THIS, P2tSweepContext *tcx, P2tPoint* ep, P2tPoint* eq, P2tTriangle* triangle, P2tPoint* point); + +/** + * Creates a new front triangle and legalize it + * + * @param tcx + * @param point + * @param node + * @return + */ +P2tNode* p2t_sweep_new_front_triangle (P2tSweep *THIS, P2tSweepContext *tcx, P2tPoint* point, P2tNode* node); + +/** + * Adds a triangle to the advancing front to fill a hole. + * @param tcx + * @param node - middle node, that is the bottom of the hole + */ +void p2t_sweep_fill (P2tSweep *THIS, P2tSweepContext *tcx, P2tNode* node); + +/** + * Returns true if triangle was legalized + */ +gboolean p2t_sweep_legalize (P2tSweep *THIS, P2tSweepContext *tcx, P2tTriangle *t); + +/** + * Requirement:
+ * 1. a,b and c form a triangle.
+ * 2. a and d is know to be on opposite side of bc
+ * 
+ *                a
+ *                +
+ *               / \
+ *              /   \
+ *            b/     \c
+ *            +-------+
+ *           /    d    \
+ *          /           \
+ *
+ * Fact: d has to be in area B to have a chance to be inside the circle formed by + * a,b and c
+ * d is outside B if orient2d(a,b,d) or orient2d(c,a,d) is CW
+ * This preknowledge gives us a way to optimize the incircle test + * @param a - triangle point, opposite d + * @param b - triangle point + * @param c - triangle point + * @param d - point opposite a + * @return true if d is inside circle, false if on circle edge + */ +gboolean p2t_sweep_incircle (P2tSweep *THIS, P2tPoint* pa, P2tPoint* pb, P2tPoint* pc, P2tPoint* pd); + +/** + * Rotates a triangle pair one vertex CW + *
+ *       n2                    n2
+ *  P +-----+             P +-----+
+ *    | t  /|               |\  t |
+ *    |   / |               | \   |
+ *  n1|  /  |n3           n1|  \  |n3
+ *    | /   |    after CW   |   \ |
+ *    |/ oT |               | oT \|
+ *    +-----+ oP            +-----+
+ *       n4                    n4
+ *
+ */ +void p2t_sweep_rotate_triangle_pair (P2tSweep *THIS, P2tTriangle *t, P2tPoint* p, P2tTriangle *ot, P2tPoint* op); + +/** + * Fills holes in the Advancing Front + * + * + * @param tcx + * @param n + */ +void p2t_sweep_fill_advancingfront (P2tSweep *THIS, P2tSweepContext *tcx, P2tNode* n); + +/** + * + * @param node - middle node + * @return the angle between 3 front nodes + */ +double p2t_sweep_hole_angle (P2tSweep *THIS, P2tNode* node); + +/** + * The basin angle is decided against the horizontal line [1,0] + */ +double p2t_sweep_basin_angle (P2tSweep *THIS, P2tNode* node); + +/** + * Fills a basin that has formed on the Advancing Front to the right + * of given node.
+ * First we decide a left,bottom and right node that forms the + * boundaries of the basin. Then we do a reqursive fill. + * + * @param tcx + * @param node - starting node, this or next node will be left node + */ +void p2t_sweep_fill_basin (P2tSweep *THIS, P2tSweepContext *tcx, P2tNode* node); + +/** + * Recursive algorithm to fill a Basin with triangles + * + * @param tcx + * @param node - bottom_node + * @param cnt - counter used to alternate on even and odd numbers + */ +void p2t_sweep_fill_basin_req (P2tSweep *THIS, P2tSweepContext *tcx, P2tNode* node); + +gboolean p2t_sweep_is_shallow (P2tSweep *THIS, P2tSweepContext *tcx, P2tNode* node); + +gboolean p2t_sweep_is_edge_side_of_triangle (P2tSweep *THIS, P2tTriangle *triangle, P2tPoint* ep, P2tPoint* eq); + +void p2t_sweep_fill_edge_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tEdge* edge, P2tNode* node); + +void p2t_sweep_fill_right_above_edge_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tEdge* edge, P2tNode* node); + +void p2t_sweep_fill_right_below_edge_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tEdge* edge, P2tNode* node); + +void p2t_sweep_fill_right_concave_edge_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tEdge* edge, P2tNode* node); + +void p2t_sweep_fill_right_convex_edge_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tEdge* edge, P2tNode* node); + +void p2t_sweep_fill_left_above_edge_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tEdge* edge, P2tNode* node); + +void p2t_sweep_fill_left_below_edge_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tEdge* edge, P2tNode* node); + +void p2t_sweep_fill_left_concave_edge_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tEdge* edge, P2tNode* node); + +void p2t_sweep_fill_left_convex_edge_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tEdge* edge, P2tNode* node); + +void p2t_sweep_flip_edge_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tPoint* ep, P2tPoint* eq, P2tTriangle* t, P2tPoint* p); + +/** + * After a flip we have two triangles and know that only one will still be + * intersecting the edge. So decide which to contiune with and legalize the other + * + * @param tcx + * @param o - should be the result of an orient2d( eq, op, ep ) + * @param t - triangle 1 + * @param ot - triangle 2 + * @param p - a point shared by both triangles + * @param op - another point shared by both triangles + * @return returns the triangle still intersecting the edge + */ +P2tTriangle* p2t_sweep_next_flip_triangle (P2tSweep *THIS, P2tSweepContext *tcx, int o, P2tTriangle *t, P2tTriangle *ot, P2tPoint* p, P2tPoint* op); + +/** + * When we need to traverse from one triangle to the next we need + * the point in current triangle that is the opposite point to the next + * triangle. + * + * @param ep + * @param eq + * @param ot + * @param op + * @return + */ +P2tPoint* p2t_sweep_next_flip_point (P2tSweep *THIS, P2tPoint* ep, P2tPoint* eq, P2tTriangle *ot, P2tPoint* op); + +/** + * Scan part of the FlipScan algorithm
+ * When a triangle pair isn't flippable we will scan for the next + * point that is inside the flip triangle scan area. When found + * we generate a new flipEdgeEvent + * + * @param tcx + * @param ep - last point on the edge we are traversing + * @param eq - first point on the edge we are traversing + * @param flipTriangle - the current triangle sharing the point eq with edge + * @param t + * @param p + */ +void p2t_sweep_flip_scan_edge_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tPoint* ep, P2tPoint* eq, P2tTriangle *flip_triangle, P2tTriangle *t, P2tPoint* p); + +void p2t_sweep_finalization_polygon (P2tSweep *THIS, P2tSweepContext *tcx); + +#endif diff --git a/sweep/sweep_context.c b/sweep/sweep_context.c new file mode 100755 index 0000000..0c827c0 --- /dev/null +++ b/sweep/sweep_context.c @@ -0,0 +1,313 @@ +/* + * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors + * http://code.google.com/p/poly2tri/ + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without modification, + * are permitted provided that the following conditions are met: + * + * * Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * * Neither the name of Poly2Tri nor the names of its contributors may be + * used to endorse or promote products derived from this software without specific + * prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ +#include "sweep_context.h" +#include "advancing_front.h" + +void +p2t_sweepcontext_basin_init (P2tSweepContextBasin* THIS) +{ + p2t_sweepcontext_basin_clear (THIS); +} + +void +p2t_sweepcontext_basin_clear (P2tSweepContextBasin* THIS) +{ + THIS->left_node = NULL; + THIS->bottom_node = NULL; + THIS->right_node = NULL; + THIS->width = 0.0; + THIS->left_highest = FALSE; +} + +void +p2t_sweepcontext_edgeevent_init (P2tSweepContextEdgeEvent* THIS) +{ + THIS->constrained_edge = NULL; + THIS->right = FALSE; +} + +void +p2t_sweepcontext_init (P2tSweepContext* THIS, P2tPointPtrArray polyline) +{ + int i; + THIS->edge_list = g_ptr_array_new (); + THIS->triangles_ = g_ptr_array_new (); + THIS->map_ = NULL; + + p2t_sweepcontext_basin_init (&THIS->basin); + p2t_sweepcontext_edgeevent_init (&THIS->edge_event); + + THIS->points_ = g_ptr_array_sized_new (polyline->len); + for (i = 0; i < polyline->len; i++) + g_ptr_array_add (THIS->points_, point_index (polyline, i)); + + p2t_sweepcontext_init_edges (THIS, THIS->points_); +} + +P2tSweepContext* +p2t_sweepcontext_new (P2tPointPtrArray polyline) +{ + P2tSweepContext* THIS = g_new (P2tSweepContext, 1); + p2t_sweepcontext_init (THIS, polyline); + return THIS; +} + +void +p2t_sweepcontext_destroy (P2tSweepContext* THIS) +{ + GList* iter; + int i; + // Clean up memory + + p2t_point_free (THIS->head_); + p2t_point_free (THIS->tail_); + p2t_advancingfront_free (THIS->front_); + p2t_node_free (THIS->af_head_); + p2t_node_free (THIS->af_middle_); + p2t_node_free (THIS->af_tail_); + + g_ptr_array_free (THIS->triangles_, TRUE); + + for (iter = g_list_first (THIS->map_); iter != NULL; iter = g_list_next (iter)) + { + P2tTriangle* ptr = triangle_val (iter); + g_free (ptr); + } + + g_list_free (THIS->map_); + + for (i = 0; i < THIS->edge_list->len; i++) + { + p2t_edge_free (edge_index (THIS->edge_list, i)); + } + + g_ptr_array_free (THIS->edge_list, TRUE); + +} + +void +p2t_sweepcontext_delete (P2tSweepContext* THIS) +{ + p2t_sweepcontext_destroy (THIS); + g_free(THIS); +} + +void +p2t_sweepcontext_add_hole (P2tSweepContext *THIS, P2tPointPtrArray polyline) +{ + int i; + p2t_sweepcontext_init_edges (THIS, polyline); + for (i = 0; i < polyline->len; i++) + { + g_ptr_array_add (THIS->points_, point_index (polyline, i)); + } +} + +void +p2t_sweepcontext_add_point (P2tSweepContext *THIS, P2tPoint* point) +{ + g_ptr_array_add (THIS->points_, point); +} + +P2tTrianglePtrArray +p2t_sweepcontext_get_triangles (P2tSweepContext *THIS) +{ + return THIS->triangles_; +} + +P2tTrianglePtrList +p2t_sweepcontext_get_map (P2tSweepContext *THIS) +{ + return THIS->map_; +} + +void +p2t_sweepcontext_init_triangulation (P2tSweepContext *THIS) +{ + int i; + double xmax = point_index (THIS->points_, 0)->x, xmin = point_index (THIS->points_, 0)->x; + double ymax = point_index (THIS->points_, 0)->y, ymin = point_index (THIS->points_, 0)->y; + + // Calculate bounds. + for (i = 0; i < THIS->points_->len; i++) + { + P2tPoint* p = point_index (THIS->points_, i); + if (p->x > xmax) + xmax = p->x; + if (p->x < xmin) + xmin = p->x; + if (p->y > ymax) + ymax = p->y; + if (p->y < ymin) + ymin = p->y; + } + + double dx = kAlpha * (xmax - xmin); + double dy = kAlpha * (ymax - ymin); + THIS->head_ = p2t_point_new_dd (xmax + dx, ymin - dy); + THIS->tail_ = p2t_point_new_dd (xmin - dx, ymin - dy); + + // Sort points along y-axis + g_ptr_array_sort (THIS->points_, p2t_point_cmp); +} + +void +p2t_sweepcontext_init_edges (P2tSweepContext *THIS, P2tPointPtrArray polyline) +{ + int i; + int num_points = polyline->len; + g_ptr_array_set_size (THIS->edge_list, THIS->edge_list->len + num_points); // C-OPTIMIZATION + for (i = 0; i < num_points; i++) + { + int j = i < num_points - 1 ? i + 1 : 0; + g_ptr_array_add (THIS->edge_list, p2t_edge_new (point_index (polyline, i), point_index (polyline, j))); + } +} + +P2tPoint* +p2t_sweepcontext_get_point (P2tSweepContext *THIS, const int index) +{ + return point_index (THIS->points_, index); +} + +void +p2t_sweepcontext_add_to_map (P2tSweepContext *THIS, P2tTriangle* triangle) +{ + THIS->map_ = g_list_append (THIS->map_, triangle); +} + +P2tNode* +p2t_sweepcontext_locate_node (P2tSweepContext *THIS, P2tPoint* point) +{ + // TODO implement search tree + return p2t_advancingfront_locate_node (THIS->front_, point->x); +} + +void +p2t_sweepcontext_create_advancingfront (P2tSweepContext *THIS, P2tNodePtrArray nodes) +{ + + // Initial triangle + P2tTriangle* triangle = p2t_triangle_new (point_index (THIS->points_, 0), THIS->tail_, THIS->head_); + + THIS->map_ = g_list_append (THIS->map_, triangle); + + THIS->af_head_ = p2t_node_new_pt_tr (p2t_triangle_get_point (triangle, 1), triangle); + THIS->af_middle_ = p2t_node_new_pt_tr (p2t_triangle_get_point (triangle, 0), triangle); + THIS->af_tail_ = p2t_node_new_pt (p2t_triangle_get_point (triangle, 2)); + THIS->front_ = p2t_advancingfront_new (THIS->af_head_, THIS->af_tail_); + + // TODO: More intuitive if head is middles next and not previous? + // so swap head and tail + THIS->af_head_->next = THIS->af_middle_; + THIS->af_middle_->next = THIS->af_tail_; + THIS->af_middle_->prev = THIS->af_head_; + THIS->af_tail_->prev = THIS->af_middle_; +} + +void +p2t_sweepcontext_remove_node (P2tSweepContext *THIS, P2tNode* node) +{ + g_free (node); +} + +void +p2t_sweepcontext_map_triangle_to_nodes (P2tSweepContext *THIS, P2tTriangle* t) +{ + int i; + for (i = 0; i < 3; i++) + { + if (!p2t_triangle_get_neighbor (t, i)) + { + P2tNode* n = p2t_advancingfront_locate_point (THIS->front_, p2t_triangle_point_cw (t, p2t_triangle_get_point (t, i))); + if (n) + n->triangle = t; + } + } +} + +void +p2t_sweepcontext_remove_from_map (P2tSweepContext *THIS, P2tTriangle* triangle) +{ + THIS->map_ = g_list_remove (THIS->map_, triangle); +} + +void +p2t_sweepcontext_mesh_clean (P2tSweepContext *THIS, P2tTriangle* triangle) +{ + int i; + if (triangle != NULL && !p2t_triangle_is_interior (triangle)) + { + p2t_triangle_is_interior_b (triangle, TRUE); + g_ptr_array_add (THIS->triangles_, triangle); + for (i = 0; i < 3; i++) + { + if (!triangle->constrained_edge[i]) + p2t_sweepcontext_mesh_clean (THIS, p2t_triangle_get_neighbor (triangle, i)); + } + } +} + +P2tAdvancingFront* +p2t_sweepcontext_front (P2tSweepContext *THIS) +{ + return THIS->front_; +} + +int +p2t_sweepcontext_point_count (P2tSweepContext *THIS) +{ + return THIS->points_->len; +} + +void +p2t_sweepcontext_set_head (P2tSweepContext *THIS, P2tPoint* p1) +{ + THIS->head_ = p1; +} + +P2tPoint* +p2t_sweepcontext_head (P2tSweepContext *THIS) +{ + return THIS->head_; +} + +void +p2t_sweepcontext_set_tail (P2tSweepContext *THIS, P2tPoint* p1) +{ + THIS->tail_ = p1; +} + +P2tPoint* +p2t_sweepcontext_tail (P2tSweepContext *THIS) +{ + return THIS->tail_; +} diff --git a/sweep/sweep_context.h b/sweep/sweep_context.h new file mode 100755 index 0000000..0e9a033 --- /dev/null +++ b/sweep/sweep_context.h @@ -0,0 +1,133 @@ +/* + * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors + * http://code.google.com/p/poly2tri/ + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without modification, + * are permitted provided that the following conditions are met: + * + * * Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * * Neither the name of Poly2Tri nor the names of its contributors may be + * used to endorse or promote products derived from this software without specific + * prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef SWEEP_CONTEXT_H +#define SWEEP_CONTEXT_H + +#include "../common/poly2tri-private.h" +#include "../common/shapes.h" +#include "advancing_front.h" + +// Inital triangle factor, seed triangle will extend 30% of +// PointSet width to both left and right. +#define kAlpha 0.3 + +struct P2tSweepContextBasin_ +{ + P2tNode* left_node; + P2tNode* bottom_node; + P2tNode* right_node; + double width; + gboolean left_highest; +}; + +void p2t_sweepcontext_basin_init (P2tSweepContextBasin* THIS); +void p2t_sweepcontext_basin_clear (P2tSweepContextBasin* THIS); + +struct P2tSweepContextEdgeEvent_ +{ + P2tEdge* constrained_edge; + gboolean right; +}; + +void p2t_sweepcontext_edgeevent_init (P2tSweepContextEdgeEvent* THIS); + +struct SweepContext_ +{ + P2tEdgePtrArray edge_list; + + P2tSweepContextBasin basin; + P2tSweepContextEdgeEvent edge_event; + + P2tTrianglePtrArray triangles_; + P2tTrianglePtrList map_; + P2tPointPtrArray points_; + + // Advancing front + P2tAdvancingFront* front_; + // head point used with advancing front + P2tPoint* head_; + // tail point used with advancing front + P2tPoint* tail_; + + P2tNode *af_head_, *af_middle_, *af_tail_; +}; + +/// Constructor +void p2t_sweepcontext_init (P2tSweepContext* THIS, P2tPointPtrArray polyline); +P2tSweepContext* p2t_sweepcontext_new (P2tPointPtrArray polyline); + +/// Destructor +void p2t_sweepcontext_destroy (P2tSweepContext* THIS); +void p2t_sweepcontext_delete (P2tSweepContext* THIS); + +void p2t_sweepcontext_set_head (P2tSweepContext *THIS, P2tPoint* p1); + +P2tPoint* p2t_sweepcontext_head (P2tSweepContext *THIS); + +void p2t_sweepcontext_set_tail (P2tSweepContext *THIS, P2tPoint* p1); + +P2tPoint* p2t_sweepcontext_tail (P2tSweepContext *THIS); + +int p2t_sweepcontext_point_count (P2tSweepContext *THIS); + +P2tNode* p2t_sweepcontext_locate_node (P2tSweepContext *THIS, P2tPoint* point); + +void p2t_sweepcontext_remove_node (P2tSweepContext *THIS, P2tNode* node); + +void p2t_sweepcontext_create_advancingfront (P2tSweepContext *THIS, P2tNodePtrArray nodes); + +/// Try to map a node to all sides of this triangle that don't have a neighbor +void p2t_sweepcontext_map_triangle_to_nodes (P2tSweepContext *THIS, P2tTriangle* t); + +void p2t_sweepcontext_add_to_map (P2tSweepContext *THIS, P2tTriangle* triangle); + +P2tPoint* p2t_sweepcontext_get_point (P2tSweepContext *THIS, const int index); + +P2tPoint* SweepContext_GetPoints (P2tSweepContext *THIS); + +void p2t_sweepcontext_remove_from_map (P2tSweepContext *THIS, P2tTriangle* triangle); + +void p2t_sweepcontext_add_hole (P2tSweepContext *THIS, P2tPointPtrArray polyline); + +void p2t_sweepcontext_add_point (P2tSweepContext *THIS, P2tPoint* point); + +P2tAdvancingFront* p2t_sweepcontext_front (P2tSweepContext *THIS); + +void p2t_sweepcontext_mesh_clean (P2tSweepContext *THIS, P2tTriangle* triangle); + +P2tTrianglePtrArray p2t_sweepcontext_get_triangles (P2tSweepContext *THIS); +P2tTrianglePtrList p2t_sweepcontext_get_map (P2tSweepContext *THIS); + +void p2t_sweepcontext_init_triangulation (P2tSweepContext *THIS); +void p2t_sweepcontext_init_edges (P2tSweepContext *THIS, P2tPointPtrArray polyline); + +#endif -- 2.40.0