---

gugr_basics.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_BASICS_H
#define GUGR_BASICS_H

namespace gugr {

using gul::ndebug;
using gul::Assert;
using gul::InternalError;
using gul::PoolAllocError;
using gul::List;
using gul::List2;
using gul::bounding_box;
using guar::Interval;
using guar::ULong;
using guar::rational;
using gul::point2;
using gul::compare;
using gust::PoolAlloc;
using gust::PoolFree;

/*------------------------------------------------------------
  converts a floating point number lying between 1 and 2 into 
  a rational number between 0 and epsilon^-1
-------------------------------------------------------------*/
inline int coord2int( double f, unsigned long *buf )
{
  gul::uint64 i;
  unsigned long hi,lo;
  
//  gul::Assert<gul::InternalError>( ndebug | (1.0 <= f && f <= 2.0) );
  if( f < 1.0 ) f = 1.0; 
  else if( f > 2.0 ) f = 2.0; 
  i = (gul::uint64)(f*gul::rtr<double>::epsilon_inv());
  i -= (gul::uint64)gul::rtr<double>::epsilon_inv();
  hi = (unsigned long)((i >> 32) & LL(0xffffffff));
  lo = (unsigned long)(i & LL(0xffffffff)); 
  if( !hi )
  {
    if( !lo ) return 0;
    buf[0] = lo;
    return 1;
  }
  buf[0] = lo;
  buf[1] = hi;
  return 2; 
}

inline int coord2int( float f, unsigned long *buf )
{
  unsigned long i;
  
//  gul::Assert<InternalError>( ndebug | (1.0f <= f && f <= 2.0f) );
  if( f < 1.0f ) f = 1.0f; 
  else if( f > 2.0f ) f = 2.0f; 
  i = (unsigned long)(f * gul::rtr<float>::epsilon_inv());
  i -= (unsigned long)gul::rtr<float>::epsilon_inv();
  if( !i ) return 0;
  buf[0] = i;
  return 1;
}

/*---------------------------------------------------------------
  converts a number between 0 and epsilon^-1 into a number
  between 1 and 2
---------------------------------------------------------------*/
template< class T >
T cnv2coord( const T& i )
{
  return i * gul::rtr<T>::epsilon() + (T)1.0;
}

/*---------------------------------------------------------------
  converts a rational between 0 and epsilon^-1 into a floating
  point number between 1 and 2
---------------------------------------------------------------*/
template< class T >
inline void cnv2coord_rnd( rational& f, T *ret )
{
  rational q,r,rd,h;
  T flt;

  f.div_mod(&q,&r);

  rd = r/f.denominator();
  h = rational(ULong(1))/rational(ULong(2));

  if( compare(rd,h) >= 0 )
    q = q + rational(ULong(1));

  guar::IntTo<T>(q.m->m_na,q.m->m_a,flt);

  *ret = cnv2coord(flt);
}

struct vertex_rep
{
  point2<rational>       v;
  int                    m_refcount;
  gul::ptr_int_union     reserved;  /* used internally as a pointer to a buffer
                                       for conversions */
  vertex_rep() 
  { 
    m_refcount = 1;
    reserved.p = 0;
    reserved.i = 0;
  }

  explicit vertex_rep( const point2<rational> &av ) : v(av) 
  { 
    m_refcount = 1;
    reserved.p = 0;
    reserved.i = 0;
  }

  ~vertex_rep()
  {
  }
  
  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 )
  {
    PoolFree( p, s );
  }
};

struct vertex
{
  friend bool operator==( const vertex& a, const vertex& b );
  
  vertex_rep *m_rep;
  
  vertex() 
  { 
    m_rep = NULL;
  }

  explicit vertex( const vertex &other )
  {
    if( other.m_rep ) other.m_rep->m_refcount++;
    m_rep = other.m_rep;
  }

  explicit vertex( const point2<rational> &av )
  {
    m_rep = new vertex_rep( av );
  }

  ~vertex() 
  { 
    if( (m_rep != NULL) && (--m_rep->m_refcount == 0) ) delete m_rep;
  }

  vertex& operator=( const vertex& other )  {
    if( other.m_rep ) other.m_rep->m_refcount++;
    if( (m_rep != NULL) && (--m_rep->m_refcount == 0) ) {
      delete m_rep;
    }
    m_rep = other.m_rep;
    return( *this );    
  }

  point2<rational>& v() const { return(m_rep->v); }
};

inline bool operator==( const vertex& a, const vertex& b )
{
  return( a.m_rep == b.m_rep );
}

struct line_rep
{
  point2<rational>     v;
  rational    dx;
  rational    dy;
  int             m_refcount;

  line_rep() { m_refcount = 1; }

