home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / listings / v_11_09 / 1109135a < prev    next >
Text File  |  1993-03-21  |  6KB  |  263 lines
  1. /******************************************************
  2.  
  3. GENERAL
  4.   Name                   : pgnclip.cpp
  5.   Author                 : Thomas Révész
  6.  
  7. PURPOSE
  8.   This file implements Sutherland-Hodgman's polygon 
  9.   clipping algorithm.
  10.  
  11. DOCUMENTS
  12.   Name                   : ---
  13.  
  14. DEPENDENCIES
  15.   Compiler dependency    : C++
  16.   Machine dependency     : None
  17.   Environment dependency : None
  18.  
  19. HISTORY
  20.   930303    1.0    Thomas Révész    Created
  21.  
  22. ******************************************************/
  23.  
  24. #include <iostream.h>
  25. #include <assert.h>
  26.  
  27.  
  28.  
  29. /**************************
  30. *
  31. *    Simple data types
  32. *
  33. **************************/
  34.                               
  35. enum bool {false, true};                  // boolean
  36.                               
  37. typedef signed long coord;                // coordinate
  38.                               
  39. class point                               // point
  40. {
  41. public:
  42.    point () : x (0), y (0) {}
  43.    point (coord x, coord y) : x (x), y (y) {}      
  44.    int operator == (point&);
  45.    int operator != (point&); 
  46.    coord x, y;
  47. };
  48.  
  49. inline point::operator == (point& p)
  50. {
  51.    return (x == p.x && y == p.y);
  52. }
  53.  
  54. inline point::operator != (point& p)
  55. {
  56.    return !(*this == p);
  57. }
  58.  
  59. inline ostream& operator << (ostream& o, point& p) 
  60. {
  61.    return o << '(' << p.x << ',' << p.y << ')';
  62. }
  63.  
  64.  
  65.  
  66. /***********************
  67. *
  68. *    Class ClipEdge
  69. *
  70. ***********************/
  71.  
  72. class ClipEdge
  73. {
  74. public:
  75.    ClipEdge () {vertex_received = false; next = 0;}
  76.    ~ClipEdge () {if (next) {delete (next);}}          
  77.    void add (ClipEdge *);
  78.    void vertex (point, point*&);
  79.    void close (point*&);
  80. protected:
  81.    virtual bool visible (point) const = 0;
  82.    virtual point clip (point, point) const = 0;
  83.    void output (point, point*&) const;
  84. private:
  85.    ClipEdge *next;
  86.    bool     vertex_received;
  87.    point    first, previous;
  88.    bool     first_visible, previous_visible;
  89. };
  90.  
  91. inline void ClipEdge::add (ClipEdge *edge)
  92. {
  93.    edge->next = next; 
  94.    next = edge;
  95. }
  96.  
  97. void ClipEdge::vertex (point current, point*& outpoint)
  98. {
  99.    bool current_visible = visible (current);
  100.  
  101.    if (!vertex_received) {
  102.       vertex_received = true;
  103.       first = current;
  104.       first_visible = current_visible;
  105.    }
  106.    else if (previous_visible ^ current_visible) {
  107.       point clipped = clip (previous, current);
  108.       output (clipped, outpoint);
  109.    }
  110.    if (current_visible) {
  111.       output (current, outpoint);
  112.    }
  113.    previous         = current;
  114.    previous_visible = current_visible;
  115. }
  116.  
  117. void ClipEdge::close (point*& outpoint)
  118. {
  119.    if (vertex_received) {
  120.       if (previous_visible ^ first_visible) {
  121.      point clipped = clip (previous, first);
  122.      output (clipped, outpoint);
  123.       }
  124.       if (next) {
  125.      next->close (outpoint);
  126.       }
  127.       vertex_received = false;
  128.    }
  129. }
  130.                               
  131. void ClipEdge::output (point current, 
  132.                point*& outpoint) const
  133. {
  134.    if (next) {
  135.       next->vertex (current, outpoint);
  136.    }
  137.    else {
  138.       *outpoint++ = current;
  139.    }
  140. }
  141.  
  142.  
  143.  
  144. /*************************
  145. *
  146. *    Class LinearEdge
  147. *
  148. *************************/
  149.  
  150. class LinearEdge : public ClipEdge
  151. {                                                     
  152. public:                                            
  153.    LinearEdge (point, point);
  154. protected:
  155.    virtual bool visible (point) const;
  156.    virtual point clip (point, point) const;
  157.    bool  isOnLeft (point) const;
  158.    const point start, end;
  159.    coord dx, dy;
  160. private:
  161.    int   sign (double value) const;
  162.    coord round (double value) const;
  163. };
  164.  
  165. LinearEdge::LinearEdge (point start, point end) : 
  166.             start (start), end (end)
  167. {
  168.    dx = end.x - start.x;
  169.    dy = end.y - start.y;
  170. }
  171.  
  172. inline bool LinearEdge::visible (point p) const 
  173. {
  174.    return isOnLeft (p);
  175. }
  176.  
  177. inline int LinearEdge::sign (double value) const 
  178. {
  179.    return (value >= 0 ? 1 : -1);
  180. }
  181.  
  182. inline coord LinearEdge::round (double value) const
  183. {
  184.    return (coord) (value + sign (value)/2.0);
  185. }
  186.  
  187. inline bool LinearEdge::isOnLeft (point p) const
  188. {
  189.    return (bool) (dx * (p.y - start.y) - 
  190.           dy * (p.x - start.x) >= 0);
  191. }
  192.  
  193. point LinearEdge::clip (point p1, point p2) const
  194. {
  195.    coord dxl = p2.x - p1.x;
  196.    coord dyl = p2.y - p1.y;
  197.    coord denominator = dx*dyl - dy*dxl;
  198.    assert (denominator != 0);
  199.    double t = (double) (dxl*(start.y - p1.y) - 
  200.             dyl*(start.x - p1.x))/
  201.             denominator;
  202.    return point (start.x + round (t*dx), 
  203.          start.y + round (t*dy));
  204. }
  205.  
  206.  
  207.  
  208. /*************************
  209. *
  210. *    The test function
  211. *
  212. *************************/
  213.  
  214. void main ()
  215. {
  216. // Set up the ClipEdge pipeline
  217.  
  218.    point p1 ( 75, 150);
  219.    point p2 (150,  75);
  220.    point p3 (225, 150);
  221.    point p4 (150, 225);
  222.  
  223.    ClipEdge *clip = new LinearEdge (p1, p2);
  224.    clip->add (new LinearEdge (p2, p3));
  225.    clip->add (new LinearEdge (p3, p4));
  226.    clip->add (new LinearEdge (p4, p1));
  227.  
  228. // Define the input polygon
  229.  
  230.    const int no_of_points = 8;
  231.  
  232.    point indata [no_of_points] = {
  233.       point ( 50,  50),
  234.       point (200,  50),
  235.       point (200, 200),
  236.       point (150, 200),
  237.       point (150, 100),
  238.       point (100, 100),
  239.       point (100, 200),
  240.       point ( 50, 200)
  241.    };
  242.  
  243. // Allocate memory for the clipped polygon 
  244. // (2*#input points + #clip edges)
  245.  
  246.    point *outpoint = new point [2*no_of_points + 4];
  247.    point *base     = outpoint;
  248.  
  249. // Clip the polygon
  250.  
  251.    for (int i = 0; i < no_of_points; i++) {
  252.       clip->vertex (indata [i], outpoint);
  253.    }
  254.    clip->close (outpoint);
  255.  
  256. // Display the result
  257.  
  258.    while (base < outpoint) {
  259.       cout << *base++ << endl;
  260.    }
  261.    cout << endl;
  262. }
  263.