/* $Id: guppi-2d.c,v 1.2 2001/07/10 02:53:26 trow Exp $ */

/*
 * guppi-2d.c
 *
 * Copyright (C) 2000 EMC Capital Management, Inc.
 *
 * Developed by Jon Trowbridge <trow@gnu.org>.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as
 * published by the Free Software Foundation; either version 2 of the
 * License, or (at your option) any later version.
 *
 * This program 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 General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
 * USA
 */

#include <config.h>
#include "guppi-2d.h"

#include <libart_lgpl/art_vpath.h>
#include <guppi-memory.h>


gboolean
guppi_2d_line_segment_intersection (double pt1_x, double pt1_y,
				    double pt2_x, double pt2_y,
				    double pt3_x, double pt3_y,
				    double pt4_x, double pt4_y)
{
  double Ax, Ay, Bx, By, Cx, Cy, num1, num2, denom;

  Ax = pt2_x - pt1_x;
  Ay = pt2_y - pt1_y;

  Bx = pt3_x - pt4_x;
  By = pt3_y - pt4_y;

  Cx = pt1_x - pt3_x;
  Cy = pt1_y - pt3_y;

  num1 = By * Cx - Bx * Cy;
  num2 = Ax * Cy - Ay * Cx;
  denom = Ay * Bx - Ax * By;

  if (denom > 0) {

    if (num1 < 0 || num1 > denom || num2 < 0 || num2 > denom)
      return FALSE;

  } else {

    if (num1 > 0 || num1 < denom || num2 > 0 || num2 < denom)
      return FALSE;



  }

  return TRUE;
}



gboolean
guppi_2d_line_segment_window_query (double seg_x0, double seg_y0,
				    double seg_x1, double seg_y1,
				    double x0, double y0,
				    double x1, double y1)
{
  double Ax, Ay, Bx, By, Cx, Cy, num1, num2, denom;
  gboolean miss;

  /* If either end-point of the line segment lines inside of the window,
     we intersect. */
  if ((x0 <= seg_x0 && seg_x0 <= x1 && y0 <= seg_y0 && seg_y0 <= y1) ||
      (x0 <= seg_x1 && seg_x1 <= x1 && y0 <= seg_y1 && seg_y1 <= y1))
    return TRUE;

  /* This is the algorithm from "Graphics Gems III" */

  /*
     P1 = (seg_x0, seg_y0)
     P2 = (seg_x1, seg_y1)
   */

  Ax = seg_x1 - seg_x0;
  Ay = seg_y1 - seg_y0;

  /*
     Check #1
     P3 = (x0, y0)
     P4 = (x1, y0)
   */
  Bx = x0 - x1;
  /* By = 0; */
  Cx = seg_x0 - x0;
  Cy = seg_y0 - y0;

  num1 = -Bx * Cy;
  num2 = Ax * Cy - Ay * Cx;
  denom = Ay * Bx;

  miss = (((denom > 0) &&
	   (num1 < 0 || num1 > denom || num2 < 0 || num2 > denom)) ||
	  ((denom < 0) &&
	   (num1 > 0 || num1 < denom || num2 > 0 || num2 < denom)));

  if (!miss)
    return TRUE;

  /*
     Check #2
     P3 = (x0, y0)
     P4 = (x0, y1)
   */
  /* Bx = 0; */
  By = y0 - y1;
  Cx = seg_x0 - x0;
  Cy = seg_y0 - y0;

  num1 = By * Cx;
  num2 = Ax * Cy - Ay * Cx;
  denom = -Ax * By;

  miss = (((denom > 0) &&
	   (num1 < 0 || num1 > denom || num2 < 0 || num2 > denom)) ||
	  ((denom < 0) &&
	   (num1 > 0 || num1 < denom || num2 > 0 || num2 < denom)));

  if (!miss)
    return TRUE;


  /*
     Check #3
     P3 = (x1, y1)
     P4 = (x1, y0)
   */
  /* Bx = 0; */
  By = y1 - y0;
  Cx = seg_x0 - x1;
  Cy = seg_y0 - y1;

  num1 = By * Cx;
  num2 = Ax * Cy - Ay * Cx;
  denom = -Ax * By;

  miss = (((denom > 0) &&
	   (num1 < 0 || num1 > denom || num2 < 0 || num2 > denom)) ||
	  ((denom < 0) &&
	   (num1 > 0 || num1 < denom || num2 > 0 || num2 < denom)));

  if (!miss)
    return TRUE;


  /*
     Check #4
     P3 = (x1, y1)
     P4 = (x0, y1)
   */
  Bx = x1 - x0;
  /* By = 0; */
  Cx = seg_x0 - x1;
  Cy = seg_y0 - y1;

  num1 = -Bx * Cy;
  num2 = Ax * Cy - Ay * Cx;
  denom = Ay * Bx;

  miss = (((denom > 0) &&
	   (num1 < 0 || num1 > denom || num2 < 0 || num2 > denom)) ||
	  ((denom < 0) &&
	   (num1 > 0 || num1 < denom || num2 > 0 || num2 < denom)));

  if (!miss)
    return TRUE;



  return FALSE;
}

/* $Id: guppi-2d.c,v 1.2 2001/07/10 02:53:26 trow Exp $ */