  line_rep( const point2<rational> &av, const rational& adx,
            const rational &ady ) : v(av), dx(adx), dy(ady)
  { m_refcount = 1; }

  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 )
  {
    PoolFree( p, s );
  }
};

struct line
{
  line_rep *m_rep;

  line() { m_rep = NULL; }

  explicit line( const line &other )
  {
    if( other.m_rep ) other.m_rep->m_refcount++;
    m_rep = other.m_rep;
  }

  ~line() { if( (m_rep != NULL)&&(--m_rep->m_refcount == 0) ) delete m_rep; }


  explicit line( const point2<rational> &av, const rational& adx,
                 const rational &ady )
  {
    m_rep = new line_rep( av, adx, ady );
  }
  GULAPI explicit line( const point2<rational>& a, const point2<rational>& b );

  line& operator=( const line& other ) {
    if( other.m_rep ) other.m_rep->m_refcount++;
    if( (m_rep != NULL) && (--m_rep->m_refcount == 0) ) {
      m_rep->~line_rep();
      PoolFree( m_rep, sizeof(line_rep) );      
    }
    m_rep = other.m_rep;
    return( *this ); }
  point2<rational>& v() const { return(m_rep->v); }
  rational& dx() const { return(m_rep->dx); }
  rational& dy() const { return(m_rep->dy); }
  bool IsNULL( void ) const { return(m_rep == NULL); }
  bool IsHorizontal(void) const { return m_rep->dy.is_zero(); }
  bool IsVertical(void) const { return m_rep->dx.is_zero(); }
};

inline bool parallel( const line& a, const line& b )
{
  if( a.IsHorizontal() )
    return b.IsHorizontal();
  else if( a.IsVertical() )
    return b.IsVertical();

  if( b.IsHorizontal() || b.IsVertical() )
    return false;

  return compare( a.dy(), b.dy() ) == 0;
}

bool intersect_nonvert( const line& a, const line& b, point2<rational>& I );
bool intersect_vert( const rational& x0, const line& b, point2<rational>& I );
bool intersect_horiz( const rational& y0, const line& b, point2<rational>& I );
bool intersect( const line& a, const line& b, point2<rational>& I );


struct graph_edge;

struct graph_vertex
{
  vertex                 v;
  graph_edge            *e;
  
  gul::ptr_int_union     reserved[2];

  graph_vertex          *next;
  graph_vertex          *prev;

  graph_vertex() 
  {
  }
  explicit graph_vertex( const point2<rational>& av, graph_edge *ae ) : v(av) 
  { 
    e = ae;
  }
  explicit graph_vertex( const vertex& av, graph_edge *ae ) 
  { 
    v = av; e = ae;
  }
                     /* sets the reserved[1] field, only for internal use! */
  explicit graph_vertex( const vertex& av, graph_edge *ae, int code ) 
  { 
    v = av; e = ae; reserved[1].set_i(code);
  }

                     /* sets the reserved[1] field, only for internal use! */
  explicit graph_vertex( const vertex& av, graph_edge *ae, gul::ptr_int_union pi ) 
  { 
    v = av; e = ae; reserved[1] = pi;
  }


  ~graph_vertex()
  {
  }

  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 )
  {
    PoolFree( p, s );
  }
};

typedef List<graph_vertex> graph_vertex_list;
typedef List2<graph_vertex> graph_vertex_list2;

struct graph_edge
{
  struct graph_vertex   *v[2];
  struct graph_edge     *e[2];
  gul::ptr_int_union     f[2];

  line                   l;
  
  gul::ptr_int_union     reserved[3];

  struct  graph_edge    *next;
  struct  graph_edge    *prev;
 
  graph_edge() { };

  explicit graph_edge( graph_vertex *v0, graph_vertex *v1 )
  { 
    v[0] = v0; v[1] = v1;
  }

  bool IsHorizontal(void)
  { 
    if( l.IsNULL() ) CalcLine();
    return( l.dy().is_zero() );
  }
    
  void CalcLine( void )   // Calculates the line on which a graph edge lies
  {
    l = line( v[0]->v.v(), v[1]->v.v() );
  }

//  graph_edge( graph_vertex *v1, graph_vertex *v2 ) { v[0] = v1; v[1] = v2; }

  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 )
  {
    PoolFree( p, s );
  }
};


typedef List<graph_edge> graph_edge_list;

typedef struct _cut_record
{
  graph_edge            *e;
  rational         val;
  graph_vertex          *v;
  
  struct _cut_record    *next;
  struct _cut_record    *prev;

  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 )
  {
    PoolFree( p, s );
  }
}
cut_record;

typedef List<cut_record> cut_record_list;

