[GRASS5] d.area progress report...

GRASS GRASS developer
1

Oops, wrong list...

Begin forwarded message:

Date: Sun, 20 Jan 2002 19:55:10 -0800
From: Eric G. Miller <egm2@jps.net>
To: GRASS <GRASSLIST@baylor.edu>
Subject: d.area progress report...

Just wanted to say, I've finally made some significant progress
implementing a area w/holes simplifier. Unfortunately, seems
I made an unwarranted assumption about the possibility of
colinear line segments (I didn't think about the fact that
that island/holes may share edges). So, hopefully I can
work in some code for handling colinear segments in the
next week, and then possibly get some of this code into GRASS.

Basically, I'm trying to implement an addition to the display
library which consists of the following three functions:

  D_area_begin() -- Set up for a new area
  D_area_add_ring (struct line_pnts *) -- Add one or more boundaries.
  D_area_finish() -- Process the rings and draw the result to the
                      display.

I'm not sure how to handle the colinear segments problem. I'm
thinking it might be better to have an interface level where the
user passes a Map_info struct, and the id for the area to draw.
I could then weed out the colinear segments by not adding any
edge that didn't have the target area on one of it's sides.
Then the interface would reduce to:

  D_area_plot (struct Map_info *, int);

Later on, I hope to implement a more generic (but more expensive)
variant to handle essentially random polys that may intersect.
I think such a routine won't be linked to the display environment,
but more of an on the fly polygon intersector.

Taking comments... ?

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

2

"Eric G. Miller" wrote:

Oops, wrong list...

Begin forwarded message:

Date: Sun, 20 Jan 2002 19:55:10 -0800
From: Eric G. Miller <egm2@jps.net>
To: GRASS <GRASSLIST@baylor.edu>
Subject: d.area progress report...

Just wanted to say, I've finally made some significant progress
implementing a area w/holes simplifier. Unfortunately, seems
I made an unwarranted assumption about the possibility of
colinear line segments (I didn't think about the fact that
that island/holes may share edges). So, hopefully I can
work in some code for handling colinear segments in the
next week, and then possibly get some of this code into GRASS.

Basically, I'm trying to implement an addition to the display
library which consists of the following three functions:

  D_area_begin() -- Set up for a new area
  D_area_add_ring (struct line_pnts *) -- Add one or more boundaries.
  D_area_finish() -- Process the rings and draw the result to the
                      display.

I'm not sure how to handle the colinear segments problem. I'm
thinking it might be better to have an interface level where the
user passes a Map_info struct, and the id for the area to draw.
I could then weed out the colinear segments by not adding any
edge that didn't have the target area on one of it's sides.
Then the interface would reduce to:

  D_area_plot (struct Map_info *, int);

Later on, I hope to implement a more generic (but more expensive)
variant to handle essentially random polys that may intersect.
I think such a routine won't be linked to the display environment,
but more of an on the fly polygon intersector.

Taking comments... ?

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

_______________________________________________
grass5 mailing list
grass5@grass.itc.it
http://grass.itc.it/mailman/listinfo/grass5

The islands always gives some kind of problems for handling them
because one traditional way is to present them in reverse order (rings)
than the outside polygon.

I though of a structure that may help. This structure define areas
and polygons. An area is made of an external polygon and may have zero
to n islands. Islands are still polygons and areas for others and
thus share boundaries. This structure should reduce the number of funtions
because polygons are always defined the same way; ex. the surface of an
area is the surface of the external polygon minus the surfaces of the
islands polygons. The polygons are only define once eventhough they are
used in more than one area.

Struct Area {
  . . .

  polygonNo : External_polygon_No ;
        int : Nb_Island ;
polygonNo * : List_Polygon_No ;

, . .

}

Struct Polygon {
  polygonNo : Polygon_Number ;
  . . .
        int : Nb_Edge ;
   EdgeNo * : Edge_List ;
  . . .
}

Struct Edge {
     EdgeNo : Edge_Number :
. . .
  segmentNo : Segment_Number ;
       Node : First_Node ; or direction ;
       Node : Last_Node ;
  . . .
}

Struct Segment {
  segmentNo : Segment_Number ;
   vertex * : Vertex_List
  . . .
}

With this structure, areas, islands and even linear features
can share edges. Areas can have islands which are areas that can
also have islands.

This approch depend heavily on lists.

I willing to spend some time to identify the impact on the GRASS
vector format and its topology.

Your comments? Your interest?

--
Robert Lagacé, professeur
Pavillon Comtois
Université Laval
Ste-Foy, Québec, G1K 7P4
tel : (418)-656-2131#2276
Fax : (418)-656-3723
E-mail : lagace@grr.ulaval.ca

