#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include "glimports.h"
#include "zlassert.h"
#include "quicksort.h"
#include "directedLine.h"
#include "polyDBG.h"
#ifdef __WATCOMC__
#pragma warning 726 10
#endif
directedLine* directedLine::deleteChain(directedLine* begin, directedLine* end)
{
if(begin->head()[0] == end->tail()[0] &&
begin->head()[1] == end->tail()[1]
)
{
directedLine *ret = begin->prev;
begin->prev->next = end->next;
end->next->prev = begin->prev;
delete begin->sline;
delete end->sline;
delete begin;
delete end;
return ret;
}
directedLine* newLine;
sampledLine* sline = new sampledLine(begin->head(), end->tail());
newLine = new directedLine(INCREASING, sline);
directedLine *p = begin->prev;
directedLine *n = end->next;
p->next = newLine;
n->prev = newLine;
newLine->prev = p;
newLine->next = n;
delete begin->sline;
delete end->sline;
delete begin;
delete end;
return newLine;
}
void directedLine::deleteSingleLine(directedLine* dline)
{
dline->next->head()[0] = dline->prev->tail()[0];
dline->next->head()[1] = dline->prev->tail()[1];
dline->prev->next = dline->next;
dline->next->prev = dline->prev;
delete dline;
}
static Int myequal(Real a[2], Real b[2])
{
if(fabs(a[0]-b[0]) < 0.00001 &&
fabs(a[1]-b[1]) < 0.00001)
return 1;
else
return 0;
}
directedLine* directedLine::deleteDegenerateLines()
{
if(this->next == this)
return this;
if(this->next == this->prev)
return this;
directedLine* temp;
directedLine* first = NULL;
if(! myequal(head(), tail()))
first = this;
else
{
for(temp = this->next; temp != this; temp = temp->next)
{
if(! myequal(temp->head(), temp->tail()))
{
first = temp;
break;
}
}
}
if(first == NULL)
{
deleteSinglePolygonWithSline();
return NULL;
}
directedLine* tempNext = NULL;
for(temp =first->next; temp != first; temp = tempNext)
{
tempNext = temp->getNext();
if(myequal(temp->head(), temp->tail()))
deleteSingleLine(temp);
}
return first;
}
directedLine* directedLine::deleteDegenerateLinesAllPolygons()
{
directedLine* temp;
directedLine *tempNext = NULL;
directedLine* ret= NULL;
directedLine* retEnd = NULL;
for(temp=this; temp != NULL; temp = tempNext)
{
tempNext = temp->nextPolygon;
temp->nextPolygon = NULL;
if(ret == NULL)
{
ret = retEnd = temp->deleteDegenerateLines();
}
else
{
directedLine *newPolygon = temp->deleteDegenerateLines();
if(newPolygon != NULL)
{
retEnd->nextPolygon = temp->deleteDegenerateLines();
retEnd = retEnd->nextPolygon;
}
}
}
return ret;
}
directedLine* directedLine::cutIntersectionAllPoly(int &cutOccur)
{
directedLine* temp;
directedLine *tempNext = NULL;
directedLine* ret= NULL;
directedLine* retEnd = NULL;
cutOccur = 0;
for(temp=this; temp != NULL; temp = tempNext)
{
int eachCutOccur=0;
tempNext = temp->nextPolygon;
temp->nextPolygon = NULL;
if(ret == NULL)
{
ret = retEnd = DBG_cutIntersectionPoly(temp, eachCutOccur);
if(eachCutOccur)
cutOccur = 1;
}
else
{
retEnd->nextPolygon = DBG_cutIntersectionPoly(temp, eachCutOccur);
retEnd = retEnd->nextPolygon;
if(eachCutOccur)
cutOccur = 1;
}
}
return ret;
}
void directedLine::deleteSinglePolygonWithSline()
{
directedLine *temp, *tempNext;
prev->next = NULL;
for(temp=this; temp != NULL; temp = tempNext)
{
tempNext = temp->next;
delete temp->sline;
delete temp;
}
}
void directedLine::deletePolygonListWithSline()
{
directedLine *temp, *tempNext;
for(temp=this; temp != NULL; temp=tempNext)
{
tempNext = temp->nextPolygon;
temp->deleteSinglePolygonWithSline();
}
}
void directedLine::deleteSinglePolygon()
{
directedLine *temp, *tempNext;
prev->next = NULL;
for(temp=this; temp != NULL; temp = tempNext)
{
tempNext = temp->next;
delete temp;
}
}
void directedLine::deletePolygonList()
{
directedLine *temp, *tempNext;
for(temp=this; temp != NULL; temp=tempNext)
{
tempNext = temp->nextPolygon;
temp->deleteSinglePolygon();
}
}
directedLine::directedLine(short dir, sampledLine* sl)
{
direction = dir;
sline = sl;
next = this;
prev = this;
nextPolygon = NULL;
rootBit = 0;
rootLink = NULL;
}
void directedLine::init(short dir, sampledLine* sl)
{
direction = dir;
sline = sl;
}
directedLine::directedLine()
{
next = this;
prev = this;
nextPolygon = NULL;
rootBit = 0;
rootLink = NULL;
}
directedLine::~directedLine()
{
}
Real* directedLine::head()
{
return (direction==INCREASING)? (sline->get_points())[0] : (sline->get_points())[sline->get_npoints()-1];
}
Real* directedLine::getVertex(Int i)
{
return (direction==INCREASING)? (sline->get_points())[i] : (sline->get_points())[sline->get_npoints() - 1 -i];
}
Real* directedLine::tail()
{
return (direction==DECREASING)? (sline->get_points())[0] : (sline->get_points())[sline->get_npoints()-1];
}
void directedLine::insert(directedLine* nl)
{
nl->next = this;
nl->prev = prev;
prev->next = nl;
prev = nl;
nl->rootLink = this;
}
Int directedLine::numEdges()
{
Int ret=0;
directedLine* temp;
if(next == this) return 1;
ret = 1;
for(temp = next; temp != this; temp = temp->next)
ret++;
return ret;
}
Int directedLine::numEdgesAllPolygons()
{
Int ret=0;
directedLine* temp;
for(temp=this; temp!= NULL; temp=temp->nextPolygon)
{
ret += temp->numEdges();
}
return ret;
}
short directedLine::isPolygon()
{
directedLine* temp;
if(numEdges() <=2) return 0;
if(! isConnected()) return 0;
for(temp=next; temp != this; temp = temp->next){
if(!isConnected()) return 0;
}
return 1;
}
short directedLine::isConnected()
{
if( (head()[0] == prev->tail()[0]) && (head()[1] == prev->tail()[1]))
return 1;
else
return 0;
}
Int compV2InY(Real A[2], Real B[2])
{
if(A[1] < B[1]) return -1;
if(A[1] == B[1] && A[0] < B[0]) return -1;
if(A[1] == B[1] && A[0] == B[0]) return 0;
return 1;
}
Int compV2InX(Real A[2], Real B[2])
{
if(A[0] < B[0]) return -1;
if(A[0] == B[0] && A[1] < B[1]) return -1;
if(A[0] == B[0] && A[1] == B[1]) return 0;
return 1;
}
Int directedLine::compInY(directedLine* nl)
{
if(head()[1] < nl->head()[1]) return -1;
if(head()[1] == nl->head()[1] && head()[0] < nl->head()[0]) return -1;
return 1;
}
Int directedLine::compInX(directedLine* nl)
{
if(head()[0] < nl->head()[0]) return -1;
if(head()[0] == nl->head()[0] && head()[1] < nl->head()[1]) return -1;
return 1;
}
static Int compInY2(directedLine* v1, directedLine* v2)
{
return v1->compInY(v2);
}
#ifdef NOT_USED
static Int compInX(directedLine* v1, directedLine* v2)
{
return v1->compInX(v2);
}
#endif
directedLine** directedLine::sortAllPolygons()
{
Int total_num_edges = 0;
directedLine** array = toArrayAllPolygons(total_num_edges);
quicksort( (void**)array, 0, total_num_edges-1, (Int (*)(void *, void *)) compInY2);
return array;
}
void directedLine::printSingle()
{
if(direction == INCREASING)
printf("direction is INCREASING\n");
else
printf("direction is DECREASING\n");
printf("head=%f,%f)\n", head()[0], head()[1]);
sline->print();
}
void directedLine::printList()
{
directedLine* temp;
printSingle();
for(temp = next; temp!=this; temp=temp->next)
temp->printSingle();
}
void directedLine::printAllPolygons()
{
directedLine *temp;
for(temp = this; temp!=NULL; temp = temp->nextPolygon)
{
printf("polygon:\n");
temp->printList();
}
}
directedLine* directedLine::insertPolygon(directedLine* oldList)
{
setRootBit();
if(oldList == NULL) return this;
nextPolygon = oldList;
return this;
}
directedLine* directedLine::cutoffPolygon(directedLine *p)
{
directedLine* temp;
directedLine* prev_polygon = NULL;
if(p == NULL) return this;
for(temp=this; temp != p; temp = temp->nextPolygon)
{
if(temp == NULL)
{
fprintf(stderr, "in cutoffPolygon, not found\n");
exit(1);
}
prev_polygon = temp;
}
p->resetRootBit();
if(prev_polygon == NULL)
return nextPolygon;
else {
prev_polygon->nextPolygon = p->nextPolygon;
return this;
}
}
Int directedLine::numPolygons()
{
if(nextPolygon == NULL) return 1;
else return 1+nextPolygon->numPolygons();
}
Int directedLine::toArraySinglePolygon(directedLine** array, Int index)
{
directedLine *temp;
array[index++] = this;
for(temp = next; temp != this; temp = temp->next)
{
array[index++] = temp;
}
return index;
}
directedLine** directedLine::toArrayAllPolygons(Int& total_num_edges)
{
total_num_edges=numEdgesAllPolygons();
directedLine** ret = (directedLine**) malloc(sizeof(directedLine*) * total_num_edges);
assert(ret);
directedLine *temp;
Int index = 0;
for(temp=this; temp != NULL; temp=temp->nextPolygon) {
index = temp->toArraySinglePolygon(ret, index);
}
return ret;
}
Real directedLine::polyArea()
{
directedLine* temp;
Real ret=0.0;
Real x1,y1,x2,y2;
x1 = this->head()[0];
y1 = this->head()[1];
x2 = this->next->head()[0];
y2 = this->next->head()[1];
ret = -(x2*y1-x1*y2);
for(temp=this->next; temp!=this; temp = temp->next)
{
x1 = temp->head()[0];
y1 = temp->head()[1];
x2 = temp->next->head()[0];
y2 = temp->next->head()[1];
ret += -( x2*y1-x1*y2);
}
return Real(0.5)*ret;
}
void directedLine::connectDiagonal(directedLine* v1, directedLine* v2,
directedLine** ret_p1,
directedLine** ret_p2,
sampledLine** generatedLine,
directedLine* polygonList )
{
sampledLine *nsline = new sampledLine(2);
nsline->setPoint(0, v1->head());
nsline->setPoint(1, v2->head());
directedLine* newLineInc = new directedLine(INCREASING, nsline);
directedLine* newLineDec = new directedLine(DECREASING, nsline);
directedLine* v1Prev = v1->prev;
directedLine* v2Prev = v2->prev;
v1 ->prev = newLineDec;
v2Prev ->next = newLineDec;
newLineDec->next = v1;
newLineDec->prev = v2Prev;
v2 ->prev = newLineInc;
v1Prev ->next = newLineInc;
newLineInc->next = v2;
newLineInc->prev = v1Prev;
*ret_p1 = newLineDec;
*ret_p2 = newLineInc;
*generatedLine = nsline;
}
void directedLine::connectDiagonal_2slines(directedLine* v1, directedLine* v2,
directedLine** ret_p1,
directedLine** ret_p2,
directedLine* polygonList )
{
sampledLine *nsline = new sampledLine(2);
sampledLine *nsline2 = new sampledLine(2);
nsline->setPoint(0, v1->head());
nsline->setPoint(1, v2->head());
nsline2->setPoint(0, v1->head());
nsline2->setPoint(1, v2->head());
directedLine* newLineInc = new directedLine(INCREASING, nsline);
directedLine* newLineDec = new directedLine(DECREASING, nsline2);
directedLine* v1Prev = v1->prev;
directedLine* v2Prev = v2->prev;
v1 ->prev = newLineDec;
v2Prev ->next = newLineDec;
newLineDec->next = v1;
newLineDec->prev = v2Prev;
v2 ->prev = newLineInc;
v1Prev ->next = newLineInc;
newLineInc->next = v2;
newLineInc->prev = v1Prev;
*ret_p1 = newLineDec;
*ret_p2 = newLineInc;
}
Int directedLine::samePolygon(directedLine* v1, directedLine* v2)
{
if(v1 == v2) return 1;
directedLine *temp;
for(temp = v1->next; temp != v1; temp = temp->next)
{
if(temp == v2) return 1;
}
return 0;
}
directedLine* directedLine::findRoot()
{
if(rootBit) return this;
directedLine* temp;
for(temp = next; temp != this; temp = temp->next)
if(temp -> rootBit ) return temp;
return NULL;
}
directedLine* directedLine::rootLinkFindRoot()
{
directedLine* tempRoot;
directedLine* tempLink;
tempRoot = this;
tempLink = rootLink;
while(tempLink != NULL){
tempRoot = tempLink;
tempLink = tempRoot->rootLink;
}
return tempRoot;
}
void directedLine::writeAllPolygons(char* filename)
{
FILE* fp = fopen(filename, "w");
assert(fp);
Int nPolygons = numPolygons();
directedLine *root;
fprintf(fp, "%i\n", nPolygons);
for(root = this; root != NULL; root = root->nextPolygon)
{
directedLine *temp;
Int npoints=0;
npoints = root->get_npoints()-1;
for(temp = root->next; temp != root; temp=temp->next)
npoints += temp->get_npoints()-1;
fprintf(fp, "%i\n", npoints);
for(Int i=0; i<root->get_npoints()-1; i++){
fprintf(fp, "%f ", root->getVertex(i)[0]);
fprintf(fp, "%f ", root->getVertex(i)[1]);
}
for(temp=root->next; temp != root; temp = temp->next)
{
for(Int i=0; i<temp->get_npoints()-1; i++){
fprintf(fp, "%f ", temp->getVertex(i)[0]);
fprintf(fp, "%f ", temp->getVertex(i)[1]);
}
fprintf(fp,"\n");
}
fprintf(fp, "\n");
}
fclose(fp);
}
directedLine* readAllPolygons(char* filename)
{
Int i,j;
FILE* fp = fopen(filename, "r");
assert(fp);
Int nPolygons;
fscanf(fp, "%i", &nPolygons);
directedLine *ret = NULL;
for(i=0; i<nPolygons; i++)
{
Int nEdges;
fscanf(fp, "%i", &nEdges);
Real vert[2][2];
Real VV[2][2];
fscanf(fp, "%f", &(vert[0][0]));
fscanf(fp, "%f", &(vert[0][1]));
fscanf(fp, "%f", &(vert[1][0]));
fscanf(fp, "%f", &(vert[1][1]));
VV[1][0] = vert[0][0];
VV[1][1] = vert[0][1];
sampledLine *sLine = new sampledLine(2, vert);
directedLine *thisPoly = new directedLine(INCREASING, sLine);
thisPoly->rootLinkSet(NULL);
directedLine *dLine;
for(j=2; j<nEdges; j++)
{
vert[0][0]=vert[1][0];
vert[0][1]=vert[1][1];
fscanf(fp, "%f", &(vert[1][0]));
fscanf(fp, "%f", &(vert[1][1]));
sLine = new sampledLine(2,vert);
dLine = new directedLine(INCREASING, sLine);
dLine->rootLinkSet(thisPoly);
thisPoly->insert(dLine);
}
VV[0][0]=vert[1][0];
VV[0][1]=vert[1][1];
sLine = new sampledLine(2,VV);
dLine = new directedLine(INCREASING, sLine);
dLine->rootLinkSet(thisPoly);
thisPoly->insert(dLine);
ret = thisPoly->insertPolygon(ret);
}
fclose(fp);
return ret;
}