[GRASS-dev] New feature (algorithm and / or module) to implent to GRASS (long)

GRASS GIS GRASS GIS developer
1

Greetings GRASS developers,

I'm attending a course in Spatial Data Algorithms
(http://www.tkk.fi/Units/Cartography/courses/maa-123340/), and we are
supposed to implement one algorithm or data structure we have talked
about. I'd like to combine this work with something useful, that is I'd
like to give whatever I implement to GRASS. Partially for altruistic
reasons, partially because I think that coding within the GRASS
environment will make debugging and testing a whole lot easier and more
comfortable. Now I'd like to know which algorithm would you like me to
implement. Here are some candidates:

1. Label position

One of the algorithms we learned about was "A generic Cartographic
Labeling Algorithm" by Edmondson, Christensen, Marks and Shrieber
published in Cartographica, Vol 33 No. 4, 1996 pp. 13-23.

This algorithm of theirs is able to position labels so that they don't
overlap and the labels are also placed in as good a place as possible.
It can handle line-, point- and area labels.

This module would not be a replacement to v.label rather an extension,
but it would have to start out as a separate module (to make it possible
to grade my work). My plan for this would be to output a label file just
like v.label does. After I'm done for school I'd merge this code to be
triggered by a flag in v.label.

2. Line generalization or smoothing

A new module which would do line generalization with one of these algorithms

*) Douglas-Peuker algorithm
*) Reumann-Witkam algorithm
*) Lang simplification algorithm
*) Cromley's Hierarchical algorithm
*) Boyle's forward-looking smoothing algorithm

The most famous of these is the Douglas-Peuker algorithm.

If you would like me to do this one please also indicate which algorithm
you would be most interesting / useful for you.

3. A new simulation/optimization algorithm for least cost path

A new module which would calculate the shortest path from a starting
point to a destination. It would use Dijkstra's algorithm do find the
shortest path in a weighted network. In other words it would treat a
cost surface (generated by r.cost) as a network and then calculate the
shortest path. This differs from r.drain in that r.drain is a local
function, greedy algorithm, whereas this a focal algorithm, that is it
takes not only it's immediate location into account, and finds a global
shortest path.

4. Shortest path in free (vector) space (avoiding obstacles)

This module would take as input a vector map with polygons. These
polygons would be treated as obstacles. It would also take a starting
and end point as input. It would output a vector map containing the
shortest path in free space (this assumes an equal cost surface).
There are 2 different ways to do this calculation:

a) by building a "road network" with the help of building trapezoids
from each corner point of the obstacles.
OR
b) by building a visibility graph and converting it into a weighted
network and running Dijkstra's shortest path on it.

------------------------

If you want more elaboration or have questions on any of the above,
please don't hesitate to ask (on or off list). I'd also like to hear any
other comments you might have.

The time-line for this project is that I will start coding at the latest
on week 13 (most probably week 12), and the project will have a demo
session on the 26th of April, and must be completed by the 10th of May.

Best regards,
--Wolf Bergenheim

--

