/* dia-geometry.c
 * Copyright (C) 1998, Alexander Larsson
 * Copyright (C) 2001, Arjan Molenaar
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library 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
 * Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public
 * License along with this library; if not, write to the
 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 * Boston, MA 02111-1307, USA.
 */

#include <math.h>
#include "dia-geometry.h"


static inline void
point_add (DiaPoint *p1, DiaPoint *p2)
{
	p1->x += p2->x;
	p1->y += p2->y;
}

static inline void
point_sub (DiaPoint *p1, DiaPoint *p2)
{
	p1->x -= p2->x;
	p1->y -= p2->y;
}

static inline gdouble
point_dot (DiaPoint *p1, DiaPoint *p2)
{
	return (p1->x * p2->x) + (p1->y * p2->y);
}
    
static inline void
point_scale (DiaPoint *p, gdouble alpha)
{
	p->x *= alpha;
	p->y *= alpha;
}

static inline void
point_normalize (DiaPoint *p)
{
	gdouble len;

	len = sqrt(p->x*p->x + p->y*p->y);

	p->x /= len;
	p->y /= len;
}

static inline gboolean
point_in_rectangle (DiaRectangle* r, DiaPoint *p)
{
	if ((p->x < r->left)
	    || (p->x > r->right)
	    || (p->y > r->bottom)
	    || (p->y < r->top))
		return FALSE;

	return TRUE;
}

/**
 * dia_rectangle_add_point:
 * @rect: 
 * @p: 
 *
 * Extent @rect so point @p is also in the rectangle.
 **/
void
dia_rectangle_add_point (DiaRectangle *rect, DiaPoint *p)
{
	if (p->x < rect->left)
		rect->left = p->x;
	else if (p->x > rect->right)
		rect->right = p->x;

	if (p->y < rect->top)
		rect->top = p->y;
	else if (p->y > rect->bottom)
		rect->bottom = p->y;
}


/**
 * dia_distance_point_point:
 * @p1: 
 * @p2: 
 *
 * Distance from one point to another point.
 *
 * Return value: Distance.
 **/
gdouble
dia_distance_point_point (DiaPoint *p1, DiaPoint *p2)
{
	gdouble dx;
	gdouble dy;

	g_return_val_if_fail (p1 != NULL, G_MAXDOUBLE);
	g_return_val_if_fail (p2 != NULL, G_MAXDOUBLE);

	dx = p1->x - p2->x;
	dy = p1->y - p2->y;

	return sqrt( dx*dx+dy*dy );
}

/**
 * dia_distance_point_point_manhattan:
 * @p1: 
 * @p2: 
 *
 * Fast distance calculation (but less accurate).
 *
 * Return value: Distance.
 **/
gdouble
dia_distance_point_point_manhattan (DiaPoint *p1, DiaPoint *p2)
{
	gdouble dx;
	gdouble dy;

	g_return_val_if_fail (p1 != NULL, G_MAXDOUBLE);
	g_return_val_if_fail (p2 != NULL, G_MAXDOUBLE);

	dx = p1->x - p2->x;
	dy = p1->y - p2->y;

	return ABS(dx) + ABS(dy);
}

/**
 * dia_distance_rectangle_point:
 * @rect: 
 * @point: 
 *
 * This function estimates the distance from a point to a rectangle.
 * If the point is in the rectangle, 0.0 is returned. Otherwise the
 * distance in a manhattan metric from the point to the nearest point
 * on the rectangle is returned.
 *
 * Return value: Distance from the rectangle to the point, 0.0 if the point
 *	is inside the rectangle.
 **/
gdouble
dia_distance_rectangle_point (DiaRectangle *rect, DiaPoint *point)
{
	gdouble dx = 0.0;
	gdouble dy = 0.0;

	g_return_val_if_fail (rect != NULL, G_MAXDOUBLE);
	g_return_val_if_fail (point != NULL, G_MAXDOUBLE);

	if (point->x < rect->left) {
		dx = rect->left - point->x;
	} else if (point->x > rect->right) {
		dx = point->x - rect->right;
	}

	if (point->y < rect->top) {
		dy = rect->top - point->y;
	} else if (point->y > rect->bottom) {
		dy = point->y - rect->bottom;
	}

	return dx + dy;
}

