Resource for Source: C/C++/Resource for Source - C-C++.iso/codelib9/v_11_08/revesz.c

C/C++ Source or Header | 1995-11-01 | 5.5 KB | 263 lines

/******************************************************

GENERAL
  Name                   : pgnclip.cpp
  Author                 : Thomas Révész

PURPOSE
  This file implements Sutherland-Hodgman's polygon
  clipping algorithm.

DOCUMENTS
  Name                   : ---

DEPENDENCIES
  Compiler dependency    : C++
  Machine dependency     : None
  Environment dependency : None

HISTORY
  930303    1.0    Thomas Révész    Created

******************************************************/

#include <iostream.h>
#include <assert.h>



/**************************
*
*    Simple data types
*
**************************/

enum bool {false, true};                  // boolean

typedef signed long coord;                // coordinate

class point                               // point
{
public:
   point () : x (0), y (0) {}
   point (coord x, coord y) : x (x), y (y) {}
   int operator == (point&);
   int operator != (point&);
   coord x, y;
};

inline point::operator == (point& p)
{
   return (x == p.x && y == p.y);
}

inline point::operator != (point& p)
{
   return !(*this == p);
}

inline ostream& operator << (ostream& o, point& p)
{
   return o << '(' << p.x << ',' << p.y << ')';
}



/***********************
*
*    Class ClipEdge
*
***********************/

class ClipEdge
{
public:
   ClipEdge () {vertex_received = false; next = 0;}
   ~ClipEdge () {if (next) {delete (next);}}
   void add (ClipEdge *);
   void vertex (point, point*&);
   void close (point*&);
protected:
   virtual bool visible (point) const = 0;
   virtual point clip (point, point) const = 0;
   void output (point, point*&) const;
private:
   ClipEdge *next;
   bool     vertex_received;
   point    first, previous;
   bool     first_visible, previous_visible;
};

inline void ClipEdge::add (ClipEdge *edge)
{
   edge->next = next;
   next = edge;
}

void ClipEdge::vertex (point current, point*& outpoint)
{
   bool current_visible = visible (current);

   if (!vertex_received) {
      vertex_received = true;
      first = current;
      first_visible = current_visible;
   }
   else if (previous_visible ^ current_visible) {
      point clipped = clip (previous, current);
      output (clipped, outpoint);
   }
   if (current_visible) {
      output (current, outpoint);
   }
   previous         = current;
   previous_visible = current_visible;
}

void ClipEdge::close (point*& outpoint)
{
   if (vertex_received) {
      if (previous_visible ^ first_visible) {
     point clipped = clip (previous, first);
     output (clipped, outpoint);
      }
      if (next) {
     next->close (outpoint);
      }
      vertex_received = false;
   }
}

void ClipEdge::output (point current,
               point*& outpoint) const
{
   if (next) {
      next->vertex (current, outpoint);
   }
   else {
      *outpoint++ = current;
   }
}



/*************************
*
*    Class LinearEdge
*
*************************/

class LinearEdge : public ClipEdge
{
public:
   LinearEdge (point, point);
protected:
   virtual bool visible (point) const;
   virtual point clip (point, point) const;
   bool  isOnLeft (point) const;
   const point start, end;
   coord dx, dy;
private:
   int   sign (double value) const;
   coord round (double value) const;
};

LinearEdge::LinearEdge (point start, point end) :
            start (start), end (end)
{
   dx = end.x - start.x;
   dy = end.y - start.y;
}

inline bool LinearEdge::visible (point p) const
{
   return isOnLeft (p);
}

inline int LinearEdge::sign (double value) const
{
   return (value >= 0 ? 1 : -1);
}

inline coord LinearEdge::round (double value) const
{
   return (coord) (value + sign (value)/2.0);
}

inline bool LinearEdge::isOnLeft (point p) const
{
   return (bool) (dx * (p.y - start.y) -
          dy * (p.x - start.x) >= 0);
}

point LinearEdge::clip (point p1, point p2) const
{
   coord dxl = p2.x - p1.x;
   coord dyl = p2.y - p1.y;
   coord denominator = dx*dyl - dy*dxl;
   assert (denominator != 0);
   double t = (double) (dxl*(start.y - p1.y) -
            dyl*(start.x - p1.x))/
            denominator;
   return point (start.x + round (t*dx),
         start.y + round (t*dy));
}



/*************************
*
*    The test function
*
*************************/

void main ()
{
// Set up the ClipEdge pipeline

   point p1 ( 75, 150);
   point p2 (150,  75);
   point p3 (225, 150);
   point p4 (150, 225);

   ClipEdge *clip = new LinearEdge (p1, p2);
   clip->add (new LinearEdge (p2, p3));
   clip->add (new LinearEdge (p3, p4));
   clip->add (new LinearEdge (p4, p1));

// Define the input polygon

   const int no_of_points = 8;

   point indata [no_of_points] = {
      point ( 50,  50),
      point (200,  50),
      point (200, 200),
      point (150, 200),
      point (150, 100),
      point (100, 100),
      point (100, 200),
      point ( 50, 200)
   };

// Allocate memory for the clipped polygon
// (2*#input points + #clip edges)

   point *outpoint = new point [2*no_of_points + 4];
   point *base     = outpoint;

// Clip the polygon

   for (int i = 0; i < no_of_points; i++) {
      clip->vertex (indata [i], outpoint);
   }
   clip->close (outpoint);

// Display the result

   while (base < outpoint) {
      cout << *base++ << endl;
   }
   cout << endl;
}