Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!ucbvax!decwrl!polyslo!vlsi3b15!vax1.cc.lehigh.edu!netnews.upenn.edu!eniac.seas.upenn.edu!gururaj
From: gururaj@eniac.seas.upenn.edu (Ravi Gururaj)
Newsgroups: comp.graphics
Subject: Combining two Polygons - Algorithm??
Message-ID: <20549@netnews.upenn.edu>
Date: 19 Feb 90 09:29:36 GMT
Sender: news@netnews.upenn.edu
Reply-To: gururaj@eniac.seas.upenn.edu (Ravi Gururaj)
Distribution: usa
Organization: University of Pennsylvania
Lines: 52

Request: Algorithm to combine two polygons.
I am looking for a 'C' or pseudo code algorithm that will look
like:

CombinePolygon(POINT aX[], POINT aY, int aN, POINT bX[], POINT bY[], int bN,
                     POINT cX[], POINT cY[], int cNum);

  aX, aY : x & y point arrays for the first polygon.
  aNum : number of points in the first polygon.
  bX, bY : x & y point arrays for the second polygon.
  bNum : number of points in the second polygon.
  cX, cY : x & y point arrays for combined polygon.
  cNum : number of points in the combined polygon.

The objective of the function is to remove all the line segments that are
common to both polygons. For example:

        d       3                       d       3
    ------------------              ------------------ 
    |       |        |              |                |
  a |     c | 4      | 2     ==>  a |                | 2
    | PolyA | PolyB  |              |      PolyC     |
    |       |        |              |                |
    ------------------              ------------------
       b        1                      b        1

PolyA = a,b,c,d  +  PolyB = 1,2,3,4    ==>    PolyC = a,b,1,2,3,d

Combining Polygons A & B will result in Polygon C. The common segments c & 4
will be removed from the combined polygon. 

Please note that the polygons I am dealing with are very complex (including
internal polygons, convex, concave etc...). The only thing I may be able to
assume about the polygons MAY be that they are in clockwise order. Also the 
polygons may touch in more than one distinct place. An algorithm that can
deal with integer or float points is ok - I can represent the polygons quite
accurately in either form.

Could someone on the network please point me to a algorithm/book or any
actual source code that may do this. 

I am sorry if this is a common request to the group. If any others are also
interested in the algorithm - let me know - when I finally do find and code
the algorithm - I could email you a copy.

Thanks in advance,

Ravi

Ravi Gururaj
University of Pennsylvania.
Pennsylvaina, PA