From 4a1f964d10f26ca6ff9a9bbb340ddd4244b3ecd9 Mon Sep 17 00:00:00 2001 From: Barak Itkin Date: Fri, 27 Apr 2012 12:12:35 +0300 Subject: [PATCH] 1. Move common functions into shared files 2. Silence many compiler warnings to make the code more C90 compatiable --- p2t/common/shapes.h | 2 +- p2t/sweep/advancing_front.h | 8 +- p2t/sweep/cdt.h | 2 +- p2t/sweep/sweep.h | 2 +- p2t/sweep/sweep_context.h | 16 +- refine/cdt.c | 299 ++++++++++++++++------------------- refine/cdt.h | 25 ++- refine/delaunay-terminator.h | 86 ++++++++++ refine/edge.c | 38 ++--- refine/math.c | 43 ++++- refine/math.h | 19 ++- refine/mesh.c | 34 ++-- refine/mesh.h | 11 ++ refine/point.c | 1 + refine/point.h | 3 + refine/triangle.c | 56 ++----- refine/triangle.h | 1 + refine/utils.c | 19 +++ refine/utils.h | 2 + 19 files changed, 407 insertions(+), 260 deletions(-) create mode 100644 refine/delaunay-terminator.h create mode 100644 refine/utils.c diff --git a/p2t/common/shapes.h b/p2t/common/shapes.h index 6287e9a..7f77e62 100755 --- a/p2t/common/shapes.h +++ b/p2t/common/shapes.h @@ -254,7 +254,7 @@ void p2t_triangle_debug_print (P2tTriangle* THIS); gint p2t_point_cmp (gconstpointer a, gconstpointer b); -// gboolean operator == (const Point& a, const Point& b); +/* gboolean operator == (const Point& a, const Point& b); */ gboolean p2t_point_equals (const P2tPoint* a, const P2tPoint* b); #endif diff --git a/p2t/sweep/advancing_front.h b/p2t/sweep/advancing_front.h index 44ef55e..dfe9af9 100755 --- a/p2t/sweep/advancing_front.h +++ b/p2t/sweep/advancing_front.h @@ -35,7 +35,7 @@ #include "../common/poly2tri-private.h" #include "../common/shapes.h" -// Advancing front node +/* Advancing front node */ struct _P2tNode { @@ -55,11 +55,11 @@ P2tNode* p2t_node_new_pt_tr (P2tPoint* p, P2tTriangle* t); void p2t_node_destroy (P2tNode* THIS); void p2t_node_free (P2tNode* THIS); -// Advancing front +/* Advancing front */ struct AdvancingFront_ { - //private: + /* private: */ P2tNode* head_, *tail_, *search_node_; @@ -78,7 +78,7 @@ 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 +/** 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); diff --git a/p2t/sweep/cdt.h b/p2t/sweep/cdt.h index bd40198..fdc57af 100755 --- a/p2t/sweep/cdt.h +++ b/p2t/sweep/cdt.h @@ -45,7 +45,7 @@ struct CDT_ { - //private: + /*private: */ /** * Internals diff --git a/p2t/sweep/sweep.h b/p2t/sweep/sweep.h index cf33169..6801b1c 100755 --- a/p2t/sweep/sweep.h +++ b/p2t/sweep/sweep.h @@ -44,7 +44,7 @@ struct Sweep_ { -//private: +/* private: */ P2tNodePtrArray nodes_; }; diff --git a/p2t/sweep/sweep_context.h b/p2t/sweep/sweep_context.h index 0e9a033..73cb4ca 100755 --- a/p2t/sweep/sweep_context.h +++ b/p2t/sweep/sweep_context.h @@ -36,8 +36,8 @@ #include "../common/shapes.h" #include "advancing_front.h" -// Inital triangle factor, seed triangle will extend 30% of -// PointSet width to both left and right. +/* Inital triangle factor, seed triangle will extend 30% of + * PointSet width to both left and right. */ #define kAlpha 0.3 struct P2tSweepContextBasin_ @@ -71,21 +71,21 @@ struct SweepContext_ P2tTrianglePtrList map_; P2tPointPtrArray points_; - // Advancing front + /** Advancing front */ P2tAdvancingFront* front_; - // head point used with advancing front + /** head point used with advancing front */ P2tPoint* head_; - // tail point used with advancing front + /** tail point used with advancing front */ P2tPoint* tail_; P2tNode *af_head_, *af_middle_, *af_tail_; }; -/// Constructor +/** Constructor */ void p2t_sweepcontext_init (P2tSweepContext* THIS, P2tPointPtrArray polyline); P2tSweepContext* p2t_sweepcontext_new (P2tPointPtrArray polyline); -/// Destructor +/** Destructor */ void p2t_sweepcontext_destroy (P2tSweepContext* THIS); void p2t_sweepcontext_delete (P2tSweepContext* THIS); @@ -105,7 +105,7 @@ 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 +/** 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); diff --git a/refine/cdt.c b/refine/cdt.c index 973cb45..810ab29 100644 --- a/refine/cdt.c +++ b/refine/cdt.c @@ -1,17 +1,49 @@ #include +#include + +#include "point.h" +#include "edge.h" +#include "triangle.h" + #include "cdt.h" +static gboolean p2tr_cdt_visible_from_edge (P2trCDT *self, + P2trEdge *e, + P2trVector2 *p); + +static gboolean p2tr_cdt_visible_from_tri (P2trCDT *self, + P2trTriangle *tri, + P2trVector2 *p); + +static gboolean p2tr_cdt_has_empty_circum_circle (P2trCDT *self, + P2trTriangle *tri); + +static GList* p2tr_cdt_triangulate_fan (P2trCDT *self, + P2trPoint *center, + GList *edge_pts); + +static void p2tr_cdt_flip_fix (P2trCDT *self, + GList *initial_triangles); + +static gboolean p2tr_cdt_try_flip (P2trCDT *self, + P2trEdge *to_flip, + GQueue *new_tris, + P2trEdge **new_edge); + +static void p2tr_cdt_on_new_point (P2trCDT *self, + P2trPoint *pt); + P2trCDT* p2tr_cdt_new (P2tCDT *cdt) { - P2tTrianglePtrArray *cdt_tris = p2t_cdt_get_triangles (cdt); - GHashTable *point_map = g_hash_table_new (g_direct_hash, g_direct_equals); + P2tTrianglePtrArray cdt_tris = p2t_cdt_get_triangles (cdt); + GHashTable *point_map = g_hash_table_new (g_direct_hash, g_direct_equal); P2trCDT *rmesh = g_slice_new (P2trCDT); - + gint i, j; - + rmesh->mesh = p2tr_mesh_new (); rmesh->outline = p2tr_pslg_new (); - + /* First iteration over the CDT - create all the points */ for (i = 0; i < cdt_tris->len; i++) { @@ -20,7 +52,7 @@ P2trCDT* p2tr_cdt_new (P2tCDT *cdt) { P2tPoint *cdt_pt = p2t_triangle_get_point(cdt_tri, j); P2trPoint *new_pt = g_hash_table_lookup (point_map, cdt_pt); - + if (new_pt == NULL) { new_pt = p2tr_point_new2 (cdt_pt->x, cdt_pt->y); @@ -34,13 +66,13 @@ P2trCDT* p2tr_cdt_new (P2tCDT *cdt) for (i = 0; i < cdt_tris->len; i++) { P2tTriangle *cdt_tri = triangle_index (cdt_tris, i); - + for (j = 0; j < 3; j++) { P2tPoint *start = p2t_triangle_get_point (cdt_tri, j); P2tPoint *end = p2t_triangle_get_point (cdt_tri, (j + 1) % 3); int edge_index = p2t_triangle_edge_index (cdt_tri, start, end); - + P2trPoint *start_new = g_hash_table_lookup (point_map, start); P2trPoint *end_new = g_hash_table_lookup (point_map, end); @@ -48,12 +80,12 @@ P2trCDT* p2tr_cdt_new (P2tCDT *cdt) { gboolean constrained = cdt_tri->constrained_edge[edge_index]; P2trEdge *edge = p2tr_mesh_new_edge (rmesh->mesh, start_new, end_new, constrained); - + /* If the edge is constrained, we should add it to the * outline */ if (constrained) - p2tr_pslg_add_new_line(rmesh->outline, &start_new.c, - &end_new.c); + p2tr_pslg_add_new_line(rmesh->outline, &start_new->c, + &end_new->c); /* We only wanted to create the edge now. We will use it * later */ @@ -79,7 +111,7 @@ P2trCDT* p2tr_cdt_new (P2tCDT *cdt) /* We won't do any usage of the triangle, so just unref it */ p2tr_triangle_unref (new_tri); } - + return rmesh; } @@ -88,7 +120,7 @@ p2tr_cdt_validate_edges (P2trCDT *self) { P2trHashSetIter iter; P2trEdge *e; - + p2tr_hash_set_iter_init (&iter, self->mesh->edges); while (p2tr_hash_set_iter_next (&iter, (gpointer*)&e)) { @@ -99,11 +131,11 @@ p2tr_cdt_validate_edges (P2trCDT *self) { gboolean found = FALSE; gint i = 0; - + for (i = 0; i < 3; i++) if (e->tri->edges[i] == e) { - found = true; + found = TRUE; break; } @@ -119,33 +151,35 @@ p2tr_cdt_visible_from_edge (P2trCDT *self, P2trVector2 *p) { P2trBoundedLine line; - - p2tr_bounded_line_init (&line, &e->start->c, &e->end->c); - + + p2tr_bounded_line_init (&line, &P2TR_EDGE_START(e)->c, &e->end->c); + return p2tr_visibility_is_visible_from_edges (self->outline, p, &line, 1); } -gboolean +static gboolean p2tr_cdt_visible_from_tri (P2trCDT *self, P2trTriangle *tri, P2trVector2 *p) { - P2trBoundedLine *lines[3]; + P2trBoundedLine lines[3]; gint i; - + for (i = 0; i < 3; i++) - p2tr_bounded_line_init (&line[i], P2TR_EDGE_START(tri->edges[i]), tri->edges[i]->end); + p2tr_bounded_line_init (&lines[i], + &P2TR_EDGE_START(tri->edges[i])->c, + &tri->edges[i]->end->c); return p2tr_visibility_is_visible_from_edges (self->outline, p, lines, 3); } -gboolean +static gboolean p2tr_cdt_has_empty_circum_circle (P2trCDT *self, P2trTriangle *tri) { P2trCircle circum; P2trPoint *p; - P2trHashSet iter; + P2trHashSetIter iter; p2tr_triangle_get_circum_circle (tri, &circum); @@ -163,7 +197,7 @@ p2tr_cdt_has_empty_circum_circle (P2trCDT *self, continue; if (! p2tr_circle_test_point_outside(&circum, &p->c) - && p2tr_cdt_visible_from_tri (cdt, tri, &p.c)) + && p2tr_cdt_visible_from_tri (self, tri, &p->c)) return FALSE; } return TRUE; @@ -172,71 +206,37 @@ p2tr_cdt_has_empty_circum_circle (P2trCDT *self, void p2tr_cdt_validate_cdt (P2trCDT *self) { - P2trHashSetIter *iter; + P2trHashSetIter iter; P2trTriangle *tri; - + p2tr_hash_set_iter_init (&iter, self->mesh->triangles); while (p2tr_hash_set_iter_next (&iter, (gpointer*)&tri)) if (! p2tr_cdt_has_empty_circum_circle(self, tri)) p2tr_exception_geometric ("Not a CDT!"); } -gboolean -p2tr_cdt_is_encroached (P2trEdge *E) -{ - P2trTriangle *T1 = E->tri; - P2trTriangle *T2 = E->mirror->tri; - - if (! E->constrained) - return FALSE; - - return (T1 != NULL && p2tr_cdt_test_encroachment_ignore_visibility (p2tr_triangle_get_opposite_point (T1, E)->c, E)) - || (T2 != NULL && p2tr_cdt_test_encroachment_ignore_visibility (p2tr_triangle_get_opposite_point (T2, E)->c, E)); -} - -P2trHashSet* -p2tr_cdt_get_segments_encroached_by (P2trCDT *self, - P2trVector2 *C) -{ - P2trHashSet *encroached_edges = p2tr_hash_set_new (g_direct_hash, - g_direct_equal, (GDestroyNotify) p2tr_edge_unref); - - P2trHashSetIter iter; - P2trEdge *e; - - p2tr_hash_set_iter_init (&iter, self->mesh->edges); - while (p2tr_hash_set_iter_next (&iter, (gpointer*)&e)) - if (e->constrained - && p2tr_hash_set_contains (encroached_edges, e->mirror) == FALSE - && p2tr_cdt_edge_will_be_encroached_by (self, e, C)) - { - p2tr_hash_set_insert (encroached_edges, e); - } - - return encroached_edges; -} - P2trPoint* p2tr_cdt_insert_point (P2trCDT *self, const P2trVector2 *pc) { - P2trTriangle *tri = this.p2tr_triangulation_rough_find_point(Pc); + P2trTriangle *tri = p2tr_triangulation_rough_find_point (self, pc); P2trPoint *pt; gboolean inserted = FALSE; - + gint i; + if (tri == NULL) p2tr_exception_geometric ("Tried to add point outside of domain!"); - pt = new P2trPoint(pc.x, pc.y, this); + pt = p2tr_mesh_new_point (self->mesh, pc); /* If the point falls on a line, we should split the line */ - for (int i = 0; i < 3; i++) + for (i = 0; i < 3; i++) { P2trEdge *edge = tri->edges[i]; if (p2tr_math_orient2d (& P2TR_EDGE_START(edge)->c, - &edge->end->c, pc) == Orientation.LINEAR) + &edge->end->c, pc) == P2TR_ORIENTATION_LINEAR) { - p2tr_cdt_split_edge (edge, pt); + p2tr_cdt_split_edge (self, edge, pt); inserted = TRUE; break; } @@ -245,25 +245,10 @@ p2tr_cdt_insert_point (P2trCDT *self, if (! inserted) /* If we reached this line, then the point is inside the triangle */ p2tr_cdt_insert_point_into_triangle (self, pt, tri); - + p2tr_cdt_on_new_point (self, pt); - - return pt; -} -static GList* -p2tr_cdt_new_reversed_pointer_list (int count, ...) -{ - int i; - va_list args; - GList *result = NULL; - - va_start (args, count); - for (i = 0; i < count; i++) - result = g_list_prepend (result, va_arg (args, gpointer)); - va_end (args); - - return result; + return pt; } /** Insert a point into a triangle. This function assumes the point is @@ -271,7 +256,7 @@ p2tr_cdt_new_reversed_pointer_list (int count, ...) */ void p2tr_cdt_insert_point_into_triangle (P2trCDT *self, - P2trPoint *pt, + P2trPoint *P, P2trTriangle *tri) { GList *new_tris; @@ -279,20 +264,22 @@ p2tr_cdt_insert_point_into_triangle (P2trCDT *self, P2trPoint *A = tri->edges[0]->end; P2trPoint *B = tri->edges[1]->end; P2trPoint *C = tri->edges[2]->end; - + P2trEdge *CA = tri->edges[1]; P2trEdge *AB = tri->edges[2]; P2trEdge *BC = tri->edges[0]; + P2trEdge *AP, *BP, *CP; + p2tr_triangle_remove (tri); - P2trEdge *AP = p2tr_mesh_new_edge (self->mesh, A, P, FALSE); - P2trEdge *BP = p2tr_mesh_new_edge (self->mesh, B, P, FALSE); - P2trEdge *CP = p2tr_mesh_new_edge (self->mesh, C, P, FALSE); + AP = p2tr_mesh_new_edge (self->mesh, A, P, FALSE); + BP = p2tr_mesh_new_edge (self->mesh, B, P, FALSE); + CP = p2tr_mesh_new_edge (self->mesh, C, P, FALSE); - new_tris = p2tr_cdt_new_reversed_pointer_list (3, - p2tr_mesh_new_triangle (self->mesh, AB, BP, AP->mirror); - p2tr_mesh_new_triangle (self->mesh, BC, CP, BP->mirror); + new_tris = p2tr_utils_new_reversed_pointer_list (3, + p2tr_mesh_new_triangle (self->mesh, AB, BP, AP->mirror), + p2tr_mesh_new_triangle (self->mesh, BC, CP, BP->mirror), p2tr_mesh_new_triangle (self->mesh, CA, AP, CP->mirror)); p2tr_edge_unref (CP); @@ -307,23 +294,6 @@ p2tr_cdt_insert_point_into_triangle (P2trCDT *self, g_list_free (new_tris); } -/* This function returns an existing edge between two points, or - * alternativly a new unconstrained edge between the two points. - * THE EDGE MUST BE UNREFERECED WHEN USING IT IS FINISHED! - */ -static P2trEdge* -p2tr_cdt_existing_or_new_unconstrained_edge (P2trCDT *self, - P2trPoint *start, - P2trPoint *end) -{ - P2trEdge *result = p2tr_point_has_edge_to (start, end); - if (result) - p2tr_edge_ref (result); - else - result = p2tr_mesh_new_edge (self->mesh, start, end, FALSE); - return result; -} - /** * Triangulate a polygon by creating edges to a center point. * 1. If there is a NULL point in the polygon, two triangles are not @@ -337,7 +307,7 @@ p2tr_cdt_triangulate_fan (P2trCDT *self, { GList *new_tris = NULL; GList *iter; - + /* We can not triangulate unless at least two points are given */ if (edge_pts == NULL || edge_pts->next == NULL) { @@ -356,9 +326,9 @@ p2tr_cdt_triangulate_fan (P2trCDT *self, continue; AB = p2tr_point_get_edge_to (A, B); - BC = p2tr_cdt_existing_or_new_unconstrained_edge (self, B, center); - CA = p2tr_cdt_existing_or_new_unconstrained_edge (self, center, A); - + BC = p2tr_mesh_new_or_existing_edge (self->mesh, B, center, FALSE); + CA = p2tr_mesh_new_or_existing_edge (self->mesh, center, A, FALSE); + tri = p2tr_mesh_new_triangle (self->mesh, AB, BC, CA); new_tris = g_list_prepend (new_tris, tri); @@ -382,29 +352,30 @@ p2tr_cdt_split_edge (P2trCDT *self, P2trEdge *e, P2trPoint *C) { - // W - // /|\ - // / | \ - // / | \ E.Mirror.Tri: YXW - // X*---*---*Y E: X->Y - // \ |C / E.Tri: XYV - // \ | / - // \|/ - // V - P2trPoint *X = P2TR_EDGE_START (e), Y = e->end; + /* W + * /|\ + * / | \ + * / | \ E.Mirror.Tri: YXW + * X*---*---*Y E: X->Y + * \ |C / E.Tri: XYV + * \ | / + * \|/ + * V + */ + P2trPoint *X = P2TR_EDGE_START (e), *Y = e->end; P2trPoint *V = (e->tri != NULL) ? p2tr_triangle_get_opposite_point(e->tri, e) : NULL; P2trPoint *W = (e->mirror->tri != NULL) ? p2tr_triangle_get_opposite_point (e->mirror->tri, e->mirror) : NULL; gboolean constrained = e->constrained; P2trEdge *XC, *CY; - GList *new_tris = NULL, fan = NULL, new_edges = NULL; + GList *new_tris = NULL, *fan = NULL, *new_edges = NULL; p2tr_edge_remove (e); - XC = p2tr_mesh_new_edge (mesh, X, C, constrained); - CY = p2tr_mesh_new_edge (mesh, C, Y, constrained); - - fan = p2tr_cdt_new_reversed_pointer_list (4, W, X, V, Y); - new_tris = p2tr_cdt_triangulate_star (self, C, fan); + XC = p2tr_mesh_new_edge (self->mesh, X, C, constrained); + CY = p2tr_mesh_new_edge (self->mesh, C, Y, constrained); + + fan = p2tr_utils_new_reversed_pointer_list (4, W, X, V, Y); + new_tris = p2tr_cdt_triangulate_fan (self, C, fan); g_list_free (fan); /* Now make this a CDT again @@ -433,7 +404,7 @@ p2tr_cdt_split_edge (P2trCDT *self, } p2tr_cdt_on_new_point (self, C); - + return new_edges; } @@ -462,7 +433,7 @@ p2tr_cdt_split_edge (P2trCDT *self, * THE GIVEN INPUT TRIANGLES MUST BE GIVEN WITH AN EXTRA REFERENCE SINCE * THEY WILL BE UNREFFED! */ -void +static void p2tr_cdt_flip_fix (P2trCDT *self, GList *initial_triangles) { @@ -481,7 +452,7 @@ p2tr_cdt_flip_fix (P2trCDT *self, P2trCircle circum_circle; gint i; - if (p2tr_triangle_is_removed (tris_to_fix)) + if (p2tr_triangle_is_removed (tri)) { p2tr_triangle_unref (tri); continue; @@ -491,7 +462,7 @@ p2tr_cdt_flip_fix (P2trCDT *self, for (i = 0; i < 3; i++) { - P2trEdge *e = tri.edges[i]; + P2trEdge *e = tri->edges[i]; P2trPoint *opposite; if (e->constrained || e->delaunay) @@ -501,23 +472,23 @@ p2tr_cdt_flip_fix (P2trCDT *self, if (! p2tr_circle_test_point_outside(&circum_circle, &opposite->c)) { P2trEdge *flipped; - if (p2tr_cdt_try_flip (self, e, tris_to_fix, &flipped)) + if (p2tr_cdt_try_flip (self, e, &tris_to_fix, &flipped)) { - g_queue_push_tail (flipped_edges, flipped); + g_queue_push_tail (&flipped_edges, flipped); /* Stop iterating this triangle since it doesn't exist * any more */ - break; + break; } } } - + /* We are finished with the triangle, so unref it as promised */ p2tr_triangle_unref (tri); } - while (! g_queue_is_empty (flipped_edges)) + while (! g_queue_is_empty (&flipped_edges)) { - P2trEdge *e = (P2trEdge*) g_queue_pop_head (flipped_edges); + P2trEdge *e = (P2trEdge*) g_queue_pop_head (&flipped_edges); e->delaunay = e->mirror->delaunay = FALSE; p2tr_edge_unref (e); } @@ -530,51 +501,55 @@ p2tr_cdt_flip_fix (P2trCDT *self, * THE NEW TRIANGLES MUST BE UNREFFED! * THE NEW EDGE MUST BE UNREFFED! */ -gboolean +static gboolean p2tr_cdt_try_flip (P2trCDT *self, P2trEdge *to_flip, GQueue *new_tris, P2trEdge **new_edge) { + /* C + * / | \ + * B-----A to_flip: A->B + * \ | / to_flip.Tri: ABC + * D + */ + P2trPoint *A, *B, *C, *D; + P2trTriangle *ABC, *ADB; + P2trEdge *DC; + new_edge = NULL; - if (to_flip->constrained || to_flip->flip_fixed) + if (to_flip->constrained || to_flip->delaunay) { return FALSE; } - // C - // / | \ - // B-----A to_flip: A->B - // \ | / to_flip.Tri: ABC - // D + A = P2TR_EDGE_START (to_flip); + B = to_flip->end; + C = p2tr_triangle_get_opposite_point (to_flip->tri, to_flip); + D = p2tr_triangle_get_opposite_point (to_flip->mirror->tri, to_flip->mirror); - P2trPoint *A = P2TR_EDGE_START (e); - P2trPoint *B = to_flip->end; - P2trPoint *C = p2tr_triangle_get_opposite_point (to_flip->tri, to_flip); - P2trPoint *D = p2tr_triangle_get_opposite_point (to_flip->mirror->tri, to_flip->mirror); - - P2trTriangle *ABC = to_flip->tri; - P2trTriangle *ADB = to_flip->mirror->tri; + ABC = to_flip->tri; + ADB = to_flip->mirror->tri; /* Check if the quadriliteral ADBC is concave (because if it is, we * can't flip the edge) */ - if (p2tr_triangle_get_angle_at(ABC, A) + p2tr_triangle_get_angle_at(ADB, A) >= Math.PI) + if (p2tr_triangle_get_angle_at(ABC, A) + p2tr_triangle_get_angle_at(ADB, A) >= G_PI) return FALSE; - if (p2tr_triangle_get_angle_at(ABC, B) + p2tr_triangle_get_angle_at(ADB, B) >= Math.PI) + if (p2tr_triangle_get_angle_at(ABC, B) + p2tr_triangle_get_angle_at(ADB, B) >= G_PI) return FALSE; p2tr_edge_remove (to_flip); - P2trEdge *DC = p2tr_mesh_new_edge (self->mesh, D, C, FALSE); + DC = p2tr_mesh_new_edge (self->mesh, D, C, FALSE); DC->delaunay = DC->mirror->delaunay = TRUE; - g_queue_push_tail (p2tr_mesh_new_triangle (self->mesh, + g_queue_push_tail (new_tris, p2tr_mesh_new_triangle (self->mesh, p2tr_point_get_edge_to (C, A), p2tr_point_get_edge_to (A, D), DC)); - g_queue_push_tail (p2tr_mesh_new_triangle (self->mesh, + g_queue_push_tail (new_tris, p2tr_mesh_new_triangle (self->mesh, p2tr_point_get_edge_to (D, B), p2tr_point_get_edge_to (B, C), DC->mirror)); @@ -590,15 +565,15 @@ p2tr_cdt_try_flip (P2trCDT *self, * may be very far from that point. * We have no choice but to check these and fix them if necessary */ -void +static void p2tr_cdt_on_new_point (P2trCDT *self, P2trPoint *pt) { GList *bad_tris = NULL; P2trTriangle *tri; - P2trHashSetIter iter + P2trHashSetIter iter; - p2tr_hash_set_iter_init (&iter, self->mesh->triangles) + p2tr_hash_set_iter_init (&iter, self->mesh->triangles); while (p2tr_hash_set_iter_next (&iter, (gpointer*)&tri)) { if (p2tr_triangle_circumcircle_contains_point (tri, &pt->c) diff --git a/refine/cdt.h b/refine/cdt.h index 5938d31..9b5588a 100644 --- a/refine/cdt.h +++ b/refine/cdt.h @@ -1,12 +1,35 @@ #ifndef __P2TC_REFINE_CDT_H__ #define __P2TC_REFINE_CDT_H__ +#include +#include "mesh.h" +#include "pslg.h" + typedef struct { P2trMesh *mesh; P2trPSLG *outline; } P2trCDT; -P2trCDT* p2tr_cdt_new (P2tCDT *cdt); +P2trCDT* p2tr_cdt_new (P2tCDT *cdt); + +gboolean p2tr_cdt_visible_from_edge (P2trCDT *self, + P2trEdge *e, + P2trVector2 *p); + +void p2tr_cdt_validate_edges (P2trCDT *self); + +void p2tr_cdt_validate_cdt (P2trCDT *self); + +P2trPoint* p2tr_cdt_insert_point (P2trCDT *self, + const P2trVector2 *pc); + +void p2tr_cdt_insert_point_into_triangle (P2trCDT *self, + P2trPoint *pt, + P2trTriangle *tri); + +GList* p2tr_cdt_split_edge (P2trCDT *self, + P2trEdge *e, + P2trPoint *C); #endif \ No newline at end of file diff --git a/refine/delaunay-terminator.h b/refine/delaunay-terminator.h new file mode 100644 index 0000000..a74cac0 --- /dev/null +++ b/refine/delaunay-terminator.h @@ -0,0 +1,86 @@ +#ifndef __P2TC_REFINE_DELAUNAY_TERMINATOR_H__ +#define __P2TC_REFINE_DELAUNAY_TERMINATOR_H__ + +typedef struct +{ + P2trCDT *mesh; + GQueue *Qs, *Qt; +} P2trDelaunayTerminator; + +gboolean +p2tr_cdt_test_encroachment_ignore_visibility (P2trVector2 *w, + P2trEdge *e) +{ + return p2tr_math_diametral_circle_contains (P2TR_EDGE_START(e) ,e->end, w); +} + +gboolean +p2tr_cdt_is_encroached (P2trMesh *mesh, + P2trEdge *e) +{ + P2trPoint *p; + P2trHashSetIter iter; + + if (! e->constrained) + return FALSE; + + p2tr_hash_set_iter_init (&iter, mesh->points); + while (p2tr_hash_set_iter_next (&iter, (gpointer*)&p)) + { + if (p == e->end || p == P2TR_EDGE_START(e)) + continue; + + if (p2tr_cdt_test_encroachment_ignore_visibility (&p->c, e) + && p2tr_cdt_visible_from_edge (mesh, e, &p->c)) + return TRUE; + } + return FALSE; +} + +gboolean +p2tr_cdt_is_encroached_by (P2trEdge *e, P2trVector2 *p) +{ + if (! e->constrained) + return FALSE; + + return p2tr_cdt_test_encroachment_ignore_visibility (&p->c, e) + && p2tr_cdt_visible_from_edge (mesh, e, &p->c); +} + + +P2trHashSet* +p2tr_cdt_get_segments_encroached_by (P2trCDT *self, + P2trVector2 *C) +{ + P2trHashSet *encroached_edges = p2tr_hash_set_new (g_direct_hash, + g_direct_equal, (GDestroyNotify) p2tr_edge_unref); + + P2trHashSetIter iter; + P2trEdge *e; + + p2tr_hash_set_iter_init (&iter, self->mesh->edges); + while (p2tr_hash_set_iter_next (&iter, (gpointer*)&e)) + if (e->constrained + && p2tr_hash_set_contains (encroached_edges, e->mirror) == FALSE + && p2tr_cdt_edge_will_be_encroached_by (self, e, C)) + { + p2tr_hash_set_insert (encroached_edges, e); + } + + return encroached_edges; +} + +gboolean +p2tr_cdt_is_encroached (P2trEdge *E) +{ + P2trTriangle *T1 = E->tri; + P2trTriangle *T2 = E->mirror->tri; + + if (! E->constrained) + return FALSE; + + return (T1 != NULL && p2tr_cdt_test_encroachment_ignore_visibility (p2tr_triangle_get_opposite_point (T1, E)->c, E)) + || (T2 != NULL && p2tr_cdt_test_encroachment_ignore_visibility (p2tr_triangle_get_opposite_point (T2, E)->c, E)); +} + +#endif \ No newline at end of file diff --git a/refine/edge.c b/refine/edge.c index b517e12..9a91c79 100644 --- a/refine/edge.c +++ b/refine/edge.c @@ -1,7 +1,10 @@ #include #include + #include "point.h" #include "edge.h" +#include "triangle.h" +#include "mesh.h" static void p2tr_edge_init (P2trEdge *self, @@ -88,8 +91,8 @@ p2tr_edge_remove (P2trEdge *self) if (mesh != NULL) { - p2tr_mesh_on_edge_removed (self); - p2tr_mesh_on_edge_removed (self->mirror); + p2tr_mesh_on_edge_removed (mesh, self); + p2tr_mesh_on_edge_removed (mesh, self->mirror); } } @@ -113,28 +116,6 @@ p2tr_edge_get_diametral_circle (P2trEdge *self, circle->radius = p2tr_vector2_norm (&radius); } -//public void p2tr_edge_remove(P2trTriangulation t) -//{ -// _p2tr_edge_remove(T, false); -//} - -//private void _p2tr_edge_remove(P2trTriangulation t, bool is_mirror) -//{ -// if (this.removed) -// return; -// -// t.edges.Remove(this); -// this.removed = true; -// -// this.start.p2tr_point_remove_edge(this); -// -// if (this.tri != null) -// this.tri.p2tr_triangle_remove(t); -// -// if (! is_mirror) -// this.mirror._p2tr_edge_remove(t, true); -//} - P2trMesh* p2tr_edge_get_mesh (P2trEdge *self) { @@ -147,13 +128,13 @@ p2tr_edge_get_mesh (P2trEdge *self) gdouble p2tr_edge_get_length(P2trEdge* self) { - return sqrt (p2tr_math_length_sq2 (&self->end, &P2TR_EDGE_START(self))); + return sqrt (p2tr_math_length_sq2 (&self->end->c, &P2TR_EDGE_START(self)->c)); } gdouble p2tr_edge_get_length_squared(P2trEdge* self) { - return p2tr_math_length_sq2 (&self->end, &P2TR_EDGE_START(self)); + return p2tr_math_length_sq2 (&self->end->c, &P2TR_EDGE_START(self)->c); } gdouble @@ -189,12 +170,15 @@ p2tr_edge_angle_between(P2trEdge *e1, P2trEdge *e2) * [180 - 360, 180 + 360] = [-180, +540] so we may need to subtract * 360 to put it back in the range [-180, +180]. */ + gdouble result; + if (e1->end != P2TR_EDGE_START(e2)) p2tr_exception_programmatic ("The end-point of the first edge isn't" " the end-point of the second edge!"); - gdouble result = G_PI - e1->angle + e2->angle; + result = G_PI - e1->angle + e2->angle; if (result > 2 * G_PI) result -= 2 * G_PI; + return result; } \ No newline at end of file diff --git a/refine/math.c b/refine/math.c index 4a6cc68..4e8ddb9 100644 --- a/refine/math.c +++ b/refine/math.c @@ -1,3 +1,4 @@ +#include #include #include "math.h" @@ -54,6 +55,46 @@ p2tr_matrix_det4 (gdouble a00, gdouble a01, gdouble a02, gdouble a03, a30, a31, a32); } +void +p2tr_math_triangle_circumcircle (const P2trVector2 *A, + const P2trVector2 *B, + const P2trVector2 *C, + P2trCircle *circle) +{ + /* | Ax Bx Cx | + * D = + | Ay By Cy | * 2 + * | +1 +1 +1 | + * + * | Asq Bsq Csq | + * X = + | Ay By Cy | / D + * | 1 1 1 | + * + * | Asq Bsq Csq | + * Y = - | Ax Bx Cx | / D + * | 1 1 1 | + */ + gdouble Asq = P2TR_VECTOR2_LEN_SQ (A); + gdouble Bsq = P2TR_VECTOR2_LEN_SQ (B); + gdouble Csq = P2TR_VECTOR2_LEN_SQ (C); + + gdouble invD = 1 / (2 * p2tr_matrix_det3 ( + A->x, B->x, C->x, + A->y, B->y, C->y, + 1, 1, 1)); + + circle->center.x = + p2tr_matrix_det3 ( + Asq, Bsq, Csq, + A->y, B->y, C->y, + 1, 1, 1) * invD; + + circle->center.y = - p2tr_matrix_det3 ( + Asq, Bsq, Csq, + A->x, B->x, C->x, + 1, 1, 1) * invD; + + circle->radius = sqrt (P2TR_VECTOR2_DISTANCE_SQ (A, &circle->center)); +} + /* The point in triangle test which is implemented below is based on the * algorithm which appears on: * @@ -199,7 +240,7 @@ p2tr_math_diametral_circle_contains (const P2trVector2 *X, p2tr_vector2_sub(X, W, &WX); p2tr_vector2_sub(Y, W, &WY); - return VECTOR2_DOT(&WX, &WY) <= 0; + return P2TR_VECTOR2_DOT(&WX, &WY) <= 0; } gboolean diff --git a/refine/math.h b/refine/math.h index d75c004..6f15b47 100644 --- a/refine/math.h +++ b/refine/math.h @@ -2,7 +2,8 @@ #define __P2TC_REFINE_MATH_H__ #include -#include "vector2.h" +#include "vector2.h" +#include "circle.h" gdouble p2tr_math_length_sq (gdouble x1, gdouble y1, @@ -11,7 +12,21 @@ gdouble p2tr_math_length_sq (gdouble x1, gdouble p2tr_math_length_sq2 (const P2trVector2 *pt1, const P2trVector2 *pt2); - + + +/** + * Find the circumscribing circle of a triangle defined by the given + * points. + * @param[in] A The first vertex of the triangle + * @param[in] B The second vertex of the triangle + * @param[in] C The third vertex of the triangle + * @param[out] circle The circumscribing circle of the triangle + */ +void p2tr_math_triangle_circumcircle (const P2trVector2 *A, + const P2trVector2 *B, + const P2trVector2 *C, + P2trCircle *circle); + typedef enum { P2TR_INTRIANGLE_OUT = -1, diff --git a/refine/mesh.c b/refine/mesh.c index bb10c80..4704135 100644 --- a/refine/mesh.c +++ b/refine/mesh.c @@ -15,7 +15,7 @@ p2tr_mesh_new (void) mesh->edges = p2tr_hash_set_new_default (); mesh->points = p2tr_hash_set_new_default (); mesh->triangles = p2tr_hash_set_new_default (); - + mesh->_is_clearing_now = FALSE; return mesh; @@ -29,10 +29,10 @@ p2tr_mesh_new_point (P2trMesh *self, pt->mesh = self; p2tr_mesh_ref (self); - + p2tr_hash_set_insert (self->points, pt); p2tr_point_ref (pt); - + return pt; } @@ -45,11 +45,25 @@ p2tr_mesh_new_edge (P2trMesh *self, P2trEdge *ed = p2tr_edge_new (start, end, constrained); p2tr_hash_set_insert (self->edges, ed); - p2tr_pdge_ref (ed); - + p2tr_edge_ref (ed); + return ed; } +P2trEdge* +p2tr_mesh_new_or_existing_edge (P2trMesh *self, + P2trPoint *start, + P2trPoint *end, + gboolean constrained) +{ + P2trEdge *result = p2tr_point_has_edge_to (start, end); + if (result) + p2tr_edge_ref (result); + else + result = p2tr_mesh_new_edge (self, start, end, constrained); + return result; +} + P2trTriangle* p2tr_mesh_new_triangle (P2trMesh *self, P2trEdge *AB, @@ -59,8 +73,8 @@ p2tr_mesh_new_triangle (P2trMesh *self, P2trTriangle *tr = p2tr_triangle_new (AB, BC, CA); p2tr_hash_set_insert (self->triangles, tr); - p2tr_pdge_ref (tr); - + p2tr_triangle_ref (tr); + return tr; } @@ -102,9 +116,9 @@ p2tr_mesh_clear (P2trMesh *self) { P2trHashSetIter iter; gpointer temp; - + self->_is_clearing_now = TRUE; - + p2tr_hash_set_iter_init (&iter, self->triangles); while (p2tr_hash_set_iter_next (&iter, &temp)) p2tr_triangle_remove ((P2trTriangle*)temp); @@ -127,7 +141,7 @@ void p2tr_mesh_free (P2trMesh *self) { p2tr_mesh_clear (self); - + p2tr_hash_set_free (self->points); p2tr_hash_set_free (self->edges); p2tr_hash_set_free (self->triangles); diff --git a/refine/mesh.h b/refine/mesh.h index d3b0df2..12539d3 100644 --- a/refine/mesh.h +++ b/refine/mesh.h @@ -27,6 +27,17 @@ P2trEdge* p2tr_mesh_new_edge (P2trMesh *mesh, P2trPoint *end, gboolean constrained); +/** + * Return a new edge between the two points if an edge doesn't exist, or + * return an existing edge between the two points if there is such one. + * THE RETURNED EDGE MUST BE UNREFFED, NO MATTER IF IT'S A NEW EDGE OR + * AN EXISTING EDGE! + */ +P2trEdge* p2tr_mesh_new_or_existing_edge (P2trMesh *self, + P2trPoint *start, + P2trPoint *end, + gboolean constrained); + P2trTriangle* p2tr_mesh_new_triangle (P2trMesh *mesh, P2trEdge *AB, P2trEdge *BC, diff --git a/refine/point.c b/refine/point.c index e4890b8..feee202 100644 --- a/refine/point.c +++ b/refine/point.c @@ -1,6 +1,7 @@ #include #include "point.h" #include "edge.h" +#include "mesh.h" P2trPoint* p2tr_point_new (const P2trVector2 *c) diff --git a/refine/point.h b/refine/point.h index ad16412..36ac404 100644 --- a/refine/point.h +++ b/refine/point.h @@ -39,6 +39,9 @@ void p2tr_point_free (P2trPoint *self); void p2tr_point_remove (P2trPoint *self); +P2trEdge* p2tr_point_has_edge_to (P2trPoint *start, + P2trPoint *end); + P2trEdge* p2tr_point_get_edge_to (P2trPoint *start, P2trPoint *end); diff --git a/refine/triangle.c b/refine/triangle.c index cd2df89..27477b3 100644 --- a/refine/triangle.c +++ b/refine/triangle.c @@ -1,10 +1,13 @@ #include #include + +#include "utils.h" +#include "math.h" + #include "point.h" #include "edge.h" #include "triangle.h" -#include "utils.h" -#include "math.h" +#include "mesh.h" P2trTriangle* p2tr_triangle_new (P2trEdge *AB, @@ -180,7 +183,6 @@ gdouble p2tr_triangle_smallest_non_constrained_angle (P2trTriangle *self) { gdouble result = G_MAXDOUBLE, angle; - gint i; if (! self->edges[0]->constrained || !self->edges[1]->constrained) { @@ -207,50 +209,20 @@ void p2tr_triangle_get_circum_circle (P2trTriangle *self, P2trCircle *circle) { - // | Ax Bx Cx | - // D = + | Ay By Cy | * 2 - // | +1 +1 +1 | - // - // | Asq Bsq Csq | - // X = + | Ay By Cy | / D - // | 1 1 1 | - // - // | Asq Bsq Csq | - // Y = - | Ax Bx Cx | / D - // | 1 1 1 | - P2trPoint *A = self->edges[0]->end; - P2trPoint *B = self->edges[1]->end; - P2trPoint *C = self->edges[2]->end; - - gdouble Asq = P2TR_VECTOR2_LEN_SQ (&A->c); - gdouble Bsq = P2TR_VECTOR2_LEN_SQ (&B->c); - gdouble Csq = P2TR_VECTOR2_LEN_SQ (&C->c); - - gdouble invD = 1 / (2 * p2tr_matrix_det3 ( - A->c.x, B->c.x, C->c.x, - A->c.y, B->c.y, C->c.y, - 1, 1, 1)); - - circle->center.x = + p2tr_matrix_det3 ( - Asq, Bsq, Csq, - A->c.y, B->c.y, C->c.y, - 1, 1, 1) * invD; - - circle->center.y = - p2tr_matrix_det3 ( - Asq, Bsq, Csq, - A->c.x, B->c.x, C->c.x, - 1, 1, 1) * invD; - - circle->radius = sqrt (P2TR_VECTOR2_DISTANCE_SQ (&A->c, &circle->center)); + p2tr_math_triangle_circumcircle ( + &self->edges[0]->end->c, + &self->edges[1]->end->c, + &self->edges[2]->end->c, + circle); } P2trInCircle p2tr_triangle_circumcircle_contains_point (P2trTriangle *self, P2trVector2 *pt) { - return p2tr_math_orient2d ( - &self->edges[0]->end.c, - &self->edges[1]->end.c, - &self->edges[2]->end.c, + return p2tr_math_incircle ( + &self->edges[0]->end->c, + &self->edges[1]->end->c, + &self->edges[2]->end->c, pt); } diff --git a/refine/triangle.h b/refine/triangle.h index d88fe65..f5b8444 100644 --- a/refine/triangle.h +++ b/refine/triangle.h @@ -2,6 +2,7 @@ #define __P2TC_REFINE_TRIANGLE_H__ #include +#include "math.h" #include "triangulation.h" /** diff --git a/refine/utils.c b/refine/utils.c new file mode 100644 index 0000000..6c05d6f --- /dev/null +++ b/refine/utils.c @@ -0,0 +1,19 @@ +#include +#include + +#include "utils.h" + +GList* +p2tr_utils_new_reversed_pointer_list (int count, ...) +{ + int i; + va_list args; + GList *result = NULL; + + va_start (args, count); + for (i = 0; i < count; i++) + result = g_list_prepend (result, va_arg (args, gpointer)); + va_end (args); + + return result; +} diff --git a/refine/utils.h b/refine/utils.h index 7af984a..93be8b1 100755 --- a/refine/utils.h +++ b/refine/utils.h @@ -71,6 +71,8 @@ extern "C" #define p2tr_exception_programmatic g_error #define p2tr_exception_geometric g_error +GList* p2tr_utils_new_reversed_pointer_list (int count, ...); + #ifdef __cplusplus } #endif -- 2.40.0