[comp.lang.c] Polygon operations?

sa1z+@andrew.cmu.edu (Sudheer Apte) (01/10/91)

Hi,

I need (pointers to) a geometric modeller or other program that can do
general 2-d polygon intersections, differences, additions, etc. based
on any representation (it doesn't have to be able to display the
polygons---I am willing to take real number coordinates and display
them myself).  This is needed for an application being written in C,
so I would really appreciate C routines that can do this.

Ideally, I would like the modeller to have function calls like:

	polylist add_poly (polylist a, polylist b);

where the type "polylist" is a data structure for a list of polygons
suitably defined in terms of arrays of coordinates, etc.

In full generality, polygonal intersection and similar operations are
not trivial to implement, so I'd rather not do it if it has already
been done properly.

Thanks in advance for pointers and suggestions.  If there is interest,
I will summarize.  If there is a more appropriate newsgroup than
comp.graphics and comp.lang.c, please let me know.

Thanks,

	Sudheer.
------------------
...{uunet|harvard}!andrew.cmu.edu!sa1z
...sa1z%andrew@CARNEGIE.BITNET

heroux@cemmva.cem.msu.edu (Brett Heroux) (01/11/91)

In article <4bWuKJW00VpMIo80Z=@andrew.cmu.edu>, sa1z+@andrew.cmu.edu (Sudheer Apte) writes:
>
>I need (pointers to) a geometric modeller or other program that can do
>general 2-d polygon intersections, differences, additions, etc. based
>on any representation

Polygon intersection is usefully reduced to segment(line) intersections. I may
be able to find the code, if I can I'll e-mail, but the method goes:
Given: segment a from (x1,y1) to (x2,y2)
  and  segment b from (x3,y3) to (x4,y4)
Define: parametric equations a x = x1 + t(x2-x1) and y = y1 + t(y2-y1)
  and   "                  " b x = x3 + s(x4-x3) and y = y3 + s(y4-y3)
Find: s and t
If 0<s<1 and 0<t<1, the segments intersect, the polygons intersect.