#include "defines.h"

/* Does a complete check of supposed delaunay diagram */
/* Note that this is slower than computing it, hence should not be used */
/* except for testing other check routine */
BOOLEAN
full_check_delaunay()
{
    EDGE_PTR e;
    SITE_PTR a,b,c,d;

    if (!check_bndry() || !check_triangles())
	return FALSE;

    for_tris(e)
	a = orig(lprev(e)); b = orig(e); c = dest(e);
	for_sites(d)
	    if (incircle(a,b,c,d))
		return FALSE;
        end_sites(d)
    end_tris(e);

    return TRUE;
}

#define ccw_rtri(e) ccw(dest(rprev(e)),dest(e),orig(e))
#define ccw_ltri(e) ccw(orig(lprev(e)),orig(e),dest(e))
#define PI 3.14159265358979

BOOLEAN
check_bndry()
{
    EDGE_PTR e;
    double ang, last_ang;
    double angle();
    int rotation = 0;

    ang = angle(orig(rnext(One_bndry_edge)),orig(One_bndry_edge));
    for_rring_a(One_bndry_edge,e)
	last_ang = ang;
	ang = angle(orig(e),dest(e));
	if (ang < last_ang)
	{
	    if (last_ang - ang > PI)
		rotation++;
	    else
		return FALSE;
	}
	else if (ang - last_ang > PI)
	    return FALSE;
    end_rring_a(One_bndry_edge,e);

    return rotation==1;
}

BOOLEAN
check_triangles()
{
    EDGE_PTR e;

    for_tris(e)
	if (!ccw_ltri(e))
	    return FALSE;
    end_tris(e)

    return TRUE;
}

BOOLEAN
check_delaunay()
{
    EDGE_PTR e;
    SITE_PTR a,b;

    if (!check_bndry() || !check_triangles())
	return FALSE;
    for_quad_edges(e)
	if ((a=orig(lprev(e)))==orig(dprev(e))
		&& (b=dest(rprev(e)))==orig(rnext(e)))
	    if (incircle(a,orig(e),dest(e),b))
		return FALSE;
    end_quad_edges(e)

    return TRUE;
}

#define rnd (r*(RAND-.5)*2)
jiggle(r)
double r;
{
    SITE_PTR v;
    for_sites(v)
	{ X(v) += rnd; Y(v) += rnd; }
    end_sites(v)
}

#define new_cvx(e) sym(connect_right(rprev(e),e))
/* add new cvx hull edge from orig(e) to dest(rprev(e)) */
#define del_cvx(e) (changed=TRUE,e=rnext(e),deleteedge(rprev(e)))

BOOLEAN
fix_delaunay()
{
    EDGE_PTR e;
    BOOLEAN changed;

    /* This first part is not guaranteed to work to fix the convex hull */
    /* If motions are very large, it might get confused. */

    /* check for deleted bndry */
    do {
	changed = FALSE;
	if (!ccw_ltri(One_bndry_edge))
	    del_cvx(One_bndry_edge);
	for_rring_o(One_bndry_edge,e)
	    if (!ccw_ltri(e))
	    {
		if (dnext(dnext(e))==e)
		    return FALSE;	/* Can't fix this */
		del_cvx(e);
	    }
	end_rring_o(One_bndry_edge,e)
    } while (changed);

    /* check for new bndry */
    do {
	changed = FALSE;

	while(ccw_rtri(One_bndry_edge))
	    One_bndry_edge = new_cvx(One_bndry_edge), changed = TRUE;

	for_rring_o(One_bndry_edge,e)
	    if (ccw_rtri(e))
	    {
		changed = TRUE;
		if (rprev(e) == One_bndry_edge)
		    { One_bndry_edge = new_cvx(e); break; }
		else
		    e = new_cvx(e), e = rnext(e);
	    }
	end_rring_o(One_bndry_edge,e);

    } while (changed);

    if (!check_bndry())
	return FALSE; /* give up if we haven't fixed bndry */

    consolidate_edges(); /* lets us use faster loop below */
    /* This should be able to fix the inside, even if some **
    ** triangles are inverted.  But if not we will give up */
    for_quad_edges(e);
	fix_edge(e);
    end_quad_edges(e);

    return check_delaunay(); /* we hope this is true often*/
}

fix_edge(e)
EDGE_PTR e;
{
    SITE_PTR a,b;

    if ((a=orig(lprev(e)))!=orig(dprev(e))
		    || (b=dest(rprev(e)))!=orig(rnext(e)))
	return; /* boundary edge */
    if (incircle(a,orig(e),dest(e),b))
    {
	swapedge(e);
	fix_edge(lprev(e));
	fix_edge(rprev(e));
	fix_edge(lnext(e));
	fix_edge(rnext(e));
    }
}