typedef struct _cut_info
{
  rational        val;
  cut_record_list       R;
  graph_edge_list       E;
  graph_vertex_list     V;
}
cut_info;

struct triangle
{
  vertex v[3];
  int code0 : 2;  
  int code1 : 2;  
  int code2 : 2;  

  struct triangle    *next;
  struct triangle    *prev;

  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 )
  {
    PoolFree( p, s );
  }
};

typedef List<triangle> triangle_list;

struct monpoly_info
{
  graph_vertex_list2 Vl;
  graph_vertex_list2 Vr;
  graph_edge_list    E;

  /* ------------------------------------------------------------------------
    Appends a edge to the left chain of a monotone polygon. If this closes
    the polygon the function returns true
  ------------------------------------------------------------------------ */
  bool AppendLeft( const graph_vertex& v1, const graph_vertex& v2 );

  /* ------------------------------------------------------------------------
    Appends a vertex to the right chain of a monotone polygon. If this closes
    the polygon the function returns true
  -------------------------------------------------------------------------- */
  bool AppendRight( const graph_vertex& v1, const graph_vertex& v2 );
};

/* ----------------------------------------------------------------
   gets the edges incident to vertex 'v'
------------------------------------------------------------------ */
int IncidentEdges( const graph_vertex *v, graph_edge **A );

/* ----------------------------------------------------------------
   gets the edges incident to edge 'e' at vertex 'v'
------------------------------------------------------------------ */
int EdgeCycle( graph_edge *e, graph_vertex *v, graph_edge **A );

/* --------------------------------------------------------------------
  Orient edge, so that y2 > y1 or x2 < x1 if y2 = y1
--------------------------------------------------------------------- */
void OrientEdge( graph_edge *e );

/* --------------------------------------------------------------------
  Orient edges, so that y2 > y1 or x2 < x1 if y2 = y1
--------------------------------------------------------------------- */
void OrientEdges( graph_edge *E );

/* ------------------------------------------------------------------------
  Determine on which side of AB the point C is
-------------------------------------------------------------------------- */
int DetermineOrientation( const point2<rational>& A, const point2<rational>& B, 
                          const point2<rational>& C );
int DetermineOrientationPV( const point2<rational>& A, const point2<rational>& AB, 
                            const point2<rational>& C );

/* --------------------------------------------------------------------
  Compares angle(AB,AC) to angle(AB,AD)

  Remarks:

  code_x = 3 if X is to the left of AB
           2 if X is on AB
           1 if X is to the right of AB
           0 if it was not necessary to calculate the cross-product
  match = 1 if C lies on AB
        = 2 if D lies on AB
        = 0 if both C and D are not on AB             
---------------------------------------------------------------------- */
int CompareAngles(
  const point2<rational>& A, const point2<rational>& B,
  const point2<rational>& C, const point2<rational>& D,
  int *match, int *code_c, int *code_d );
 
/* --------------------------------------------------------------------
  Find the insertion positon for a oriented line segment in an edge 
  cycle of a DCEL 

  Remarks:

  code_edge = 3 if angle(ab,edge) < 180
            = 2 if angle(ab,edge) = 0 or 180
            = 1 if angle(ab,edge) > 180
  match = 1 if ab and left are colinear 
        = 2 if ab and right are colinear
        = 0 if none of both edges lies on ab         
---------------------------------------------------------------------*/ 
int EdgeInsertPosition(
         const vertex& a, const vertex& b,
         int nE, graph_edge **E,
         int *eleft, int *eright,
         int *code_left, int *code_right );

/* ----------------------------------------------------------------------
  Connects a edge at its ends into a graph
-----------------------------------------------------------------------*/
void ConnectEdge( graph_edge *e, int maxE );

/* ----------------------------------------------------------------------
  Disconnect the ends of an edge from a graph. Bit 1/2 of the result
  indicate that v[0/1] of the edge are isolated afterwards 
-----------------------------------------------------------------------*/
int DisconnectEdge( graph_edge *e, int maxE );

/*-------------------------------------------------------------------------
  Converts simple polygon to a DCEL (doubly connected edge list, winged edge
  list)
--------------------------------------------------------------------------*/
template< class T >
void PolygonToGraph( 
      const int n, gul::Ptr< gul::point2<T> > P,
      const T orgx, const T orgy,
      const T scalex, const T scaley,
      int fleft, int fright,
      graph_edge_list *E, graph_vertex_list *V );

template< class T >
inline void PolygonToGraphNV( 
      const int n, gul::Ptr< gul::point2<T> > P,
      const T orgx, const T orgy,
      const T scalex, const T scaley,
      int fleft, int fright,
      graph_edge_list *E, graph_vertex_list *V );


}


#endif

---