3

"Eric G. Miller" wrote:

Basically, I'm trying to implement an addition to the display
library which consists of the following three functions:

  D_area_begin() -- Set up for a new area
  D_area_add_ring (struct line_pnts *) -- Add one or more boundaries.
  D_area_finish() -- Process the rings and draw the result to the
                      display.

I'm not sure how to handle the colinear segments problem. I'm
thinking it might be better to have an interface level where the
user passes a Map_info struct, and the id for the area to draw.
I could then weed out the colinear segments by not adding any
edge that didn't have the target area on one of it's sides.
Then the interface would reduce to:

  D_area_plot (struct Map_info *, int);

Later on, I hope to implement a more generic (but more expensive)
variant to handle essentially random polys that may intersect.
I think such a routine won't be linked to the display environment,
but more of an on the fly polygon intersector.

Taking comments... ?

Eric,
I developped some 20 years ago (before X11) a set of functions for
a graphic card in order to create a graphical GUI similar to the
Suntools one.
Searching in my archives (Yes, I keeped the C code), I found some
functions very useable for d.area : the first adds one boundary,
the second finish the process. the filling routine is passed as
a parameter : my implementation had the possibility to fill with
plain color or with a pattern.
The algorithm is just based on the traversal of elementary segments,
so holes and twisted polygons are managed.
We should adapt the code for d.area (but the commentaries are all in
french :wink:
I have not keeped the code for filling, but It was very hardware
dependant, and I could easely rewrote it. BTW, I think it may be
done in the monitor driver (the drawing function's parameters are
the row number, the start and end column in monitor coordinates).

regards,
--
Michel WURTZ - DIG - Maison de la télédétection
               500, rue J.F. Breton
               34093 MONTPELLIER Cedex 5

4

On Tue, 22 Jan 2002 11:37:35 +0000, Michel Wurtz <mw@teledetection.fr> wrote:

[snip]

Eric,
I developped some 20 years ago (before X11) a set of functions for
a graphic card in order to create a graphical GUI similar to the
Suntools one.
Searching in my archives (Yes, I keeped the C code), I found some
functions very useable for d.area : the first adds one boundary,
the second finish the process. the filling routine is passed as
a parameter : my implementation had the possibility to fill with
plain color or with a pattern.
The algorithm is just based on the traversal of elementary segments,
so holes and twisted polygons are managed.
We should adapt the code for d.area (but the commentaries are all in
french :wink:
I have not keeped the code for filling, but It was very hardware
dependant, and I could easely rewrote it. BTW, I think it may be
done in the monitor driver (the drawing function's parameters are
the row number, the start and end column in monitor coordinates).

It might be useful. I understand already the general scanline
conversion (which GRASS does via G_plot_polygon). However,
G_plot_polygon can not handle eliminating nested areas/holes.
What I'm doing is breaking up the exterior with interiors
such that a set of simple exterior polygons (no holes) are
formed.

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

5

On Monday 21 January 2002 19:10, Robert Lagacé wrote:

"Eric G. Miller" wrote:
> Just wanted to say, I've finally made some significant progress
> implementing a area w/holes simplifier. Unfortunately, seems
> I made an unwarranted assumption about the possibility of
> colinear line segments (I didn't think about the fact that
> that island/holes may share edges). So, hopefully I can
> work in some code for handling colinear segments in the
> next week, and then possibly get some of this code into GRASS.

I don't think that islands can share edges. If area contains two areas
(which share boundaries) only one island (without that shared lines)
is build. That is how v.build works.

But in grass51, we have support for shapefiles for example, and there
you can get any mess of course.

> D_area_plot (struct Map_info *, int);

I would prefer less access to the internal structures. Even instead of
  D_area_add_ring (struct line_pnts *)
I woud suggest
  D_area_add_ring (double *x, double *y, int n_points)
That is more universal.

I though of a structure that may help. This structure define areas
and polygons. An area is made of an external polygon and may have zero
to n islands. Islands are still polygons and areas for others and
thus share boundaries. This structure should reduce the number of funtions
because polygons are always defined the same way; ex. the surface of an
area is the surface of the external polygon minus the surfaces of the
islands polygons. The polygons are only define once eventhough they are
used in more than one area.

With this structure, areas, islands and even linear features
can share edges. Areas can have islands which are areas that can
also have islands.

This approch depend heavily on lists.

I willing to spend some time to identify the impact on the GRASS
vector format and its topology.

I think that this structure is similar to grass. But island is something else
than area. Islands and areas inside other area are not identical!
(See my comments above about shared edges)

You have:
Area { polygon; *polygons(islands) }
Polygon{ *edges }

In grass:
Area{ *edges; *islands }
Island{ *edges }

Radim

6

On Wed, 23 Jan 2002 05:05:59 +0100, Radim Blazek <radim.blazek@wo.cz> wrote:

On Monday 21 January 2002 19:10, Robert Lagacé wrote:
> "Eric G. Miller" wrote:
> > Just wanted to say, I've finally made some significant progress
> > implementing a area w/holes simplifier. Unfortunately, seems
> > I made an unwarranted assumption about the possibility of
> > colinear line segments (I didn't think about the fact that
> > that island/holes may share edges). So, hopefully I can
> > work in some code for handling colinear segments in the
> > next week, and then possibly get some of this code into GRASS.

I don't think that islands can share edges. If area contains two areas
(which share boundaries) only one island (without that shared lines)
is build. That is how v.build works.

It's possible my test for colinearity is in error. But what I'm
referring to is the case where an outer area contains interior
areas which can indeed share edges. In the context of the outer
area, they should be considered as holes. But, what I want to
get is the maximal interior boundary without any shared edges
of interior areas. Make sense?

But in grass51, we have support for shapefiles for example, and there
you can get any mess of course.

> > D_area_plot (struct Map_info *, int);

I would prefer less access to the internal structures. Even instead of
  D_area_add_ring (struct line_pnts *)
I woud suggest
  D_area_add_ring (double *x, double *y, int n_points)
That is more universal.

Yes, I guess so. But I'm tending to lean toward the D_area_plot ()
interface for the functionality I'm currently working on, since the
algorithm I'm using has the assumption that rings intersect or
share edges. I intend to also implement the more generalized
version later (it is slightly more expensive).

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

7

On Tuesday 22 January 2002 17:39, Eric G. Miller wrote:

It might be useful. I understand already the general scanline
conversion (which GRASS does via G_plot_polygon). However,
G_plot_polygon can not handle eliminating nested areas/holes.
What I'm doing is breaking up the exterior with interiors
such that a set of simple exterior polygons (no holes) are
formed.

I use G_plot_polygon in d.vect / g51 and it works (checked also for island
attached to area by line going through that island). What is the problem with
G_plot_polygon?

Radim

8

On Fri, 25 Jan 2002 14:08:43 +0100, Radim Blazek <radim.blazek@wo.cz> wrote:

On Tuesday 22 January 2002 17:39, Eric G. Miller wrote:

> It might be useful. I understand already the general scanline
> conversion (which GRASS does via G_plot_polygon). However,
> G_plot_polygon can not handle eliminating nested areas/holes.
> What I'm doing is breaking up the exterior with interiors
> such that a set of simple exterior polygons (no holes) are
> formed.

I use G_plot_polygon in d.vect / g51 and it works (checked also for island
attached to area by line going through that island). What is the problem with
G_plot_polygon?

Hmm, how did you put the data together? I tried appending island/hole data to
the exterior and got a mess.

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

9

On Friday 25 January 2002 03:05, Eric G. Miller wrote:

On Fri, 25 Jan 2002 14:08:43 +0100, Radim Blazek <radim.blazek@wo.cz> wrote:
> On Tuesday 22 January 2002 17:39, Eric G. Miller wrote:
> > It might be useful. I understand already the general scanline
> > conversion (which GRASS does via G_plot_polygon). However,
> > G_plot_polygon can not handle eliminating nested areas/holes.
> > What I'm doing is breaking up the exterior with interiors
> > such that a set of simple exterior polygons (no holes) are
> > formed.
>
> I use G_plot_polygon in d.vect / g51 and it works (checked also for
> island attached to area by line going through that island). What is the
> problem with G_plot_polygon?

Hmm, how did you put the data together? I tried appending island/hole data
to the exterior and got a mess.

Very simply, from last point of area to first of isle and from last of isle
back to last of area. But I have tested only with simple data and some
problems may occure later. But in that case I would prefer improvement of
G_plot_polygon. You can see the code in d.vect / g51. (And test in grass51)

Radim

10

On Sat, 26 Jan 2002 06:41:23 +0100, Radim Blazek <radim.blazek@wo.cz> wrote:

[snip]

Very simply, from last point of area to first of isle and from last of isle
back to last of area. But I have tested only with simple data and some
problems may occure later. But in that case I would prefer improvement of
G_plot_polygon. You can see the code in d.vect / g51. (And test in grass51)

Yea. I think you got lucky. Try it with non-convex polygons with little
holes spread around in nooks and crannies. Also, don't draw unlabeled
areas, they'll mask the outcome.

I'm thinking G_plot_polygon, or a derivative, could be modified and either
present a three part interface as previously described or a single function
that can take **xs, **ys, and *n for inputs. It would have to process the
edges of each ring (finding the scanline intersections), before moving on
to do the point sort and generating the fill start/stop extents.

What I don't understand is why any of these functions are in libgis. IMHO,
they should all be in the display library (and the display and raster libes
should be merged). One problem encountered is there's more than one method
used for world/screen coordinate mappings, and they aren't consistent.

Anyway, I'll play around with it a little...

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

11

Eric G. Miller wrote:

> Very simply, from last point of area to first of isle and from last of isle
> back to last of area. But I have tested only with simple data and some
> problems may occure later. But in that case I would prefer improvement of
> G_plot_polygon. You can see the code in d.vect / g51. (And test in grass51)

Yea. I think you got lucky. Try it with non-convex polygons with little
holes spread around in nooks and crannies. Also, don't draw unlabeled
areas, they'll mask the outcome.

I'm thinking G_plot_polygon, or a derivative, could be modified and either
present a three part interface as previously described or a single function
that can take **xs, **ys, and *n for inputs. It would have to process the
edges of each ring (finding the scanline intersections), before moving on
to do the point sort and generating the fill start/stop extents.

What I don't understand is why any of these functions are in libgis. IMHO,
they should all be in the display library

G_plot_polygon() isn't restricted to displaying polygons on a monitor.
It's "output" is generated by calling the "move" and "cont" functions
which were previously registered with G_setup_plot(). It could just as
easily be used to "draw" into an array, or into a raster map layer.

(and the display and raster libes should be merged).

The raster library is a low-level interface to the monitor protocol.
Most of the functions simply send their parameters to the monitor,
preceded by an "opcode". The only non-trivial files are:

1. Raster.c, due to R_raster(), which analyses the data then calls
R_raster_char() (if all of the data can be represented as bytes) or
R_raster_int() (otherwise).

2. parse_mon.c, for R_parse_monitorcap() and supporting functions.

3. io.c, for socket/FIFO connection setup, termination and locking,
and the low-level I/O primitives (_send_*, _get_*).

The display library provides an application-level interface, e.g.
automatic scaling according to screen size.

Ultimately I would like to scrap the existing raster library and
monitor protocol altogether, and replace them with something more
flexible (e.g. floating-point geometric coordinates rather than
integer pixel indices, coordinate transformations, etc; IOW, something
more like PostScript or OpenGL).

The display library would initially need to be retained for backwards
compatibility.

One problem encountered is there's more than one method used for
world/screen coordinate mappings, and they aren't consistent.

That is certainly undesirable.

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

12

On Fri, 25 Jan 2002 17:38:35 -0800, "Eric G. Miller" <egm2@jps.net> wrote:

On Sat, 26 Jan 2002 06:41:23 +0100, Radim Blazek <radim.blazek@wo.cz> wrote:

[snip]
> Very simply, from last point of area to first of isle and from last of isle
> back to last of area. But I have tested only with simple data and some
> problems may occure later. But in that case I would prefer improvement of
> G_plot_polygon. You can see the code in d.vect / g51. (And test in grass51)

Yea. I think you got lucky. Try it with non-convex polygons with little
holes spread around in nooks and crannies. Also, don't draw unlabeled
areas, they'll mask the outcome.

I'm thinking G_plot_polygon, or a derivative, could be modified and either
present a three part interface as previously described or a single function
that can take **xs, **ys, and *n for inputs. It would have to process the
edges of each ring (finding the scanline intersections), before moving on
to do the point sort and generating the fill start/stop extents.

FYI, I created a modified G_plot_polygon with arguments:
  
    double **xs, -- The x's for each polygon (xs[0], xs[1], etc...)
    double **ys, -- The y's for each polygon (ys[0], ys[1], etc...)
    int *npnts, -- Number of points per polygon
    int ring -- Number of rings/polygons

On my hardcase test cover (geology of California with hundreds of
islands per area), it worked nicely. I will be committing it soon,
after syncing CVS with head, and then will fix d.area (including
the category issue).

I think we need a discussion on how to handle vector drawing
specs. There are several things to consider compared to
rasters. We should consider point styles, line styles, and
area fill styles. We may not have the infrastructure to
do all the drawing styles we'd like at present, but I'd like
to consider building an infrastructure for specify such things
as fill type: solid, pixmap, hatchured; line style: width,
dashing, color, end & join styles, complex line styles; etc...

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