tim@tslvax.UUCP (07/12/86)
Hello, a long discussion about polygons follows...
I am in the process of developing a routine to reduce a polygon
into a set of trapezoids. What I want to do is this:
Given a closed polygon with N points, I would like to be able to
decompose it into a set of trapezoids that fully describe the
polygon. Each trapezoid have top and bottom segments (or point
in the case of coincedence) that are parallel to each other and
to the X-axis. The vertical segments can be non-parallel.
Example shapes could look like this,
x-------x x x---x
\ \ | | | |
x-------x x---x x
"normal" trap. triangle inverted triangle square(not shown)
A seemingly simple solution is to take the N points of the polygon
and sort them according to Y minima. This would produce a set of
points S1..Sn. To get the first trapezoid, the following simplified
algorithm (mine) is:
1. From point S1, check to see if S2 has the same Y value; if it
does the bottom segment is the segment S1..S2; if it doesn't
the bottom segment is the point S1.
2. The top segment starts with S2, if S2 did not have the same Y
value as S1, else S3 (or S4 if S3 the same Y as S1, S2, S3...).
[The special case of a polygon being collinear is handled here]
The following trapezoids may be found similarly by incrementing
S?. Where this all falls apart is the case of non-concave polygons.
An example would be (excuse the art!):
{points numbered as the input list and the sorted list}
P2,S5 x------------x P3,S6
| |
| x P6,S4 |
| /| |
| / x--------x P4,S3
|/ P5,S2
P1,S1 x
The first trapezoid should be P1/P6. The above alg. would try to
give P1/P5 - no good.
My question is: how do I determine (efficiently) the correct trapezoid, given
the above example. I would GREATLY appreciate any literature ref's or
help. Tear this apart if necessary! I've searched a good bit, but found
little on this particular problem. Thanks very much.
--
...!ihnp4!{duke, akgua}!ucf-cs!tslvax!tim Tim Beres
Tech-Source # subsidiary of Ciprico, Inc.thomas@utah-gr.UUCP (07/16/86)
Some references:
"A Linear Time Algorithm for Triangulating a Point-Visible Polygon",
T.C. Woo and S.Y. Shin, ACM Transactions on Graphics, Vol 4, # 1,
(January 1985).
"Convex Decomposition of Simple Polygons", S.B. Tor and A.E.
Middleditch, ACM TOG, Vol 3, # 4, (October 1984).
"Triangulation and Shape Complexity", B. Chazelle and J. Incerpi,
ACM TOG, Vol 3, #2, (April 1984).
"Triangulating Simple Polygons and Equivalent Problems",
A. Fournier and D.Y. Montuno, ACM TOG, Vol 3, #2, (April 1984).
--
=Spencer ({ihnp4,decvax}!utah-cs!thomas, thomas@utah-cs.ARPA)ph@pixar.UUCP (07/16/86)
Timothy Beres (tim@tslvax.uucp) asks how to decompose a concave polygon
into triangles and trapezoids with horizontal top and bottom.
I think the best approach would be a scan conversion algorithm.
Below is the outline of a simple scan converter for concave polygons which
has worked well for me; it could easily be modified to output trapezoids
and triangles.
To scan convert polygon having n vertices X[i] Y[i]:
create y-sorted array of indices ind[k] into vertex list: Y[ind[k-1]]<Y[ind[k]]
for (k=0, y=ymin; y<=ymax; y++) {
/* maintain list of currently active polygon edges crossing scan line y */
for (; k<n && Y[ind[k]]<=y; k++) {
i = ind[k]
/* invariant: y-1 < Y[i] <= y */
insert or delete edges before and after vertex i (i-1 to i and i to i+1)
from active list if they cross scan line y
}
sort list of m active polygon edges by x of intersection point with line y
for (j=0; j<m; j+=2) {
/* span between j and j+1 is inside, span from j+1 and j+2 is outside */
draw pixels between active[j].x and active[j+1].x
}
}
This scan conversion algorithm requires no special cases for horizontal edges
as many others do.
--
Paul Heckbert
Pixar 415-499-3600
P.O. Box 13719 UUCP: {sun,ucbvax}!pixar!ph
San Rafael, CA 94913 ARPA: ph%pixar.uucp@ucbvax.berkeley.edu