greg@virgil.UUCP (Greg McRary) (01/28/89)
I am plotting a landmass of 4000 points that I wish to fill. But due to a hardware limitation in the Hewlett-Packard 835 SRX, the maximum size of a polygon is 512 points. Therefore, I wish to find an algorithm to break the 4000 point polygon into sub-polygons. Would someone please forward an algorithm or direct me to a possible source for such an algorithm? Thanks, Greg McRary -- Greg McRary greg@virgil.UUCP EDO Coporation Government Systems Division 814 Greenbrier Circle, Chesapeake Va. 23320
greg@jif.berkeley.edu (Greg) (01/28/89)
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