|
|
| GeoCommunity Mailing List |
| |
| Mailing List Archives |
| Subject: | [gislist] SUM: simplify polygons to 4 points |
| Date: |
07/13/2005 01:40:01 PM |
| From: |
John Callahan |
|
|
I apologize for the long delay in getting this post out. I had
originally asked this question back in Feb 2005 and never posted the
responses. Thanks to everyone who offered assistance. Well, better
late than never!
Ultimately, we went with the VBA code written by Kirk Kuykendall for
ArcMap found in the ESRI Discussion Forums (see first response below.)
Although the other (some very interesting) methods mentioned below
should work as well. Kirk's code worked great and ran very quick (a
surprise for anything running in ArcMap!) Note that if your irregular
polygons are spaced close together and oriented in just such as way,
then the resulting 4-pt boxes will overlap. Some work will need to be
done on your original and resulting data to minimize the amount of
overlap, if that doesn't suite your needs.
- John
-----Original Message-----
From: John Callahan [mailto:diodata@UDEL.EDU]
Sent: Wednesday, February 23, 2005 10:49 PM
Subject: simplify polygons to 4 points
This might sound strange but I am looking for a tool (extension, algorithm,
etc...) that simplifies multi-vertex (5+) polygons to only 4 points. An
example would be to imagine you had building footprints for a town. And all
you need is a rectangle to represent each building. It would be nice if the
rectangle had the same general orientation and size as the building
footprint. Sounds like an easy enough question but might be very time
consuming to code up from scratch.
Thanks for any advice you can give. Will sum.
- John
Responses (cut-n-paste from emails):
-------------------------------------
Your question is not strange and there is already a solution. See
http://forums.esri.com/Thread.asp?c=93&f=993&t=132642&mc=7
*********************************
If the polygons are relatively rectangle-shaped already, you might just
run a line thinning process over them. Google for the Douglas-Peucker
line thinning algorithm if you need to build a tool for this.
**********************************
a simple algorithm would be retrieving maxX maxY minX minY of the
polygon and then drawing bounding rectangles with same IDs on a new
layer using maxX maxY minX minY as coordinates for rectangle.
**********************************
> a simple algorithm would be retrieving maxX maxY minX minY of the
> polygon and then drawing bounding rectangles with same IDs on a new
> layer using maxX maxY minX minY as coordinates for rectangle.
That's a good initial cut and very efficient. However, it can be
arbitrarily bad. The worst cases occur for long, skinny buildings
angled near 45 degrees. (The bad cases can easily be detected by
computing the ratio of the polygon's area to its bounding box's area. A
small ratio is bad: how small depends on the application.)
This idea can be improved, at some effort, in various ways. For
instance, a similar question was asked on a French GIS list ("Georezo")
four years ago. One solution proposed has worked well: allow the
bounding boxes to be rotated until they achieve a minimum area. (A
minimum-perimeter solution or a minimum-diameter solution would work as
easily.)
If for each building we view the area (or perimeter or diameter) as
being a function of rotation angle, then--because the
area/perimeter/diameter is continuous and varies periodically with
angle, we are guaranteed that a minimum exists. It can be found using
any of a myriad one-dimensional minimum-finders: see nr.com for
instance. This gives a fairly efficient solution, but one has to do the
associated scripting or programming.
To check the practicability of this idea, I implemented the solution as
a set of ArcView 3.x scripts. It works.
Another idea, which I have not implemented, is to compute the second
moments of the polygon, which gives an inertial ellipse. Replace that
ellipse by a rectangle having the same area as the polygon, oriented
with the major axis of the ellipse, and having the same aspect ratio.
In many GIS implementations this will be a faster algorithm because it
only has to visit each polygon vertex once, rather than repeatedly
rotating the polygon while searching for a minimum area.
Yet another is to reformulate the problem: rather than using rectangles,
just convert the polygon (by moving its vertices independently) into one
whose sides are parallel to either the x- or y-axes. (All its vertices
will form 90 degree angles, but often it will have more than four
sides.) This, too, can be formulated as an optimization problem:
minimize some measure of deviations from 90 degrees at all angles,
subject to the constraints that the area must equal the original area,
the centroid must not move, and the total movement of the vertices
should also be small. This is a multidimensional optimization problem,
but it is (relatively
|
|
Sponsored by:
For information
regarding
advertising rates
Click Here!
|