<:3 )---- Wolf Bergenheim ----( 8:>

2

On Fri, 02 Mar 2007 00:54:03 +0200
Wolf Bergenheim wrote:

Greetings GRASS developers,

I'm attending a course in Spatial Data Algorithms
(http://www.tkk.fi/Units/Cartography/courses/maa-123340/), and we are
supposed to implement one algorithm or data structure we have talked
about. I'd like to combine this work with something useful, that is I'd
like to give whatever I implement to GRASS. Partially for altruistic
reasons, partially because I think that coding within the GRASS
environment will make debugging and testing a whole lot easier and more
comfortable. Now I'd like to know which algorithm would you like me to
implement. Here are some candidates:

Get marks and code for GRASS. What a wonderful idea.

The options all sound interesting. My personal vote would be for label
placement as I see cartography as a major weakness in GRASS and this
would lay part of the foundation for better cartography in GRASS. My
experience in most systems is that when it comes time for output
hours can be wasted in label placement so an algorithm to get one
90% good on that would be a huge time saver for cartographic use. It
would be very useful, if it can be written such that it could be
used by either v.label, ps.map or perhaps a new interface in the
future. In that regard label size in relation to a paper or view size
will need to be taken into account.

My other choices in order of preference are 4, 3, and 2. In regard to
line smoothing I know little about it so I can't state a preference on
algorithm and thus it is my last choice. I've not needed this
functionality before so I've never researched it.

Thanks

T

1. Label position

One of the algorithms we learned about was "A generic Cartographic
Labeling Algorithm" by Edmondson, Christensen, Marks and Shrieber
published in Cartographica, Vol 33 No. 4, 1996 pp. 13-23.

This algorithm of theirs is able to position labels so that they don't
overlap and the labels are also placed in as good a place as possible.
It can handle line-, point- and area labels.

This module would not be a replacement to v.label rather an extension,
but it would have to start out as a separate module (to make it possible
to grade my work). My plan for this would be to output a label file just
like v.label does. After I'm done for school I'd merge this code to be
triggered by a flag in v.label.

2. Line generalization or smoothing

A new module which would do line generalization with one of these algorithms

*) Douglas-Peuker algorithm
*) Reumann-Witkam algorithm
*) Lang simplification algorithm
*) Cromley's Hierarchical algorithm
*) Boyle's forward-looking smoothing algorithm

The most famous of these is the Douglas-Peuker algorithm.

If you would like me to do this one please also indicate which algorithm
you would be most interesting / useful for you.

3. A new simulation/optimization algorithm for least cost path

A new module which would calculate the shortest path from a starting
point to a destination. It would use Dijkstra's algorithm do find the
shortest path in a weighted network. In other words it would treat a
cost surface (generated by r.cost) as a network and then calculate the
shortest path. This differs from r.drain in that r.drain is a local
function, greedy algorithm, whereas this a focal algorithm, that is it
takes not only it's immediate location into account, and finds a global
shortest path.

4. Shortest path in free (vector) space (avoiding obstacles)

This module would take as input a vector map with polygons. These
polygons would be treated as obstacles. It would also take a starting
and end point as input. It would output a vector map containing the
shortest path in free space (this assumes an equal cost surface).
There are 2 different ways to do this calculation:

a) by building a "road network" with the help of building trapezoids
from each corner point of the obstacles.
OR
b) by building a visibility graph and converting it into a weighted
network and running Dijkstra's shortest path on it.

------------------------

If you want more elaboration or have questions on any of the above,
please don't hesitate to ask (on or off list). I'd also like to hear any
other comments you might have.

The time-line for this project is that I will start coding at the latest
on week 13 (most probably week 12), and the project will have a demo
session on the 26th of April, and must be completed by the 10th of May.

Best regards,
--Wolf Bergenheim

--

