#ifndef lint
static char rcsid [] = "$RCSfile$ $Revision$ $State$";
#endif
/****************************************************************************
*   File: rtmp_simplify.c                                                   *
*                                                                           *
*       Copyright 1994 by Loral Advanced Distributed Simulation, Inc.       *
*                                                                           *
*               Loral Advanced Distributed Simulation, Inc.                 *
*               10 Moulton Street                                           *
*               Cambridge, MA 02238                                         *
*               617-873-1850                                                *
*                                                                           *
*       This software was developed by Loral under U. S. Government contracts*
*       and may be reproduced by or for the U. S. Government pursuant to    *
*       the copyright license under the clause at DFARS 252.227-7013        *
*       (OCT 1988).                                                         *
*                                                                           *
*       Contents:                                                           *
*       Created:                                                            *
*       Author: tlp                                                         *
*       Remarks:                                                            *
*                                                                           *
****************************************************************************/

#include "librtmp_local.h"
#include "rtmp_convolve.h"

polygonal * routemap_ensure_simple_polygon(my_poly)
     polygonal *my_poly;
{
  int i, min_index;
  real min_y;
  point_list *output;
  point_list *points_tail;
  int first_time;
  point *crossing;
  int index;
  int next_index;
  int old_index=-1;

  output=NULL;

  if (!my_poly) return NULL;
  if (my_poly->num_vertices <= 3) return my_poly;

  /* find bottom vertex, which is guaranteed to be on simple polygon. */
  min_index = 0;
  min_y = my_poly->vertex[0].y;
  for (i = 1; i < my_poly->num_vertices; i++) 
    {
      if (my_poly->vertex[i].y < min_y) 
	{
	  min_index = i;
	  min_y = my_poly->vertex[i].y;
	}
    }
  output = my_point_add(output, &(my_poly->vertex[min_index]), 1);
/*  printf("adding point %f,%f\n",my_poly->vertex[min_index].x,my_poly->vertex[min_index].y);  */

  /* Walk around the boundary, constructing point_list */
  points_tail=output;
  index=min_index;
  first_time=1;
  while (first_time || (index!=min_index))
    {
      first_time=0;
      crossing = first_crossing(index, old_index, my_poly, points_tail->p, &next_index);
      if (crossing==NULL)
	{
	  next_index = (index+1)%(my_poly->num_vertices);
	  points_tail = my_point_add(points_tail,&(my_poly->vertex[next_index]),1);

/*	   printf("adding point %f,%f\n",my_poly->vertex[next_index].x,my_poly->vertex[next_index].y);   */

	}
      else
	{
	  points_tail = my_point_add(points_tail, crossing,0);

/*	  printf("adding crossed point %f , %f\n",crossing->x,crossing->y);  */

	}
/*       printf("going from %d to %d\n",index,next_index);   */
      old_index=index;
      index=next_index;
    }

#if 0
  output = 
    routemap_ensure_simple_polygon_aux(min_index, min_index, my_poly, output, output);
#endif
  return(point_list_to_polygonal(output));
}

point_list* routemap_ensure_simple_polygon_aux(index, start_index, poly, points_head, points_tail) 
     int index, start_index;
     polygonal *poly;
     point_list *points_head, *points_tail;
{
  point *crossing;
  int next_index = -1;

  crossing = first_crossing(index, poly, points_tail->p, &next_index);
  if (crossing) 
    {
      printf("yoo hoo I'm crossing at %f %f\n",crossing->x,crossing->y);
      /* Crossing, add intersection vertex and take a sharp right */
      points_tail = my_point_add(points_tail, crossing,0);
      routemap_ensure_simple_polygon_aux(next_index, start_index, 
				poly, points_head, points_tail);
    }
  else 
    {
      /* No crossing, return the next vertex */
      next_index = (index+1)%(poly->num_vertices);
      points_tail = my_point_add(points_tail,&(poly->vertex[next_index]),1);
      printf("adding point %f,%f\n",poly->vertex[next_index].x,poly->vertex[next_index].y);
      if (next_index != start_index) 
	{
	  routemap_ensure_simple_polygon_aux(next_index, start_index, 
				    poly, points_head, points_tail);
	}
      else
	return(points_head);
    }
}
  
/* 
Will return a point if a crossing exists after base_pt but before the next
vertex (after index), will set the value of next_index to that of the
vertex at the base of the crossing edge 
*/

