ttl_constr Namespace Reference

Constrained Delaunay triangulation. More...

Functions
template<class DartType >
bool	isTheConstraint (const DartType &dart, const DartType &dstart, const DartType &dend)
template<class TraitsType , class DartType >
bool	crossesConstraint (DartType &dstart, DartType &dend, DartType &d1, DartType &d2)
template<class TraitsType , class DartType >
DartType	getAtSmallestAngle (const DartType &dstart, const DartType &dend)
template<class TraitsType , class DartType , class ListType >
DartType	findCrossingEdges (const DartType &dstart, const DartType &dend, ListType &elist)
template<class TraitsType , class DartType >
void	transformToConstraint (DartType &dstart, DartType &dend, list< DartType > &elist)

---

Detailed Description

Constrained Delaunay triangulation.

Basic generic algorithms in TTL for inserting a constrained edge between two existing nodes.

See documentation for the namespace ttl for general requirements and assumptions.

Author:

Øyvind Hjelle, oyvindhj@ifi.uio.no

---

Function Documentation

template<class TraitsType , class DartType >

bool ttl_constr::crossesConstraint	(	DartType &	dstart,
		DartType &	dend,
		DartType &	d1,
		DartType &	d2
	)			[inline]

Definition at line 113 of file ttl_constr.h.

                                                                                         {
    
    typename TraitsType::real_type orient_1 = TraitsType::orient2d(dstart,d1,dend);
    typename TraitsType::real_type orient_2 = TraitsType::orient2d(dstart,d2,dend);
    // ??? Should we refine this? e.g. find if (dstart,dend) (d1,d2) represent the same edge
    if ((orient_1 <= 0 && orient_2 <= 0) || (orient_1 >= 0 && orient_2 >= 0))
      return false;
    
    return true;
  }

template<class TraitsType , class DartType , class ListType >

DartType ttl_constr::findCrossingEdges	(	const DartType &	dstart,
		const DartType &	dend,
		ListType &	elist
	)			[inline]

Definition at line 263 of file ttl_constr.h.

                                                                                              {
    
    const DartType my_start = getAtSmallestAngle<TraitsType>(dstart, dend);
    DartType my_end   = getAtSmallestAngle<TraitsType>(dend, dstart);
    
    DartType d_iter = my_start;
    if (d_iter.alpha0().alpha2() == my_end)
      return d_iter; // The constraint is an existing edge and we are done
    
    // Facts/status so far:
    // - my_start and my_end are now both CCW and the constraint is not a boundary edge.
    // - Further, the constraint is not one single existing edge, but it might be a collection
    //   of collinear edges in which case we return the current collinear edge
    //   and calling this function until all are collected.
    
    my_end.alpha1(); // CW! // ??? this is probably ok for testing now?
    
    d_iter = my_start;
    d_iter.alpha0().alpha1(); // alpha0 is downwards or along the constraint
    
    // Facts:
    // - d_iter is guaranteed to intersect, but can be in start point.
    // - d_iter.alpha0() is not at dend yet
    typename TraitsType::real_type orient = TraitsType::orient2d(dstart, d_iter, dend);

    // Use round-off error/tolerance or rely on the orient2d predicate ???
    // Make a warning message if orient != exact 0
    if (orient == 0)
      return d_iter;

#ifdef DEBUG_TTL_CONSTR
    else if (fabs(orient) <= ROUNDOFFZERO) {
      cout << "The darts are not exactly colinear, but |d1 x d2| <= " << ROUNDOFFZERO << endl;
      return d_iter; // collinear, not done (and not collect in the list)
    }
#endif

    // Collect intersecting edges
    // --------------------------
    elist.push_back(d_iter); // The first with interior intersection point
    
    // Facts, status so far:
    // - The first intersecting edge is now collected
    // (- d_iter.alpha0() is still not at dend)
    
    // d_iter should always be the edge that intersects and be below or on the constraint
    // One of the two edges opposite to d_iter must intersect, or we have collinearity
    
    // Note: Almost collinear cases can be handled on the
    // application side with orient2d. We should probably
    // return an int and the application will set it to zero
    for(;;) {
      // assume orient have been calc. and collinearity has been tested,
      // above the first time and below later
      d_iter.alpha2().alpha1(); // 2a same node
      
      DartType d0 = d_iter;
      d0.alpha0(); // CW
      if (d0 == my_end)
        return dend; // WE ARE DONE (but can we enter an endless loop???)
      
      // d_iter or d_iter.alpha0().alpha1() must intersect
      orient = TraitsType::orient2d(dstart, d0, dend);
      
      if (orient == 0) 
        return d0.alpha1();

#ifdef DEBUG_TTL_CONSTR
      else if (fabs(orient) <= ROUNDOFFZERO) {
        return d0.alpha1(); // CCW, collinear
      }
#endif

      else if (orient > 0) { // orient > 0 and still below
        // This one must intersect!
        d_iter = d0.alpha1();
      }
      elist.push_back(d_iter);
    }
  }

