fist/degenerate.cpp

/*****************************************************************************/
/*                                                                           */
/*           F I S T :  Fast, Industrial-Strength Triangulation              */
/*                                                                           */
/*****************************************************************************/
/*                                                                           */
/* (C)                            Martin Held                                */
/* (C)            Universitaet Salzburg, Salzburg, Austria                   */
/*                                                                           */
/* This code is not in the public domain. All rights reserved! Please make   */
/* sure to read the full copyright statement contained in api_functions.cpp. */
/*                                                                           */
/*****************************************************************************/

/*                                                                           */
/* get standard libraries                                                    */
/*                                                                           */
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <assert.h>

/*                                                                           */
/* get my header files                                                       */
/*                                                                           */
#include "fpkernel.h"
#include "martin.h"
#include "defs.h"
#include "list.h"
#include "header.h"
#include "basic.h"
#include "numerics.h"

/*                                                                           */
/* function prototypes of functions provided in this file                    */
/*                                                                           */
boolean HandleDegeneracies(global_struct *all, int i1, list_ind ind1, int i2,
		                   int i3, int i4,list_ind ind4);


/*                                                                           */
/* this function checks whether the triangle  i1, i2, i3  is an ear, where   */
/* the vertex  i4  lies on at least one of the two edges  i1, i2  or  i3, i1.*/
/* basically, we can cut the polygon at  i4  into two pieces. the polygon    */
/* touches at  i4  back to back if following the next-pointers in one        */
/* subpolygon and following the prev-pointers in the other subpolygon yields */
/* the same orientation for both subpolygons. otherwise,  i4  forms a        */
/* bottle neck of the polygon, and  i1, i2, i3  is no valid ear.             */
/*                                                                           */
/* note that this function may come up with the incorrect answer if the      */
/* polygon has self-intersections.                                           */
/*                                                                           */
boolean HandleDegeneracies(global_struct *all, int i1, list_ind ind1, int i2,
                           int i3, int i4, list_ind ind4)
{
   listdef *list = &all->c_list;
   datadef *data = &all->c_data;
   
   tmp_data_def tmp_data;

   int i0, i5, pnt_on_edge_classifier = 0;
   list_ind ind0, ind2, ind5;
   boolean is_inside_prev = false, is_inside_next = false, flag;
   double area = C_0_0, area1 = C_0_0, area2 = C_0_0;

   assert(InPointsList(data,i1));
   assert(InPointsList(data,i2));
   assert(InPointsList(data,i3));
   assert(InPointsList(data,i4));

   /*                                                                        */
   /* first check whether the successor or predecessor of  i4  is inside the */
   /* triangle, or whether any of the two edges incident at  i4  intersects  */
   /* i2, i3.                                                                */
   /*                                                                        */
   ind5 = GetPrevNode(list,ind4);
   i5   = GetIndex(list,ind5);
   assert(ind4 != ind5);
   assert(InPointsList(data, i5));
   if ((i5 != i2)  &&  (i5 != i3)) {
      VtxInTriangle(data, tmp_data, i1, i2, i3, i5, is_inside_prev, pnt_on_edge_classifier);
      if (is_inside_prev  &&  (pnt_on_edge_classifier == 0))  return true;
      if (i2 <= i3) {
         if (i4 <= i5)      flag = SegIntersect(all, i2, i3, i4, i5, -1);
         else               flag = SegIntersect(all, i2, i3, i5, i4, -1);
      } 
      else {
         if (i4 <= i5)      flag = SegIntersect(all, i3, i2, i4, i5, -1);
         else               flag = SegIntersect(all, i3, i2, i5, i4, -1);
      }
      if (flag)  return true;
   }
   else {
      is_inside_prev = true;
   }

   ind5 = GetNextNode(list, ind4);
   i5   = GetIndex(list, ind5);
   assert(ind4 != ind5);
   assert(InPointsList(data, i5));
   if ((i5 != i2)  &&  (i5 != i3)) {
      VtxInTriangle(data, tmp_data, i1, i2, i3, i5, is_inside_next, pnt_on_edge_classifier);
      if (is_inside_next  &&  (pnt_on_edge_classifier == 0))  return true;
      if (i2 <= i3) {
         if (i4 <= i5)      flag = SegIntersect(all, i2, i3, i4, i5, -1);
         else               flag = SegIntersect(all, i2, i3, i5, i4, -1);
      } 
      else {
         if (i4 <= i5)      flag = SegIntersect(all, i3, i2, i4, i5, -1);
         else               flag = SegIntersect(all, i3, i2, i5, i4, -1);
      }
      if (flag)  return true;
   }
   else {
      is_inside_next = true;
   }

   if (!(is_inside_prev  ||  is_inside_next))  return false;

   /*                                                                        */
   /* the edges  i1,i2  and  i1,i3  overlap pairwise with the two edges      */
   /* incident at  i4 (i.e., ind4). no chance to decide locally whether or   */
   /* not  i1,i2,i3  forms a valid ear. thus, we'll compute signed areas.    */
   /*                                                                        */
   i0   = i1;
   ind0 = ind1;
   ind1 = GetNextNode(list, ind1);
   i1   = GetIndex(list, ind1);
   while (ind1 != ind4) {
      ind2   = GetNextNode(list, ind1);
      i2     = GetIndex(list, ind2);
      StableDet2D(data, tmp_data, i0, i1, i2, area);
      area1 += area;
      ind1   = ind2;
      i1     = i2;
   }
   
   ind1 = GetPrevNode(list, ind0);
   i1   = GetIndex(list, ind1);
   while (ind1 != ind4) {
      ind2   = GetPrevNode(list, ind1);
      i2     = GetIndex(list, ind2);
      StableDet2D(data, tmp_data, i0, i1, i2, area);
      area2 += area;
      ind1   = ind2;
      i1     = i2;
   }
 
   if (le(area1, ZERO)  &&  le(area2, ZERO))       return false;
   else if (ge(area1, ZERO)  &&  ge(area2, ZERO))  return false;
   else                                            return true;
}