<:3 )---- Wolf Bergenheim ----( 8:>

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

--
Trevor Wiens
twiens@interbaun.com

The significant problems that we face cannot be solved at the same
level of thinking we were at when we created them.
(Albert Einstein)

3

Hi,

2007/3/1, Wolf Bergenheim <wolf+grass@bergenheim.net>:

[snip]

1. Label position

One of the algorithms we learned about was "A generic Cartographic
Labeling Algorithm" by Edmondson, Christensen, Marks and Shrieber
published in Cartographica, Vol 33 No. 4, 1996 pp. 13-23.

This algorithm of theirs is able to position labels so that they don't
overlap and the labels are also placed in as good a place as possible.
It can handle line-, point- and area labels.

This module would not be a replacement to v.label rather an extension,
but it would have to start out as a separate module (to make it possible
to grade my work). My plan for this would be to output a label file just
like v.label does. After I'm done for school I'd merge this code to be
triggered by a flag in v.label.

+1

[snip]

Regards, Martin

--
Martin Landa <landa.martin@gmail.com> * http://gama.fsv.cvut.cz/~landa *

4

Wolf,

I agree 100% with Trevor; label placement is critical for my work, and
always had to be done in Arc to achieve the desired level of control. I
don't have any preference amongst the other three options, as I never
have need of this functionality in my work.

Whatever your decision, thanks for offering to improve Grass
functionality!

Cheers,

--
Eric Patton
email: epatton@nrcan.gc.ca

-----Original Message-----
From: grass-dev-bounces@grass.itc.it
[mailto:grass-dev-bounces@grass.itc.it] On Behalf Of Trevor Wiens
Sent: Thursday, March 01, 2007 7:35 PM
To: Wolf Bergenheim
Cc: GRASS developers list
Subject: Re: [GRASS-dev] New feature (algorithm and / or
module) to implentto GRASS (long)

Get marks and code for GRASS. What a wonderful idea.

The options all sound interesting. My personal vote would be
for label placement as I see cartography as a major weakness
in GRASS and this would lay part of the foundation for better
cartography in GRASS. My experience in most systems is that
when it comes time for output hours can be wasted in label
placement so an algorithm to get one 90% good on that would
be a huge time saver for cartographic use. It would be very
useful, if it can be written such that it could be used by
either v.label, ps.map or perhaps a new interface in the
future. In that regard label size in relation to a paper or
view size will need to be taken into account.

My other choices in order of preference are 4, 3, and 2. In
regard to line smoothing I know little about it so I can't
state a preference on algorithm and thus it is my last
choice. I've not needed this functionality before so I've
never researched it.

Thanks

Trevor

5

I agree with Trevor about the #1 priority (i.e., labeling). I need to mull
over the other options.

Michael

On 3/1/07 4:35 PM, "Trevor Wiens" <twiens@interbaun.com> wrote:

On Fri, 02 Mar 2007 00:54:03 +0200
Wolf Bergenheim wrote:

Greetings GRASS developers,

I'm attending a course in Spatial Data Algorithms
(http://www.tkk.fi/Units/Cartography/courses/maa-123340/), and we are
supposed to implement one algorithm or data structure we have talked
about. I'd like to combine this work with something useful, that is I'd
like to give whatever I implement to GRASS. Partially for altruistic
reasons, partially because I think that coding within the GRASS
environment will make debugging and testing a whole lot easier and more
comfortable. Now I'd like to know which algorithm would you like me to
implement. Here are some candidates:

Get marks and code for GRASS. What a wonderful idea.

The options all sound interesting. My personal vote would be for label
placement as I see cartography as a major weakness in GRASS and this
would lay part of the foundation for better cartography in GRASS. My
experience in most systems is that when it comes time for output
hours can be wasted in label placement so an algorithm to get one
90% good on that would be a huge time saver for cartographic use. It
would be very useful, if it can be written such that it could be
used by either v.label, ps.map or perhaps a new interface in the
future. In that regard label size in relation to a paper or view size
will need to be taken into account.

My other choices in order of preference are 4, 3, and 2. In regard to
line smoothing I know little about it so I can't state a preference on
algorithm and thus it is my last choice. I've not needed this
functionality before so I've never researched it.

Thanks

T

1. Label position

One of the algorithms we learned about was "A generic Cartographic
Labeling Algorithm" by Edmondson, Christensen, Marks and Shrieber
published in Cartographica, Vol 33 No. 4, 1996 pp. 13-23.

This algorithm of theirs is able to position labels so that they don't
overlap and the labels are also placed in as good a place as possible.
It can handle line-, point- and area labels.

This module would not be a replacement to v.label rather an extension,
but it would have to start out as a separate module (to make it possible
to grade my work). My plan for this would be to output a label file just
like v.label does. After I'm done for school I'd merge this code to be
triggered by a flag in v.label.

2. Line generalization or smoothing

A new module which would do line generalization with one of these algorithms

*) Douglas-Peuker algorithm
*) Reumann-Witkam algorithm
*) Lang simplification algorithm
*) Cromley's Hierarchical algorithm
*) Boyle's forward-looking smoothing algorithm

The most famous of these is the Douglas-Peuker algorithm.

If you would like me to do this one please also indicate which algorithm
you would be most interesting / useful for you.

3. A new simulation/optimization algorithm for least cost path

A new module which would calculate the shortest path from a starting
point to a destination. It would use Dijkstra's algorithm do find the
shortest path in a weighted network. In other words it would treat a
cost surface (generated by r.cost) as a network and then calculate the
shortest path. This differs from r.drain in that r.drain is a local
function, greedy algorithm, whereas this a focal algorithm, that is it
takes not only it's immediate location into account, and finds a global
shortest path.

