#include "gluos.h"
#include <stdlib.h>
#include <stdio.h>
#include <GL/gl.h>
#include "glimports.h"
#include "zlassert.h"
#include "monoChain.h"
#include "quicksort.h"
#include "searchTree.h"
#include "polyUtil.h"
#ifndef max
#define max(a,b) ((a>b)? a:b)
#endif
#ifndef min
#define min(a,b) ((a>b)? b:a)
#endif
extern Int isCusp(directedLine *v);
extern Int deleteRepeatDiagonals(Int num_diagonals, directedLine** diagonal_vertices, directedLine** new_vertices);
#if 0 // UNUSED
static void drawDiagonals(Int num_diagonals, directedLine** diagonal_vertices)
{
Int i;
for(i=0; i<num_diagonals; i++)
{
glBegin(GL_LINE);
glVertex2fv(diagonal_vertices[2*i]->head());
glVertex2fv(diagonal_vertices[2*i+1]->head());
glEnd();
}
}
#endif
inline Real intersectHoriz(Real x1, Real y1, Real x2, Real y2, Real y)
{
return ((y2==y1)? (x1+x2)*0.5 : x1 + ((y-y1)/(y2-y1)) * (x2-x1));
}
static int compChainHeadInY(monoChain* mc1, monoChain* mc2)
{
return compV2InY(mc1->getHead()->head(), mc2->getHead()->head());
}
monoChain::monoChain(directedLine* cHead, directedLine* cTail)
{
chainHead = cHead;
chainTail = cTail;
next = this;
prev = this;
nextPolygon = NULL;
directedLine* temp;
minX = maxX = chainTail->head()[0];
minY = maxY = chainTail->head()[1];
for(temp=chainHead; temp!=cTail; temp = temp->getNext())
{
if(temp->head()[0] < minX)
minX = temp->head()[0];
if(temp->head()[0] > maxX)
maxX = temp->head()[0];
if(temp->head()[1] < minY)
minY = temp->head()[1];
if(temp->head()[1] > maxY)
maxY = temp->head()[1];
}
if(chainHead->compInY(chainTail) <0)
isIncrease = 1;
else
isIncrease = 0;
if(isIncrease)
current = chainHead;
else
current = chainTail;
isKey = 0;
}
void monoChain::insert(monoChain* nc)
{
nc->next = this;
nc->prev = prev;
prev->next = nc;
prev = nc;
}
void monoChain::deleteLoop()
{
monoChain *temp, *tempNext;
prev->next = NULL;
for(temp=this; temp != NULL; temp = tempNext)
{
tempNext = temp->next;
delete temp;
}
}
void monoChain::deleteLoopList()
{
monoChain *temp, *tempNext;
for(temp=this; temp != NULL; temp = tempNext)
{
tempNext = temp->nextPolygon;
temp->deleteLoop();
}
}
Int monoChain::toArraySingleLoop(monoChain** array, Int index)
{
monoChain *temp;
array[index++] = this;
for(temp = next; temp != this; temp = temp->next)
{
array[index++] = temp;
}
return index;
}
monoChain** monoChain::toArrayAllLoops(Int& num_chains)
{
num_chains = numChainsAllLoops();
monoChain **ret = (monoChain**) malloc(sizeof(monoChain*) * num_chains);
assert(ret);
monoChain *temp;
Int index = 0;
for(temp = this; temp != NULL; temp=temp->nextPolygon){
index = temp->toArraySingleLoop(ret, index);
}
return ret;
}
Int monoChain::numChainsSingleLoop()
{
Int ret=0;
monoChain* temp;
if(next == this) return 1;
ret = 1;
for(temp=next; temp != this; temp = temp->next)
ret++;
return ret;
}
Int monoChain::numChainsAllLoops()
{
Int ret=0;
monoChain *temp;
for(temp =this; temp != NULL; temp = temp->nextPolygon)
ret += temp->numChainsSingleLoop();
return ret;
}
Real monoChain::chainIntersectHoriz(Real y)
{
directedLine* temp;
if(isIncrease)
{
for(temp= current; temp != chainTail; temp = temp->getNext())
{
if(temp->head()[1] > y)
break;
}
current = temp->getPrev();
}
else
{
for(temp = current; temp != chainHead; temp = temp->getPrev())
{
if(temp->head()[1] > y)
break;
}
current = temp->getNext();
}
return intersectHoriz(current->head()[0], current->head()[1], current->tail()[0], current->tail()[1], y);
}
monoChain* directedLineLoopToMonoChainLoop(directedLine* loop)
{
directedLine *temp;
monoChain *ret=NULL;
directedLine *prevCusp=NULL;
directedLine *firstCusp;
if(isCusp(loop))
prevCusp = loop;
else
{
for(temp = loop->getNext(); temp != loop; temp = temp->getNext())
if(isCusp(temp))
break;
prevCusp = temp;
}
firstCusp = prevCusp;
for(temp = prevCusp->getNext(); temp != loop; temp = temp->getNext())
{
if(isCusp(temp))
{
if(ret == NULL)
{
ret = new monoChain(prevCusp, temp);
}
else
ret->insert(new monoChain(prevCusp, temp));
prevCusp = temp;
}
}
ret->insert(new monoChain(prevCusp, firstCusp));
return ret;
}
monoChain* directedLineLoopListToMonoChainLoopList(directedLine* list)
{
directedLine* temp;
monoChain* mc;
monoChain* mcEnd;
mc = directedLineLoopToMonoChainLoop(list);
mcEnd = mc;
for(temp = list->getNextPolygon(); temp != NULL; temp = temp->getNextPolygon())
{
monoChain *newLoop = directedLineLoopToMonoChainLoop(temp);
mcEnd->setNextPolygon(newLoop);
mcEnd = newLoop;
}
return mc;
}
static Int compEdges(directedLine *e1, directedLine *e2)
{
Real* head1 = e1->head();
Real* tail1 = e1->tail();
Real* head2 = e2->head();
Real* tail2 = e2->tail();
Real e1_Ymax, e1_Ymin, e2_Ymax, e2_Ymin;
if(head1[1]>tail1[1]) {
e1_Ymax= head1[1];
e1_Ymin= tail1[1];
}
else{
e1_Ymax = tail1[1];
e1_Ymin = head1[1];
}
if(head2[1]>tail2[1]) {
e2_Ymax= head2[1];
e2_Ymin= tail2[1];
}
else{
e2_Ymax = tail2[1];
e2_Ymin = head2[1];
}
Real Ymax = min(e1_Ymax, e2_Ymax);
Real Ymin = max(e1_Ymin, e2_Ymin);
Real y = 0.5*(Ymax + Ymin);
Real x1 = intersectHoriz(head1[0], head1[1], tail1[0], tail1[1], y);
Real x2 = intersectHoriz(head2[0], head2[1], tail2[0], tail2[1], y);
if(x1<= x2) return -1;
else return 1;
}
Int compChains(monoChain* mc1, monoChain* mc2)
{
Real y;
assert(mc1->isKey || mc2->isKey);
if(mc1->isKey)
y = mc1->keyY;
else
y = mc2->keyY;
directedLine *d1 = mc1->find(y);
directedLine *d2 = mc2->find(y);
mc2->find(y);
return compEdges(d1, d2);
}
directedLine* monoChain::find(Real y)
{
directedLine *ret;
directedLine *temp;
assert(current->head()[1] <= y);
if(isIncrease)
{
assert(chainTail->head()[1] >=y);
for(temp=current; temp!=chainTail; temp = temp->getNext())
{
if(temp->head()[1] > y)
break;
}
current = temp->getPrev();
ret = current;
}
else
{
for(temp=current; temp != chainHead; temp = temp->getPrev())
{
if(temp->head()[1] > y)
break;
}
current = temp->getNext();
ret = temp;
}
return ret;
}
void monoChain::printOneChain()
{
directedLine* temp;
for(temp = chainHead; temp != chainTail; temp = temp->getNext())
{
printf("(%f,%f) ", temp->head()[0], temp->head()[1]);
}
printf("(%f,%f) \n", chainTail->head()[0], chainTail->head()[1]);
}
void monoChain::printChainLoop()
{
monoChain* temp;
this->printOneChain();
for(temp = next; temp != this; temp = temp->next)
{
temp->printOneChain();
}
printf("\n");
}
void monoChain::printAllLoops()
{
monoChain* temp;
for(temp=this; temp != NULL; temp = temp->nextPolygon)
temp->printChainLoop();
}
Int MC_sweepY(Int nVertices, monoChain** sortedVertices, sweepRange** ret_ranges)
{
Int i;
Real keyY;
Int errOccur=0;
treeNode* searchTree = NULL;
for(i=0; i<nVertices; i++)
{
monoChain* vert = sortedVertices[i];
keyY = vert->getHead()->head()[1]; directedLine *dline = vert->getHead();
directedLine *dlinePrev = dline->getPrev();
if(isBelow(dline, dline) && isBelow(dline, dlinePrev))
{
vert->isKey = 1;
vert->keyY = keyY;
treeNode* thisNode = TreeNodeFind(searchTree, vert, (Int (*) (void *, void *))compChains);
vert->isKey = 0;
vert->getPrev()->isKey = 1;
vert->getPrev()->keyY = keyY;
treeNode* prevNode = TreeNodeFind(searchTree, vert->getPrev(), (Int (*) (void *, void *))compChains);
vert->getPrev()->isKey = 0;
if(cuspType(dline) == 1) {
treeNode* leftEdge = TreeNodePredecessor(prevNode);
treeNode* rightEdge = TreeNodeSuccessor(thisNode);
if(leftEdge == NULL || rightEdge == NULL)
{
errOccur = 1;
goto JUMP_HERE;
}
directedLine* leftEdgeDline = ((monoChain* ) leftEdge->key)->find(keyY);
directedLine* rightEdgeDline = ((monoChain* ) rightEdge->key)->find(keyY);
ret_ranges[i] = sweepRangeMake(leftEdgeDline, 1, rightEdgeDline, 1);
}
else
{
ret_ranges[i] = sweepRangeMake( dline, 1, dlinePrev, 1);
}
searchTree = TreeNodeDeleteSingleNode(searchTree, thisNode);
searchTree = TreeNodeDeleteSingleNode(searchTree, prevNode);
}
else if(isAbove(dline, dline) && isAbove(dline, dlinePrev))
{
treeNode* thisNode = TreeNodeMake(vert);
treeNode* prevNode = TreeNodeMake(vert->getPrev());
vert->isKey = 1;
vert->keyY = keyY;
searchTree = TreeNodeInsert(searchTree, thisNode, (Int (*) (void *, void *))compChains);
vert->isKey = 0;
vert->getPrev()->isKey = 1;
vert->getPrev()->keyY = keyY;
searchTree = TreeNodeInsert(searchTree, prevNode, (Int (*) (void *, void *))compChains);
vert->getPrev()->isKey = 0;
if(cuspType(dline) == 1) {
treeNode* leftEdge = TreeNodePredecessor(thisNode);
treeNode* rightEdge = TreeNodeSuccessor(prevNode);
if(leftEdge == NULL || rightEdge == NULL)
{
errOccur = 1;
goto JUMP_HERE;
}
directedLine* leftEdgeDline = ((monoChain*) leftEdge->key)->find(keyY);
directedLine* rightEdgeDline = ((monoChain*) rightEdge->key)->find(keyY);
ret_ranges[i] = sweepRangeMake( leftEdgeDline, 1, rightEdgeDline, 1);
}
else {
ret_ranges[i] = sweepRangeMake(dlinePrev, 1, dline, 1);
}
}
else
{
errOccur = 1;
goto JUMP_HERE;
fprintf(stderr, "error in MC_sweepY\n");
exit(1);
}
}
JUMP_HERE:
TreeNodeDeleteWholeTree(searchTree);
return errOccur;
}
void MC_findDiagonals(Int total_num_edges, monoChain** sortedVertices,
sweepRange** ranges, Int& num_diagonals,
directedLine** diagonal_vertices)
{
Int i,j,k;
k=0;
for(i=0; i<total_num_edges; i++)
sortedVertices[i]->resetCurrent();
for(i=0; i<total_num_edges; i++)
{
directedLine* vert = sortedVertices[i]->getHead();
directedLine* thisEdge = vert;
directedLine* prevEdge = vert->getPrev();
if(isBelow(vert, thisEdge) && isBelow(vert, prevEdge) && compEdges(prevEdge, thisEdge)<0)
{
diagonal_vertices[k++] = vert;
directedLine* leftEdge = ranges[i]->left;
directedLine* rightEdge = ranges[i]->right;
directedLine* leftVert = leftEdge;
directedLine* rightVert = rightEdge->getNext();
assert(leftVert->head()[1] >= vert->head()[1]);
assert(rightVert->head()[1] >= vert->head()[1]);
directedLine* minVert = (leftVert->head()[1] <= rightVert->head()[1])?leftVert:rightVert;
Int found = 0;
for(j=i+1; j<total_num_edges; j++)
{
if(sortedVertices[j]->getHead()->head()[1] > minVert->head()[1])
break;
if(sweepRangeEqual(ranges[i], ranges[j]))
{
found = 1;
break;
}
}
if(found)
diagonal_vertices[k++] = sortedVertices[j]->getHead();
else
diagonal_vertices[k++] = minVert;
}
else if(isAbove(vert, thisEdge) && isAbove(vert, prevEdge) && compEdges(prevEdge, thisEdge)>0)
{
diagonal_vertices[k++] = vert;
directedLine* leftEdge = ranges[i]->left;
directedLine* rightEdge = ranges[i]->right;
directedLine* leftVert = leftEdge->getNext();
directedLine* rightVert = rightEdge;
assert(leftVert->head()[1] <= vert->head()[1]);
assert(rightVert->head()[1] <= vert->head()[1]);
directedLine* maxVert = (leftVert->head()[1] > rightVert->head()[1])? leftVert:rightVert;
Int found=0;
for(j=i-1; j>=0; j--)
{
if(sortedVertices[j]->getHead()->head()[1] < maxVert->head()[1])
break;
if(sweepRangeEqual(ranges[i], ranges[j]))
{
found = 1;
break;
}
}
if(found)
diagonal_vertices[k++] = sortedVertices[j]->getHead();
else
diagonal_vertices[k++] = maxVert;
}
}
num_diagonals = k/2;
}
directedLine* MC_partitionY(directedLine *polygons, sampledLine **retSampledLines)
{
Int total_num_chains = 0;
monoChain* loopList = directedLineLoopListToMonoChainLoopList(polygons);
monoChain** array = loopList->toArrayAllLoops(total_num_chains);
if(total_num_chains<=2) {
loopList->deleteLoopList();
free(array);
*retSampledLines = NULL;
return polygons;
}
quicksort( (void**)array, 0, total_num_chains-1, (Int (*)(void*, void*))compChainHeadInY);
sweepRange** ranges = (sweepRange**)malloc(sizeof(sweepRange*) * (total_num_chains));
assert(ranges);
if(MC_sweepY(total_num_chains, array, ranges))
{
loopList->deleteLoopList();
free(array);
*retSampledLines = NULL;
return NULL;
}
Int num_diagonals;
directedLine** diagonal_vertices = (directedLine**) malloc(sizeof(directedLine*) * total_num_chains*2);
assert(diagonal_vertices);
MC_findDiagonals(total_num_chains, array, ranges, num_diagonals, diagonal_vertices);
directedLine* ret_polygons = polygons;
sampledLine* newSampledLines = NULL;
Int i,k;
num_diagonals=deleteRepeatDiagonals(num_diagonals, diagonal_vertices, diagonal_vertices);
Int *removedDiagonals=(Int*)malloc(sizeof(Int) * num_diagonals);
for(i=0; i<num_diagonals; i++)
removedDiagonals[i] = 0;
for(i=0,k=0; i<num_diagonals; i++,k+=2)
{
directedLine* v1=diagonal_vertices[k];
directedLine* v2=diagonal_vertices[k+1];
directedLine* ret_p1;
directedLine* ret_p2;
directedLine* root1 = v1->rootLinkFindRoot();
directedLine* root2 = v2->rootLinkFindRoot();
if(root1 != root2)
{
removedDiagonals[i] = 1;
sampledLine* generatedLine;
v1->connectDiagonal(v1,v2, &ret_p1, &ret_p2, &generatedLine, ret_polygons);
newSampledLines = generatedLine->insert(newSampledLines);
ret_polygons = ret_polygons->cutoffPolygon(root2);
root2->rootLinkSet(root1);
ret_p1->rootLinkSet(root1);
ret_p2->rootLinkSet(root1);
Int ii, kk;
for(ii=0, kk=0; ii<num_diagonals; ii++, kk+=2)
if( removedDiagonals[ii]==0)
{
directedLine* d1=diagonal_vertices[kk];
directedLine* d2=diagonal_vertices[kk+1];
if(d1 == v1) {
if(! pointLeft2Lines(v1->getPrev()->head(),
v1->head(), v1->tail(), d2->head()))
{
diagonal_vertices[kk] = v2->getPrev();
}
}
if(d1 == v2) {
if(! pointLeft2Lines(v2->getPrev()->head(),
v2->head(), v2->tail(), d2->head()))
{
diagonal_vertices[kk] = v1->getPrev();
}
}
if(d2 == v1) {
if(! pointLeft2Lines(v1->getPrev()->head(),
v1->head(), v1->tail(), d1->head()))
{
diagonal_vertices[kk+1] = v2->getPrev();
}
}
if(d2 == v2) {
if(! pointLeft2Lines(v2->getPrev()->head(),
v2->head(), v2->tail(), d1->head()))
{
diagonal_vertices[kk+1] = v1->getPrev();
}
}
}
}
}
for(i=0,k=0; i<num_diagonals; i++, k += 2)
if(removedDiagonals[i] == 0)
{
directedLine* v1=diagonal_vertices[k];
directedLine* v2=diagonal_vertices[k+1];
directedLine* ret_p1;
directedLine* ret_p2;
directedLine *root1 = v1->findRoot();
sampledLine* generatedLine;
v1->connectDiagonal(v1,v2, &ret_p1, &ret_p2, &generatedLine, ret_polygons);
newSampledLines = generatedLine->insert(newSampledLines);
ret_polygons = ret_polygons->cutoffPolygon(root1);
ret_polygons = ret_p1->insertPolygon(ret_polygons);
ret_polygons = ret_p2->insertPolygon(ret_polygons);
for(Int j=i+1; j<num_diagonals; j++)
{
if(removedDiagonals[j] ==0)
{
directedLine* temp1=diagonal_vertices[2*j];
directedLine* temp2=diagonal_vertices[2*j+1];
if(temp1==v1 || temp1==v2 || temp2==v1 || temp2==v2)
if(! temp1->samePolygon(temp1, temp2))
{
assert(temp1==v1 || temp1 == v2 || temp2==v1 || temp2 ==v2);
if(temp1==v1)
{
diagonal_vertices[2*j] = v2->getPrev();
}
if(temp2==v1)
{
diagonal_vertices[2*j+1] = v2->getPrev();
}
if(temp1==v2)
{
diagonal_vertices[2*j] = v1->getPrev();
}
if(temp2==v2)
{
diagonal_vertices[2*j+1] = v1->getPrev();
}
}
}
}
}
loopList->deleteLoopList();
free(array);
free(ranges);
free(diagonal_vertices);
free(removedDiagonals);
*retSampledLines = newSampledLines;
return ret_polygons;
}