/*****************************************************************************/ /* */ /* F I S T : Fast, Industrial-Strength Triangulation */ /* */ /*****************************************************************************/ /* */ /* (C) Martin Held */ /* (C) Universitaet Salzburg, Salzburg, Austria */ /* */ /* This code is not in the public domain. All rights reserved! Please make */ /* sure to read the full copyright statement contained in api_functions.cpp. */ /* */ /*****************************************************************************/ /* */ /* get standard libraries */ /* */ #include #include #include #include /* */ /* get my header files */ /* */ #include "fpkernel.h" #include "martin.h" #include "defs.h" #include "list.h" #include "header.h" #include "basic.h" #include "numerics.h" #include "bv_tree.h" #ifdef GRAPHICS #include "graphics.h" #endif /* */ /* function prototypes of functions provided in this file */ /* */ void FindLeftMostVertex(listdef* list, list_ind ind, list_ind *left_ind, int *left_i); void ConstructBridges(global_struct* all, int i1, int i2); boolean FindBridge(global_struct *all, list_ind ind, int i, int start, list_ind *ind1, int *i1); void InsertBridge(global_struct *all, list_ind ind1, int i1, list_ind ind3, int i3); void SimpleBridge(global_struct *all, list_ind ind1, list_ind ind2); void FreeBridges(bridgedef* bridge); int d_comp(const void *a, const void *); int l_comp(const void *a, const void *); #define BLOCK_SIZE 65536 void InitBridgeDefaults(bridgedef* bridge) { bridge->distances = (distance*)NULL; bridge->max_num_dist = 0; bridge->left_most = (left*)NULL; bridge->max_num_left_most = 0; } /* */ /* This routine constructs bridges for a multiply-connected polygon. */ /* A "bridge" is nothing but a pair of segments that is used for linking an */ /* island loop with a boundary loop. That is, it transforms a */ /* multiply-connected polygon into a simply-connected polygon. Formally */ /* speaking, the resulting polygon isn't truly simple as part of its */ /* boundary overlaps (at the bridges). */ /* */ /* Of course, the bridge routines also have a "desperate mode"!! E.g., we */ /* have to handle islands whose left-most point lies outside of the boundary */ /* polygon, and similar problems... */ /* */ void ConstructBridges(global_struct* all, int loop_min, int loop_max) { #ifndef NDEBUG griddef *grid = &all->c_grid; #endif listdef *list = &all->c_list; bridgedef *bridge = &all->c_bridge; datadef *data = &all->c_data; int i0, i, j, i1, num_dist, num_left_most; int ind0, ind1; assert(!grid->no_grid_yet); assert(loop_max > loop_min); assert(loop_min >= 0); assert(loop_max <= all->c_list.num_loops); num_left_most = loop_max - loop_min - 1; if (num_left_most > bridge->max_num_left_most) { bridge->max_num_left_most = num_left_most; bridge->left_most = (left*) ReallocateArray(bridge->memptr, bridge->left_most, bridge->max_num_left_most, sizeof(left), "bridge:left_most"); } /* */ /* insert all vertices of the outer loop into a grid structure */ /* */ BuildBridgeBuckets(all, list->loops[loop_min], true); /* */ /* for each contour, find the left-most vertex. (we will use the fact */ /* that the vertices appear in sorted order!) */ /* */ FindLeftMostVertex(list, list->loops[loop_min], &ind0, &i0); j = 0; for (i = loop_min + 1; i < loop_max; ++i) { FindLeftMostVertex(list, list->loops[i], &(bridge->left_most[j].ind), &(bridge->left_most[j].index)); ++j; } /* */ /* sort the inner contours according to their left-most vertex */ /* */ qsort(bridge->left_most, num_left_most, sizeof(left), &l_comp); /* */ /* construct bridges. every bridge will eminate at the left-most point of */ /* its corresponding inner loop. */ /* */ num_dist = data->num_pnts + 2 * list->num_loops; if (num_dist > bridge->max_num_dist) { bridge->distances = CORE_ReallocateArray(bridge->memptr, bridge->distances, bridge->max_num_dist, num_dist, distance, "bridge:distances"); bridge->max_num_dist = num_dist; } for (j = 0; j < num_left_most; ++j) { if (!FindBridge(all, ind0, i0, bridge->left_most[j].index, &ind1, &i1)) { if (all->rt_opt.verbose) FIST_Warning("ConstructBridges() -- the contour loops intersect!\n"); } /* */ /* insert all vertices of the current hole loop into a grid structure */ /* */ BuildBridgeBuckets(all, bridge->left_most[j].ind, false); if (i1 == bridge->left_most[j].index) /* */ /* the left-most node of the hole coincides with a node of the */ /* boundary */ /* */ SimpleBridge(all, ind1, bridge->left_most[j].ind); else /* */ /* two bridge edges need to be inserted */ /* */ InsertBridge(all, ind1, i1, bridge->left_most[j].ind, bridge->left_most[j].index); } return; } void SimpleBridge(global_struct *all, list_ind ind1, list_ind ind2) { listdef *list = &all->c_list; datadef *data = &all->c_data; list_ind prev, next; int i1, i2, prv, nxt; int angle; /* */ /* change the links */ /* */ RotateLinks(list, ind1, ind2); /* */ /* reset the angles */ /* */ i1 = GetIndex(list, ind1); next = GetNextNode(list, ind1); nxt = GetIndex(list, next); prev = GetPrevNode(list, ind1); prv = GetIndex(list, prev); angle = IsConvexAngle(list, data, prv, i1, nxt, ind1); SetAngle(list, ind1, angle); #ifdef GRAPHICS if (all->rt_opt.graphics) { if (angle == 1) DrawPnt(data->points[i1], ConvexColor); else if (angle == 2) DrawPnt(data->points[i1], ZeroColor); else if (angle == 0) DrawPnt(data->points[i1], TangentColor); } #endif i2 = GetIndex(list, ind2); next = GetNextNode(list, ind2); nxt = GetIndex(list, next); prev = GetPrevNode(list, ind2); prv = GetIndex(list, prev); angle = IsConvexAngle(list, data, prv, i2, nxt, ind2); SetAngle(list, ind2, angle); SetBridgeNodePair(list, ind1, ind2); return; } void InsertBridge(global_struct *all, list_ind ind1, int i1, list_ind ind3, int i3) { griddef *grid = &all->c_grid; listdef *list = &all->c_list; datadef *data = &all->c_data; list_ind ind2, ind4, prev, next; int prv, nxt, angle; bounding_box bb; /* */ /* duplicate nodes in order to form end points of the bridge edges */ /* */ ind2 = MakeNode(list, i1); InsertAfter(list, ind1, ind2); SetOriginal(list, ind2, GetOriginal(list, ind1)); ind4 = MakeNode(list, i3); InsertAfter(list, ind3, ind4); SetOriginal(list, ind4, GetOriginal(list, ind3)); /* */ /* insert the bridge edges into the boundary loops */ /* */ SplitSplice(list, ind1, ind2, ind3, ind4); #ifdef GRAPHICS /* */ /* update the graphics */ /* */ if (all->rt_opt.graphics) { DrawSeg(data->points[i1], data->points[i3], BridgeColor); AddEdgeToBuffer(&all->c_redraw, i1, i3, BridgeColor); } #endif /* */ /* reset the angles */ /* */ next = GetNextNode(list, ind1); nxt = GetIndex(list, next); prev = GetPrevNode(list, ind1); prv = GetIndex(list, prev); angle = IsConvexAngle(list, data, prv, i1, nxt, ind1); SetAngle(list, ind1, angle); #ifdef GRAPHICS if (all->rt_opt.graphics) { if (angle == 1) DrawPnt(data->points[i1], ConvexColor); else if (angle == 2) DrawPnt(data->points[i1], ZeroColor); else if (angle == 0) DrawPnt(data->points[i1], TangentColor); } #endif next = GetNextNode(list, ind2); nxt = GetIndex(list, next); prev = GetPrevNode(list, ind2); prv = GetIndex(list, prev); angle = IsConvexAngle(list, data, prv, i1, nxt, ind2); SetAngle(list, ind2, angle); next = GetNextNode(list, ind3); nxt = GetIndex(list, next); prev = GetPrevNode(list, ind3); prv = GetIndex(list, prev); angle = IsConvexAngle(list, data, prv, i3, nxt, ind3); SetAngle(list, ind3, angle); #ifdef GRAPHICS if (all->rt_opt.graphics) { if (angle == 1) DrawPnt(data->points[i3], ConvexColor); else if (angle == 2) DrawPnt(data->points[i3], ZeroColor); else if (angle == 0) DrawPnt(data->points[i3], TangentColor); } #endif next = GetNextNode(list, ind4); nxt = GetIndex(list, next); prev = GetPrevNode(list, ind4); prv = GetIndex(list, prev); angle = IsConvexAngle(list, data, prv, i3, nxt, ind4); SetAngle(list, ind4, angle); BBox(data, i1, i3, bb); if(!grid->no_grid_yet) InsertSegmentIntoGrid(data, grid, bb); SetBridgeNodePair(list, ind1, ind2); SetBridgeNodePair(list, ind3, ind4); return; } /* */ /* we try to find a vertex i1 on the loop which contains i such that i1 */ /* is close to start, and such that i1, start is a valid diagonal */ /* */ boolean FindBridge(global_struct *all, list_ind ind, int i, int start, list_ind *ind1, int *i1) { datadef *data = &all->c_data; listdef *list = &all->c_list; bridgedef *bridge = &all->c_bridge; tmp_data_def tmp_data; int i0, i2, j, num_dist, grid_offset, number_of_tries; list_ind ind0, ind2; bounding_box bb; boolean convex, cone_ok, grid_exhausted, check_cone, cone_strict; #ifdef GRAZING machine_double x_start; #endif /* */ /* sort the points according to their distance from start. */ /* */ *ind1 = ind; *i1 = i; if (*i1 == start) return true; cone_strict = true; check_cone = true; cone_ok = true; number_of_tries = 0; do { num_dist = 0; grid_offset = 0; #ifdef GRAZING x_start = data->points[start].x + EPS; #endif do { /* */ /* find a valid diagonal. note that no node with index i1 > start */ /* can be feasible! (if --DGRAZING is specified at compile time */ /* then we also consider points i1 with x-coordinate similar to */ /* that of start. */ /* */ #ifdef GRAZING ScanBridgeBuckets(all, start, grid_offset, bridge->distances, &num_dist, &grid_exhausted, x_start); #else ScanBridgeBuckets(all, start, grid_offset, bridge->distances, &num_dist, &grid_exhausted); #endif qsort(bridge->distances, num_dist, sizeof(distance), &d_comp); for (j = 0; j < num_dist; ++j) { *ind1 = bridge->distances[j].ind; *i1 = GetIndex(list,*ind1); if (*i1 == start) return true; ind0 = GetPrevNode(list,*ind1); i0 = GetIndex(list,ind0); ind2 = GetNextNode(list,*ind1); i2 = GetIndex(list,ind2); convex = GetAngle(list,*ind1) > 0; if (check_cone) { #ifdef GRAZING IsInConeEps(data, tmp_data, i0, *i1, i2, start, convex, cone_ok); #else if (cone_strict) { IsInConeStrict(data, tmp_data, i0, *i1, i2, start, convex, cone_ok, THRES); } else { IsInCone(data, tmp_data, i0, *i1, i2, start, convex, cone_ok); } #endif } if (cone_ok) { BBox(data, *i1, start, bb); if (!GridIntersectionExists(all, bb, -1, -1, *ind1, -1)) { return check_cone; } } } ++grid_offset; } while (!grid_exhausted); /* */ /* the left-most point of the hole does not lie within the outer */ /* boundary! what is the best bridge in this case??? we'll make a */ /* brute-force decision... */ /* */ ++number_of_tries; if (number_of_tries == 1) { cone_strict = false; cone_ok = true; } else if (number_of_tries == 2) { check_cone = false; cone_ok = true; } } while (number_of_tries <= 3); /* */ /* still no diagonal??? yikes! oh well, this polygon is messed up badly! */ /* time for genuine desperate mode... */ /* */ *ind1 = ind; *i1 = i; return false; } void FindLeftMostVertex(listdef* list, list_ind ind, list_ind *left_ind, int *left_i) { list_ind ind1; int i1; i1 = GetIndex(list,ind); *left_ind = ind; *left_i = i1; ind1 = GetNextNode(list,ind); i1 = GetIndex(list,ind1); while (ind1 != ind) { if (i1 < *left_i) { *left_ind = ind1; *left_i = i1; } else if (i1 == *left_i) { if (GetAngle(list,ind1) < 0) { *left_ind = ind1; *left_i = i1; } } ind1 = GetNextNode(list,ind1); i1 = GetIndex(list,ind1); } return; } int l_comp(const void *a, const void *b) { if (((left*)a)->index < ((left*)b)->index) return -1; else if (((left*)a)->index > ((left*)b)->index) return 1; else return 0; } int d_comp(const void *a, const void *b) { if (((distance*)a)->dist < ((distance*)b)->dist) return -1; else if (((distance*)a)->dist > ((distance*)b)->dist) return 1; else return 0; } void FreeBridges(bridgedef* bridge) { bridge->max_num_dist = 0; bridge->max_num_left_most = 0; FreeMemory(bridge->memptr, (void**) &bridge->left_most, "bridge:left_most"); CORE_FreeMemory(bridge->memptr, &bridge->distances, "bridge:distances"); return; }