[GRASS5] Polygon Simplification... (d.area revisited)

[Eric G. Miller]

On Sun, 6 Jan 2002 03:46:45 -0800 (PST), Alex Shevlakov <sixote at yahoo.com> wrote:

> Hi,
> 
> I have chosen areas with holes and no intersections to
> test d.area; it now both outlines and fills the areas
> correctly which is due to the major code add-on done
> by Eric since release 1.5 to handle isles
> (screenpoly.c functions).

Yes. I wrote that.

> Sorry, I can not gather why another algorytm is needed
> to handle isles, or that new one is for clipping only?

Because it has terrible time complexity (try it on a
big map with lots of holes and a large numbers of
vertices).  It is a brute force implementation, and
I think it has error conditions where it may never
return. Also, there's some disagreement with d.vect
about screen mapping.  Furthermore, there's still a
need for window clipping.

> I'm thinking about cloning part of the new d.area
> code into d.what.v.pg to handle drawing and filling
> isles correctly.

Please don't clone the old code.  It never was quite
complete, and has an error in the "cats" handling
(oops, need a cats lookup for area id).

My intention, is to write a rather generic routine
suitable for drawing polygons with holes, and then
incorporate it into the display library.  I'm brushing
up on my computational geometry, so I can put together
a fast routine.  I expect to model the interface
somewhat after OpenGL, with begin/end parts, so it's
easy to add the exterior, then any interiors. 

For polygon drawing, there also needs to be a separation
between the fill drawing vs. the boundary.  I haven't
decided if one set of routines should do both, or if
the lines should be drawn only after all the area fill
has been done.  I lean toward the latter, with the
caller deciding which to do (fill must come first
so boundaries don't get clobbered).

I'm getting closer to an implementation, but don't
expect one right away.  I'm still learning as I go.
There are several parts to implement, and I have
the least experience with the necessary tree 
structure (one of height sorted, 2-3, or red black
-- height sorted seems the best fit).

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