4. Shortest path in free (vector) space (avoiding obstacles)

This module would take as input a vector map with polygons. These
polygons would be treated as obstacles. It would also take a starting
and end point as input. It would output a vector map containing the
shortest path in free space (this assumes an equal cost surface).
There are 2 different ways to do this calculation:

a) by building a "road network" with the help of building trapezoids
from each corner point of the obstacles.
OR
b) by building a visibility graph and converting it into a weighted
network and running Dijkstra's shortest path on it.

------------------------

If you want more elaboration or have questions on any of the above,
please don't hesitate to ask (on or off list). I'd also like to hear any
other comments you might have.

The time-line for this project is that I will start coding at the latest
on week 13 (most probably week 12), and the project will have a demo
session on the 26th of April, and must be completed by the 10th of May.

Best regards,
--Wolf Bergenheim

--

<:3 )---- Wolf Bergenheim ----( 8:>

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

__________________________________________
Michael Barton, Professor of Anthropology
School of Human Evolution & Social Change
Center for Social Dynamics & Complexity
Arizona State University

phone: 480-965-6213
fax: 480-965-7671
www: http://www.public.asu.edu/~cmbarton

6

My second choices after #1 would be (in ranked order) 3,2,4

Michael

On 3/1/07 3:54 PM, "Wolf Bergenheim" <wolf+grass@bergenheim.net> wrote:

Greetings GRASS developers,

I'm attending a course in Spatial Data Algorithms
(http://www.tkk.fi/Units/Cartography/courses/maa-123340/), and we are
supposed to implement one algorithm or data structure we have talked
about. I'd like to combine this work with something useful, that is I'd
like to give whatever I implement to GRASS. Partially for altruistic
reasons, partially because I think that coding within the GRASS
environment will make debugging and testing a whole lot easier and more
comfortable. Now I'd like to know which algorithm would you like me to
implement. Here are some candidates:

1. Label position

One of the algorithms we learned about was "A generic Cartographic
Labeling Algorithm" by Edmondson, Christensen, Marks and Shrieber
published in Cartographica, Vol 33 No. 4, 1996 pp. 13-23.

This algorithm of theirs is able to position labels so that they don't
overlap and the labels are also placed in as good a place as possible.
It can handle line-, point- and area labels.

This module would not be a replacement to v.label rather an extension,
but it would have to start out as a separate module (to make it possible
to grade my work). My plan for this would be to output a label file just
like v.label does. After I'm done for school I'd merge this code to be
triggered by a flag in v.label.

2. Line generalization or smoothing

A new module which would do line generalization with one of these algorithms

*) Douglas-Peuker algorithm
*) Reumann-Witkam algorithm
*) Lang simplification algorithm
*) Cromley's Hierarchical algorithm
*) Boyle's forward-looking smoothing algorithm

The most famous of these is the Douglas-Peuker algorithm.

If you would like me to do this one please also indicate which algorithm
you would be most interesting / useful for you.

3. A new simulation/optimization algorithm for least cost path

A new module which would calculate the shortest path from a starting
point to a destination. It would use Dijkstra's algorithm do find the
shortest path in a weighted network. In other words it would treat a
cost surface (generated by r.cost) as a network and then calculate the
shortest path. This differs from r.drain in that r.drain is a local
function, greedy algorithm, whereas this a focal algorithm, that is it
takes not only it's immediate location into account, and finds a global
shortest path.

4. Shortest path in free (vector) space (avoiding obstacles)

This module would take as input a vector map with polygons. These
polygons would be treated as obstacles. It would also take a starting
and end point as input. It would output a vector map containing the
shortest path in free space (this assumes an equal cost surface).
There are 2 different ways to do this calculation:

a) by building a "road network" with the help of building trapezoids
from each corner point of the obstacles.
OR
b) by building a visibility graph and converting it into a weighted
network and running Dijkstra's shortest path on it.

------------------------

