polyDBG.cc File Reference

#include <math.h>
#include "polyDBG.h"

Include dependency graph for polyDBG.cc:

Go to the source code of this file.

Functions
static Real	area (Real A[2], Real B[2], Real C[2])
Int	DBG_isConvex (directedLine *poly)
Int	DBG_is_U_monotone (directedLine *poly)
Int	DBG_is_U_direction (directedLine *poly)
Int	DBG_edgesIntersect (directedLine *l1, directedLine *l2)
Int	DBG_edgesIntersectGen (Real A[2], Real B[2], Real C[2], Real D[2])
Int	DBG_intersectChain (vertexArray *chain, Int start, Int end, Real A[2], Real B[2])
Int	DBG_polygonSelfIntersect (directedLine *poly)
Int	DBG_edgeIntersectPoly (directedLine *edge, directedLine *poly)
Int	DBG_polygonsIntersect (directedLine *p1, directedLine *p2)
Int	DBG_polygonListIntersect (directedLine *pList)
Int	DBG_isCounterclockwise (directedLine *poly)
Int	DBG_rayIntersectEdge (Real v0[2], Real dx, Real dy, Real v10[2], Real v1[2], Real v2[2])
Int	DBG_rayIntersectPoly (Real v0[2], Real dx, Real dy, directedLine *poly)
Int	DBG_pointInsidePoly (Real v[2], directedLine *poly)
Int	DBG_enclosingPolygons (directedLine *poly, directedLine *list)
void	DBG_reverse (directedLine *poly)
Int	DBG_checkConnectivity (directedLine *polygon)
Int	DBG_check (directedLine *polyList)
static directedLine *	DBG_edgeIntersectChainD (directedLine *e, directedLine *begin, directedLine *end)
directedLine *	DBG_cutIntersectionPoly (directedLine *polygon, int &cutOccur)
directedLine *	DBG_cutIntersectionAllPoly (directedLine *list)
sampledLine *	DBG_collectSampledLinesAllPoly (directedLine *polygonList)
void	DBG_collectSampledLinesPoly (directedLine *polygon, sampledLine *&retHead, sampledLine *&retTail)

Function Documentation

static Real area ( Real  A[2], Real  B[2], Real  C[2]  )

static

Definition at line 50 of file polyDBG.cc.

Referenced by DBG_edgesIntersect(), DBG_edgesIntersectGen(), DBG_isConvex(), and DBG_rayIntersectEdge().

{
  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_check

(

directedLine *

polyList

)

Definition at line 482 of file polyDBG.cc.

{
  directedLine* temp;
  if(polyList == NULL) return 0;

  /*if there are intersections, print out error message
   */
  if(DBG_polygonListIntersect(polyList))
    {
      fprintf(stderr, "DBG_check: there are self intersections, don't know to modify the polygons\n");
    return 1;
    }

  /*check the connectivity of each polygon*/
  for(temp = polyList; temp!= NULL; temp = temp ->getNextPolygon())
    {
      if(! DBG_checkConnectivity(temp))
    {
      fprintf(stderr, "DBG_check, polygon not connected\n");
      return 1;
    }
    }

  /*check the orientation of each polygon*/
  for(temp = polyList; temp!= NULL; temp = temp ->getNextPolygon())
    {


      Int correctDir;

      if( DBG_enclosingPolygons(temp, polyList) % 2 == 0)
    correctDir = 1; /*counterclockwise*/
      else
    correctDir = 0; /*clockwise*/

      Int actualDir = DBG_isCounterclockwise(temp);

      if(correctDir != actualDir)
    {
      fprintf(stderr, "DBG_check: polygon with incorrect orientations. reversed\n");

      DBG_reverse(temp);
    }

    }
  return 0;
}

Int DBG_checkConnectivity

(

directedLine *

polygon

)

Definition at line 461 of file polyDBG.cc.

Referenced by DBG_check().

{
  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;
}

sampledLine* DBG_collectSampledLinesAllPoly

(

directedLine *

polygonList

)

Definition at line 697 of file polyDBG.cc.

{
  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
	)

Definition at line 721 of file polyDBG.cc.

Referenced by DBG_collectSampledLinesAllPoly().

{
  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);
    }
}

directedLine* DBG_cutIntersectionAllPoly

(

directedLine *

list

)

Definition at line 679 of file polyDBG.cc.

{
  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;
}

directedLine* DBG_cutIntersectionPoly	(	directedLine *	polygon,
		int &	cutOccur
	)

Definition at line 549 of file polyDBG.cc.

Referenced by directedLine::cutIntersectionAllPoly(), and DBG_cutIntersectionAllPoly().

{
  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()))
         {
           //trying to fix it
           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; //we fixed it
         }
           if(i==n) // we didn't fix it
         {
           fixed = 0;
           //back to original
           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;
}

static directedLine* DBG_edgeIntersectChainD ( directedLine *  e, directedLine *  begin, directedLine *  end  )

static

Definition at line 532 of file polyDBG.cc.

Referenced by DBG_cutIntersectionPoly().

{
  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;
}

Int DBG_edgeIntersectPoly	(	directedLine *	edge,
		directedLine *	poly
	)

Definition at line 257 of file polyDBG.cc.

Referenced by DBG_polygonsIntersect().

