#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include "zlassert.h"
#include "polyDBG.h"
#ifdef __WATCOMC__
#pragma warning 14 10
#pragma warning 391 10
#pragma warning 726 10
#endif
static Real area(Real A[2], Real B[2], Real C[2])
{
Real Bx, By, Cx, Cy;
Bx = B[0] - A[0];
By = B[1] - A[1];
Cx = C[0] - A[0];
Cy = C[1] - A[1];
return Bx*Cy - Cx*By;
}
Int DBG_isConvex(directedLine *poly)
{
directedLine* temp;
if(area(poly->head(), poly->tail(), poly->getNext()->tail()) < 0.00000)
return 0;
for(temp = poly->getNext(); temp != poly; temp = temp->getNext())
{
if(area(temp->head(), temp->tail(), temp->getNext()->tail()) < 0.00000)
return 0;
}
return 1;
}
Int DBG_is_U_monotone(directedLine* poly)
{
Int n_changes = 0;
Int prev_sign;
Int cur_sign;
directedLine* temp;
cur_sign = compV2InX(poly->tail(), poly->head());
n_changes = (compV2InX(poly->getPrev()->tail(), poly->getPrev()->head())
!= cur_sign);
for(temp = poly->getNext(); temp != poly; temp = temp->getNext())
{
prev_sign = cur_sign;
cur_sign = compV2InX(temp->tail(), temp->head());
if(cur_sign != prev_sign)
n_changes++;
}
if(n_changes ==2) return 1;
else return 0;
}
Int DBG_is_U_direction(directedLine* poly)
{
Int V_count = 0;
Int U_count = 0;
directedLine* temp;
if( fabs(poly->head()[0] - poly->tail()[0]) <= fabs(poly->head()[1]-poly->tail()[1]))
V_count += poly->get_npoints();
else
U_count += poly->get_npoints();
for(temp = poly->getNext(); temp != poly; temp = temp->getNext())
{
if( fabs(temp->head()[0] - temp->tail()[0]) <= fabs(temp->head()[1]-temp->tail()[1]))
V_count += temp->get_npoints();
else
U_count += temp->get_npoints();
}
if(U_count > V_count) return 1;
else return 0;
}
Int DBG_edgesIntersect(directedLine* l1, directedLine* l2)
{
if(l1->getNext() == l2)
{
if(area(l1->head(), l1->tail(), l2->tail()) == 0) {
if( (l1->tail()[0] - l1->head()[0])*(l2->tail()[0]-l2->head()[0]) +
(l1->tail()[1] - l1->head()[1])*(l2->tail()[1]-l2->head()[1]) >=0)
return 0; else
return 1;
}
}
else if(l1->getPrev() == l2)
{
if(area(l2->head(), l2->tail(), l1->tail()) == 0) {
if( (l2->tail()[0] - l2->head()[0])*(l1->tail()[0]-l1->head()[0]) +
(l2->tail()[1] - l2->head()[1])*(l1->tail()[1]-l1->head()[1]) >=0)
return 0; else
return 1;
}
}
else {
if((l1->head()[0] == l2->head()[0] &&
l1->head()[1] == l2->head()[1]) ||
(l1->tail()[0] == l2->tail()[0] &&
l1->tail()[1] == l2->tail()[1]))
return 1;
}
if(
(
area(l1->head(), l1->tail(), l2->head())
*
area(l1->head(), l1->tail(), l2->tail())
< 0
)
&&
(
area(l2->head(), l2->tail(), l1->head())
*area(l2->head(), l2->tail(), l1->tail())
< 0
)
)
return 1;
else
return 0;
}
Int DBG_edgesIntersectGen(Real A[2], Real B[2], Real C[2], Real D[2])
{
if(
(
area(A, B, C) * area(A,B,D) <0
)
&&
(
area(C,D,A) * area(C,D,B) < 0
)
)
return 1;
else
return 0;
}
Int DBG_intersectChain(vertexArray* chain, Int start, Int end, Real A[2], Real B[2])
{
Int i;
for(i=start; i<=end-2; i++)
if(DBG_edgesIntersectGen(chain->getVertex(i), chain->getVertex(i+1), A, B))
return 1;
return 0;
}
Int DBG_polygonSelfIntersect(directedLine* poly)
{
directedLine* temp1;
directedLine* temp2;
temp1=poly;
for(temp2=temp1->getNext(); temp2 != temp1; temp2=temp2->getNext())
{
if(DBG_edgesIntersect(temp1, temp2))
{
return 1;
}
}
for(temp1=poly->getNext(); temp1 != poly; temp1 = temp1->getNext())
for(temp2=temp1->getNext(); temp2 != temp1; temp2=temp2->getNext())
{
if(DBG_edgesIntersect(temp1, temp2))
{
return 1;
}
}
return 0;
}
Int DBG_edgeIntersectPoly(directedLine* edge, directedLine* poly)
{
directedLine* temp;
if(DBG_edgesIntersect(edge, poly))
return 1;
for(temp=poly->getNext(); temp != poly; temp=temp->getNext())
if(DBG_edgesIntersect(edge, temp))
return 1;
return 0;
}
Int DBG_polygonsIntersect(directedLine* p1, directedLine* p2)
{
directedLine* temp;
if(DBG_edgeIntersectPoly(p1, p2))
return 1;
for(temp=p1->getNext(); temp!= p1; temp = temp->getNext())
if(DBG_edgeIntersectPoly(temp, p2))
return 1;
return 0;
}
Int DBG_polygonListIntersect(directedLine* pList)
{
directedLine *temp;
for(temp=pList; temp != NULL; temp = temp->getNextPolygon())
if(DBG_polygonSelfIntersect(temp))
return 1;
directedLine* temp2;
for(temp=pList; temp!=NULL; temp=temp->getNextPolygon())
{
for(temp2=temp->getNextPolygon(); temp2 != NULL; temp2=temp2->getNextPolygon())
if(DBG_polygonsIntersect(temp, temp2))
return 1;
}
return 0;
}
Int DBG_isCounterclockwise(directedLine* poly)
{
return (poly->polyArea() > 0);
}
Int DBG_rayIntersectEdge(Real v0[2], Real dx, Real dy, Real v10[2], Real v1[2], Real v2[2])
{
Real denom = (v2[0]-v1[0])*(-dy) - (v2[1]-v1[1]) * (-dx);
Real nomRay = (v2[0]-v1[0]) * (v0[1] - v1[1]) - (v2[1]-v1[1])*(v0[0]-v1[0]);
Real nomEdge = (v0[0]-v1[0]) * (-dy) - (v0[1]-v1[1])*(-dx);
if(denom == 0.0)
return 0;
if(nomRay == 0.0)
return 0;
if(nomEdge == 0)
{
if(dx*(v1[0]-v0[0])>=0 && dy*(v1[1]-v0[1])>=0)
{
if(area(v0, v1, v10) * area(v0, v1, v2) >0)
return 0;
else
return 1;
}
else
return 0;
}
if(nomEdge == denom) {
return 0;
}
if(denom*nomRay>0 && denom*nomEdge>0 && nomEdge/denom <=1.0)
return 1;
return 0;
}
Int DBG_rayIntersectPoly(Real v0[2], Real dx, Real dy, directedLine* poly)
{
directedLine* temp;
Int count=0;
if(DBG_rayIntersectEdge(v0, dx, dy, poly->getPrev()->head(), poly->head(), poly->tail()))
count++;
for(temp=poly->getNext(); temp != poly; temp = temp->getNext())
if(DBG_rayIntersectEdge(v0, dx, dy, temp->getPrev()->head(), temp->head(), temp->tail()))
count++;
return count;
}
Int DBG_pointInsidePoly(Real v[2], directedLine* poly)
{
assert( (DBG_rayIntersectPoly(v,1,0,poly) % 2 )
== (DBG_rayIntersectPoly(v,1,Real(0.1234), poly) % 2 )
);
if(DBG_rayIntersectPoly(v, 1, 0, poly) % 2 == 1)
return 1;
else
return 0;
}
Int DBG_enclosingPolygons(directedLine* poly, directedLine* list)
{
directedLine* temp;
Int count=0;
for(temp = list; temp != NULL; temp = temp->getNextPolygon())
{
if(poly != temp)
if(DBG_pointInsidePoly(poly->head(), temp))
count++;
}
return count;
}
void DBG_reverse(directedLine* poly)
{
if(poly->getDirection() == INCREASING)
poly->putDirection(DECREASING);
else
poly->putDirection(INCREASING);
directedLine* oldNext = poly->getNext();
poly->putNext(poly->getPrev());
poly->putPrev(oldNext);
directedLine* temp;
for(temp=oldNext; temp!=poly; temp = oldNext)
{
if(temp->getDirection() == INCREASING)
temp->putDirection(DECREASING);
else
temp->putDirection(INCREASING);
oldNext = temp->getNext();
temp->putNext(temp->getPrev());
temp->putPrev(oldNext);
}
printf("reverse done\n");
}
Int DBG_checkConnectivity(directedLine *polygon)
{
if(polygon == NULL) return 1;
directedLine* temp;
if(polygon->head()[0] != polygon->getPrev()->tail()[0] ||
polygon->head()[1] != polygon->getPrev()->tail()[1])
return 0;
for(temp=polygon->getNext(); temp != polygon; temp=temp->getNext())
{
if(temp->head()[0] != temp->getPrev()->tail()[0] ||
temp->head()[1] != temp->getPrev()->tail()[1])
return 0;
}
return 1;
}
Int DBG_check(directedLine *polyList)
{
directedLine* temp;
if(polyList == NULL) return 0;
if(DBG_polygonListIntersect(polyList))
{
fprintf(stderr, "DBG_check: there are self intersections, don't know to modify the polygons\n");
return 1;
}
for(temp = polyList; temp!= NULL; temp = temp ->getNextPolygon())
{
if(! DBG_checkConnectivity(temp))
{
fprintf(stderr, "DBG_check, polygon not connected\n");
return 1;
}
}
for(temp = polyList; temp!= NULL; temp = temp ->getNextPolygon())
{
Int correctDir;
if( DBG_enclosingPolygons(temp, polyList) % 2 == 0)
correctDir = 1;
else
correctDir = 0;
Int actualDir = DBG_isCounterclockwise(temp);
if(correctDir != actualDir)
{
fprintf(stderr, "DBG_check: polygon with incorrect orientations. reversed\n");
DBG_reverse(temp);
}
}
return 0;
}
static directedLine* DBG_edgeIntersectChainD(directedLine *e,
directedLine *begin, directedLine *end)
{
directedLine *temp;
for(temp=begin; temp != end; temp = temp->getNext())
{
if(DBG_edgesIntersect(e, temp))
return temp;
}
if(DBG_edgesIntersect(e, end))
return end;
return NULL;
}
directedLine* DBG_cutIntersectionPoly(directedLine *polygon, int& cutOccur)
{
directedLine *begin, *end, *next;
begin = polygon;
end = polygon;
cutOccur = 0;
while( (next = end->getNext()) != begin)
{
directedLine *interc = NULL;
if( (interc = DBG_edgeIntersectChainD(next, begin, end)))
{
int fixed = 0;
if(DBG_edgesIntersect(next, interc->getNext()))
{
Real buf[2];
int i;
Int n=5;
buf[0] = interc->tail()[0];
buf[1] = interc->tail()[1];
for(i=1; i<n; i++)
{
Real r = ((Real)i) / ((Real) n);
Real u = (1-r) * interc->head()[0] + r * interc->tail()[0];
Real v = (1-r) * interc->head()[1] + r * interc->tail()[1];
interc->tail()[0] = interc->getNext()->head()[0] = u;
interc->tail()[1] = interc->getNext()->head()[1] = v;
if( (! DBG_edgesIntersect(next, interc)) &&
(! DBG_edgesIntersect(next, interc->getNext())))
break; }
if(i==n) {
fixed = 0;
interc->tail()[0] = interc->getNext()->head()[0] = buf[0];
interc->tail()[1] = interc->getNext()->head()[1] = buf[1];
}
else
{
fixed = 1;
}
}
if(fixed == 0)
{
cutOccur = 1;
begin->deleteSingleLine(next);
if(begin != end)
{
if(DBG_polygonSelfIntersect(begin))
{
directedLine* newEnd = end->getPrev();
begin->deleteSingleLine(end);
end = newEnd;
}
}
}
else
{
end = end->getNext();
}
}
else
{
end = end->getNext();
}
}
return begin;
}
#if 0 // UNUSED
static directedLine* DBG_cutIntersectionPoly_notwork(directedLine *polygon)
{
directedLine *crt; directedLine *begin;
directedLine *end;
directedLine *temp;
crt = polygon;
int find=0;
while(1)
{
if(crt->getPrev()->getPrev() == crt)
return NULL;
if(DBG_edgesIntersect(crt, crt->getNext()) ||
(crt->head()[0] == crt->getNext()->tail()[0] &&
crt->head()[1] == crt->getNext()->tail()[1])
)
{
find = 1;
crt=crt->deleteChain(crt, crt->getNext());
}
else
{
begin = crt;
end = crt->getNext();
for(temp=end->getNext(); temp!=begin; temp= temp->getNext())
{
directedLine *intersect = DBG_edgeIntersectChainD(temp, begin, end);
if(intersect != NULL)
{
crt = crt->deleteChain(intersect, temp);
find=1;
break; }
else
{
end = temp;
}
}
}
if(find == 0)
return crt;
else
find = 0; }
}
#endif
directedLine* DBG_cutIntersectionAllPoly(directedLine* list)
{
directedLine* temp;
directedLine* tempNext=NULL;
directedLine* ret = NULL;
int cutOccur=0;
for(temp=list; temp != NULL; temp = tempNext)
{
directedLine *left;
tempNext = temp->getNextPolygon();
left = DBG_cutIntersectionPoly(temp, cutOccur);
if(left != NULL)
ret=left->insertPolygon(ret);
}
return ret;
}
sampledLine* DBG_collectSampledLinesAllPoly(directedLine *polygonList)
{
directedLine *temp;
sampledLine* tempHead = NULL;
sampledLine* tempTail = NULL;
sampledLine* cHead = NULL;
sampledLine* cTail = NULL;
if(polygonList == NULL)
return NULL;
DBG_collectSampledLinesPoly(polygonList, cHead, cTail);
assert(cHead);
assert(cTail);
for(temp = polygonList->getNextPolygon(); temp != NULL; temp = temp->getNextPolygon())
{
DBG_collectSampledLinesPoly(temp, tempHead, tempTail);
cTail->insert(tempHead);
cTail = tempTail;
}
return cHead;
}
void DBG_collectSampledLinesPoly(directedLine *polygon, sampledLine*& retHead, sampledLine*& retTail)
{
directedLine *temp;
retHead = NULL;
retTail = NULL;
if(polygon == NULL)
return;
retHead = retTail = polygon->getSampledLine();
for(temp = polygon->getNext(); temp != polygon; temp=temp->getNext())
{
retHead = temp->getSampledLine()->insert(retHead);
}
}