If you want more elaboration or have questions on any of the above,
please don't hesitate to ask (on or off list). I'd also like to hear any
other comments you might have.

The time-line for this project is that I will start coding at the latest
on week 13 (most probably week 12), and the project will have a demo
session on the 26th of April, and must be completed by the 10th of May.

Best regards,
--Wolf Bergenheim

__________________________________________
Michael Barton, Professor of Anthropology
School of Human Evolution & Social Change
Center for Social Dynamics & Complexity
Arizona State University

phone: 480-965-6213
fax: 480-965-7671
www: http://www.public.asu.edu/~cmbarton

7

Hi Wolf,

indeed, a wonderful list of ideas - it's great to see this.

Like the others I would opt for "label position" (you will gain
most kudos like that in the GFOSS world :slight_smile:

The DP generalization might be rather easily solved using
the GMT/GSHHS code which probably needs "only" an update to
match the GRASS vector structure.

But labeling is a real problem for now.

Good luck,
Markus

8

Well,

it seems that the label placement is what I'm going to implement for
this course. It was also my number one preference. After I'm done I'll
see about starting on another, or perhaps they could be ideas for the
Google SoC? I have copies of those algorithms, so I'll be happy to shear
them too (though they are public knowledge). The algorithms are not that
complex, and so these could be an easy way to introduce people to the
GRASS library.

Anyway I'd like to thank you all on your comments and encouragement. :slight_smile:

--Wolf

--

<:3 )---- Wolf Bergenheim ----( 8:>

9

Hey list,

Is it OK if I create a branch[1] in CVS in the vector directory for
this? That way you all can also observe my progress, and I will have the
safety of version control during this process, and it won't mess the
rest of the build system. Another option would be that I would simply
work in the main trunk of the CVS, since my work will only be localized
to the module I'm working on. What are your thoughts?

--Wolf

[1] What is a branch? A branch is a separate line of development which
will me to work concurrently with the CVS without messing with the main
development branch. The subversion manual has a nice explanation on
branches:
http://svnbook.red-bean.com/en/1.1/svn-book.html#svn-ch-4-sect-1

On 03.03.2007 22:48, Wolf Bergenheim wrote:

Well,

it seems that the label placement is what I'm going to implement for
this course. It was also my number one preference. After I'm done I'll
see about starting on another, or perhaps they could be ideas for the
Google SoC? I have copies of those algorithms, so I'll be happy to shear
them too (though they are public knowledge). The algorithms are not that
complex, and so these could be an easy way to introduce people to the
GRASS library.

Anyway I'd like to thank you all on your comments and encouragement. :slight_smile:

--Wolf

--

<:3 )---- Wolf Bergenheim ----( 8:>

10

Wolf Bergenheim wrote:

Is it OK if I create a branch[1] in CVS in the vector directory for
this? That way you all can also observe my progress, and I will have the
safety of version control during this process, and it won't mess the
rest of the build system. Another option would be that I would simply
work in the main trunk of the CVS, since my work will only be localized
to the module I'm working on. What are your thoughts?

If all of your work will be in new files, just work on the trunk. A
branch is only justified if you intend to make significant,
incompatible changes to existing files.

--
Glynn Clements <glynn@gclements.plus.com>

11

On Saturday 03 March 2007 12:48, Wolf Bergenheim wrote:

Well,

it seems that the label placement is what I'm going to implement for
this course. It was also my number one preference. After I'm done I'll
see about starting on another, or perhaps they could be ideas for the
Google SoC? I have copies of those algorithms, so I'll be happy to shear
them too (though they are public knowledge). The algorithms are not that
complex, and so these could be an easy way to introduce people to the
GRASS library.

Anyway I'd like to thank you all on your comments and encouragement. :slight_smile:

--Wolf

This is great news Wolf! Once your label collision system is complete I think
that it can be tied in nicely with the GRASS-GMT work that has been underway.
Label placement in GMT is done feature-by-feature, so the output from your
module should be a drop-in upgrade to the current use of centroids, etc.

Cheers,

Dylan

--
Dylan Beaudette
Soils and Biogeochemistry Graduate Group
University of California at Davis
530.754.7341