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

[Rich Shepard]

On Sat, 24 Feb 2001, Eric G. Miller wrote:

> I've been looking into the d.area island drawing problem.  Anyway, I'm
> trying to figure out how you find out:
>
>   For a given area A:
>     How many interior boundary islands does it have?
>     How do I get line_pnts struct(s) for just these interior islands?

Eric,

  Funny that you mention this. In order to better help David with the
v.in.mif (and v.in.shape) modules, I've discovered the subject I need to
learn: computational geometry. My buddy in Boulder (CO) pointed me to Joseph
O'Rourke's book, "Computational Geometry in C", 2nd Edition; I bought a copy
last night at Powell's Technical Books in Portland. This book contains the
answer to these questions and a bunch of other vector-related questions.

  Briefly, read the nodes of the polygons into a structure (he uses a
doubly-linked, circular list for a number of reasons). If you walk the
vertices (nodes) in order, v0 -> v1 -> v2 ... -> v(n-1), the interior of the
polygon will be to your left when the nodes are traversed counter-clockwise.
If traversing the nodes in a clockwise direction, then the interior of the
polygon is to your right. By knowing on which edge you're walking, you can
tell if you're walking on the polygon external boundary or an internal
boundary defining a hole. Clear as mud, right?

  The clockwiseness he uses is the opposite of that used by ESRI on their
shapefiles. I'd stick with his approach for it permits the computation of
many polygon attributes.

  While I'm in the first chapter still (it's toward the end where he
discusses implementation rather than just the math), I now understand how to
easily determine if two lines intersect (what he calls "proper
intersection") or if one line ends with a point collinear on another line
("improper intersection") and how to triangulate polygons and calculate
polygon areas. Cool stuff! I've been curious about this for more than a
decade.

  The next stage (eventually) will be to learn some graph theory algorithms
so we can add network analyses to GRASS using vectors.

  Anyway, perhaps your local library or geek book store has a copy of
O'Rourke's book (quite reasonably priced, too, for today's technical book
prices), and you can read about it for yourself. Otherwise, you'll have to
wait until I finish reading it. :-)

Rich

Dr. Richard B. Shepard, President

                       Applied Ecosystem Services, Inc. (TM)
              Making environmentally-responsible mining happen. (SM)
                       --------------------------------
            2404 SW 22nd Street | Troutdale, OR 97060-1247 | U.S.A.
 + 1 503-667-4517 (voice) | + 1 503-667-8863 (fax) | rshepard at appl-ecosys.com


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