---

gugr_contour.h

Go to the documentation of this file.

/* LIBGUL - Geometry Utility Library
 * Copyright (C) 1998-1999 Norbert Irmer
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public
 * License along with this library; if not, write to the
 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 * Boston, MA 02111-1307, USA.
 */

#ifndef GUGR_CONTOUR_H
#define GUGR_CONTOUR_H

#ifndef NDEBUG
  #include <iostream>   // for debug dump functions
#endif

namespace gugr {

using gul::Ptr;
using guar::rational;
using gul::point2;
using gul::rtr;
using gul::RefMap;

struct polyline
{
  Ptr<point2<rational> >  verts;
  int                     nVerts;

  Ptr<line>               lines;

  template< class T >
  bool init( int nP, const Ptr< point2<T> >& P, T minx, T miny, T scalei )
  {
    T x,y;
    int i,j;
    rational vx,vy;
    unsigned long *cbuf = 
      (unsigned long *)alloca(gul::rtr<T>::mantissa_length());

    verts.reserve_pool(nP);
    lines.reserve_pool(nP);

    x = (P[0].x - minx)*scalei;
    y = (P[0].y - miny)*scalei;
    verts[0].x = rational(coord2int(x,cbuf),cbuf);
    verts[0].y = rational(coord2int(y,cbuf),cbuf);
    j = 0;
    i = 1;

    for( ;; )
    {
      while( i < nP )
      {
        x = (P[i].x - minx)*scalei;
        y = (P[i].y - miny)*scalei;
        vx = rational(coord2int(x,cbuf),cbuf);
        vy = rational(coord2int(y,cbuf),cbuf);

        if( (compare(vx,verts[j].x)!=0) ||
            (compare(vy,verts[j].y)!=0) )
          break;

        i++;
      }

      if( i == nP ) break;

      j++;

      verts[j].x = vx;
      verts[j].y = vy;
      lines[j-1] = line( verts[j-1], verts[j] );
    }

    nVerts = j+1;
    if( (compare(verts[nVerts-1].x,verts[0].x)==0) &&
        (compare(verts[nVerts-1].y,verts[0].y)==0) )
      nVerts--;

    if( nVerts < 2 ) return false;

    lines[nVerts-1] = line( verts[nVerts-1], verts[0] );
    return true;
  }

  template<>
  bool init( int nP, const Ptr< point2<rational> >& P )
  {
    int i,j;

    verts.reserve_pool(nP);
    lines.reserve_pool(nP);

    verts[0] = P[0];
    j = 0;
    i = 1;

    for(;;)
    {
      while( (i < nP) &&
             (compare(P[i].x,verts[j].x)==0) && 
             (compare(P[i].y,verts[j].y)==0) )
        i++;

      if( i == nP ) break;

      j++;
      verts[j] = P[i];
      lines[j-1] = line( verts[j-1], verts[j] );

    }

    nVerts = j+1;
    if( (compare(verts[nVerts-1].x,verts[0].x)==0) &&
        (compare(verts[nVerts-1].y,verts[0].y)==0) )
      nVerts--;

    if( nVerts < 2 ) return false;

    lines[nVerts-1] = line( verts[nVerts-1], verts[0] );
    return true;
  }
};

struct contour_node
{
  int         nVerts;
  Ptr<vertex> verts;

  Ptr<line>   lines;

  int         nOwners;
  Ptr<void*>  owners;

  bool        side;
  bool        hole;

  contour_node *parent;
  RefMap<void> childs;

  segment      *hseg;
  segment      *seg;

  bool hseg_firstref; // needed later when cleaning up, has a bit of a hack

  contour_node *next;
  contour_node *prev;

  contour_node(bool aside) 
  { 
    parent = 0; 
    side = aside; 
    nOwners = 0; }

  bool hasOwner( void *o )
  {
    int i;

    for( i=0; i < nOwners; i++ )
    {
      if( owners[i] == o )
        return true;
    }
    return false;
  }

  void get_polyline( gul::polyline<gul::point2<guar::rational> >& pl )
  {
    int i;

    pl.P.reserve_pool(nVerts);
    pl.n = nVerts;

    for( i = 0; i < nVerts; i++ )
      pl.P[i] = verts[i].v();
  }

