Index: cdt/point.h =================================================================== --- cdt/point.h (revision 32651) +++ cdt/point.h (nonexistent) @@ -1,72 +0,0 @@ -#ifndef POINT_H -#define POINT_H - -#include -#include - -#include "typedefs.h" - -struct point_s { - pos_t pos; - edgelist_node_t *adj_edges; - trianglelist_node_t *adj_triangles; - - void *data; -}; - -typedef point_t* point_ptr_t; - - -/* List */ -#define LST(x) pointlist_ ## x -#define LST_ITEM_T point_ptr_t -#define LST_DONT_TYPEDEF_NODE - -#include "list/list.h" - -#ifndef LST_DONT_UNDEF - #undef LST - #undef LST_ITEM_T - #undef LST_DONT_TYPEDEF_NODE -#endif - -#define POINTLIST_FOREACH(_loop_item_, _list_) do { \ - pointlist_node_t *_node_ = _list_; \ - while (_node_ != NULL) { \ - point_t *_loop_item_ = _node_->item; - -#define POINTLIST_FOREACH_END() \ - _node_ = _node_->next; \ - } \ -} while(0) - - -/* Vector */ -#define GVT(x) vtpoint_ ## x -#define GVT_ELEM_TYPE point_ptr_t -#define GVT_SIZE_TYPE size_t -#define GVT_DOUBLING_THRS 4096 -#define GVT_START_SIZE 32 -#define GVT_FUNC -#define GVT_SET_NEW_BYTES_TO 0 -#define GVT_ELEM_CONSTRUCTOR -#define GVT_ELEM_DESTRUCTOR -#define GVT_ELEM_COPY - -#include -#define GVT_REALLOC(vect, ptr, size) realloc(ptr, size) -#define GVT_FREE(vect, ptr) free(ptr) -int GVT(constructor)(GVT(t) *vect, GVT_ELEM_TYPE *elem); -void GVT(destructor)(GVT(t) *vect, GVT_ELEM_TYPE *elem); -#include - -#define VTPOINT_FOREACH(_loop_item_, _vt_) do { \ - int _i_; \ - for (_i_ = 0; _i_ < vtpoint_len(_vt_); _i_++) { \ - point_t *_loop_item_ = (_vt_)->array[_i_]; - -#define VTPOINT_FOREACH_END() \ - } \ -} while(0) - -#endif Index: cdt/cdt.h =================================================================== --- cdt/cdt.h (revision 32651) +++ cdt/cdt.h (nonexistent) @@ -1,66 +0,0 @@ -/* - * Copyright (C) 2018 Wojciech Krutnik - * - * Constrained Delaunay Triangulation using incremental algorithm, as described in: - * Yizhi Lu and Wayne Wei-Ming Dai, "A numerical stable algorithm for constructing - * constrained Delaunay triangulation and application to multichip module layout," - * China., 1991 International Conference on Circuits and Systems, Shenzhen, 1991, - * pp. 644-647 vol.2. - */ - -#ifndef CDT_H -#define CDT_H - -#include "typedefs.h" -#include "point.h" -#include "edge.h" -#include "triangle.h" - - -typedef struct { - vtpoint_t points; - vtedge_t edges; - vttriangle_t triangles; - - pos_t bbox_tl; - pos_t bbox_br; -} cdt_t; - - -void cdt_init(cdt_t *cdt, coord_t bbox_x1, coord_t bbox_y1, coord_t bbox_x2, coord_t bbox_y2); -void cdt_free(cdt_t *cdt); - -point_t *cdt_insert_point(cdt_t *cdt, coord_t x, coord_t y); -void cdt_delete_point(cdt_t *cdt, point_t *p); /* any edge adjecent to this point cannot be constrained */ -edge_t *cdt_insert_constrained_edge(cdt_t *cdt, point_t *p1, point_t *p2); -void cdt_delete_constrained_edge(cdt_t *cdt, edge_t *edge); - -int cdt_check_delaunay(cdt_t *cdt, pointlist_node_t **point_violations, trianglelist_node_t **triangle_violations); -void cdt_dump_animator(cdt_t *cdt, int show_circles, pointlist_node_t *point_violations, trianglelist_node_t *triangle_violations); - - -edge_t *get_edge_from_points(point_t *p1, point_t *p2); - -#define ORIENT_CCW(a, b, c) (orientation(a, b, c) < 0) -#define ORIENT_CW(a, b, c) (orientation(a, b, c) > 0) -#define ORIENT(dir, a, b, c) ((dir) ? ORIENT_CW(a, b, c) : ORIENT_CCW(a, b, c)) -/* TODO: check epsilon for collinear case? */ -#define ORIENT_COLLINEAR(a, b, c) (orientation(a, b, c) == 0) -#define ORIENT_CCW_CL(a, b, c) (orientation(a, b, c) <= 0) -static inline double orientation(point_t *p1, point_t *p2, point_t *p3) -{ - return ((double)p2->pos.y - (double)p1->pos.y) * ((double)p3->pos.x - (double)p2->pos.x) - - ((double)p2->pos.x - (double)p1->pos.x) * ((double)p3->pos.y - (double)p2->pos.y); -} - -#define LINES_INTERSECT(p1, q1, p2, q2) \ - (ORIENT_CCW(p1, q1, p2) != ORIENT_CCW(p1, q1, q2) && ORIENT_CCW(p2, q2, p1) != ORIENT_CCW(p2, q2, q1)) - -#define EDGE_OTHER_POINT(edge, point) \ - ((edge)->endp[0] != (point) ? (edge)->endp[0] : (edge)->endp[1]) - -#define DIST2(p, q) \ - (((double)((p)->pos.x - (q)->pos.x) * (double)((p)->pos.x - (q)->pos.x)) \ - + ((double)((p)->pos.y - (q)->pos.y) * (double)((p)->pos.y - (q)->pos.y))) - -#endif Index: cdt/edge.c =================================================================== --- cdt/edge.c (revision 32651) +++ cdt/edge.c (nonexistent) @@ -1,22 +0,0 @@ -#define LST_DONT_UNDEF -#define GVT_DONT_UNDEF -#include "edge.h" - -static int LST(compare_func)(LST_ITEM_T *a, LST_ITEM_T *b) -{ - return *a == *b; -} - -int GVT(constructor)(GVT(t) *vect, GVT_ELEM_TYPE *elem) -{ - *elem = calloc(1, sizeof(**elem)); - return *elem == NULL; -} - -void GVT(destructor)(GVT(t) *vect, GVT_ELEM_TYPE *elem) -{ - free(*elem); -} - -#include "list/list.c" -#include Index: cdt/triangle.c =================================================================== --- cdt/triangle.c (revision 32651) +++ cdt/triangle.c (nonexistent) @@ -1,22 +0,0 @@ -#define LST_DONT_UNDEF -#define GVT_DONT_UNDEF -#include "triangle.h" - -static int LST(compare_func)(LST_ITEM_T *a, LST_ITEM_T *b) -{ - return *a == *b; -} - -int GVT(constructor)(GVT(t) *vect, GVT_ELEM_TYPE *elem) -{ - *elem = calloc(1, sizeof(**elem)); - return *elem == NULL; -} - -void GVT(destructor)(GVT(t) *vect, GVT_ELEM_TYPE *elem) -{ - free(*elem); -} - -#include "list/list.c" -#include Index: cdt/typedefs.h =================================================================== --- cdt/typedefs.h (revision 32651) +++ cdt/typedefs.h (nonexistent) @@ -1,19 +0,0 @@ -#ifndef TYPEDEFS_H -#define TYPEDEFS_H - -typedef int coord_t; - -typedef struct { - coord_t x; - coord_t y; -} pos_t; - -typedef struct point_s point_t; -typedef struct edge_s edge_t; -typedef struct triangle_s triangle_t; - -typedef struct pointlist_node_s pointlist_node_t; -typedef struct edgelist_node_s edgelist_node_t; -typedef struct trianglelist_node_s trianglelist_node_t; - -#endif Index: cdt/point.c =================================================================== --- cdt/point.c (revision 32651) +++ cdt/point.c (nonexistent) @@ -1,22 +0,0 @@ -#define LST_DONT_UNDEF -#define GVT_DONT_UNDEF -#include "point.h" - -static int LST(compare_func)(LST_ITEM_T *a, LST_ITEM_T *b) -{ - return *a == *b; -} - -int GVT(constructor)(GVT(t) *vect, GVT_ELEM_TYPE *elem) -{ - *elem = calloc(1, sizeof(**elem)); - return *elem == NULL; -} - -void GVT(destructor)(GVT(t) *vect, GVT_ELEM_TYPE *elem) -{ - free(*elem); -} - -#include "list/list.c" -#include Index: cdt/cdt_test.c =================================================================== --- cdt/cdt_test.c (revision 32651) +++ cdt/cdt_test.c (nonexistent) @@ -1,222 +0,0 @@ -#include -#include -#include "cdt.h" - -#define ORIENT_CCW(a, b, c) (orientation(a, b, c) < 0) -#define ORIENT_CW(a, b, c) (orientation(a, b, c) > 0) -/* TODO: check epsilon for collinear case? */ -#define ORIENT_COLLINEAR(a, b, c) (orientation(a, b, c) == 0) -#define ORIENT_CCW_CL(a, b, c) (orientation(a, b, c) <= 0) -static double orientation(point_t *p1, point_t *p2, point_t *p3) -{ - return ((double)p2->pos.y - (double)p1->pos.y) * ((double)p3->pos.x - (double)p2->pos.x) - - ((double)p2->pos.x - (double)p1->pos.x) * ((double)p3->pos.y - (double)p2->pos.y); -} -#define LINES_INTERSECT(p1, q1, p2, q2) \ - (ORIENT_CCW(p1, q1, p2) != ORIENT_CCW(p1, q1, q2) && ORIENT_CCW(p2, q2, p1) != ORIENT_CCW(p2, q2, q1)) - -cdt_t cdt; - -int main(void) -{ - point_t *p, *p1, *p2, *pd[1000]; - edge_t *e, *ed[500]; - int i, j, e_num; - clock_t t; - pointlist_node_t *p_violations = NULL; - - //cdt_init(&cdt, 1000, 1000, 5000, 5000); - cdt_init(&cdt, 0, 0, 100000, 100000); - - /* - cdt_insert_point(&cdt, 2500, 3000); - cdt_insert_point(&cdt, 2600, 3000); - cdt_insert_point(&cdt, 2700, 3000); - cdt_insert_point(&cdt, 2800, 3000); - cdt_insert_point(&cdt, 2900, 3000); - cdt_insert_point(&cdt, 3000, 3000); - cdt_insert_point(&cdt, 3100, 3000); - cdt_insert_point(&cdt, 3200, 3000); - cdt_insert_point(&cdt, 3300, 3000); - cdt_insert_point(&cdt, 2800, 4800); - */ - - /* - cdt_insert_point(&cdt, 2700, 2700); - cdt_insert_point(&cdt, 2400, 2400); - cdt_insert_point(&cdt, 2400, 3000); - - cdt_insert_point(&cdt, 3400, 2700); - cdt_insert_point(&cdt, 3700, 2400); - cdt_insert_point(&cdt, 3700, 3000); - - cdt_insert_point(&cdt, 2900, 2700); - cdt_insert_point(&cdt, 3000, 2700); - cdt_insert_point(&cdt, 3100, 2700); - cdt_insert_point(&cdt, 3200, 2700); - */ - - /* - srand(time(NULL)); - t = clock(); - for (i = 0; i < 1000; i++) { - cdt_insert_point(&cdt, rand()%99999 + 1, rand()%99999 + 1); - } - t = clock() - t; - fprintf(stderr, "Triangulation time: %f\n", ((float)t)/CLOCKS_PER_SEC); - */ - - /* octagon */ - /* - cdt_insert_point(&cdt, 4000, 3000); - cdt_insert_point(&cdt, 3700, 3700); - cdt_insert_point(&cdt, 3000, 4000); - cdt_insert_point(&cdt, 2300, 3700); - cdt_insert_point(&cdt, 2000, 3000); - cdt_insert_point(&cdt, 2300, 2300); - cdt_insert_point(&cdt, 3000, 2000); - cdt_insert_point(&cdt, 3700, 2300); - - p = cdt_insert_point(&cdt, 3000, 3000); - cdt_delete_point(&cdt, p); - */ - - /* concave poly */ - /* - cdt_insert_point(&cdt, 2000, 4000); - cdt_insert_point(&cdt, 3000, 3500); - cdt_insert_point(&cdt, 4000, 4000); - cdt_insert_point(&cdt, 4000, 2000); - cdt_insert_point(&cdt, 2000, 2000); - - p = cdt_insert_point(&cdt, 3000, 3000); - cdt_delete_point(&cdt, p); - */ - - /* constrained edge */ - /* - p1 = cdt_insert_point(&cdt, 1500, 3000); - cdt_insert_point(&cdt, 2000, 3500); - cdt_insert_point(&cdt, 2500, 2500); - cdt_insert_point(&cdt, 3000, 3500); - cdt_insert_point(&cdt, 3500, 2500); - cdt_insert_point(&cdt, 4000, 3500); - p2 = cdt_insert_point(&cdt, 4500, 3000); - - e = cdt_insert_constrained_edge(&cdt, p1, p2); - cdt_delete_constrained_edge(&cdt, e); - */ - - /* constrained edge 2 */ - /* - p1 = cdt_insert_point(&cdt, 1500, 3800); - cdt_insert_point(&cdt, 2700, 3000); - cdt_insert_point(&cdt, 2800, 3000); - cdt_insert_point(&cdt, 2900, 3000); - cdt_insert_point(&cdt, 3000, 3000); - cdt_insert_point(&cdt, 3100, 3000); - cdt_insert_point(&cdt, 3200, 3000); - cdt_insert_point(&cdt, 3300, 3000); - p2 = cdt_insert_point(&cdt, 4500, 3800); - cdt_insert_point(&cdt, 3000, 4800); - - e = cdt_insert_constrained_edge(&cdt, p1, p2); - */ - - /* - srand(time(NULL)); - for (i = 0; i < 1000; i++) { - cdt_insert_point(&cdt, rand()%99999 + 1, rand()%99999 + 1); - pd[i] = cdt_insert_point(&cdt, rand()%99999 + 1, rand()%99999 + 1); - } - for (i = 0; i < 1000; i++) { - cdt_delete_point(&cdt, pd[i]); - } - */ - - /* tricky case for triangulate_polygon */ - /* - p = cdt_insert_point(&cdt, 98347, 51060); - cdt_insert_point(&cdt, 92086, 47852); - cdt_insert_point(&cdt, 95806, 44000); - cdt_insert_point(&cdt, 95030, 41242); - cdt_insert_point(&cdt, 94644, 55629); - cdt_insert_point(&cdt, 94000, 45300); - - cdt_delete_point(&cdt, p); - */ - - /* delete constrained edge */ - /* - p1 = cdt_insert_point(&cdt, 1500, 3000); - cdt_insert_point(&cdt, 2000, 3500); - cdt_insert_point(&cdt, 1900, 2500); - cdt_insert_point(&cdt, 2400, 2500); - - cdt_insert_point(&cdt, 2800, 3500); - cdt_insert_point(&cdt, 3000, 3500); - cdt_insert_point(&cdt, 3200, 3500); - - cdt_insert_point(&cdt, 3600, 2500); - cdt_insert_point(&cdt, 4100, 2500); - cdt_insert_point(&cdt, 4000, 3500); - p2 = cdt_insert_point(&cdt, 4500, 3000); - - e = cdt_insert_constrained_edge(&cdt, p1, p2); - cdt_delete_constrained_edge(&cdt, e); - */ - - /* delete 2 constrained edges */ - /* - p1 = cdt_insert_point(&cdt, 2400, 1500); - cdt_insert_point(&cdt, 2200, 3500); - cdt_insert_point(&cdt, 2200, 2000); - p2 = cdt_insert_point(&cdt, 2400, 4000); - ed[0] = cdt_insert_constrained_edge(&cdt, p1, p2); - - p1 = cdt_insert_point(&cdt, 2500, 3000); - cdt_insert_point(&cdt, 3000, 2800); - cdt_insert_point(&cdt, 3500, 2800); - cdt_insert_point(&cdt, 2800, 3200); - cdt_insert_point(&cdt, 3500, 3200); - p2 = cdt_insert_point(&cdt, 4500, 3000); - ed[1] = cdt_insert_constrained_edge(&cdt, p1, p2); - - p2 = cdt_insert_point(&cdt, 3500, 3500); - ed[2] = cdt_insert_constrained_edge(&cdt, p1, p2); - - cdt_delete_constrained_edge(&cdt, ed[0]); - cdt_delete_constrained_edge(&cdt, ed[1]); - cdt_delete_constrained_edge(&cdt, ed[2]); - */ - - srand(time(NULL)); - e_num = 0; - for (i = 0; i < 100; i++) { - int isect = 0; - p1 = cdt_insert_point(&cdt, rand()%99999 + 1, rand()%99999 + 1); - p2 = cdt_insert_point(&cdt, rand()%99999 + 1, rand()%99999 + 1); - for (j = 0; j < e_num; j++) - if (LINES_INTERSECT(p1, p2, ed[j]->endp[0], ed[j]->endp[1])) { - isect = 1; - break; - } - if (!isect) { - ed[e_num] = cdt_insert_constrained_edge(&cdt, p1, p2); - e_num++; - } - } - for (i = 0; i < e_num; i++) { - fprintf(stderr, "deleting edge (%d, %d) - (%d, %d)\n", ed[i]->endp[0]->pos.x, ed[i]->endp[0]->pos.y, ed[i]->endp[1]->pos.x, ed[i]->endp[1]->pos.y); - cdt_delete_constrained_edge(&cdt, ed[i]); - } - - - if (cdt_check_delaunay(&cdt, &p_violations, NULL)) - fprintf(stderr, "delaunay\n"); - else - fprintf(stderr, "not delaunay\n"); - cdt_dump_animator(&cdt, 0, p_violations, NULL); - pointlist_free(p_violations); - cdt_free(&cdt); -} Index: cdt/edge.h =================================================================== --- cdt/edge.h (revision 32651) +++ cdt/edge.h (nonexistent) @@ -1,72 +0,0 @@ -#ifndef EDGE_H -#define EDGE_H - -#include -#include - -#include "typedefs.h" - -struct edge_s { - point_t *endp[2]; - triangle_t *adj_t[2]; - - int is_constrained; - void *data; -}; - -typedef edge_t* edge_ptr_t; - - -/* List */ -#define LST(x) edgelist_ ## x -#define LST_ITEM_T edge_ptr_t -#define LST_DONT_TYPEDEF_NODE - -#include "list/list.h" - -#ifndef LST_DONT_UNDEF - #undef LST - #undef LST_ITEM_T - #undef LST_DONT_TYPEDEF_NODE -#endif - -#define EDGELIST_FOREACH(_loop_item_, _list_) do { \ - edgelist_node_t *_node_ = _list_; \ - while (_node_ != NULL) { \ - edge_t *_loop_item_ = _node_->item; - -#define EDGELIST_FOREACH_END() \ - _node_ = _node_->next; \ - } \ -} while(0) - - -/* Vector */ -#define GVT(x) vtedge_ ## x -#define GVT_ELEM_TYPE edge_ptr_t -#define GVT_SIZE_TYPE size_t -#define GVT_DOUBLING_THRS 4096 -#define GVT_START_SIZE 32 -#define GVT_FUNC -#define GVT_SET_NEW_BYTES_TO 0 -#define GVT_ELEM_CONSTRUCTOR -#define GVT_ELEM_DESTRUCTOR -#define GVT_ELEM_COPY - -#include -#define GVT_REALLOC(vect, ptr, size) realloc(ptr, size) -#define GVT_FREE(vect, ptr) free(ptr) -int GVT(constructor)(GVT(t) *vect, GVT_ELEM_TYPE *elem); -void GVT(destructor)(GVT(t) *vect, GVT_ELEM_TYPE *elem); -#include - -#define VTEDGE_FOREACH(_loop_item_, _vt_) do { \ - int _i_; \ - for (_i_ = 0; _i_ < vtedge_len(_vt_); _i_++) { \ - edge_t *_loop_item_ = (_vt_)->array[_i_]; - -#define VTEDGE_FOREACH_END() \ - } \ -} while(0) - -#endif Index: cdt/cdt.c =================================================================== --- cdt/cdt.c (revision 32651) +++ cdt/cdt.c (nonexistent) @@ -1,849 +0,0 @@ -/* - * Copyright (C) 2018 Wojciech Krutnik - * - * Constrained Delaunay Triangulation using incremental algorithm, as described in: - * Yizhi Lu and Wayne Wei-Ming Dai, "A numerical stable algorithm for constructing - * constrained Delaunay triangulation and application to multichip module layout," - * China., 1991 International Conference on Circuits and Systems, Shenzhen, 1991, - * pp. 644-647 vol.2. - */ - -#include -#include -#include - -#include "cdt.h" - -#define DEBUG - -#define LEFTPOINT(p1, p2) ((p1)->pos.x < (p2)->pos.x || ((p1)->pos.x == (p2)->pos.x && (p1)->pos.y > (p2)->pos.y)) - - -static point_t *new_point(cdt_t *cdt, pos_t pos) -{ - point_t *p = *vtpoint_alloc_append(&cdt->points, 1); - p->pos = pos; - return p; -} - -static edge_t *new_edge(cdt_t *cdt, point_t *p1, point_t *p2, int constrain) -{ - edge_t *e; - assert(p1->pos.x != p2->pos.x || p1->pos.y != p2->pos.y); - e = *vtedge_alloc_append(&cdt->edges, 1); - /* always orient the edge to the right (or down when x1==x2; requires epsilon check?) */ - if (LEFTPOINT(p1, p2)) { - e->endp[0] = p1; - e->endp[1] = p2; - } - else { - e->endp[0] = p2; - e->endp[1] = p1; - } - e->is_constrained = constrain; - p1->adj_edges = edgelist_prepend(p1->adj_edges, &e); - p2->adj_edges = edgelist_prepend(p2->adj_edges, &e); - return e; -} - -edge_t *get_edge_from_points(point_t *p1, point_t *p2) -{ - EDGELIST_FOREACH(e1, p1->adj_edges) - EDGELIST_FOREACH(e2, p2->adj_edges) - if (e1 == e2) - return e1; - POINTLIST_FOREACH_END(); - EDGELIST_FOREACH_END(); - return NULL; -} - -static void order_triangle_points_ccw(point_t **p1, point_t **p2, point_t **p3) -{ - pointlist_node_t *points = NULL; - points = pointlist_prepend(points, p1); - points = pointlist_prepend(points, p2); - points = pointlist_prepend(points, p3); - - /* first point */ - *p1 = LEFTPOINT(*p1, *p2) ? *p1 : *p2; - *p1 = LEFTPOINT(*p1, *p3) ? *p1 : *p3; - points = pointlist_remove_item(points, p1); - - /* two other points */ - if (ORIENT_CCW(*p1, points->item, points->next->item)) { - *p2 = points->item; - *p3 = points->next->item; - } else { - *p2 = points->next->item; - *p3 = points->item; - } - points = pointlist_remove_front(points); - points = pointlist_remove_front(points); -} - -static triangle_t *new_triangle(cdt_t *cdt, point_t *p1, point_t *p2, point_t *p3) -{ - edge_t *e1, *e2, *e3; - triangle_t *t = *vttriangle_alloc_append(&cdt->triangles, 1); - - assert(!ORIENT_COLLINEAR(p1, p2, p3)); /* points cannot be colinear */ - - order_triangle_points_ccw(&p1, &p2, &p3); - t->p[0] = p1; - t->p[1] = p2; - t->p[2] = p3; - p1->adj_triangles = trianglelist_prepend(p1->adj_triangles, &t); - p2->adj_triangles = trianglelist_prepend(p2->adj_triangles, &t); - p3->adj_triangles = trianglelist_prepend(p3->adj_triangles, &t); - - e1 = get_edge_from_points(p1, p2); - e2 = get_edge_from_points(p2, p3); - e3 = get_edge_from_points(p3, p1); - assert(e1 != NULL && e2 != NULL && e3 != NULL); - t->e[0] = e1; - t->e[1] = e2; - t->e[2] = e3; - -#define connect_adjacent_triangle(_t_, _edge_num_, _e_) \ - if ((_e_)->adj_t[0] == NULL && (_e_)->adj_t[1] == NULL) \ - (_e_)->adj_t[0] = (_t_); \ - else { \ - int i = (_e_)->adj_t[0] == NULL ? 0 : 1; \ - (_e_)->adj_t[i] = (_t_); \ - (_t_)->adj_t[(_edge_num_)] = (_e_)->adj_t[i^1]; \ - if ((_t_)->adj_t[(_edge_num_)] != NULL) { \ - for (i = 0; i < 3; i++) { \ - if ((_t_)->adj_t[(_edge_num_)]->e[i] == (_e_)) \ - (_t_)->adj_t[(_edge_num_)]->adj_t[i] = (_t_); \ - } \ - } \ - } - - connect_adjacent_triangle(t, 0, e1); - connect_adjacent_triangle(t, 1, e2); - connect_adjacent_triangle(t, 2, e3); -#undef connect_adjacent_triangle - - return t; -} - -static void remove_triangle(cdt_t *cdt, triangle_t *t) -{ - int i, j; - - for (i = 0; i < 3; i++) { - /* disconnect adjacent points */ - t->p[i]->adj_triangles = trianglelist_remove_item(t->p[i]->adj_triangles, &t); - /* disconnect adjacent edges */ - for (j = 0; j < 2; j++) - if (t->e[i]->adj_t[j] == t) - t->e[i]->adj_t[j] = NULL; - /* disconnect adjacent triangles */ - for (j = 0; j < 3; j++) { - triangle_t *adj_t = t->adj_t[i]; - if (adj_t != NULL && adj_t->adj_t[j] == t) - adj_t->adj_t[j] = NULL; - } - } - - /* remove triangle */ - for(i = 0; i < vttriangle_len(&cdt->triangles); i++) { - if (cdt->triangles.array[i] == t) { - vttriangle_remove(&cdt->triangles, i, 1); - break; - } - } -} - -static void remove_edge(cdt_t *cdt, edge_t *e) -{ - int i; - - assert(e != NULL); - - /* disconnect adjacent triangles */ - for (i = 0; i < 2; i++) - if (e->adj_t[i]) - remove_triangle(cdt, e->adj_t[i]); - /* disconnect endpoints */ - for (i = 0; i < 2; i++) - e->endp[i]->adj_edges = edgelist_remove_item(e->endp[i]->adj_edges, &e); - - /* remove edge */ - for(i = 0; i < vtedge_len(&cdt->edges); i++) { - if (cdt->edges.array[i] == e) { - vtedge_remove(&cdt->edges, i, 1); - break; - } - } -} - -static int is_point_in_circumcircle(point_t *p, triangle_t *t) -{ - double x1 = t->p[0]->pos.x, x2 = t->p[1]->pos.x, x3 = t->p[2]->pos.x; - double y1 = t->p[0]->pos.y, y2 = t->p[1]->pos.y, y3 = t->p[2]->pos.y; - double d1, d2, d3, d4; - double n1, n2, n3; - double px = p->pos.x, py = p->pos.y; - - n1 = (x1 * x1) + (y1 * y1); - n2 = (x2 * x2) + (y2 * y2); - n3 = (x3 * x3) + (y3 * y3); - - d1 = (x1 * y2) + (x2 * y3) + (x3 * y1) - (x3 * y2) - (x1 * y3) - (x2 * y1); - d2 = (n1 * y2) + (n2 * y3) + (n3 * y1) - (n3 * y2) - (n1 * y3) - (n2 * y1); - d3 = (n1 * x2) + (n2 * x3) + (n3 * x1) - (n3 * x2) - (n1 * x3) - (n2 * x1); - d4 = (n1 * x2 * y3) + (n2 * x3 * y1) + (n3 * x1 * y2) - (n3 * x2 * y1) - (n1 * x3 * y2) - (n2 * x1 * y3); - - return d1 * ( (px * (px*d1 - d2)) + (py * (py*d1 + d3)) - d4 ) < 0 ? 1 : 0; -} - -static void init_bbox(cdt_t *cdt, coord_t bbox_x1, coord_t bbox_y1, coord_t bbox_x2, coord_t bbox_y2) -{ - pos_t bbox; - point_t *p_tl, *p_tr, *p_bl, *p_br; - - bbox.x = bbox_x1; - bbox.y = bbox_y1; - cdt->bbox_tl = bbox; - p_bl = new_point(cdt, bbox); - bbox.x = bbox_x2; - bbox.y = bbox_y1; - p_br = new_point(cdt, bbox); - bbox.x = bbox_x1; - bbox.y = bbox_y2; - p_tl = new_point(cdt, bbox); - bbox.x = bbox_x2; - bbox.y = bbox_y2; - p_tr = new_point(cdt, bbox); - cdt->bbox_br = bbox; - - new_edge(cdt, p_tl, p_bl, 1); - new_edge(cdt, p_bl, p_br, 1); - new_edge(cdt, p_br, p_tr, 1); - new_edge(cdt, p_tr, p_tl, 1); - new_edge(cdt, p_bl, p_tr, 0); /* diagonal */ - - new_triangle(cdt, p_bl, p_br, p_tr); - new_triangle(cdt, p_tl, p_bl, p_tr); -} - -void cdt_init(cdt_t *cdt, coord_t bbox_x1, coord_t bbox_y1, coord_t bbox_x2, coord_t bbox_y2) -{ - cdt->points.elem_constructor = vtpoint_constructor; - cdt->points.elem_destructor = vtpoint_destructor; - cdt->points.elem_copy = NULL; - vtpoint_init(&cdt->points); - cdt->edges.elem_constructor = vtedge_constructor; - cdt->edges.elem_destructor = vtedge_destructor; - cdt->edges.elem_copy = NULL; - vtedge_init(&cdt->edges); - cdt->triangles.elem_constructor = vttriangle_constructor; - cdt->triangles.elem_destructor = vttriangle_destructor; - cdt->triangles.elem_copy = NULL; - vttriangle_init(&cdt->triangles); - - init_bbox(cdt, bbox_x1, bbox_y1, bbox_x2, bbox_y2); -} - -void cdt_free(cdt_t *cdt) -{ - vttriangle_uninit(&cdt->triangles); - vtedge_uninit(&cdt->edges); - VTPOINT_FOREACH(p, &cdt->points) - trianglelist_free(p->adj_triangles); - edgelist_free(p->adj_edges); - VTPOINT_FOREACH_END(); - vtpoint_uninit(&cdt->points); -} - -static int is_point_in_triangle(point_t *p, triangle_t *t) -{ - return ORIENT_CCW_CL(t->p[0], t->p[1], p) && ORIENT_CCW_CL(t->p[1], t->p[2], p) && ORIENT_CCW_CL(t->p[2], t->p[0], p); -} - -typedef struct { - edgelist_node_t *border_edges; - edgelist_node_t *edges_to_remove; -} retriangulation_region_t; - -static void check_adjacent_triangle(triangle_t *adj_t, edge_t *adj_e, point_t *new_p, retriangulation_region_t *region) -{ - int i; - - assert(adj_t != NULL && adj_e != NULL); - - if (is_point_in_circumcircle(new_p, adj_t)) { - region->edges_to_remove = edgelist_prepend(region->edges_to_remove, &adj_e); - region->border_edges = edgelist_remove_item(region->border_edges, &adj_e); - for (i = 0; i < 3; i++) { - if (adj_t->e[i] == adj_e) - continue; - else { - edge_t *next_adj_e = adj_t->e[i]; - triangle_t *next_adj_t = adj_t->adj_t[i]; - - region->border_edges = edgelist_prepend(region->border_edges, &next_adj_e); - if (!next_adj_e->is_constrained) - check_adjacent_triangle(next_adj_t, next_adj_e, new_p, region); /* recursive call */ - } - } - } -} - -#ifdef DEBUG -void dump_pointlist(pointlist_node_t *list) -{ - POINTLIST_FOREACH(p, list) - fprintf(stderr, "\t{pos=(%d, %d) adj_t=(", p->pos.x, p->pos.y); - TRIANGLELIST_FOREACH(t, p->adj_triangles) - fprintf(stderr, "%p", (void*)t); - if(_node_->next != NULL) - fprintf(stderr, ", "); - TRIANGLELIST_FOREACH_END(); - fprintf(stderr, ") adj_e=("); - EDGELIST_FOREACH(t, p->adj_edges) - fprintf(stderr, "%p", (void*)t); - if(_node_->next != NULL) - fprintf(stderr, ", "); - EDGELIST_FOREACH_END(); - fprintf(stderr, ")}\n"); - POINTLIST_FOREACH_END(); -} - -void dump_edgelist(edgelist_node_t *list) -{ - EDGELIST_FOREACH(e, list) - fprintf(stderr, "\t{endp1=(%p (pos=(%d, %d))) endp2=(%p (pos=(%d, %d))) adj_t=(", - (void*)e->endp[0], e->endp[0]->pos.x, e->endp[0]->pos.y, (void*)e->endp[1], e->endp[1]->pos.x, e->endp[1]->pos.y); - fprintf(stderr, "%p, %p)", (void*)e->adj_t[0], (void*)e->adj_t[1]); - fprintf(stderr, " %s}\n", e->is_constrained ? "constrained" : ""); - EDGELIST_FOREACH_END(); -} - -void dump_trianglelist(trianglelist_node_t *list) -{ - TRIANGLELIST_FOREACH(t, list) - fprintf(stderr, "\t{p1=(%d, %d) p2=(%d, %d) p3=(%d, %d)", - t->p[0]->pos.x, t->p[0]->pos.y, t->p[1]->pos.x, t->p[1]->pos.y, t->p[2]->pos.x, t->p[2]->pos.y); - fprintf(stderr, " adj_e=(%p, %p, %p)", (void*)t->e[0], (void*)t->e[1], (void*)t->e[2]); - fprintf(stderr, " adj_t=(%p, %p, %p)}\n", (void*)t->adj_t[0], (void*)t->adj_t[1], (void*)t->adj_t[2]); - TRIANGLELIST_FOREACH_END(); -} -#endif - -static pointlist_node_t *order_edges_adjacently(edgelist_node_t *edges) -{ - pointlist_node_t *plist_ordered = NULL; - edge_t *e1 = edges->item; - point_t *p = e1->endp[0]; - int i = 1; - - plist_ordered = pointlist_prepend(plist_ordered, &p); - edges = edgelist_remove_front(edges); - - while (edges != NULL) { - p = e1->endp[i]; - EDGELIST_FOREACH(e2, edges) - if (e2->endp[0] == p || e2->endp[1] == p) { - plist_ordered = pointlist_prepend(plist_ordered, &p); - edges = edgelist_remove(edges, _node_); - i = e2->endp[0] == p ? 1 : 0; - e1 = e2; - break; - } - EDGELIST_FOREACH_END(); - } - - return plist_ordered; -} - -static void triangulate_polygon(cdt_t *cdt, pointlist_node_t *polygon) -{ - pointlist_node_t *current_point_node; - point_t *p[3]; - int i; - - assert(pointlist_length(polygon) >= 3); - - current_point_node = polygon; - while (pointlist_length(polygon) > 3) { - triangle_t candidate_t; - edge_t candidate_e; - pointlist_node_t *pnode; - - candidate_t.p[0] = current_point_node->item; - candidate_e.endp[0] = candidate_t.p[0]; - if (current_point_node->next == NULL) - current_point_node = polygon; /* wrap around */ - else - current_point_node = current_point_node->next; - candidate_t.p[1] = current_point_node->item; - if (current_point_node->next == NULL) - candidate_t.p[2] = polygon->item; /* wrap around */ - else - candidate_t.p[2] = current_point_node->next->item; - candidate_e.endp[1] = candidate_t.p[2]; - - if (ORIENT_COLLINEAR(candidate_t.p[0], candidate_t.p[1], candidate_t.p[2])) - goto skip; - - /* case 1: another point of the polygon violates the circle criterion */ - POINTLIST_FOREACH(p, polygon) - if (p != candidate_t.p[0] && p != candidate_t.p[1] && p != candidate_t.p[2]) - if (is_point_in_circumcircle(p, &candidate_t)) - goto skip; - POINTLIST_FOREACH_END(); - - /* case 2: edge to be added already exists */ - EDGELIST_FOREACH(e1, candidate_e.endp[0]->adj_edges) - EDGELIST_FOREACH(e2, candidate_e.endp[1]->adj_edges) - if (e1 == e2) - goto skip; - EDGELIST_FOREACH_END(); - EDGELIST_FOREACH_END(); - - /* case 3: edge to be added intersects an existing edge */ - /* case 4: a point adjacent to the current_point is in the candidate triangle */ - EDGELIST_FOREACH(e, candidate_t.p[1]->adj_edges) - if (e != get_edge_from_points(candidate_t.p[0], candidate_t.p[1]) - && e != get_edge_from_points(candidate_t.p[1], candidate_t.p[2])) { - triangle_t ord_t; - if (LINES_INTERSECT(candidate_e.endp[0], candidate_e.endp[1], e->endp[0], e->endp[1])) - goto skip; - ord_t.p[0] = candidate_t.p[0]; - ord_t.p[1] = candidate_t.p[1]; - ord_t.p[2] = candidate_t.p[2]; - order_triangle_points_ccw(&ord_t.p[0], &ord_t.p[1], &ord_t.p[2]); - if (is_point_in_triangle(e->endp[0] != candidate_t.p[1] ? e->endp[0] : e->endp[1], &ord_t)) - goto skip; - } - EDGELIST_FOREACH_END(); - - new_edge(cdt, candidate_e.endp[0], candidate_e.endp[1], 0); - new_triangle(cdt, candidate_t.p[0], candidate_t.p[1], candidate_t.p[2]); - - /* update polygon: remove the point now covered by the new edge */ - if (current_point_node->next == NULL) - pnode = polygon; /* wrap around */ - else - pnode = current_point_node->next; - polygon = pointlist_remove(polygon, current_point_node); - current_point_node = pnode; - -skip: - continue; - } - - /* create triangle from the remaining edges */ - for (i = 0; i < 3; i++) { - p[i] = polygon->item; - polygon = pointlist_remove_front(polygon); - } - new_triangle(cdt, p[0], p[1], p[2]); -} - -static void insert_point_(cdt_t *cdt, point_t *new_p) -{ - triangle_t *enclosing_triangle = NULL; - retriangulation_region_t region = {NULL, NULL}; - pointlist_node_t *points_to_attach, *prev_point_node; - int i; - - /* find enclosing triangle */ - VTTRIANGLE_FOREACH(t, &cdt->triangles) - if (is_point_in_triangle(new_p, t)) { - enclosing_triangle = t; - break; - } - VTTRIANGLE_FOREACH_END(); - assert(enclosing_triangle != NULL); - - /* remove invalid edges and attach enclosing points */ - for (i = 0; i < 3; i++) { - edge_t *adj_e = enclosing_triangle->e[i]; - triangle_t *adj_t = enclosing_triangle->adj_t[i]; - - region.border_edges = edgelist_prepend(region.border_edges, &adj_e); - if (!adj_e->is_constrained && adj_t != NULL) - check_adjacent_triangle(adj_t, adj_e, new_p, ®ion); - } - remove_triangle(cdt, enclosing_triangle); - EDGELIST_FOREACH(e, region.edges_to_remove) - remove_edge(cdt, e); - EDGELIST_FOREACH_END(); - edgelist_free(region.edges_to_remove); - - points_to_attach = order_edges_adjacently(region.border_edges); - prev_point_node = points_to_attach; - new_edge(cdt, points_to_attach->item, new_p, 0); - POINTLIST_FOREACH(p, points_to_attach->next) - point_t *prev_p = prev_point_node->item; - new_edge(cdt, p, new_p, 0); - new_triangle(cdt, prev_p, p, new_p); - prev_point_node = _node_; - POINTLIST_FOREACH_END(); - new_triangle(cdt, prev_point_node->item, points_to_attach->item, new_p); - pointlist_free(points_to_attach); -} - -point_t *cdt_insert_point(cdt_t *cdt, coord_t x, coord_t y) -{ - pos_t pos; - point_t *new_p; - - pos.x = x; - pos.y = y; - VTPOINT_FOREACH(p, &cdt->points) - if (p->pos.x == pos.x && p->pos.y == pos.y) /* point in the same pos already exists */ - return p; - VTPOINT_FOREACH_END(); - - new_p = new_point(cdt, pos); - insert_point_(cdt, new_p); - - return new_p; -} - -void cdt_delete_point(cdt_t *cdt, point_t *p) -{ - edgelist_node_t *polygon_edges = NULL; - pointlist_node_t *polygon_points; - int i; - - /* find opposite edges of adjacent triangles and add them to the polygon */ - TRIANGLELIST_FOREACH(t, p->adj_triangles) - i = 0; - while(i < 3) { - edge_t *edge_of_triangle = t->e[i]; - EDGELIST_FOREACH(edge_of_point, p->adj_edges) - if (edge_of_point == edge_of_triangle) - goto next_i; - EDGELIST_FOREACH_END(); - polygon_edges = edgelist_prepend(polygon_edges, &edge_of_triangle); - break; -next_i: - i++; - } - TRIANGLELIST_FOREACH_END(); - - /* remove adjacent edges */ - EDGELIST_FOREACH(e, p->adj_edges) - assert(e->is_constrained == 0); - _node_ = _node_->next; - remove_edge(cdt, e); - continue; - EDGELIST_FOREACH_END(); - - /* remove point */ - for(i = 0; i < vtpoint_len(&cdt->points); i++) { - if (cdt->points.array[i] == p) { - vtpoint_remove(&cdt->points, i, 1); - break; - } - } - - polygon_points = order_edges_adjacently(polygon_edges); - triangulate_polygon(cdt, polygon_points); -} - -static trianglelist_node_t *triangles_intersecting_line(point_t *p1, point_t *p2) -{ - trianglelist_node_t *triangles = NULL; - triangle_t *next_t = NULL; - edge_t *adj_e; - int i; - - /* find first triangle */ - TRIANGLELIST_FOREACH(t, p1->adj_triangles) - for (i = 0; i < 3; i++) - if (t->e[i]->endp[0] != p1 && t->e[i]->endp[1] != p1) /* opposite edge */ - if (LINES_INTERSECT(p1, p2, t->e[i]->endp[0], t->e[i]->endp[1])) { - adj_e = t->e[i]; - next_t = adj_e->adj_t[0] != t ? adj_e->adj_t[0] : adj_e->adj_t[1]; - triangles = trianglelist_prepend(triangles, &t); - goto first_triangle_found; - } - TRIANGLELIST_FOREACH_END(); - -first_triangle_found: - assert(next_t != NULL); - - /* follow the path */ - while (next_t->p[0] != p2 && next_t->p[1] != p2 && next_t->p[2] != p2) { - triangle_t *t = next_t; - for (i = 0; i < 3; i++) - if (t->e[i] != adj_e && LINES_INTERSECT(p1, p2, t->e[i]->endp[0], t->e[i]->endp[1])) { - adj_e = t->e[i]; - next_t = adj_e->adj_t[0] != t ? adj_e->adj_t[0] : adj_e->adj_t[1]; - triangles = trianglelist_prepend(triangles, &t); - break; - } - } - - triangles = trianglelist_prepend(triangles, &next_t); - return triangles; -} - -static void insert_constrained_edge_(cdt_t *cdt, point_t *p1, point_t *p2, pointlist_node_t **left_poly, pointlist_node_t **right_poly) -{ - edge_t *e; - triangle_t *t; - trianglelist_node_t *triangles; - pointlist_node_t *left_polygon = NULL, *right_polygon = NULL; - int i; - - /* find intersecting edges and remove them */ - triangles = triangles_intersecting_line(p1, p2); - t = triangles->item; - triangles = trianglelist_remove_front(triangles); - left_polygon = pointlist_prepend(left_polygon, &p2); /* triangle list begins from p2 */ - right_polygon = pointlist_prepend(right_polygon, &p2); - for (i = 0; i < 3; i++) - if (t->p[i] != p2) { - if (ORIENT_CCW(p1, p2, t->p[i])) - left_polygon = pointlist_prepend(left_polygon, &t->p[i]); - else - right_polygon = pointlist_prepend(right_polygon, &t->p[i]); - } - - while (triangles->next != NULL) { - t = triangles->item; - triangles = trianglelist_remove_front(triangles); - e = get_edge_from_points(left_polygon->item, right_polygon->item); - for (i = 0; i < 3; i++) - if (t->p[i] != left_polygon->item && t->p[i] != right_polygon->item) { - if (ORIENT_CCW(p1, p2, t->p[i])) - left_polygon = pointlist_prepend(left_polygon, &t->p[i]); - else - right_polygon = pointlist_prepend(right_polygon, &t->p[i]); - break; - } - remove_edge(cdt, e); - } - triangles = trianglelist_remove_front(triangles); - remove_edge(cdt, get_edge_from_points(left_polygon->item, right_polygon->item)); - left_polygon = pointlist_prepend(left_polygon, &p1); - right_polygon = pointlist_prepend(right_polygon, &p1); - *left_poly = left_polygon; - *right_poly = right_polygon; -} - -edge_t *cdt_insert_constrained_edge(cdt_t *cdt, point_t *p1, point_t *p2) -{ - edge_t *e; - pointlist_node_t *left_polygon, *right_polygon; - - /* edge already exists - just constrain it */ - e = get_edge_from_points(p1, p2); - if (e != NULL) { - e->is_constrained = 1; - return e; - } - - insert_constrained_edge_(cdt, p1, p2, &left_polygon, &right_polygon); - - /* add new edge */ - e = new_edge(cdt, p1, p2, 1); - - /* triangulate the created polygons */ - triangulate_polygon(cdt, left_polygon); - triangulate_polygon(cdt, right_polygon); - - return e; -} - -void cdt_delete_constrained_edge(cdt_t *cdt, edge_t *edge) -{ - pointlist_node_t *polygon = NULL; - edgelist_node_t *border_edges = NULL; - edgelist_node_t *constrained_edges_within_scope = NULL; - pointlist_node_t *isolated_points = NULL; - int i, j; - - assert(edge->is_constrained); - - /* initial polygon */ - polygon = pointlist_prepend(polygon, &edge->endp[0]); - polygon = pointlist_prepend(polygon, &edge->endp[1]); - for (i = 0; i < 2; i++) { - triangle_t *t = edge->adj_t[i]; - for(j = 0; j < 3; j++) { - if (t->p[j] != edge->endp[0] && t->p[j] != edge->endp[1]) - polygon = pointlist_prepend(polygon, &edge->adj_t[i]->p[j]); - if (t->e[j] != edge) - border_edges = edgelist_prepend(border_edges, &t->e[j]); - } - } - remove_edge(cdt, edge); - - /* find invalid edges and remove them */ - EDGELIST_FOREACH(e, border_edges) - triangle_t *t = e->adj_t[0] != NULL ? e->adj_t[0] : e->adj_t[1]; - edgelist_node_t *e_node = _node_; - int invalid_edge = 0; - if (t != NULL) { - POINTLIST_FOREACH(p, polygon) - if (p != t->p[0] && p != t->p[1] && p != t->p[2] && is_point_in_circumcircle(p, t)) { - for (i = 0; i < 3; i++) { - if (t->p[i] != e->endp[0] && t->p[i] != e->endp[1]) - polygon = pointlist_prepend(polygon, &t->p[i]); - if (t->e[i] != e) - border_edges = edgelist_prepend(border_edges, &t->e[i]); - } - if (e->is_constrained) { /* don't remove constrained edges - only detach them */ - constrained_edges_within_scope = edgelist_prepend(constrained_edges_within_scope, &e); - for (i = 0; i < 2; i++) - e->endp[i]->adj_edges = edgelist_remove_item(e->endp[i]->adj_edges, &e); - remove_triangle(cdt, t); - } - else - remove_edge(cdt, e); - border_edges = edgelist_remove(border_edges, e_node); - invalid_edge = 1; - break; - } - POINTLIST_FOREACH_END(); - } - else { /* triangle beyond a border edge was removed earlier - the edge should be removed too */ - point_t *endp[2]; - endp[0] = e->endp[0]; - endp[1] = e->endp[1]; - for (i = 0; i < 2; i++) /* check if the edge is not bbox of the triangulation */ - if ((e->endp[i]->pos.x == cdt->bbox_tl.x && e->endp[i]->pos.y == cdt->bbox_tl.y) - || (e->endp[i]->pos.x == cdt->bbox_br.x && e->endp[i]->pos.y == cdt->bbox_br.y)) - goto next_edge; - border_edges = edgelist_remove(border_edges, e_node); - border_edges = edgelist_remove_item(border_edges, &e); - invalid_edge = 1; /* TODO: the loop doesn't have to start from the beginning, but border removal should preserve current node */ - if (e->is_constrained) { - constrained_edges_within_scope = edgelist_prepend(constrained_edges_within_scope, &e); - for (i = 0; i < 2; i++) - endp[i]->adj_edges = edgelist_remove_item(endp[i]->adj_edges, &e); /* detach the edge */ - } - else - remove_edge(cdt, e); - for (i = 0; i < 2; i++) { - if (endp[i]->adj_edges == NULL) { /* isolated point */ - polygon = pointlist_remove_item(polygon, &endp[i]); - isolated_points = pointlist_prepend(isolated_points, &endp[i]); - } - } - } - if (invalid_edge) { - _node_ = border_edges; /* start from the beginning (new point to check was added) */ - continue; - } -next_edge: - EDGELIST_FOREACH_END(); - pointlist_free(polygon); - - /* triangulate the resultant polygon */ - polygon = order_edges_adjacently(border_edges); - triangulate_polygon(cdt, polygon); - - /* reattach isolated points and constrained edges */ - POINTLIST_FOREACH(p, isolated_points) - insert_point_(cdt, p); - POINTLIST_FOREACH_END(); - pointlist_free(isolated_points); - EDGELIST_FOREACH(e, constrained_edges_within_scope) - pointlist_node_t *left_polygon, *right_polygon; - insert_constrained_edge_(cdt, e->endp[0], e->endp[1], &left_polygon, &right_polygon); - for (i = 0; i < 2; i++) - e->endp[i]->adj_edges = edgelist_prepend(e->endp[i]->adj_edges, &e); /* reattach the edge to the endpoints */ - triangulate_polygon(cdt, left_polygon); - triangulate_polygon(cdt, right_polygon); - EDGELIST_FOREACH_END(); - edgelist_free(constrained_edges_within_scope); -} - -static void circumcircle(const triangle_t *t, pos_t *p, int *r) -{ - double x1 = t->p[0]->pos.x, x2 = t->p[1]->pos.x, x3 = t->p[2]->pos.x; - double y1 = t->p[0]->pos.y, y2 = t->p[1]->pos.y, y3 = t->p[2]->pos.y; - double d1, d2, d3, d4; - double n1, n2, n3; - - n1 = (x1 * x1) + (y1 * y1); - n2 = (x2 * x2) + (y2 * y2); - n3 = (x3 * x3) + (y3 * y3); - - d1 = (x1 * y2) + (x2 * y3) + (x3 * y1) - (x3 * y2) - (x1 * y3) - (x2 * y1); - d2 = (n1 * y2) + (n2 * y3) + (n3 * y1) - (n3 * y2) - (n1 * y3) - (n2 * y1); - d3 = (n1 * x2) + (n2 * x3) + (n3 * x1) - (n3 * x2) - (n1 * x3) - (n2 * x1); - d4 = (n1 * x2 * y3) + (n2 * x3 * y1) + (n3 * x1 * y2) - (n3 * x2 * y1) - (n1 * x3 * y2) - (n2 * x1 * y3); - - p->x = d2/(2*d1); - p->y = -d3/(2*d1); - *r = sqrt((d2*d2)/(d1*d1) + (d3*d3)/(d1*d1) + 4*d4/d1)/2; -} - -void cdt_dump_animator(cdt_t *cdt, int show_circles, pointlist_node_t *point_violations, trianglelist_node_t *triangle_violations) -{ - int last_c = 0; - int triangle_num = 0; - printf("frame\n"); - printf("scale 0.9\n"); - printf("viewport %f %f - %f %f\n", (double)cdt->bbox_tl.x - 1.0, (double)cdt->bbox_tl.y - 1.0, (double)cdt->bbox_br.x + 1.0, (double)cdt->bbox_br.y + 1.0); - - VTEDGE_FOREACH(edge, &cdt->edges) - if(last_c != edge->is_constrained) { - printf("color %s\n", edge->is_constrained ? "red" : "black"); - printf("thick %s\n", edge->is_constrained ? "2" : "1"); - last_c = edge->is_constrained; - } - printf("line %d %d %d %d\n", edge->endp[0]->pos.x, edge->endp[0]->pos.y, edge->endp[1]->pos.x, edge->endp[1]->pos.y); - VTEDGE_FOREACH_END(); - - printf("color green\n"); - VTTRIANGLE_FOREACH(triangle, &cdt->triangles) - pos_t pos; - int r; - if (show_circles) { - circumcircle(triangle, &pos, &r); - printf("circle %d %d %d 50\n", pos.x, pos.y, r); - } - triangle_num++; - VTTRIANGLE_FOREACH_END(); - - printf("color red\n"); - if (point_violations) { - POINTLIST_FOREACH(p, point_violations) - printf("circle %d %d 50 10\n", p->pos.x, p->pos.y); - POINTLIST_FOREACH_END(); - } - - printf("color darkred\n"); - if (triangle_violations) { - TRIANGLELIST_FOREACH(t, triangle_violations) - pos_t pos; - int r; - circumcircle(t, &pos, &r); - printf("circle %d %d %d 50\n", pos.x, pos.y, r); - TRIANGLELIST_FOREACH_END(); - } - - printf("flush\n"); - fprintf(stderr, "triangle num: %d\n", triangle_num); -} - -int cdt_check_delaunay(cdt_t *cdt, pointlist_node_t **point_violations, trianglelist_node_t **triangle_violations) -{ - int delaunay = 1; - VTTRIANGLE_FOREACH(triangle, &cdt->triangles) - VTPOINT_FOREACH(point, &cdt->points) - if (is_point_in_circumcircle(point, triangle) - && point != triangle->p[0] - && point != triangle->p[1] - && point != triangle->p[2]) { - delaunay = 0; - if (point_violations != NULL) - *point_violations = pointlist_prepend(*point_violations, &point); - if (triangle_violations != NULL) - *triangle_violations = trianglelist_prepend(*triangle_violations, &triangle); - } - VTPOINT_FOREACH_END(); - VTTRIANGLE_FOREACH_END(); - return delaunay; -} Index: cdt/triangle.h =================================================================== --- cdt/triangle.h (revision 32651) +++ cdt/triangle.h (nonexistent) @@ -1,70 +0,0 @@ -#ifndef TRIANGLE_H -#define TRIANGLE_H - -#include -#include - -#include "typedefs.h" - -struct triangle_s { - point_t *p[3]; - edge_t *e[3]; - triangle_t *adj_t[3]; -}; - -typedef triangle_t* triangle_ptr_t; - - -/* List */ -#define LST(x) trianglelist_ ## x -#define LST_ITEM_T triangle_ptr_t -#define LST_DONT_TYPEDEF_NODE - -#include "list/list.h" - -#ifndef LST_DONT_UNDEF - #undef LST - #undef LST_ITEM_T - #undef LST_DONT_TYPEDEF_NODE -#endif - -#define TRIANGLELIST_FOREACH(_loop_item_, _list_) do { \ - trianglelist_node_t *_node_ = _list_; \ - while (_node_ != NULL) { \ - triangle_t *_loop_item_ = _node_->item; - -#define TRIANGLELIST_FOREACH_END() \ - _node_ = _node_->next; \ - } \ -} while(0) - - -/* Vector */ -#define GVT(x) vttriangle_ ## x -#define GVT_ELEM_TYPE triangle_ptr_t -#define GVT_SIZE_TYPE size_t -#define GVT_DOUBLING_THRS 4096 -#define GVT_START_SIZE 32 -#define GVT_FUNC -#define GVT_SET_NEW_BYTES_TO 0 -#define GVT_ELEM_CONSTRUCTOR -#define GVT_ELEM_DESTRUCTOR -#define GVT_ELEM_COPY - -#include -#define GVT_REALLOC(vect, ptr, size) realloc(ptr, size) -#define GVT_FREE(vect, ptr) free(ptr) -int GVT(constructor)(GVT(t) *vect, GVT_ELEM_TYPE *elem); -void GVT(destructor)(GVT(t) *vect, GVT_ELEM_TYPE *elem); -#include - -#define VTTRIANGLE_FOREACH(_loop_item_, _vt_) do { \ - int _i_; \ - for (_i_ = 0; _i_ < vttriangle_len(_vt_); _i_++) { \ - triangle_t *_loop_item_ = (_vt_)->array[_i_]; - -#define VTTRIANGLE_FOREACH_END() \ - } \ -} while(0) - -#endif Index: cdt/list/list.h =================================================================== --- cdt/list/list.h (revision 32651) +++ cdt/list/list.h (nonexistent) @@ -1,24 +0,0 @@ - -struct LST(node_s) { - LST_ITEM_T item; - struct LST(node_s) *next; -}; - -#ifndef LST_DONT_TYPEDEF_NODE -typedef struct LST(node_s) LST(node_t); -#endif - -LST(node_t) *LST(prepend)(LST(node_t) *list, LST_ITEM_T *item); -LST(node_t) *LST(insert_after)(LST(node_t) *node, LST_ITEM_T *item); -LST(node_t) *LST(insert_after_nth)(LST(node_t) *list, int n, LST_ITEM_T *item); -LST(node_t) *LST(remove_front)(LST(node_t) *list); -LST(node_t) *LST(remove)(LST(node_t) *list, LST(node_t) *node); -LST(node_t) *LST(remove_item)(LST(node_t) *list, LST_ITEM_T *item); -LST(node_t) *LST(find)(LST(node_t) *list, LST_ITEM_T *item); -LST(node_t) *LST(nth)(LST(node_t) *list, int n); -LST(node_t) *LST(last)(LST(node_t) *list); - -size_t LST(length)(LST(node_t) *list); -int LST(get_index)(LST(node_t) *list, LST(node_t) *node); - -void LST(free)(LST(node_t) *list); Index: cdt/list/testlist.c =================================================================== --- cdt/list/testlist.c (revision 32651) +++ cdt/list/testlist.c (nonexistent) @@ -1,88 +0,0 @@ -#include - -typedef struct { - int x; - int y; -} pos_t; - -#define LST(x) poslist_ ## x -#define LST_ITEM_T pos_t -int LST(compare_func)(LST_ITEM_T *a, LST_ITEM_T *b) -{ - return a->x == b->x && a->y == b->y; -} -#include "list.h" -#include "list.c" -#define POSLIST_FOREACH(loop_item, list) do { \ - poslist_node_t *node = list; \ - pos_t *loop_item; \ - while (node != NULL) { \ - loop_item = &node->item; - -#define POSLIST_FOREACH_END() \ - node = node->next; \ - } \ -} while(0) -#undef LST -#undef LST_ITEM_T - -#define LST(x) intlist_ ## x -#define LST_ITEM_T int -int LST(compare_func)(LST_ITEM_T *a, LST_ITEM_T *b) -{ - return *a == *b; -} -#include "list.h" -#include "list.c" -#define INTLIST_FOREACH(loop_item, list) do { \ - intlist_node_t *node = list; \ - int *loop_item; \ - while (node != NULL) { \ - loop_item = &node->item; - -#define INTLIST_FOREACH_END() \ - node = node->next; \ - } \ -} while(0) - - -int main(void) -{ - poslist_node_t *list1 = NULL; - intlist_node_t *list2 = NULL; - intlist_node_t *list2_node = NULL; - - pos_t p = {1, 2}; - int i = 4; - - list1 = poslist_prepend(list1, &p); p.x = 4; p.y = 5; - list1 = poslist_prepend(list1, &p); p.x = 8; p.y = 1; - list1 = poslist_prepend(list1, &p); - - list2 = intlist_prepend(list2, &i); i = 1; - list2 = intlist_prepend(list2, &i); i = 5; - list2 = intlist_prepend(list2, &i); - - i = 5; - list2 = intlist_remove_item(list2, &i); - - //~ list2_node = list2->next; - //~ list2 = intlist_remove(list2, list2_node); - - //~ list2 = intlist_remove_front(list2); - //~ list2 = intlist_remove_front(list2); - //~ list2 = intlist_remove_front(list2); - //~ list2 = intlist_remove_front(list2); - //~ list2 = intlist_remove_front(list2); i = 423; - //~ list2 = intlist_prepend(list2, &i); - - printf("list1:\n"); - POSLIST_FOREACH(pos, list1) - printf("%d, %d\n", pos->x, pos->y); - POSLIST_FOREACH_END(); - - printf("list2:\n"); - INTLIST_FOREACH(num, list2) - printf("%d\n", *num); - INTLIST_FOREACH_END(); -} Index: cdt/list/list.c =================================================================== --- cdt/list/list.c (revision 32651) +++ cdt/list/list.c (nonexistent) @@ -1,134 +0,0 @@ -#include - -static LST(node_t) *LST(create)(LST_ITEM_T *item, LST(node_t) *next) -{ - LST(node_t) *new_node = (LST(node_t)*) malloc(sizeof(LST(node_t))); - new_node->item = *item; - new_node->next = next; - return new_node; -} - -LST(node_t) *LST(prepend)(LST(node_t) *list, LST_ITEM_T *item) -{ - LST(node_t) *new_head = LST(create)(item, list); - return new_head; -} - -LST(node_t) *LST(insert_after)(LST(node_t) *node, LST_ITEM_T *item) -{ - LST(node_t) *new_node; - if (node == NULL) - return NULL; - new_node = LST(create)(item, node->next); - node->next = new_node; - return new_node; -} - -LST(node_t) *LST(insert_after_nth)(LST(node_t) *list, int n, LST_ITEM_T *item) -{ - return LST(insert_after)(LST(nth)(list, n), item); -} - -LST(node_t) *LST(remove_front)(LST(node_t) *list) -{ - LST(node_t) *new_head; - if (list == NULL) - return NULL; - new_head = list->next; - free(list); - return new_head; -} - -LST(node_t) *LST(remove)(LST(node_t) *list, LST(node_t) *node) -{ - LST(node_t) *prev_node; - if (list == NULL) - return NULL; - if (list == node) - return LST(remove_front)(list); - for (prev_node = list; prev_node->next != NULL; prev_node = prev_node->next) { - if (prev_node->next == node) { - prev_node->next = node->next; - free(node); - break; - } - } - return list; -} - -LST(node_t) *LST(remove_item)(LST(node_t) *list, LST_ITEM_T *item) -{ - LST(node_t) *prev_node, *node; - if (list == NULL) - return NULL; - if (LST(compare_func)(&list->item, item)) - return LST(remove_front)(list); - for (prev_node = list, node = prev_node->next; node != NULL; prev_node = prev_node->next, node = node->next) { - if (LST(compare_func)(&node->item, item)) { - prev_node->next = node->next; - free(node); - break; - } - } - return list; -} - -LST(node_t) *LST(find)(LST(node_t) *list, LST_ITEM_T *item) -{ - LST(node_t) *node; - for (node = list; node != NULL; node = node->next) { - if (LST(compare_func)(&node->item, item)) { - return node; - } - } - return NULL; -} - -LST(node_t) *LST(nth)(LST(node_t) *list, int n) -{ - int i; - for (i = 0; i < n && list != NULL; i++) - list = list->next; - return list; -} - -LST(node_t) *LST(last)(LST(node_t) *list) -{ - if (list == NULL) - return NULL; - while (list->next != NULL) - list = list->next; - return list; -} - -size_t LST(length)(LST(node_t) *list) -{ - size_t len = 0; - if (list == NULL) - return 0; - for (; list != NULL; list = list->next) - len++; - return len; -} - -int LST(get_index)(LST(node_t) *list, LST(node_t) *node) -{ - int i; - if (list == NULL) - return -1; - for (i = 0; list != node && list != NULL; list = list->next) - i++; - if (list == NULL) - return -1; - return i; -} - -void LST(free)(LST(node_t) *list) -{ - LST(node_t) *node, *next_node; - if (list == NULL) - return; - for (node = list, next_node = node->next; next_node != NULL; node = next_node, next_node = next_node->next) - free(node); - free(node); -} Index: cdt/Makefile =================================================================== --- cdt/Makefile (revision 32651) +++ cdt/Makefile (nonexistent) @@ -1,7 +0,0 @@ -CFLAGS=-Wall -O0 -g3 -I. -I../../../src_3rd -LDFLAGS=-lm - -cdt_test: cdt_test.o cdt.o point.o edge.o triangle.o - -%.o: %.c - gcc $(CFLAGS) -c $< -o $@ Index: Plug.tmpasm =================================================================== --- Plug.tmpasm (revision 32651) +++ Plug.tmpasm (revision 32652) @@ -6,10 +6,10 @@ $(PLUGDIR)/sketch_route/ewire_point.o $(PLUGDIR)/sketch_route/spoke.o $(PLUGDIR)/sketch_route/pointdata.o - $(PLUGDIR)/sketch_route/cdt/cdt.o - $(PLUGDIR)/sketch_route/cdt/edge.o - $(PLUGDIR)/sketch_route/cdt/point.o - $(PLUGDIR)/sketch_route/cdt/triangle.o + $(SRC_3RD_DIR)/libcdtr/cdt.o + $(SRC_3RD_DIR)/libcdtr/edge.o + $(SRC_3RD_DIR)/libcdtr/point.o + $(SRC_3RD_DIR)/libcdtr/triangle.o @] switch /local/pcb/sketch_route/controls Index: sketch_route.c =================================================================== --- sketch_route.c (revision 32651) +++ sketch_route.c (revision 32652) @@ -55,7 +55,7 @@ #include "ewire_point.h" #include "pointdata.h" #include "spoke.h" -#include "cdt/cdt.h" +#include #include #include #include Index: spoke.h =================================================================== --- spoke.h (revision 32651) +++ spoke.h (revision 32652) @@ -4,7 +4,7 @@ #include "sktypedefs.h" #include "obj_common.h" #include "ewire.h" -#include "cdt/point.h" +#include #include Index: wire.c =================================================================== --- wire.c (revision 32651) +++ wire.c (revision 32652) @@ -111,5 +111,5 @@ free(*elem); } -#include "cdt/list/list.c" +#include #include Index: wire.h =================================================================== --- wire.h (revision 32651) +++ wire.h (revision 32652) @@ -5,7 +5,7 @@ #include #include "config.h" -#include "cdt/typedefs.h" +#include #include "sktypedefs.h" @@ -43,7 +43,7 @@ #define LST_ITEM_T wire_ptr_t #define LST_DONT_TYPEDEF_NODE -#include "cdt/list/list.h" +#include #ifndef LST_DONT_UNDEF #undef LST