|
|
| GeoCommunity Mailing List |
| |
| Mailing List Archives |
| Subject: | Re: [gislist] simplify polygons to 4 points |
| Date: |
02/24/2005 08:35:01 AM |
| From: |
Quantitative Decisions |
|
|
At 10:41 AM 2/24/2005 -0800, "viktoras" wrote:
>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) easily solved and leads to very good looking solutions. I
have also implemented this one on an experimental basis to test the effects
of different formulations: I do not have an automatic solution.
I will be interested in hearing of other formulations and proposed solutions.
--Bill Huber
Quantitative Decisions
_______________________________________________
gislist mailing list
gislist@lists.geocomm.com
http://lists.geocomm.com/mailman/listinfo/gislist
_________________________________
This list is brought to you by
The GeoCommunity
http://www.geocomm.com/
Get Access to the latest GIS & Geospatial Industry RFPs and bids
http://www.geobids.com
|
|
Sponsored by:
For information
regarding
advertising rates
Click Here!
|
