Delaunay triangle for neighboring

* structure for neighboring

number -

#ifdef REAL_AS_DOUBLE

typedef double real_t;

#else

typedef float real_t;

#endif

#define abs(x) ((x) > 0 ? (x) : -(x))

#define sqr(x) ((x)*(x))

point -

typedef struct {
   int reference; // reference counter
   int dimension; // n-dimension
   real_t *x; // n-tuples
} point_t;

point_t *point_new(int n);
point_t *point_new_and_assign(int n, real_t *tuples);
int point_assign(int n, real_t *tuples);
point_t *point_new_and_copy(point_t *arg);
int point_copy(point_t *arg);
void point_destroy(point_t *arg);
void point_subtract(point_t *c, point_t *a, point_t *b);

line -

typedef struct {
   int ref;
   point_t *a;
   point_t *b;
} line_t;

line_t *line_new(int dim);
line_t *line_new_and_assign(point_t *a, point_t *b);
int line_assign(line_t *line, point_t *a, point_t *b);
void line_destroy(line_t *line);

polygon -

typedef struct {
   int reference;
   int vertices;
   point_t **points;
} polygon_t;

polygon_t *polygon_new(int dim, int vertices);

* container

type -

enum {
   TYPE_NORMAL = 0,
   TYPE_BITMAP,
   TYPE_BYTEMAP,
   TYPE_WORDMAP,
   TYPE_DWORDMAP,
   TYPE_FLOATMAP,
   TYPE_DOUBLEMAP,
   TYPE_POINT,
   TYPE_LINE,
   TYPE_POLYGON
};

double linked list -

typedef struct {
   int type;
   void *object;
   d_link_t *prev;
   d_link_t *next;
} d_link_t;

typedef struct {
   d_link_t *head;
   d_link_t *tail;
} d_link_list_t;

* Measuring tool

Outer product in 2-dimension -

real_t outer_product_of_2d_points(point_t *a, point_t *b)
{
   assert(a);
   assert(b);
   assert(a->dimension >= 2);
   assert(b->dimension >= 2);

   return (a->x[0])*(b->x[1]) - (a->x[1]) * (b->x[0]);
}

Distance in 2-dimension - 

real_t distance_between_2d_points(point_t *a, point_t *b)

{

   assert(a);

   assert(b);

   assert(a->dimension >= 2);

   assert(b->dimension >= 2);

   return (a->x[0])*(b->x[0]) + (a->x[1]) * (b->x[1]);

}

Determinant for trianglation -

real_t determinant_for_delaunay_triangle(point_t *a, point_t *b, point_t *c)
{
   point_t *ba, *ca;

   assert(a);
   assert(b);
   assert(c);
   assert(a->dimension >= 2);
   assert(b->dimension >= 2);
   assert(c->dimension >= 2);

   ba = point_new(2);
   point_subtract(ba, b, a);

   ca = point_new(2);

   point_subtract(ca, c, a);

   return distance_between_2d_points(a, b) *distance_between_2d_points(b, c)*distance_between_2d_points(c, a) / 2 * abs(outer_product_of_2d_points(ba, ca));
}

Center of Circumscribed Circle of triangle -

void circumcenter_of_triangle(point_t *orig, polygon_t *triangle)
{

   point_t *a, *b, *c;

   real_t a1, b1, c1, a2, b2, c2;

   assert(triangle);

   assert(triangle->vertices >= 3);

   a = triangle->points[0];

   b = triangle->points[1];

   c = triangle->points[2];

   a1 = 2*(b->x[0] - a->x[0]);

   b1 = 2*(b->x[1] - a->x[1]);

   c1 = sqr(b->x[0])+sqr(b->x[1]) -(sqr(a->x[0])+sqr(a->x[1]));

   a2 = 2*(c->x[0] - b->x[0]);

   b2 = 2*(c->x[1] - b->x[1]);

   c2 = sqr(c->x[0])+sqr(c->x[1]) -(sqr(b->x[0])+sqr(b->x[1]));

   orig->x[0] = (c1*b2 - c2*b1) / (a1*b2 - a2*b1);

   orig->x[1] = (c1*a2 - c2*a1) / (b1*a2 - b2*a1);

}

Diameter of Circumscribed Circle of triangle -

real_t diameter_of_circumcircle_of_triangle(polygon_t *triangle)

{

   point_t *a, *b, *c;

   real_t da, db, dc;

   assert(triangle);

   assert(triangle->vertices >= 3);

   a = triangle->points[0];

   b = triangle->points[1];

   c = triangle->points[2];

   da = distance_of_2d_point(a);

   db = distance_of_2d_point(b);

   dc = distance_of_2d_point(c);

   return 2*da*db*dc / sqrt((da+db+dc)*(-da+db*dc)*(da-db+dc)*(da+db-dc));

}

* Procedure

1. Choose an arbitrary point.
2. Find the point with minimum distance from chosen point.
3. Find the point with minimum 'deteminant_of_triangle' with previous two points.
4. Build the initial triangle.
5. Three edges of the above triangle are gathered at the pool of edges.
6. For edge of the pool, incremental construction is performed.
7. For points at right hand of each edge
7.1. Find 'circumcircle' and 'circumdiameter'.
7.2. If any points do not exist in this circumcircle, construct another trinangle.
7.3. Except for the edge in 7., two edge are gathered at the pool of edges.
7.4. Repeat 7. until there is no points.