/* pdnmesh - a 2D finite element solver Copyright (C) 2001-2005 Sarod Yatawatta This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA $Id: poly.c,v 1.13 2005/02/11 18:11:28 sarod Exp $ */ /* polygon and related stuff */ #include #include #include /* for time() */ #include "types.h" extern int ntriangles; extern RBT_tree rt; extern DAG_tree dt; /* initialize a polygon */ void init_poly (polygon * poly) { poly->head = 0; poly->nedges = 0; } /* insert an edge to a polygon */ int insert_edge_to_poly (polygon * poly, poly_edge * e) { poly_elist *newnode; /* empty case */ if (!poly->head) { if ((poly->head = (poly_elist *) malloc (sizeof (poly_elist))) == 0) { fprintf (stderr, "%s: %d: no free memory", __FILE__, __LINE__); exit (1); } poly->head->data.p1 = e->p1; poly->head->data.p2 = e->p2; poly->head->data.type = e->type; poly->head->next = poly->head; poly->head->prev = poly->head; } else { /* not empty */ if ((newnode = (poly_elist *) malloc (sizeof (poly_elist))) == 0) { fprintf (stderr, "%s: %d: no free memory", __FILE__, __LINE__); exit (1); } newnode->data.p1 = e->p1; newnode->data.p2 = e->p2; newnode->data.type = e->type; newnode->prev = poly->head->prev; newnode->prev->next = newnode; newnode->next = poly->head; newnode->next->prev = newnode; poly->head = newnode; } poly->nedges += 1; return (0); } /* sanity check polygon */ /* arrange edges in correct adjacent order */ void arrange_polgon_edges (polygon * poly) { poly_elist *idx; int i; idx = poly->head; for (i = 0; i < poly->nedges; i++) { if ((idx) && (idx->next) && (idx->data.p2 != idx->next->data.p1)) { if (idx->data.p2 == idx->next->data.p2) { /* need to switch the next one */ idx->next->data.p2 = idx->next->data.p1; idx->next->data.p1 = idx->data.p2; } else if (idx->data.p1 == idx->next->data.p1) { /* need to switch the current one */ idx->data.p1 = idx->data.p2; idx->data.p2 = idx->next->data.p1; } else if (idx->data.p1 == idx->next->data.p2) { /* need to switch both */ idx->data.p1 = idx->data.p2; idx->data.p2 = idx->next->data.p2; idx->next->data.p2 = idx->next->data.p1; idx->next->data.p1 = idx->data.p2; } } #ifdef DEBUG printf ("poly: edge (%d,%d)\n", idx->data.p1, idx->data.p2); #endif idx = idx->next; } } typedef struct line_ { double p1x, p2x, p1y, p2y; } line; /* functions from sedgewick and dirk stuker */ static int ccw (double p0x, double p0y, double p1x, double p1y, double p2x, double p2y) { double dx1, dx2, dy1, dy2; dx1 = p1x - p0x; dy1 = p1y - p0y; dx2 = p2x - p0x; dy2 = p2y - p0y; #ifdef DEBUG printf ("ccw dx1=%lf, dy1=%lf, dx2=%lf dy2=%lf\n", dx1, dy1, dx2, dy2); #endif if (dx1 * dy2 > dy1 * dx2) return (1); if (dx1 * dy2 < dy1 * dx2) return (-1); if (dx1 * dy2 == dy1 * dx2) { if ((dx1 * dx2 < 0) || (dy1 * dy2 < 0)) { return (-1); } else if (dx1 * dx1 + dy1 * dy1 >= dx2 * dx2 + dy2 * dy2) { return (0); } /* else */ return (1); } /* will not reach here */ return (0); } /* general intersection, point overlap taken as intersection */ static int intersect (line e1, line e2) { int ccw11, ccw12, ccw21, ccw22; ccw11 = ccw (e1.p1x, e1.p1y, e1.p2x, e1.p2y, e2.p1x, e2.p1y); ccw12 = ccw (e1.p1x, e1.p1y, e1.p2x, e1.p2y, e2.p2x, e2.p2y); ccw21 = ccw (e2.p1x, e2.p1y, e2.p2x, e2.p2y, e1.p1x, e1.p1y); ccw22 = ccw (e2.p1x, e2.p1y, e2.p2x, e2.p2y, e1.p2x, e1.p2y); #ifdef DEBUG printf ("intersect %d %d %d %d\n", ccw11, ccw12, ccw21, ccw22); #endif return (((ccw11 * ccw12 < 0) && (ccw21 * ccw22 < 0)) || (!ccw11 || !ccw12 || !ccw21 || !ccw22)); } /* point overlap is not intersection */ static int clean_intersect (line e1, line e2) { int ccw11, ccw12, ccw21, ccw22; ccw11 = ccw (e1.p1x, e1.p1y, e1.p2x, e1.p2y, e2.p1x, e2.p1y); ccw12 = ccw (e1.p1x, e1.p1y, e1.p2x, e1.p2y, e2.p2x, e2.p2y); ccw21 = ccw (e2.p1x, e2.p1y, e2.p2x, e2.p2y, e1.p1x, e1.p1y); ccw22 = ccw (e2.p1x, e2.p1y, e2.p2x, e2.p2y, e1.p2x, e1.p2y); #ifdef DEBUG printf ("clean_intersect: (%lf %lf)-(%lf %lf) and (%lf %lf)-(%lf %lf)\n", e1.p1x, e1.p1y, e1.p2x, e1.p2y, e2.p1x, e2.p1y, e2.p2x, e2.p2y); printf ("clean_intersect: %d %d %d %d\n", ccw11, ccw12, ccw21, ccw22); #endif return (((ccw11 * ccw12 < 0) && (ccw21 * ccw22 < 0))); } /* check point is inside the polygon */ /* returns 1 if true */ /* note the points, and the edges has to be in ccw order */ int inside_poly (polygon * poly, int p) { int *parray; poly_elist *tempe; line lt, lv, lp; int i, j, count; if ((parray = (int *) calloc (poly->nedges + 1, sizeof (int))) == 0) { fprintf (stderr, "%s: %d: no free memory", __FILE__, __LINE__); exit (1); } tempe = poly->head; for (i = 1; i < poly->nedges + 1; i++) { parray[i] = tempe->data.p2; tempe = tempe->prev; #ifdef DEBUG printf ("inside_poly: %d \n", parray[i]); #endif } parray[0] = parray[i - 1]; #ifdef DEBUG printf ("inside_poly: %d \n", parray[0]); #endif /* run the vanilla algorithm */ count = 0; j = 0; /* test line */ lt.p1x = Mx (p,M); lt.p1y = My (p,M); srand(time(0)); /* FIXME! */ lt.p2y = 10.0 + rand (); lt.p2x = 10.0 + rand (); /* use a random number */ #ifdef DEBUG printf ("detect point (%lf,%lf)\n", lt.p1x, lt.p1y); #endif lv.p1x = Mx (p,M); lv.p1y = My (p,M); lv.p2x = Mx (p,M); lv.p2y = My (p,M); for (i = 1; i < poly->nedges + 1; i++) { lp.p1x = Mx (parray[i],M); lp.p1y = My (parray[i],M); lp.p2x = Mx (parray[i - 1],M); lp.p2y = My (parray[i - 1],M); if (intersect (lv, lp)) { free (parray); return (1); } lp.p2x = Mx (parray[i],M); lp.p2y = My (parray[i],M); if (!intersect (lp, lt)) { lp.p2x = Mx (parray[j],M); lp.p2y = My (parray[j],M); if (intersect (lp, lt)) { count += 1; #ifdef DEBUG printf ("case 1\n"); printf ("intersection (%lf,%lf)-(%lf,%lf) with (%lf,%lf)-(%lf,%lf)\n", lp.p1x, lp.p1y, lp.p2x, lp.p2y, lt.p1x, lt.p1y, lt.p2x, lt.p2y); printf ("intersect with line (%d,%d)\n", i, j); #endif } else { if ((i != j + 1) && (ccw (lt.p1x, lt.p1y, lt.p2x, lt.p2y, Mx (parray[j],M), My (parray[j],M)) * ccw (lt.p1x, lt.p1y, lt.p2x, lt.p2y, Mx (parray[i],M), My (parray[i],M)) < 1)) { count += 1; #ifdef DEBUG printf ("case 2\n"); #endif } } j = i; } } if ((j != poly->nedges) && (ccw (lt.p1x, lt.p1y, lt.p2x, lt.p2y, Mx (parray[j],M), My (parray[j],M)) * ccw (lt.p1x, lt.p1y, lt.p2x, lt.p2y, Mx (parray[1],M), My (parray[1],M)) == 1)) { count -= 1; #ifdef DEBUG printf ("j=%d poly edges=%d\n", j, poly->nedges); printf ("case 3\n"); printf ("count=%d\n", count); #endif } free (parray); /*printf("count=%d\n",count); */ return ((count % 2) == 1); } /* check if point p is inside polygon poly */ int inside_poly_point (polygon * poly, point p) { int *parray; poly_elist *tempe; line lt, lv, lp; int i, j, count; if ((parray = (int *) calloc (poly->nedges + 1, sizeof (int))) == 0) { fprintf (stderr, "%s: %d: no free memory", __FILE__, __LINE__); exit (1); } tempe = poly->head; for (i = 1; i < poly->nedges + 1; i++) { parray[i] = tempe->data.p2; tempe = tempe->prev; #ifdef DEBUG printf ("%d \n", parray[i]); #endif } parray[0] = parray[i - 1]; #ifdef DEBUG printf ("%d \n", parray[0]); #endif /* run the vanilla algorithm */ count = 0; j = 0; /* test line */ lt.p1x = p.x; lt.p1y = p.y; srand(time(0)); /* FIXME! */ lt.p2y = 10.0 + rand (); lt.p2x = 10.0 + rand (); /* use a random number */ #ifdef DEBUG printf ("detect point (%lf,%lf)\n", lt.p1x, lt.p1y); #endif lv.p1x = p.x; lv.p1y = p.y; lv.p2x = p.x; lv.p2y = p.y; for (i = 1; i < poly->nedges + 1; i++) { lp.p1x = Mx (parray[i],M); lp.p1y = My (parray[i],M); lp.p2x = Mx (parray[i - 1],M); lp.p2y = My (parray[i - 1],M); if (intersect (lv, lp)) { free (parray); return (1); } lp.p2x = Mx (parray[i],M); lp.p2y = My (parray[i],M); if (!intersect (lp, lt)) { lp.p2x = Mx (parray[j],M); lp.p2y = My (parray[j],M); if (intersect (lp, lt)) { count += 1; #ifdef DEBUG printf ("case 1\n"); printf ("intersection (%lf,%lf)-(%lf,%lf) with (%lf,%lf)-(%lf,%lf)\n", lp.p1x, lp.p1y, lp.p2x, lp.p2y, lt.p1x, lt.p1y, lt.p2x, lt.p2y); printf ("intersect with line (%d,%d)\n", i, j); #endif } else { if ((i != j + 1) && (ccw (lt.p1x, lt.p1y, lt.p2x, lt.p2y, Mx (parray[j],M), My (parray[j],M)) * ccw (lt.p1x, lt.p1y, lt.p2x, lt.p2y, Mx (parray[i],M), My (parray[i],M)) < 1)) { count += 1; #ifdef DEBUG printf ("case 2\n"); #endif } } j = i; } } if ((j != poly->nedges) && (ccw (lt.p1x, lt.p1y, lt.p2x, lt.p2y, Mx (parray[j],M), My (parray[j],M)) * ccw (lt.p1x, lt.p1y, lt.p2x, lt.p2y, Mx (parray[1],M), My (parray[1],M)) == 1)) { count -= 1; #ifdef DEBUG printf ("j=%d poly edges=%d\n", j, poly->nedges); printf ("case 3\n"); printf ("count=%d\n", count); #endif } free (parray); /*printf("count=%d\n",count); */ return ((count % 2) == 1); } /* function to remove intersection of the triangles with polygon edges */ int remove_polygon_mesh_intersections (polygon * poly) { line lt, lp; poly_elist *e, *newnode; triangle *rec; int break_loop, number_of_edges_checked; point p; int pn; /* cycle through the edge list */ e = poly->head; DAG_traverse_list_reset (&dt); number_of_edges_checked = poly->nedges; while (number_of_edges_checked) { lt.p1x = Mx (e->data.p1,M); lt.p1y = My (e->data.p1,M); lt.p2x = Mx (e->data.p2,M); lt.p2y = My (e->data.p2,M); #ifdef DEBUG printf ("remove_polygon_mesh: checking edge (%d,%d)\n", e->data.p1, e->data.p2); #endif /* flag reset */ /* only if we have enough length in the point to be split */ if (ABS (lt.p1x - lt.p2x) + ABS (lt.p1y - lt.p2y) < TOL) { fprintf (stderr, "%s: %d: Warning: comething wrong with your input file.\n Edges may be intersecting.\n", __FILE__, __LINE__); break; } break_loop = 0; /* chek each triangle */ /* for faster search, keep a list of live triangles */ rec = DAG_traverse_prune_list (&dt); while (rec) { if (rec && rec->status == LIVE) { /* triangle is alive and we need to check its edges for intersection */ lp.p1x = Mx (rec->p0,M); lp.p1y = My (rec->p0,M); lp.p2x = Mx (rec->p1,M); lp.p2y = My (rec->p1,M); /* check for intersection */ #ifdef DEBUG printf ("remove_polygon_mesh: check triangle %d(%d,%d,%d) status %d\n", rec->n, rec->p0, rec->p1, rec->p2, rec->status); #endif if (clean_intersect (lt, lp)) { #ifdef DEBUG printf ("remove_polygon_mesh: check triangle %d(%d,%d,%d) status %d\n", rec->n, rec->p0, rec->p1, rec->p2, rec->status); printf ("remove_polygon_mesh: case 1 edges %d,%d and %d,%d intersect\n", e->data.p1, e->data.p2, rec->p0, rec->p1); printf ("clean_intersect: (%lf %lf)-(%lf %lf) and (%lf %lf)-(%lf %lf)\n", lt.p1x, lt.p1y, lt.p2x, lt.p2y, lp.p1x, lp.p1y, lp.p2x, lp.p2y); #endif /* split polygon edge at mid point */ /* find mid point */ p.x = 0.5 * (lt.p1x + lt.p2x); p.y = 0.5 * (lt.p1y + lt.p2y); p.val = (e->data.type == DR ? FX : VAR); #ifdef DEBUG if (p.val == FX) { printf ("remove_polygon_mesh: fixed point\n"); } else { printf ("remove_polygon_mesh: variable point\n"); } #endif if ((p.z = (MY_DOUBLE *) malloc ((size_t) (degree_of_freedom) * sizeof (MY_DOUBLE))) == 0) { fprintf (stderr, "%s: %d: no free memory\n", __FILE__, __LINE__); exit (1); } p.z[0] = (Mz (e->data.p1,M) + Mz (e->data.p2,M)) * 0.5; /* modify other details */ /* insert it to mesh */ pn = insert_point_to_mesh (p); #ifdef DEBUG printf ("remove_polygon_mesh: inserted point %d potential %lf\n", pn, p.z[0]); #endif /* insert two new edges to polygon, remove old edge */ if ((newnode = (poly_elist *) malloc (sizeof (poly_elist))) == 0) { fprintf (stderr, "%s: %d: no free memory", __FILE__, __LINE__); exit (1); } newnode->data.p2 = e->data.p2; newnode->data.p1 = pn; newnode->data.type = e->data.type; newnode->prev = e; newnode->next = e->next; e->next->prev = newnode; e->next = newnode; e->data.p2 = pn; poly->nedges += 1; number_of_edges_checked = poly->nedges; break_loop = 1; } else { /* try the second edge */ lp.p1x = Mx (rec->p1,M); lp.p1y = My (rec->p1,M); lp.p2x = Mx (rec->p2,M); lp.p2y = My (rec->p2,M); /* check for intersection */ if (clean_intersect (lt, lp)) { #ifdef DEBUG printf ("remove_polygon_mesh: check triangle %d(%d,%d,%d) status %d\n", rec->n, rec->p0, rec->p1, rec->p2, rec->status); printf ("remove_polygon_mesh: case 2 edges %d,%d and %d,%d intersect\n", e->data.p1, e->data.p2, rec->p1, rec->p2); printf ("clean_intersect: (%lf %lf)-(%lf %lf) and (%lf %lf)-(%lf %lf)\n", lt.p1x, lt.p1y, lt.p2x, lt.p2y, lp.p1x, lp.p1y, lp.p2x, lp.p2y); #endif /* split polygon edge at mid point */ /* find mid point */ p.x = 0.5 * (lt.p1x + lt.p2x); p.y = 0.5 * (lt.p1y + lt.p2y); p.val = (e->data.type == DR ? FX : VAR); if ((p.z = (MY_DOUBLE *) malloc ((size_t) (degree_of_freedom) * sizeof (MY_DOUBLE))) == 0) { fprintf (stderr, "%s: %d: no free memory\n", __FILE__, __LINE__); exit (1); } p.z[0] = (Mz (e->data.p1,M) + Mz (e->data.p2,M)) * 0.5; /* modify other details */ /* insert it to mesh */ pn = insert_point_to_mesh (p); /* insert two new edges to polygon, remove old edge */ if ((newnode = (poly_elist *) malloc (sizeof (poly_elist))) == 0) { fprintf (stderr, "%s: %d: no free memory", __FILE__, __LINE__); exit (1); } newnode->data.p2 = e->data.p2; newnode->data.p1 = pn; newnode->data.type = e->data.type; newnode->prev = e; newnode->next = e->next; e->next->prev = newnode; e->next = newnode; e->data.p2 = pn; poly->nedges += 1; number_of_edges_checked = poly->nedges; break_loop = 1; } else { /* try the third edge */ lp.p1x = Mx (rec->p2,M); lp.p1y = My (rec->p2,M); lp.p2x = Mx (rec->p0,M); lp.p2y = My (rec->p0,M); /* check for intersection */ if (clean_intersect (lt, lp)) { #ifdef DEBUG printf ("remove_polygon_mesh: check triangle %d(%d,%d,%d) status %d\n", rec->n, rec->p0, rec->p1, rec->p2, rec->status); printf ("remove_polygon_mesh: case 3 edges %d,%d and %d,%d intersect\n", e->data.p1, e->data.p2, rec->p2, rec->p0); printf ("clean_intersect: (%lf %lf)-(%lf %lf) and (%lf %lf)-(%lf %lf)\n", lt.p1x, lt.p1y, lt.p2x, lt.p2y, lp.p1x, lp.p1y, lp.p2x, lp.p2y); #endif /* split polygon edge at mid point */ /* find mid point */ p.x = 0.5 * (lt.p1x + lt.p2x); p.y = 0.5 * (lt.p1y + lt.p2y); p.val = (e->data.type == DR ? FX : VAR); if ((p.z = (MY_DOUBLE *) malloc ((size_t) (degree_of_freedom) * sizeof (MY_DOUBLE))) == 0) { fprintf (stderr, "%s: %d: no free memory\n", __FILE__, __LINE__); exit (1); } p.z[0] = (Mz (e->data.p1,M) + Mz (e->data.p2,M)) * 0.5; /* modify other details */ /* insert it to mesh */ pn = insert_point_to_mesh (p); /* insert two new edges to polygon, remove old edge */ if ((newnode = (poly_elist *) malloc (sizeof (poly_elist))) == 0) { fprintf (stderr, "%s: %d: no free memory", __FILE__, __LINE__); exit (1); } newnode->data.p2 = e->data.p2; newnode->data.p1 = pn; newnode->data.type = e->data.type; newnode->prev = e; newnode->next = e->next; e->next->prev = newnode; e->next = newnode; e->data.p2 = pn; poly->nedges += 1; number_of_edges_checked = poly->nedges; break_loop = 1; } } } } rec = DAG_traverse_prune_list (&dt); if (break_loop) break; } if ( !break_loop ) number_of_edges_checked--; /* we traverse in reverse direction to prevent * modifying the same intersection over and over */ e = e->prev; /* start traversing the triangle list from beginning */ DAG_traverse_list_reset (&dt); } return (0); } /* copies polygon a to b, returns edges copied */ int copy_polygon (polygon * a, polygon * b) { poly_elist *current_node, *current_index; /* empty case */ if (!a->nedges) { return (0); } if ((b->head = (poly_elist *) malloc (sizeof (poly_elist))) == 0) { fprintf (stderr, "%s: %d: no free memory", __FILE__, __LINE__); exit (1); } b->head->data.p1 = a->head->data.p1; b->head->data.p2 = a->head->data.p2; b->head->data.type = a->head->data.type; current_node = b->head; current_index = a->head->next; for (b->nedges = 1; b->nedges < a->nedges; b->nedges++) { if ((current_node->next = (poly_elist *) malloc (sizeof (poly_elist))) == 0) { fprintf (stderr, "%s: %d: no free memory", __FILE__, __LINE__); exit (1); } current_node->next->data.p1 = current_index->data.p1; current_node->next->data.p2 = current_index->data.p2; current_node->next->data.type = current_index->data.type; current_node->next->prev = current_node; current_node = current_node->next; current_index = current_index->next; } current_node->next = b->head; b->head->prev = current_node; return (b->nedges); } /* destroy a polygon */ void destroy_polygon (polygon * a) { poly_elist *head, *temp; head = a->head; for (; a->nedges; a->nedges--) { temp = head->next; free (head); head = temp; } a->head = 0; } /* following are used in dxf.c */ /* routines to handle a list of polygons */ void init_boundary_list (boundary_list * b) { b->head = 0; b->count = 0; } /* insert a polygon */ int insert_poly_to_boundary (boundary_list * b, dxf_polygon * p) { poly_list *new_node, *current; /* new list node */ if ((new_node = (poly_list *) malloc (sizeof (poly_list))) == 0) { fprintf (stderr, "%s: %d: no free memory", __FILE__, __LINE__); exit (1); } new_node->data = p; new_node->number = b->count; /* empty boundary case is special */ if (!b->head) { b->head = new_node; b->count++; new_node->prev = new_node->next = 0; } else { /* find tail node */ current = b->head; while (current->next) { current = current->next; } /* now current->next==0 */ new_node->next = current->next; current->next = new_node; new_node->prev = current; b->count++; } return (b->count); } /* destroy a polygon */ void destroy_dxf_polygon (dxf_polygon * a) { dxf_int *head, *temp; head = a->head; for (; a->nedges; a->nedges--) { temp = head->next; free (head); head = temp; } a->head = 0; } /* remove a polygon from list, given by number */ void remove_poly_from_boundary (boundary_list * b, int number) { poly_list *current, *temp; /* first find the element with the given number */ current = b->head; while (current && (current->number != number)) { current = current->next; } /* we reach here if current==0 or current->number==number */ if (current) { /* removing head is special */ if (current == b->head) { b->head = current->next; if (b->head) b->head->prev = 0; b->count--; destroy_dxf_polygon (current->data); free (current); /* now reduce the node numbering by one */ current = b->head; while (current) { current->number--; current = current->next; } } else { /* not head */ current->prev->next = current->next; if (current->next) current->next->prev = current->prev; temp = current->next; b->count--; destroy_dxf_polygon (current->data); free (current); /* now reduce the node numbering by one */ current = temp; while (current) { current->number--; current = current->next; } } } } /* get polygon from list, given by number */ /* returns 0 if not found */ dxf_polygon * lookup_poly_from_boundary (boundary_list * b, int number) { poly_list *current; /* first find the element with the given number */ current = b->head; while (current && (current->number != number)) { current = current->next; } /* we reach here if current==0 or current->number==number */ if (current) { return (current->data); } else { return (0); } } /* insert edge if it is not included in the polygon * else remove it from the polygon */ /* returns 0 if inserted, 1 if removed, -1 if error */ int insert_remove_from_polygon (dxf_polygon * p, int n) { /* insert in number order */ dxf_int *h, *new_node; h = p->head; if (!h) { /* empty polygon */ /* insert */ if ((h = (dxf_int *) malloc (sizeof (dxf_int))) == 0) { fprintf (stderr, "%s: %d: no free memory", __FILE__, __LINE__); exit (1); } h->next = 0; h->prev = 0; h->n = n; p->head = h; p->nedges++; #ifdef DEBUG printf ("insert_remove_edge_poly:inserted %d at root, %d\n", n, p->nedges); #endif return (0); } /* root has the match */ if (h->n == n) { /* remove root */ new_node = h->next; if (new_node) new_node->prev = 0; p->head = new_node; free (h); p->nedges--; #ifdef DEBUG printf ("insert_remove_edge_poly:removed %d at root, %d\n", n, p->nedges); #endif return (1); } /* root has a greater number. insert at root */ if (h->n > n) { if ((new_node = (dxf_int *) malloc (sizeof (dxf_int))) == 0) { fprintf (stderr, "%s: %d: no free memory", __FILE__, __LINE__); exit (1); } new_node->n = n; new_node->next = h; h->prev = new_node; new_node->prev = 0; p->head = new_node; p->nedges++; #ifdef DEBUG printf ("insert_remove_edge_poly:inserted %d at root, %d\n", n, p->nedges); #endif return (0); } /* else find if n exists */ while (h->next && (h->n < n)) { h = h->next; #ifdef DEBUG printf ("insert_remove_edge_poly:traversing list %d\n", h->n); #endif } if (!h->next && h->n != n) { /* we have reached end of list, but n is not in the list */ if ((new_node = (dxf_int *) malloc (sizeof (dxf_int))) == 0) { fprintf (stderr, "%s: %d: no free memory", __FILE__, __LINE__); exit (1); } new_node->n = n; new_node->next = h->next; new_node->prev = h; h->next = new_node; p->nedges++; #ifdef DEBUG printf ("insert_remove_edge_poly:inserted %d at tail, %d\n", n, p->nedges); #endif return (0); } if (h->n == n) { /* we have found a match. remove this node */ new_node = h->next; if (h->next) h->next->prev = h->prev; if (h->prev) h->prev->next = new_node; free (h); p->nedges--; #ifdef DEBUG printf ("insert_remove_edge_poly:removed %d , %d\n", n, p->nedges); #endif return (1); } else { /* h->n > n */ if ((new_node = (dxf_int *) malloc (sizeof (dxf_int))) == 0) { fprintf (stderr, "%s: %d: no free memory", __FILE__, __LINE__); exit (1); } new_node->n = n; new_node->next = h; new_node->prev = h->prev; if (h->prev) h->prev->next = new_node; h->prev = new_node; p->nedges++; #ifdef DEBUG printf ("insert_remove_edge_poly:inserted %d at middle, %d\n", n, p->nedges); #endif return (0); } return (-1); } static int sort_edges_p (poly_list * p) { dxf_polygon *pgn; dxf_int *pint; int **p_to_e = 0; int *edges = 0; int i, j, e, p1; pgn = p->data; if (pgn) { /* allocate an array equal to number of edges */ /* format * | edge no. | point 1 | point 2 | */ if ((p_to_e = (int **) malloc (sizeof (int *) * (size_t) pgn->nedges)) == 0) { fprintf (stderr, "%s: %d: no free memory", __FILE__, __LINE__); exit (1); } for (i = 0; i < pgn->nedges; i++) { if ((p_to_e[i] = (int *) malloc (sizeof (int) * 3)) == 0) { fprintf (stderr, "%s: %d: no free memory", __FILE__, __LINE__); exit (1); } p_to_e[i][1] = p_to_e[i][2] = -1; } /* read each edge, and fill up array */ i = 0; pint = pgn->head; #ifdef DEBUG printf ("original poly: edge list:"); #endif while (pint) { /* get data corresponding to this edge */ /* fill up array */ p_to_e[i][0] = pint->n; p_to_e[i][1] = edge_array[pint->n].p1; p_to_e[i][2] = edge_array[pint->n].p2; pint = pint->next; i++; #ifdef DEBUG printf (" %d, ", p_to_e[i - 1][0]); #endif } #ifdef DEBUG printf ("\n"); #endif /* output edge array */ if ((edges = (int *) malloc (sizeof (int) * (size_t) pgn->nedges)) == 0) { fprintf (stderr, "%s: %d: no free memory", __FILE__, __LINE__); exit (1); } i = 0; e = p_to_e[i][0]; p1 = p_to_e[i][2]; while (i < pgn->nedges) { edges[i] = e; j = 0; while (j < pgn->nedges && !(e != p_to_e[j][0] && ((p1 == p_to_e[j][1]) || (p1 == p_to_e[j][2])))) { j++; } /* error */ if (j == pgn->nedges) { #ifdef DEBUG printf ("ERROR: boundary may not be closed\n"); #endif return (-1); } /* else we have a valid j */ e = p_to_e[j][0]; if (p1 == p_to_e[j][1]) { p1 = p_to_e[j][2]; } else { p1 = p_to_e[j][1]; } i++; } /* now traverse the list again, changin the edge * numbers */ #ifdef DEBUG printf ("sorted poly: edge list:"); #endif /* check to detect double loops * in edges due to inclusion of * edges not in the closed loop */ for (i = 1; i < pgn->nedges; i++) { if (edges[0] == edges[i]) { #ifdef DEBUG printf ("ERROR: boundary may have more than one loop\n"); #endif return (-1); } } i = 0; pint = pgn->head; while (pint) { pint->n = edges[i]; pint = pint->next; #ifdef DEBUG printf (" %d, ", edges[i]); #endif i++; } #ifdef DEBUG printf ("\n"); #endif } free (edges); for (i = 0; i < pgn->nedges; i++) { free (p_to_e[i]); } free (p_to_e); return (0); } /* sort all edges in polygons of the * boundaries so that they are adjacent */ int sort_edges_in_polygons (boundary_list * b) { int i; int return_val = 0; poly_list *p; if (b) { p = b->head; for (i = 0; i < b->count; i++) { return_val += sort_edges_p (p); p = p->next; } } return (return_val); }