Xref: utzoo comp.graphics:4249 comp.sys.hp:1493
Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!ames!pasteur!agate!math!greg
From: greg@jif.berkeley.edu (Greg)
Newsgroups: comp.graphics,comp.sys.hp
Subject: Re: Algorithm to divide polygon into sub-polygons needed
Message-ID: <19608@agate.BERKELEY.EDU>
Date: 28 Jan 89 01:44:17 GMT
References: <1979@virgil.UUCP>
Sender: usenet@agate.BERKELEY.EDU
Reply-To: greg@math.Berkeley.EDU (Greg)
Organization: U.C. Berkeley
Lines: 29

In article <1979@virgil.UUCP> greg@virgil.UUCP (Greg McRary) writes:
>I wish to find an algorithm to break [a] 4000 point polygon
>into [512 point] sub-polygons.

With this many points, you don't need to worry about finding sub-polygons
with the same vertices as the original big polygon.  Thus, you can cut
the polygon into pieces in any convenient way.  The following procedure
will work as well as any:

1) Sort the vertices according to x-coordinate.
2) Identify vertical lines that divide the vertices into groups smaller
than about 500 or so.
3) Call the first vertical line L.  Identify the edges of the polygon
that intersect L (the endpoints of such an edge will be on opposite sides
of L).  Find where the edges intersect L.
4) Sort the edges by height of intersection with L, and connect them
in pairs.  This will divide the original polygon into two sub-polygons,
each of which will in all likelihood have 512 edges or less.
5) Repeat steps 4) and 5) on the subpolygons as necessary using the
other vertical lines, or new ones.

This algorithm will terminate as long as no vertical line intersects
the original polygon more than 256 times.  If, by (monumental) bad luck
or by design, the polygons in this algorithm are getting more vertices
rather than fewer, you can pick lines with random orientation instead
of vertical orientation, or use a more enlightened algorithm that doesn't
create new vertices.
---
Greg