#include "simple.h"
#include <stdio.h>
#include <stdlib.h>
void find_intersection(struct vertex *l, struct vertex *m,
struct intersection ilist[], struct data *input);
void
find_ints(vertex_list, polygon_list, input, ilist)
struct vertex vertex_list[];
struct polygon polygon_list[];
struct data *input ;
struct intersection ilist[];
{
int i,j,k,gt();
struct active_edge_list all;
struct active_edge *new,*tempa;
struct vertex *pt1,*pt2,*templ,**pvertex;
input->ninters = 0;
all.first = all.final = NIL; all.number = 0;
pvertex = (struct vertex **)
malloc((input->nvertices) * sizeof(struct vertex *));
for (i = 0; i < input->nvertices ; i++ )
pvertex[i] = vertex_list + i ;
qsort(pvertex,input->nvertices,sizeof(struct vertex *),gt);
for (i = 0 ; i < input->nvertices ; i++ ) {
pt1 = pvertex[i]; templ = pt2 = prior(pvertex[i]);
for (k = 0 ; k < 2 ; k++ ) {
switch (gt(&pt1,&pt2)) {
case -1:
for (tempa=all.first,j=0 ; j<all.number ; j++ , tempa = tempa->next )
find_intersection(tempa->name,templ,ilist,input);
new = (struct active_edge *) malloc(sizeof(struct active_edge));
if (all.number == 0) { all.first = new; new->last = NIL; }
else { all.final->next = new; new->last = all.final; }
new->name = templ; new->next = NIL;
templ->active = new; all.final = new; all.number++;
break;
case 1:
if( (tempa = templ->active) == NIL) {
fprintf(stderr,"\n***ERROR***\n trying to delete a non line\n");
exit(1); }
if (all.number == 1) all.final = all.first = NIL;
else if (tempa == all.first)
{ all.first = all.first->next; all.first->last = NIL; }
else if (tempa == all.final) {
all.final = all.final->last; all.final->next = NIL; }
else { tempa->last->next = tempa->next;
tempa->next->last = tempa->last; }
free((char *) tempa);
all.number--; templ->active = NIL;
break;
}
pt2 = after(pvertex[i]); templ = pvertex[i];
}
}
}
int gt(i,j)
struct vertex **i,**j;
{
double t;
if ((t = (*i)->pos.x - (*j)->pos.x) != 0.) return( (t > 0.) ? 1 : -1 );
if ((t = (*i)->pos.y - (*j)->pos.y) == 0.) return(0);
else return( (t > 0.) ? 1 : -1 );
}