point *first_crossing(index, old_index, poly, base_pt, next_index)
     int32 index; 
     int32 old_index;
     polygonal *poly;
     point *base_pt;
     int32 *next_index;
{
  int32 j, nj, min_j;
  int32 num = poly->num_vertices;
  int32 nindex = (index+1)%(poly->num_vertices);
  int32 pindex = modulo((index-1),(poly->num_vertices));
  real x0, y0, dx, dy, dot, dist, s, min_s;
  real x1, x2, y1, y2, nx, ny, min_dist;
  point a,b,c,d,i,min_i;
  int32 found_min=0;

  a.x=base_pt->x;
  a.y=base_pt->y;
  b.x=poly->vertex[nindex].x;
  b.y=poly->vertex[nindex].y;
  
  min_dist=INFINITY;
  for (j = 0; j < num; j++) 
    {
      if (j != pindex && j != index && j != nindex && j != old_index) 
	{
	  c.x = poly->vertex[j].x;
	  c.y = poly->vertex[j].y;
	  nj = (j+1)%num;
	  d.x = poly->vertex[nj].x;
	  d.y = poly->vertex[nj].y;

/*	  printf("my intersect would say %d\n",routemap_line_intersection(&a,&b,&c,&d));  */

	  if (((SAME(a.x,b.x))) && ((SAME(c.x,d.x))))       /*they're both vertical*/
	      continue;
	  if (abs(a.x-b.x)<=1.0)                       /*one is vertical to within one pixel. I know thats a lot, but otherwise this routine screws up */
	    {
	      i.x=(a.x+b.x)/2.0;
	      i.y=(((c.y-d.y)*i.x)+(c.y*(c.x-d.x))-(c.x*(c.y-d.y)))/(c.x-d.x);
	    }
	  else if (SAME(c.x,d.x))                  /* the other is vertical */
	    {
	      i.x=(c.x+d.x)/2.0;
	      i.y=(((a.y-b.y)*i.x)+(a.y*(a.x-b.x))-(a.x*(a.y-b.y)))/(a.x-b.x);
	    }
	  else 
	    if ((SAME(((c.y-d.y)/(c.x-d.x)),((a.y-b.y)/(a.x-b.x))))) /*they're parallel*/
	      continue;
	  /* finally, they're not parallel, not vertical, so there's an intersection*/
	  else
	    {
	      i.x=((c.x-d.x)/((a.y-b.y)*(c.x-d.x)-(c.y-d.y)*(a.x-b.x))) *
		((-a.y*(a.x-b.x)) + (a.x*(a.y-b.y)) + (c.y*(a.x-b.x)) - (c.x*(a.x-b.x)*(c.y-d.y)/(c.x-d.x)));
	      i.y=(((a.y-b.y)*i.x)+(a.y*(a.x-b.x))-(a.x*(a.y-b.y)))/(a.x-b.x);
	    }
/*	  printf("%d: %f,%f\n",j,i.x,i.y);  */
	  if (ROUTEMAP_TOTAL_WITHIN_SEGMENT(&a,&b,&i) && ROUTEMAP_TOTAL_WITHIN_SEGMENT(&c,&d,&i))
	    {
	      dist = fsqrt(routemap_distance_squared(&a,&i));
/*	      printf("dist %f, point is %f,%f,  j is %d\n",dist,i.x,i.y,j);   */
	      if (dist<min_dist)
		{
		  found_min=1;
		  min_dist=dist;
		  min_j=j;
		  min_i.x=i.x;
		  min_i.y=i.y;
		}
	    }
	}
    }
  if (found_min)
    {
      *next_index = min_j;
      return (new_point(min_i.x,min_i.y));
    }
  else 
    return NULL;
	  



#if 0
  x0 = base_pt->x;
  y0 = base_pt->y;
  dx = poly->vertex[nindex].x - x0;
  dy = poly->vertex[nindex].y - y0;
  min_s = 2.;
printf("checking for intersection with the line going from index %d to %d %d\n",index,nindex,pindex);
  for (j = 0; j < num; j++) 
    {
      if (j != pindex && j != index && j != nindex) 
	{
	  x1 = poly->vertex[j].x;
	  y1 = poly->vertex[j].y;
	  nj = (j+1)%num;
	  x2 = poly->vertex[nj].x;
	  y2 = poly->vertex[nj].y;
	  nx = y1 - y2;		/* normal */
	  ny = x2 - x1;
	  d  = nx * x1 + ny * y1;	/* offset */
	  dot = nx * dx + ny * dy;
	  if (dot == 0.0) continue;	/* parallel */
	  
	  /* might have to check for aligned edges overlapping! */
	  
	  dist = nx * x0 + ny * y0;
	  s = (d - dist)/dot;
	  if (s >= 0.0 && s <= 1.0) {
	    if (s < min_s) {
	      min_s = s; min_j = j;
	    }
	  }
	}
      if (min_s <= 1.0) 
	{
	  *next_index = min_j;
	  return (new_point(x0+s*dx, y0+s*dy));
	}
      else 
	return NULL;
    }
#endif

}

point_list* my_point_add(my_list, pt, copy)
     point_list *my_list;
     point *pt;
     int copy;
{
  point_list *new = (point_list *)malloc(sizeof(point_list));
  if (copy)
    new->p = new_point(pt->x, pt->y);
  else
    new->p = pt;
  new->next = NULL;
  new->prev = my_list;		/* needed? */
  if (my_list!=NULL)
    my_list->next = new;
  else
    my_list=new;
  return new;
}

polygonal *point_list_to_polygonal(my_list)
     point_list *my_list;
{
  int i, count;
  polygonal *poly;
  point_list *l;

  if (!my_list) return NULL;
  for(count=0, l=my_list; l->next != NULL; l = l->next, count++);
  poly = new_polygonal(count);
  for (i = 0, l=my_list; i < count; l=l->next, i++) {
    poly->vertex[i].x = x_coordinate(l->p);
    poly->vertex[i].y = y_coordinate(l->p);
  }
  return poly;
}