/**
 * dia_distance_line_point:
 * @line_start: 
 * @line_end: 
 * @point: 
 * @line_width: 
 * @style: 
 * @point_on_line: OUT point on the line, closest to @point. May be NULL.
 *
 * This function estimates the distance from a point to a line segment
 * specified by two endpoints.
 * If the point is on the line, 0.0 is returned. Otherwise the
 * distance in the R^2 metric from the point to the nearest point
 * on the line segment is returned. Does one sqrt per call.
 *
 * If @point can not be projected on the line, the distance from the start
 * or end point is taken. If @style is #DIA_CAP_ROUND or #DIA_CAP_SQUARE
 * the distance is decreased by @line_width/2.
 *
 * Return value: Distance from the @point to the line (this is equal to
 *	the distance from @point to @point_on_line - @line_width/2).
 **/
gdouble
dia_distance_line_point (DiaPoint *line_start, DiaPoint *line_end,
			 DiaPoint *point, gdouble line_width, DiaCapStyle style,
			 DiaPoint *point_on_line)
{
	DiaPoint v1, v2;
	gdouble v1_lensq;
	gdouble projlen;
	gdouble perp_dist;

	g_return_val_if_fail (line_start != NULL, G_MAXDOUBLE);
	g_return_val_if_fail (line_end != NULL, G_MAXDOUBLE);
	g_return_val_if_fail (point != NULL, G_MAXDOUBLE);

	// "Move" the line, so it "starts" on (0, 0)
	v1 = *line_end;
	point_sub (&v1,line_start);

	// v2: Move v2, so it's relative to (0, 0)
	v2 = *point;
	point_sub (&v2, line_start);

	// Calculate the sqr of the line length:
	v1_lensq = point_dot (&v1,&v1);

	// If both start and end point are very close together:
	if (v1_lensq < 0.000001) {
		if (point_on_line)
			*point_on_line = *line_start;
		return sqrt (point_dot (&v2,&v2));
	}

	projlen = point_dot (&v1,&v2) / v1_lensq;

	if (projlen < 0.0) {
		/* Point has a projection before the begin of the line */
		if (point_on_line)
			*point_on_line = *line_start;

		perp_dist = sqrt (point_dot (&v2,&v2));
		if ((style == DIA_CAP_SQUARE) || (style == DIA_CAP_ROUND)) {
			perp_dist -= line_width / 2.0;
		}
	} else if (projlen > 1.0) {
		/* Point has a projection after the end of the line */
		DiaPoint v3 = *point;
		point_sub(&v3,line_end);
		if (point_on_line)
			*point_on_line = *line_end;

		perp_dist = sqrt (point_dot (&v3,&v3));
		if ((style == DIA_CAP_SQUARE) || (style == DIA_CAP_ROUND)) {
			perp_dist -= line_width / 2.0;
		}
	} else {
		/* Point has a projection on the line */
		point_scale (&v1, projlen);
		if (point_on_line) {
			*point_on_line = v1;
			point_add (point_on_line, line_start);
		}

		point_sub (&v1, &v2);
		perp_dist = sqrt (point_dot (&v1,&v1));

		perp_dist -= line_width / 2.0;
	}

	return (perp_dist < 0.0) ? 0.0 : perp_dist;
}


/**
 * dia_intersection_line_line:
 * @start1: Starting point of line 1.
 * @end1: End of line 1.
 * @start2: Start of line 2.
 * @end2: End of line 2.
 * @intersect: If TRUE is returned, @intersect contains the point of
 *	intersection.
 *
 * Find the intersection point of two lines, if any.
 *
 * Return value: TRUE if an intersection point is found, FALSE otherwise.
 **/
