| /* For copyright information, see olden_v1.0/COPYRIGHT */ |
| |
| #include <math.h> |
| |
| typedef int BOOLEAN; |
| typedef unsigned long uptrint; |
| |
| struct edge_rec { |
| struct VERTEX *v; |
| struct edge_rec *next; |
| long wasseen; |
| void *Buffer; |
| }; |
| |
| |
| struct get_point { |
| struct VERTEX *v; |
| double curmax; |
| int seed; |
| }; |
| |
| |
| typedef struct edge_rec *EDGE_PTR; |
| typedef struct VERTEX *VERTEX_PTR; |
| typedef struct edge_rec *QUAD_EDGE; |
| |
| struct VEC2 { |
| double x,y; |
| double norm; |
| }; |
| |
| |
| struct VERTEX { |
| struct VEC2 v; |
| struct VERTEX *left, *right; |
| }; |
| |
| |
| typedef struct { |
| QUAD_EDGE left, right; |
| } EDGE_PAIR; |
| |
| |
| struct EDGE_STACK { |
| int ptr; |
| QUAD_EDGE *elts ; |
| int stack_size; |
| }; |
| |
| |
| #define onext(a) (a)->next |
| #define oprev(a) rot(onext(rot(a))) |
| #define lnext(a) rot(onext(rotinv(a))) |
| #define lprev(a) sym(onext(a)) |
| #define rnext(a) rotinv(onext(rot(a))) |
| #define rprev(a) onext(sym(a)) |
| #define dnext(a) sym(onext(sym(a))) |
| #define dprev(a) rotinv(onext(rotinv(a))) |
| |
| #define X(r) r->v.x |
| #define Y(r) r->v.y |
| #define NORM(r) r->v.norm |
| #define orig(a) (a)->v |
| #define dest(a) orig(sym(a)) |
| #define seen(a) (a)->wasseen |
| |
| #define origv(a) orig(a)->v |
| #define destv(a) dest(a)->v |
| |
| |
| #define SIZE ((uptrint) sizeof(struct edge_rec)) |
| #define ANDF ((uptrint) 4*sizeof(struct edge_rec) - 1) |
| |
| #define sym(a) ((QUAD_EDGE) (((uptrint) (a)) ^ 2*SIZE)) |
| #define rot(a) ((QUAD_EDGE) ( (((uptrint) (a) + 1*SIZE) & ANDF) | ((uptrint) (a) & ~ANDF) )) |
| #define rotinv(a) ((QUAD_EDGE) ( (((uptrint) (a) + 3*SIZE) & ANDF) | ((uptrint) (a) & ~ANDF) )) |
| #define base(a) ((QUAD_EDGE) ((uptrint a) & ~ANDF)) |
| |
| QUAD_EDGE alloc_edge(); |
| void free_edge(QUAD_EDGE e); |
| QUAD_EDGE makeedge(); |
| void splice(); |
| void swapedge(); |
| void deleteedge(); |
| QUAD_EDGE build_delaunay_triangulation(); |
| EDGE_PAIR build_delaunay(VERTEX_PTR tree, VERTEX_PTR extra); |
| EDGE_PAIR do_merge(QUAD_EDGE ldo, QUAD_EDGE ldi, QUAD_EDGE rdi, QUAD_EDGE rdo); |
| QUAD_EDGE connect_left(); |
| QUAD_EDGE connect_right(); |
| |
| int myrandom(int seed); |
| void zero_seen(); |
| QUAD_EDGE pop_edge(); |
| |
| #define drand(seed) (((double) (seed=myrandom(seed))) / (double) 2147483647) |
| |
| extern VERTEX_PTR *vp ; |
| extern struct VERTEX *va ; |
| extern EDGE_PTR *next ; |
| extern VERTEX_PTR *org ; |
| extern int num_vertices, num_edgeparts, stack_size ; |
| extern int to_lincoln , to_off, to_3d_out, to_color , voronoi , delaunay , interactive , ahost ; |
| extern char *see; |
| extern int NumNodes, NDim; |
| |
| |
| void push_ring(struct EDGE_STACK *stack, QUAD_EDGE edge); |
| void push_edge(struct EDGE_STACK *stack, QUAD_EDGE edge); |
| BOOLEAN ccw(VERTEX_PTR a, VERTEX_PTR b, VERTEX_PTR c); |
| int dealwithargs(int argc, char *argv[]); |
| void output_voronoi_diagram(QUAD_EDGE edge, int nv, struct EDGE_STACK *stack); |
| struct get_point get_points(int n, double curmax,int i, int seed, |
| int processor, int numnodes); |
| struct EDGE_STACK *allocate_stack(int num_vertices); |
| |
| |
| double V2_cprod(struct VEC2 u,struct VEC2 v); |
| double V2_dot(struct VEC2 u, struct VEC2 v); |
| struct VEC2 V2_times(double c, struct VEC2 v); |
| struct VEC2 V2_sum(struct VEC2 u, struct VEC2 v); |
| struct VEC2 V2_sub(struct VEC2 u, struct VEC2 v); |
| double V2_magn(struct VEC2 u); |
| struct VEC2 V2_cross(struct VEC2 v); |