{
  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_edgesIntersect	(	directedLine *	l1,
		directedLine *	l2
	)

Definition at line 138 of file polyDBG.cc.

Referenced by DBG_cutIntersectionPoly(), DBG_edgeIntersectChainD(), DBG_edgeIntersectPoly(), and DBG_polygonSelfIntersect().

{
  if(l1->getNext() == l2)
    {
      if(area(l1->head(), l1->tail(), l2->tail()) == 0) //colinear
    {
      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; //not intersect
      else
        return 1;
    }
      //else we use the normal code
    }
  else if(l1->getPrev() == l2)
    {
      if(area(l2->head(), l2->tail(), l1->tail()) == 0) //colinear
    {
      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; //not intersect
      else
        return 1;
    }
      //else we use the normal code
    }
  else //the two edges are not connected
    {
      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]
	)

Definition at line 198 of file polyDBG.cc.

Referenced by DBG_intersectChain().

{
  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_enclosingPolygons	(	directedLine *	poly,
		directedLine *	list
	)

Definition at line 412 of file polyDBG.cc.

Referenced by DBG_check().

{
  directedLine* temp;
  Int count=0;
/*
printf("%i\n", DBG_pointInsidePoly(poly->head(),
                   list->getNextPolygon()
                   ->getNextPolygon()
                   ->getNextPolygon()
                   ->getNextPolygon()
));
*/

  for(temp = list; temp != NULL; temp = temp->getNextPolygon())
    {
      if(poly != temp)
    if(DBG_pointInsidePoly(poly->head(), temp))
      count++;
/*  printf("count=%i\n", count);*/
    }
  return count;
}

Int DBG_intersectChain	(	vertexArray *	chain,
		Int	start,
		Int	end,
		Real	A[2],
		Real	B[2]
	)

Definition at line 216 of file polyDBG.cc.

Referenced by findDownCorners(), and findUpCorners().

{
  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_is_U_direction

(

directedLine *

poly

)

Definition at line 98 of file polyDBG.cc.

Referenced by sampleMonoPoly(), and triangulateConvexPoly().

{
/*
  if(! DBG_is_U_monotone(poly))
    return 0;
*/
  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();
  /*
  else if(poly->head()[1] == poly->tail()[1])
    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(temp->head()[0] == temp->tail()[0])
    V_count += temp->get_npoints();
      else if(temp->head()[1] == temp->tail()[1])
    U_count += temp->get_npoints();
    */
    }

  if(U_count > V_count) return 1;
  else return 0;
}

Int DBG_is_U_monotone

(

directedLine *

poly

)

Definition at line 73 of file polyDBG.cc.

{
  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_isConvex

(

directedLine *

poly

)

Definition at line 60 of file polyDBG.cc.

Referenced by sampleMonoPoly().

{
  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_isCounterclockwise

(

directedLine *

poly

)

Definition at line 302 of file polyDBG.cc.

Referenced by DBG_check().

{
  return (poly->polyArea() > 0);
}

Int DBG_pointInsidePoly	(	Real	v[2],
		directedLine *	poly
	)

Definition at line 392 of file polyDBG.cc.

Referenced by DBG_enclosingPolygons().

{
/*
printf("enter pointInsidePoly , v=(%f,%f)\n", v[0], v[1]);
printf("the polygon is\n");
poly->printList();
*/
  /*for debug purpose*/
  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_polygonListIntersect

(

directedLine *

pList

)

Definition at line 284 of file polyDBG.cc.

Referenced by DBG_check().

{
  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_polygonSelfIntersect

(

directedLine *

poly

)

Definition at line 230 of file polyDBG.cc.

Referenced by DBG_cutIntersectionPoly(), and DBG_polygonListIntersect().

{
  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_polygonsIntersect	(	directedLine *	p1,
		directedLine *	p2
	)

Definition at line 270 of file polyDBG.cc.

Referenced by DBG_polygonListIntersect().

{
  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_rayIntersectEdge	(	Real	v0[2],
		Real	dx,
		Real	dy,
		Real	v10[2],
		Real	v1[2],
		Real	v2[2]
	)

Definition at line 321 of file polyDBG.cc.

Referenced by DBG_rayIntersectPoly().

{
/*
if( (v1[1] >= v0[1] && v2[1]<= v0[1] )
  ||(v2[1] >= v0[1] && v1[1]<= v0[1] )
   )
  printf("rayIntersectEdge, *********\n");
*/

  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 the ray is parallel to the edge, return 0: not intersect*/
  if(denom == 0.0)
    return 0;

  /*if v0 is on the edge, return 0: not intersect*/
  if(nomRay == 0.0)
    return 0;

  /*if v1 is on the positive ray, and the neighbor of v1 crosses the ray
   *return 1: intersect
   */
  if(nomEdge == 0)
    { /*v1 is on the positive or negative ray*/

/*
      printf("v1 is on the ray\n");
*/

      if(dx*(v1[0]-v0[0])>=0 && dy*(v1[1]-v0[1])>=0) /*v1 on positive ray*/
    {
      if(area(v0, v1, v10) * area(v0, v1, v2) >0)
        return 0;
      else
        return 1;
    }
      else /*v1 on negative ray*/
    return 0;
    }

  /*if v2 is on the ray, always return 0: not intersect*/
  if(nomEdge == denom) {
/*    printf("v2 is on the ray\n");*/
    return 0;
  }

  /*finally */
  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
	)

Definition at line 378 of file polyDBG.cc.

Referenced by DBG_pointInsidePoly().

{
  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++;
/*printf("ray intersect poly: count=%i\n", count);*/
  return count;
}

void DBG_reverse

(

directedLine *

poly

)

Definition at line 435 of file polyDBG.cc.

Referenced by DBG_check().

{
  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");
}