gururaj@eniac.seas.upenn.edu (Ravi Gururaj) (02/19/90)
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, PAgordon@photon.tamu.edu (Dan Gordon) (02/20/90)
In article <20549@netnews.upenn.edu> gururaj@eniac.seas.upenn.edu (Ravi Gururaj) writes: >Request: Algorithm to combine two polygons. Note that a very simple modification of the Weiler-Atherton clipping algorithm yields an algorithm that combines the 2 input polygons. It can handle concave polygons and holes as well.
bdb@becker.UUCP (Bruce Becker) (02/23/90)
In article <4279@helios.TAMU.EDU> gordon@photon.tamu.edu (Dan Gordon) writes: |In article <20549@netnews.upenn.edu> gururaj@eniac.seas.upenn.edu (Ravi Gururaj) writes: |>Request: Algorithm to combine two polygons. | |Note that a very simple modification of the Weiler-Atherton clipping algorithm |yields an algorithm that combines the 2 input polygons. It can handle concave |polygons and holes as well. Some details (or pointers to same) might well prove to be fascinating. -- (__) Bruce Becker Toronto, Ontario w \@@/ Internet: bdb@becker.UUCP, bruce@gpu.utcs.toronto.edu `/v/-e UUCP: ...!uunet!mnetor!becker!bdb _/ \_ "They never tell you shit like this in high school!" - J. R. Dobbs
webber@athos.rutgers.edu (Bob Webber) (02/25/90)
In article <4916@becker.UUCP>, bdb@becker.UUCP (Bruce Becker) writes: > In article <4279@helios.TAMU.EDU> gordon@photon.tamu.edu (Dan Gordon) writes: > |In article <20549@netnews.upenn.edu> gururaj@eniac.seas.upenn.edu (Ravi Gururaj) writes: > |>Request: Algorithm to combine two polygons. > | > |Note that a very simple modification of the Weiler-Atherton clipping algorithm > |yields an algorithm that combines the 2 input polygons. It can handle concave > |polygons and holes as well. > > Some details (or pointers to same) > might well prove to be fascinating. I assume the relevant pointer would be: Keven Weiler, Polygon comparison using a graph representation, SIGGRAPH'80, 10-18. This came three years after Weiler & Atherton, Hidden surface removal using polygon clipping, SIGGRAPH'77, 214-222. The 1980 paper begins: All of the information necessary to perform that polygon set operations (union, intersection, and difference) and therefore polygon clipping can be generated by a single application of a process called polygon comparison. ... The algorithm is sufficiently general to compare sets of concave polygons with holes. More than two polygons can be compared at one time; all information for future comparisons of subsets of the original input polygon set is avaiilable from the results of the initial application of the process. The author viewed this as an improvement over the SIGGRAPH'77 approach due to greater simplicity, fewer special cases, etc. When the Weiler-Atherton algorithm was presented in Roger's Procedural Algorithms for Commputer Graphics, the '80 paper is cited as implementation details on the '77 paper. --- BOB (webber@athos.rutgers.edu ; rutgers!athos.rutgers.edu!webber)