template<class TraitsType , class DartType >

DartType ttl_constr::getAtSmallestAngle	(	const DartType &	dstart,
		const DartType &	dend
	)			[inline]

Definition at line 151 of file ttl_constr.h.

References ttl::isBoundaryNode(), and ttl::positionAtNextBoundaryEdge().

                                                                              {
    
    // - Must boundary be convex???
    // - Handle the case where the constraint is already present???
    // - Handle dstart and/or dend at the boundary
    //   (dstart and dend may define a boundary edge)
    
    DartType d_iter = dstart;
    if (ttl::isBoundaryNode(d_iter)) {
      d_iter.alpha1(); // CW
      ttl::positionAtNextBoundaryEdge(d_iter); // CCW (was rotated CW to the boundary)
    }
    
    // assume convex boundary; see comments
    
    DartType d0 = d_iter;
    d0.alpha0();
    bool ccw = true; // the rotation later
    typename TraitsType::real_type o_iter = TraitsType::orient2d(d_iter, d0, dend);
    if (o_iter == 0) { // collinear BUT can be on "back side"
      d0.alpha1().alpha0(); // CW
      if (TraitsType::orient2d(dstart, dend, d0) > 0)
        return d_iter; //(=dstart) collinear
      else {
        // collinear on "back side"
        d_iter.alpha1().alpha2(); // assume convex boundary
        ccw = true;
      }
    }
    else if (o_iter < 0) {
      // Prepare for rotating CW and with d_iter CW
      d_iter.alpha1();
      ccw = false;
    }
    
    // Set first angle
    d0 = d_iter; d0.alpha0();
    o_iter = TraitsType::orient2d(dstart, d0, dend);
    
    typename TraitsType::real_type o_next;
    
    // Rotate towards the constraint CCW or CW.
    // Here we assume that the boundary is convex.
    DartType d_next = d_iter;
    for (;;) {
      d_next.alpha1(); // CW !!! (if ccw == true)
      d0 = d_next; d0.alpha0();
      o_next = TraitsType::orient2d(dstart, d0, dend);
      
      if (ccw && o_next < 0) // and o_iter > 0
        return d_iter;
      else if (!ccw && o_next > 0)
        return d_next; // CCW
      else if (o_next == 0) {
        if (ccw)
          return d_next.alpha2(); // also ok if boundary
        else
          return d_next;
      }
      
      // prepare next
      d_next.alpha2(); // CCW if ccw
      d_iter = d_next; // also ok if boundary CCW if ccw == true
    }
  }

template<class DartType >

bool ttl_constr::isTheConstraint	(	const DartType &	dart,
		const DartType &	dstart,
		const DartType &	dend
	)			[inline]

Definition at line 82 of file ttl_constr.h.

References ttl::same_0_orbit().

Referenced by transformToConstraint().

                                                                                             {
    DartType d0 = dart;
    d0.alpha0(); // CW
    if ((ttl::same_0_orbit(dstart, dart) && ttl::same_0_orbit(dend, d0)) ||
      (ttl::same_0_orbit(dstart, d0)  && ttl::same_0_orbit(dend, dart))) {
      return true;
    }
    return false;
  }

template<class TraitsType , class DartType >

void ttl_constr::transformToConstraint	(	DartType &	dstart,
		DartType &	dend,
		list< DartType > &	elist
	)			[inline]

