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

GRASS GRASS developer
1

Okay, haven't finished implementing it yet, but I managed to try
writing up how I'm attempting to do it...

(bring out the way-back machine about d.area and handling
holes as well as clipping...).

I think I understand an algorithm that should produce the
desired results. But I haven't yet finished implementing it.
Given, it might take me a while to get it done, I thought I'd
try to explain it, and if any enterprising soul wants to
give it a crack... just try to get it done before I do :wink:

I've posted a little write-up and some poorly done graphics
that try to illustrate the process at:

http://pweb.jps.net/~egm2/grass/algorithms/poly_simplify/algorithm.html

Perhaps it will make sense to someone? Perhaps it is flawed?
Perhaps I will figure out how to get working code for it...?

With a little bit more thought, I think the general concept
described can be extended/modified for general overlay
operations...

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

2

hi
I guess this is to enable functions like R_polygon_abs
to handle islands?
--alex

--- "Eric G. Miller" <egm2@jps.net> wrote:

Okay, haven't finished implementing it yet, but I
managed to try
writing up how I'm attempting to do it...

(bring out the way-back machine about d.area and
handling
holes as well as clipping...).

I think I understand an algorithm that should
produce the
desired results. But I haven't yet finished
implementing it.
Given, it might take me a while to get it done, I
thought I'd
try to explain it, and if any enterprising soul
wants to
give it a crack... just try to get it done before I
do :wink:

I've posted a little write-up and some poorly done
graphics
that try to illustrate the process at:

http://pweb.jps.net/~egm2/grass/algorithms/poly_simplify/algorithm.html

Perhaps it will make sense to someone? Perhaps it
is flawed?
Perhaps I will figure out how to get working code
for it...?

With a little bit more thought, I think the general
concept
described can be extended/modified for general
overlay
operations...

--
Eric G. Miller <egm2@jps.net>
_______________________________________________
grass5 mailing list
grass5@grass.itc.it
http://grass.itc.it/mailman/listinfo/grass5

__________________________________________________
Do You Yahoo!?
Check out Yahoo! Shopping and Yahoo! Auctions for all of
your unique holiday gifts! Buy at http://shopping.yahoo.com
or bid at http://auctions.yahoo.com

3

Alex Shevlakov wrote:

I guess this is to enable functions like R_polygon_abs
to handle islands?

R_polygon_abs wouldn't be the right place for it. However, it would
allow d.area to tesellate the shape into a set of convex polygons,
each of which would be passed to R_polygon_abs.

The input to R_polygon_abs is just a list of points, which implies a
single continuous path. Complex shapes (with islands) comprise
multiple paths, requiring either a list of lists of points, or
distinct moveto/lineto operations (as in PostScript).

Also, doesn't v.report need something like this for area computations?

--
Glynn Clements <glynn.clements@virgin.net>

4

On Tue, 11 Dec 2001 15:48:18 +0000, Glynn Clements <glynn.clements@virgin.net> wrote:

Alex Shevlakov wrote:

> I guess this is to enable functions like R_polygon_abs
> to handle islands?

R_polygon_abs wouldn't be the right place for it. However, it would
allow d.area to tesellate the shape into a set of convex polygons,
each of which would be passed to R_polygon_abs.

To clarify, the method I'm trying to implement would not guarantee
convex polygons as a result, only simple polygons.

[snip]

Also, doesn't v.report need something like this for area computations?

I wouldn't think this is necessary for area computations. For area you
can calculate the exterior and any interiors and then subtract the
interiors from the exterior. Haven't done it myself, but I'm pretty
sure this is already a capability available in GRASS. There are some
tricky methods for the computation that do summation of parts with
positive/negative areas to get the correct area of a simple polygon.

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

5

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).

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

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

--alex

--- "Eric G. Miller" <egm2@jps.net> wrote:

Okay, haven't finished implementing it yet, but I
managed to try
writing up how I'm attempting to do it...

(bring out the way-back machine about d.area and
handling
holes as well as clipping...).

I think I understand an algorithm that should
produce the
desired results. But I haven't yet finished
implementing it.
Given, it might take me a while to get it done, I
thought I'd
try to explain it, and if any enterprising soul
wants to
give it a crack... just try to get it done before I
do :wink:

I've posted a little write-up and some poorly done
graphics
that try to illustrate the process at:

http://pweb.jps.net/~egm2/grass/algorithms/poly_simplify/algorithm.html

Perhaps it will make sense to someone? Perhaps it
is flawed?
Perhaps I will figure out how to get working code
for it...?

With a little bit more thought, I think the general
concept
described can be extended/modified for general
overlay
operations...

--
Eric G. Miller <egm2@jps.net>
_______________________________________________
grass5 mailing list
grass5@grass.itc.it
http://grass.itc.it/mailman/listinfo/grass5

__________________________________________________
Do You Yahoo!?
Send FREE video emails in Yahoo! Mail!
http://promo.yahoo.com/videomail/

6

On Sun, 6 Jan 2002 03:46:45 -0800 (PST), Alex Shevlakov <sixote@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@jps.net>