[GRASS5] Q. How do you find the islands for a given area?

[Eric G. Miller]

On Sun, Feb 25, 2001 at 09:25:25AM -0800, Rich Shepard wrote:
> On Sun, 25 Feb 2001, Eric G. Miller wrote:
> 
> > The biggest killer is the search for the closest tie point between the
> > outer polygon and it's inner islands.
> 
> Eric,
> 
>   Do you know which objects are islands in which bounding polygons? If so,
> my suggestion of a short time ago can probably be modified to comparing the
> minimum x values or maximum x values of the two polygons. Then look at the y
> values.

Yes, v.support would have already identified the 1st generation interior
islands for each boundary area.  One thing I did that help enormously
was to remove duplicate points.  I'm working in converted screen
positions, so it's often likely that what would otherwise be two
distinct points in geographic space degenerate into a single point in
screen real estate.

I thought about using delta_x, delta_y vs. a distance calculation, but
I'm not sure that would make the routine any faster.  I don't know how
expensive sqrt() is; maybe there's a cheaper method to find the distance
between two points (other than the algebraic distance formula)?

I do only hit two node pairs once, and I have a short-circuit if the
distance drops below 1.0.  I don't know, but maybe I don't need all of
this extra work.  I just don't want filled space showing up where it
shouldn't.  Now, since I basically create two line segments between the
outer ring and the inner ring that are colinear, would the driver draw
any fill at all along that segment?  If not, then this extra effort is
probably unnecessary.

>   If the relationships among polygons are not known, I wonder if the "plane
> sweep" algorithm will help. This algorithm sweeps from max(y) of a polygon
> through min(y), stopping at every node's y value and checking for
> intersections of this sweep line with polygon edges. Because we cannot
> assume that interior holes line up with the nodes of the bounding polygon,
> the algorithm can be modified to step down a fixed distance each time
> through the loop, and see if there are more than two polygon edges
> intersecting at that distance.

Luckily, I'm relying on v.support having already done this.  Many of
these algorithms are implemented in the vector library already.  It's
just sometimes hard to follow the code.

-- 
Eric G. Miller <egm2 at jps.net>

---------------------------------------- 
If you want to unsubscribe from GRASS Development Team mailing list write to:
minordomo at geog.uni-hannover.de with
subject 'unsubscribe grass5'