Category : Files from Magazines
Archive : CUJ9309.ZIP
Filename : 1109135A
Output of file : 1109135A contained in archive : CUJ9309.ZIP
GENERAL
Name : pgnclip.cpp
Author : Thomas Rvsz
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 Rvsz Created
******************************************************/
#include
#include
/**************************
*
* 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;
}
Very nice! Thank you for this wonderful archive. I wonder why I found it only now. Long live the BBS file archives!
This is so awesome! 😀 I’d be cool if you could download an entire archive of this at once, though.
But one thing that puzzles me is the “mtswslnkmcjklsdlsbdmMICROSOFT” string. There is an article about it here. It is definitely worth a read: http://www.os2museum.com/wp/mtswslnk/