hdaffin@oucsace.cs.OHIOU.EDU (Howard Daffin) (05/02/89)
Hey there all.. Does anyone have the source code to a good polygon clipping algorithm. This is to be used with borland's turbo-c (2.0) Any help will be appreciated!! _Tanx_in_advance_ -Howie AKA: Howard H Daffin III +------------------------------------------------------------------+ | / / ____ _ _ _ ___ ____> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| | /==/ / * / \ / \ / / /__> + hdaffin@oucsace.cs.OHIOU.EDU+| | / / /___/ / / _/_ /____> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| +------------------------------------------------------------------+ | - Soon, we will see given some time that: | | - Computers are an empirical representation of the mind - ;>) | +__________________________________________________________________+
cm26+@andrew.cmu.edu (Curt McDowell) (05/03/89)
The following is a package which maintains polygons and includes a
routine to clip polygons to a rectangle. It is written in an
object-oriented style. It works quite well. The first file is an
example of how you'd put it to use, the second is a simple definition of
a viewport (clipping rectangle), the third is the polygon header file to
be included by other modules, and the fourth is the polygon code file.
Curt McDowell
Carnegie Mellon University
--- FILE EXAMPLE.C ---
#include <stdio.h>
#include <polygon.h>
#include <viewport.h>
main(argc, argv)
char **argv;
{
struct polygon *p;
struct viewport v;
p = polygon_New();
polygon_Insert(p, 10, 100);
polygon_Insert(p, ..., ...);
... etc ...;
v.left = 1;
v.top = ...;
v.width = ...;
v.height = ...;
polygon_Clip(p, &v);
printf("Clipped polygon:\n");
for (i = 0; i < p->n; i++)
printf("(%d,%d)\n", p->x[i], p->y[i]);
}
--- FILE VIEWPORT.H ---
struct viewport {
int left, top;
int width, height;
};
--- FILE POLYGON.H ---
/*
* Polygon data structure
*/
struct polygon {
short n, alloc;
short *x, *y;
};
#define polygon_Clear(p) ((p)->n = 0)
extern struct polygon *polygon_New();
extern void polygon_Insert();
extern void polygon_Destroy();
extern void polygon_Clip();
--- FILE POLYGON.C ---
/*
* Polygon object
* by Curt McDowell, CMU Information Technology Center
*
* This code comes under the IBM Copyright of the Andrew Toolkit,
* which is to say, you can do anything but sell it.
*/
#include <polygon.h>
#include <viewport.h>
char *malloc(), *realloc();
/* Similar triangle macro:
* Given three coordinates along axis 1 and two
* along axis 2, finds the third on axis 2 which
* falls between the two on axis 1. */
#define ClipCase(left, middle, right, start, end) \
(((start) * ((right) - (middle)) + \
(end) * ((middle) - (left))) / ((right) - (left)))
/* Polygon manipulation:
* Dynamically allocated polygon structure
* Use this to create and destroy polygons to be
* passed to the clipping and filling routines. */
struct polygon *polygon_New()
{
struct polygon *p;
p = (struct polygon *) malloc(sizeof (struct polygon));
p->alloc = 8;
p->x = (short *) malloc(p->alloc * sizeof (short));
p->y = (short *) malloc(p->alloc * sizeof (short));
p->n = 0;
return p;
}
void polygon_Insert(p, x, y)
struct polygon *p;
short x, y;
{
if (p->n == p->alloc) {
p->alloc *= 2;
p->x = (short *) realloc(p->x, p->alloc * sizeof (short));
p->y = (short *) realloc(p->y, p->alloc * sizeof (short));
}
p->x[p->n] = x;
p->y[p->n] = y;
p->n++;
}
void polygon_Destroy(p)
struct polygon *p;
{
free(p->x);
free(p->y);
free(p);
}
/*
* Clip Polygon associated code
*/
#define edge_LEFT 0
#define edge_RIGHT 1
#define edge_ABOVE 2
#define edge_BELOW 3
static short Inside(x, y, v, which)
short x, y;
struct viewport *v;
short which;
{
switch (which) {
case edge_ABOVE:
return (y >= v->top);
case edge_BELOW:
return (y < v->top + v->height);
case edge_LEFT:
return (x >= v->left);
case edge_RIGHT:
return (x < v->left + v->width);
}
}
static void Intersect(px, py, fx, fy, tx, ty, v, which)
short *px, *py;
short fx, fy, tx, ty;
struct viewport *v;
short which;
{
switch (which) {
case edge_ABOVE:
*py = v->top;
*px = ClipCase(fy, *py, ty, fx, tx);
break;
case edge_BELOW:
*py = v->top + v->height - 1;
*px = ClipCase(fy, *py, ty, fx, tx);
break;
case edge_LEFT:
*px = v->left;
*py = ClipCase(fx, *px, tx, fy, ty);
break;
case edge_RIGHT:
*px = v->left + v->width - 1;
*py = ClipCase(fx, *px, tx, fy, ty);
break;
}
}
static void ClipEdge(in, out, v, which)
struct polygon *in, *out;
struct viewport *v;
short which;
{
short i, ix, iy;
i = 0;
out->n = 0;
do {
/* case I loop as long as inside */
while (i < in->n && Inside(in->x[i], in->y[i], v, which)) {
polygon_Insert(out, in->x[i], in->y[i]);
i++;
}
if (i < in->n) {
/* case II unless first point is outside */
if (i > 0) {
Intersect(&ix, &iy, in->x[i - 1], in->y[i - 1],
in->x[i], in->y[i], v, which);
polygon_Insert(out, ix, iy);
}
/* case III loop as long as outside */
while (i < in->n && ! Inside(in->x[i], in->y[i], v, which))
i++;
/* case IV outside to inside */
if (i < in->n) {
Intersect(&ix, &iy, in->x[i - 1], in->y[i - 1],
in->x[i], in->y[i], v, which);
polygon_Insert(out, ix, iy);
}
}
} while (i < in->n);
/* Now check if there's a crossing between the last & first points */
if (Inside(in->x[in->n - 1], in->y[in->n - 1], v, which) ^
Inside(in->x[0], in->y[0], v, which)) {
Intersect(&ix, &iy, in->x[in->n - 1], in->y[in->n - 1],
in->x[0], in->y[0], v, which);
polygon_Insert(out, ix, iy);
}
}
void polygon_Clip(p, v)
struct polygon *p;
struct viewport *v;
{
static struct polygon *t = 0; /* temporary polygon, stays around */
if (t == 0)
t = polygon_New();
else
t->n = 0;
ClipEdge(p, t, v, edge_ABOVE);
ClipEdge(t, p, v, edge_BELOW);
ClipEdge(p, t, v, edge_LEFT);
ClipEdge(t, p, v, edge_RIGHT);
}