gboolean
dia_intersection_line_line (DiaPoint *start1, DiaPoint *end1,
			    DiaPoint *start2, DiaPoint *end2,
			    DiaPoint *intersect)
{
	gdouble a1 = 0.0, a2 = 0.0;
	gdouble b1 = 0.0, b2 = 0.0;
	gboolean vertical1 = FALSE;
	gboolean vertical2 = FALSE;
	DiaRectangle bb1, bb2;
	DiaPoint p;

	/* first line: y1 = a1*x + b1 */
	/* line is vertical? */
	if ((start1->x - end1->x) != 0.0) {
		a1 = (start1->y - end1->y) / (start1->x - end1->x);
		b1 = start1->y - a1 * start1->x;
	} else {
		vertical1 = TRUE;
	}

	if ((start2->x - end2->x) != 0.0) {
		a2 = (start2->y - end2->y)/ (start2->x - end2->x);
		b2 = start2->y - a2 * start2->x;
	} else {
		vertical2 = TRUE;
	}

	/* two parallel vertical lines */ 
	if (vertical1 && vertical2)
		return FALSE;

	if (vertical1) {
	/* line one is vertical */
		p.x = start1->x;
		p.y = a2 * p.x + b2;
	} else if (vertical2) {
		/* line two is vertical */
		p.x = start2->x;
		p.y = a1 * p.x + b1;
	} else if (a1 == a2) {
		/* two parallel lines */
		return FALSE;
	} else {
		/* two normal crossing lines */
		p.x = (b2 - b1) / (a1 - a2);
		p.y = a1 * p.x + b1;
	} 

	/* If the intersection point is within both bounding boxes, there
	 * is a valid intersection. */
	bb1.top = MIN (start1->y, end1->y);
	bb1.bottom = MAX (start1->y, end1->y);
	bb1.left = MIN (start1->x, end1->x);
	bb1.right = MAX (start1->x, end1->x);

	bb2.top = MIN (start2->y, end2->y);
	bb2.bottom = MAX (start2->y, end2->y);
	bb2.left = MIN (start2->x, end2->x);
	bb2.right = MAX (start2->x, end2->x);

	if (point_in_rectangle (&bb1, &p) && point_in_rectangle (&bb2, &p)) {
		if (intersect)
			*intersect = p;
		return TRUE;
	}

	return FALSE;
}

/**
 * dia_intersection_line_rectangle:
 * @start: 
 * @end: 
 * @rect: 
 * @intersect: A list of intersections.
 *
 * Find the intersection points of a line and a rectangle by comparing each
 * border line of the rectangle with the line's intersection.
 *
 * Return value: Number of intersections: 0, 1 or 2.
 **/
gint
dia_intersection_line_rectangle (DiaPoint *start, DiaPoint *end,
				 DiaRectangle *rect, DiaPoint intersect[2])
{
	DiaPoint tl; /* top-left */
	DiaPoint tr; /* top-right */
	DiaPoint bl; /* bottom... ah well */
	DiaPoint br;
	DiaPoint p;
	gint count = 0;
	DiaPoint *is;

	g_return_val_if_fail (start != NULL, 0);
	g_return_val_if_fail (end != NULL, 0);
	g_return_val_if_fail (rect != NULL, 0);
	g_return_val_if_fail (intersect != NULL, 0);

	/* A line can intersect with no more than two points of the rectangle
	 * (plus one for the delimiter). */
	is = intersect;

	tl.x = bl.x = rect->left;
	tr.x = br.x = rect->right;
	tl.y = tr.y = rect->top;
	bl.y = br.y = rect->bottom;

	/* top */
	if (dia_intersection_line_line (start, end, &tl, &tr, &p)) {
		is[count++] = p;
	}

	/* bottom */
	if (dia_intersection_line_line (start, end, &bl, &br, &p)) {
		is[count++] = p;
	}

	if (count > 1) {
		if ((is[0].x == is[1].x) && (is[0].y == is[1].y))
			return 1;
		return count;
	}

	/* left */
	if (dia_intersection_line_line (start, end, &tl, &bl, &p)) {
		is[count++] = p;
	}

	if (count > 1) {
		if ((is[0].x == is[1].x) && (is[0].y == is[1].y))
			return 1;
		return count;
	}

	/* right */
	if (dia_intersection_line_line (start, end, &tr, &br, &p)) {
		is[count++] = p;
	}

	if ((is[0].x == is[1].x) && (is[0].y == is[1].y))
		return 1;
	return count;
}

/**
 * dia_intersection_rectangle_rectangle:
 * @r1: 
 * @r2: 
 *
 * Determine if two rectangles intersect with each other.
 *
 * Return value: TRUE if an intersection is found, FALSE otherwise.
 **/
gboolean
dia_intersection_rectangle_rectangle (DiaRectangle *r1, DiaRectangle *r2)
{
	g_return_val_if_fail (r1 != NULL, FALSE);
	g_return_val_if_fail (r2 != NULL, FALSE);

	if ((r1->right < r2->left)
	    || (r1->left > r2->right)
	    || (r1->top > r2->bottom)
	    || (r1->bottom < r2->top))
	return FALSE;

	return TRUE;
}