  void get_polyline_joined( gul::polyline<gul::point2<guar::rational> >& pl )
  {
    int i,j,i1,iend;

    pl.P.reserve_pool(nVerts);
    pl.n = nVerts;

    // find a point which is not in the midst of a series of
    // colinear points
    i1 = nVerts-1;
    for( i = 0; i < nVerts; i++ )
    {
      if( (compare(lines[i].dx(),lines[i1].dx())!=0) ||
          (compare(lines[i].dy(),lines[i1].dy())!=0) )
        break;
      i1 = i;
    }
    if( i == nVerts ) // not found
    {
      pl.n = 0;  // everything is colinear, so whole contour is unnecessary
      return;    
    }

    pl.P[0] = verts[i].v();
    // DumpPS<float>::dump_point(pl.P[0]);

    i1 = iend = i;
    i++; 
    if( i >= nVerts ) i = 0;
    j = 1;

    for(;;)
    {
      // search next point which is not colinear
      while( i != iend )
      {
        if( (compare(lines[i].dx(),lines[i1].dx())!=0) ||
            (compare(lines[i].dy(),lines[i1].dy())!=0) )
          break;

        i++;
        if( i >= nVerts ) i = 0; // wrap around
      }

      // start point of contour reached again
      if( i == iend )
        break;

      pl.P[j] = verts[i].v();
      // DumpPS<float>::dump_point(pl.P[j]);

      i1 = i;
      i++;
      if( i >= nVerts ) i = 0; // wrap around
      j++;
    }

    pl.n = j;
  }

  void Insert( contour_node *achild )
  {
    int side;
    RefMap<void>::Node pos,child;

    side = childs.SearchNode( (void *)achild, compare_pointer_to_pointer,
                               &pos );
    if( side != 0 )
    {
      child = childs.NewNode((void *)achild);
      achild->parent = this;
      childs.InsertNode( child, pos, side );
    }
  }

  // #ifndef NDEBUG
  void dump( int indent )
  {
    RefMap<void>::Node mn;
    int i;

    for( i = 0; i < indent; i++ ) std::cout << " ";
    std::cout << "contour " << (void *)this << "\n";
    for( i = 0; i < indent; i++ ) std::cout << " ";
    std::cout << "parent = " << (void *)parent << "\n";
    for( i = 0; i < indent; i++ ) std::cout << " ";
    std::cout << "childs = (\n";

    mn = childs.First();
    while( !mn.IsEmpty() )
    {
      for( i = 0; i < indent; i++ ) std::cout << " ";
      std::cout << "  " << mn.key() << "\n";
      mn = childs.Successor( mn );
    }
    for( i = 0; i < indent; i++ ) std::cout << " ";
    std::cout << ")\n\n";

    // recursion, dump childs
    mn = childs.First();
    while( !mn.IsEmpty() )
    {
      ((contour_node *)mn.key())->dump(indent+4);
      mn = childs.Successor( mn );
    }
  }
  // #endif
};

void AppendContour( polyline *c, int keyleft, int keyright,
                    List< ListNode<segment> >& segs );

template< class EP >
struct seg_point_info
{
  EP  *f;
  EP  *n;
  EP  *t;

  void *operator new( size_t s )
  {
    size_t dummy;
    void *p = PoolAlloc( s, &dummy );
    if( p == NULL ) throw PoolAllocError();
    return(p);
  }
  void operator delete( void *p, size_t s )
  {
    if( p != 0 ) PoolFree( p, s );
  }
};

template< class EP >
void AppendContourFNT( polyline *c, Ptr<EP>& F, Ptr<EP>& N, Ptr<EP>& T,
                 int keyleft, int keyright, List< ListNode<segment> >& segs );


void LeftSideContour( graph_edge *e, graph_edge_list& E, contour_node *cn );
void RightSideContour( graph_edge *e, graph_edge_list& E, contour_node *cn );


/*------------------------------------------------------------------
  Finds all contours in a graph. It also constructs a help line for
  each contour, which can be used to apply the odd even rule,
  or to build a containment tree 
------------------------------------------------------------------*/
void FindContours( 
        graph_edge_list& E, graph_vertex_list& V,
        const rational& far_maxx, const rational& far_maxy,
        List< ListNode<segment> >& outsegs,
        List<contour_node>& contours );

/*------------------------------------------------------------------
  Removes unnecessary edges by applying the odd/even winding rule
------------------------------------------------------------------*/
void RemoveUnnecessaryEdges( 
        graph_edge_list& E, graph_vertex_list& V,
        const rational& far_maxx, const rational& far_maxy,
        int key_inside, int key_outside,
        List< ListNode<segment> >& outsegs );

/*------------------------------------------------------------------
  Forms a graph from a couple of contours, and removes  unnecessary 
  edges in this graph by applying the odd/even winding rule
------------------------------------------------------------------*/
GULAPI void OddEvenRule( 
        List< ListNode<polyline> >& inC, 
        const rational& far_maxx, const rational& far_maxy,
        int key_inside, int key_outside,
        graph_edge_list& E, graph_vertex_list& V, 
        List< ListNode<segment> >& outsegs );

}

#endif

---