Re: Polygon

From: Georges Fadel (
Date: Tue Mar 11 1997 - 15:01:38 EET

> From Mon Mar 10 16:33:54 1997
> X-Sender:
> X-Mailer: Windows Eudora Light Version 3.0.1 (32)
> Date: Mon, 10 Mar 1997 16:29:56 -0500
> To:
> From: Atul Damani <>
> Subject: Polygon
> Mime-Version: 1.0
> Sender:
> Hi EveryBody
> I need some help for a project I am working on. The problem is as follows
> Given two simple polygons A & B of any shape with or without holes how do
> we compute the union , intersection and A-B or B-A . If anybody could point
> me towards some good literature or better still some source codeI would
> really appreciate it.
> Thanks a lot
> Atul Damani
The problem is described in the computer graphics books.
If you think about it in two dimensions, you can use the illustration below:

             | A |
             | |
        | | | |
        | ----- |
        | B |

consider the two objects A and B. To get the union, you start on one
border of A that does not belong to B. Move along the border in one direction
until you reach the intersection with B. At this intersection, continue
on the border of B in the same direction (normal pointing to the outside on
either right or left) until you reach again the intersection with A. Jump onto
A, and continue until you end up back at your starting point.

For intersection, you do the same thing, but start at a point common to both

For difference, you start on A for instance, move in a certain direction,
and at the intersection point, change direction on the next object.

If you have holes, the same type logic can be used. For 3D objects, you
can extend this logic to polygons, take their intersection, and decide which
to keep, and which to discard.

Hope this helps.

Georges M. Fadel 
Associate Professor
Mechanical Engineering Department			Tel: (864) 656-5620
Clemson University					Fax: (864) 656-4435
Clemson SC 29634-0921 USA

This archive was generated by hypermail 2.1.2 : Tue Jun 05 2001 - 22:39:25 EEST