Definition at line 383 of file ttl_constr.h.

References isTheConstraint().

                                                                                        {
    
    typename list<DartType>::iterator it, used;
    
    // We may enter in a situation where dstart and dend are altered because of a swap.
    // (The general rule is that darts inside the actual quadrilateral can be changed,
    // but not those outside.)
    // So, we need some look-ahead strategies for dstart and dend and change these
    // after a swap if necessary.
    
    int dartsInList = elist.size();
    if (dartsInList == 0)
      return;

    bool erase; // indicates if an edge is swapped away from the constraint such that it can be
                // moved to the back of the list
    bool locked = false;
    do {
      int noswap = 0;
      it = elist.begin();

      // counts how many edges that have been swapped per list-cycle
      int counter = 1;
      while(it != elist.end()) { // ??? change this test with counter > dartsInList
        erase = false;
        // Check if our virtual end of the list has been crossed. It breaks the
        // while and starts all over again in the do-while loop
        if (counter > dartsInList)
          break;
        
        if (ttl::swappableEdge<TraitsType, DartType>(*it, true)) {
          // Dyn & Goren & Rippa 's notation:
          // The node assosiated with dart *it is denoted u_m. u_m has edges crossing the constraint
          // named w_1, ... , w_r . The other node to the edge assosiated with dart *it is w_s.
          // We want to swap from edge u_m<->w_s to edge w_{s-1}<->w_{s+1}.
          DartType op1 = *it;
          DartType op2 = op1;
          op1.alpha1().alpha0(); //finds dart with node w_{s-1}
          op2.alpha2().alpha1().alpha0(); // (CW) finds dart with node w_{s+1}
          DartType tmp = *it; tmp.alpha0(); // Dart with assosiated node opposite to node of *it allong edge
          // If there is a locked situation we swap, even if the result is crossing the constraint
          // If there is a looked situation, but we do an ordinary swap, it should be treated as
          // if we were not in a locked situation!!

          // The flag swap_away indicates if the edge is swapped away from the constraint such that
          // it does not cross the constraint.
          bool swap_away = (crossesConstraint<TraitsType>(dstart, dend, *it, tmp) &&
                            !crossesConstraint<TraitsType>(dstart, dend, op1, op2));
          if (swap_away || locked) {
            // Do a look-ahead to see if dstart and/or dend are in the quadrilateral
            // If so, we mark it with a flag to make sure we update them after the swap
            // (they may have been changed during the swap according to the general rule!)
            bool start = false;
            bool end = false;
            
            DartType d = *it;
            if (d.alpha1().alpha0() == dstart)
              start = true;
            d = *it;
            if (d.alpha2().alpha1().alpha0().alpha1() == dend)
              end = true;
            
            // This is the only place swapping is called when inserting a constraint
            ttl::swapEdgeInList<TraitsType, DartType>(it,elist);
            
            // If we, during look-ahead, found that dstart and/or dend were in the quadrilateral,
            // we update them.
            if (end)
              dend = *it;
            if (start) {
              dstart = *it;
              dstart.alpha0().alpha2();
            }
            
            if (swap_away) { // !locked || //it should be sufficient with swap_away ???
              noswap++;
              erase = true;
            }
            
            if (isTheConstraint(*it, dstart, dend)) {
              // Move the constraint to the end of the list
              DartType the_constraint = *it;
              elist.erase(it);
              elist.push_back(the_constraint);
              return;
            } //endif
          } //endif
        } //endif "swappable edge"
        
                
        // Move the edge to the end of the list if it was swapped away from the constraint
        if (erase) {
          used = it;
          elist.push_back(*it);
          ++it;
          elist.erase(used);
          --dartsInList;
        } 
        else {
          ++it;
          ++counter;
        }
        
      } //end while
      
      if (noswap == 0)
        locked = true;
      
    } while (dartsInList != 0);
    
    
#ifdef DEBUG_TTL_CONSTR
    // We will never enter here. (If elist is empty, we return above).
    cout << "??????? ERROR 2, should never enter here ????????????????????????? SKIP ???? " << endl;
    exit(-1);
#endif

  }