home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
The C Users' Group Library 1994 August
/
wc-cdrom-cusersgrouplibrary-1994-08.iso
/
listings
/
v_11_08
/
revesz.c
< prev
next >
Wrap
C/C++ Source or Header
|
1993-03-21
|
6KB
|
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;
}