[GRASS-dev] Adding hexagonal rasters to GRASS

GRASS GIS GRASS GIS developer
,
1

Dear friends,

I presented hex-utils at the GISTAM conference in April, here is the video:

https://www.youtube.com/watch?v=uLO4HDCVBp0

This was before the QGis plug-in was completed, but for the rest it is pretty much the same story.

Before the FOSS4G-E, in my mind the next phase of the project would be to code the abstraction functionalities in C++ (or C), to make it fully portable and easier to use with other languages, particularly Java. After that would then come a map algebra and spatial analysis.

But as Luca said during the Q/A, it is probably better to start outright within GRASS. This will require the abstraction of the raster concept, together with operations like neighbourhood, number of neighbours, distance to neighbours, etc. With that done most of the raster modules would function the same way for squared and hexagonal rasters. Still, this would require a complete revision of all the raster modules.

For a programmer, the main difference between hexagonal and squared rasters is the cell addressing system: with hexagons the axis are not orthogonal. However, it is possible to store an hexagonal raster in a bi-dimensional array like you would store a squared raster. I wrote an article last year with full details on the HexASCII file format and how to deal with hexagonal cell adressing, but it is still under review. I can not send it to the list, please send me a personal message if you wish to read it.

It would be great if we can take this forward. I imagine it is a load of work, but it will make GRASS an even more awesome system :wink:

All the best.

···

–

Luís Moreira de Sousa

Im Grund 6

CH-8600 Dübendorf

Switzerland

Phone: +41 (0)79 812 62 65

Email: luis.de.sousa@protonmail.ch

URL: https://sites.google.com/site/luismoreiradesousa

2

Dear Luís,

···

On Sun, Jul 23, 2017 at 11:50 AM, Luí­s Moreira de Sousa <luis.de.sousa@protonmail.ch> wrote:

I presented hex-utils at the GISTAM conference in April, here is the video:

https://www.youtube.com/watch?v=uLO4HDCVBp0

But as Luca said during the Q/A, it is probably better to start outright within GRASS. This will require the abstraction of the raster concept, together with operations like neighbourhood, number of neighbours, distance to neighbours, etc. With that done most of the raster modules would function the same way for squared and hexagonal rasters. Still, this would require a complete revision of all the raster modules.

Sounds good. I think there is a way in GRASS GIS to make it revolutionary and at the same time keeping everything in place. See below.

For a programmer, the main difference between hexagonal and squared rasters is the cell addressing system: with hexagons the axis are not orthogonal.

If there would be a way, like the abstraction you mentioned, which would, e.g. make the current rectangle-only code work with hexagonal data (e.g. by presenting converting hexagons as rectangles on the fly), that would be helpful, but on the other side, I don’t think it is necessarily the first step if there is an other way how to connect with rectangular rasters (even if it involves converting back and forth or less precision).

However, it is possible to store an hexagonal raster in a bi-dimensional array like you would store a squared raster.

That would help the implementation and hopefully also the integration and adoption, again see below.

I wrote an article last year with full details on the HexASCII file format and how to deal with hexagonal cell adressing, but it is still under review. I can not send it to the list, please send me a personal message if you wish to read it.

If you can share it, I would like to see it.

It would be great if we can take this forward. I imagine it is a load of work, but it will make GRASS an even more awesome system :wink:

Load of work and resulting code to maintain should be part of the consideration. Using existing functionality (algorithms, formats) and integrating with it will be crucial for both users and developers alike.

thank you, this is very informative and exiting!

Can you implement it this as a layer on top of existing functionality in GRASS GIS? There is several examples and concepts in GRASS GIS of this. For example, the temporal (t.) modules work with series of rasters and vectors registered as spatio-temporal datasets and the image processing (i.) modules work with series of rasters registered as imagery groups and subgroups (“multiband image”). In both cases standard storage of rasters (or vectors) is used, so there is no new backend format in GRASS database except for the additional data (metadata) needed for these tools. What is important is that you can work with the existing tools on the data handled by temporal or imagery modules, i.e. you can use the existing tools to implement the new tools (e.g. average of spatio-temporal raster dataset can be implemented through a tool for average of multiple rasters) and if the imagery or temporal modules miss specific functionality you need, you can fallback to the standard modules (e.g. loop over members of imagery group).

I was thinking that the hexagonal rasters can be implemented in GRASS GIS using two rasters which would be shifted against each other, but aligned with the hexagonal cells, i.e. two rectangular rasters making up one hexagonal raster/grid (but I didn’t test that or examined that more). After seeing your video with slightly rotated hexagonal grid, I’m thinking if it is possible to fit only one raster but with different resolution to the hexagons. The idea is that 1) you don’t need another storage format and 2) you can use the raw data without the hexagon-aware algorithms. Of course we can settle just with re-using the storage format (1).

Another approach is to threat hexagonal rasters/grids as another basic data type next to raster maps, vector maps, and 3D raster maps (in GRASS GIS there are also the aforementioned spatio-temporal datasets and imagery groups). They would be connected to the rest where it makes sense. For example, (2D) rasters and 3D rasters are independent, but there is also several connections: there are modules for conversion in between the two types, a lot of code for handling colors is the same, and computational region applies to both and is handled from the same module.

If I may ask, what would you need to create a prototype and what do you envision as a final goal?

Best,

Vaclav

3

Hi there Vaclav, an assorted reaction to your remarks:

  • Hexagonal rasters have to be integrated as new data type, there are too many differences to a squared raster to make it practical otherwise. Note however, that I do not know the code in GRASS, so you suggestions may still make sense.

  • The abstraction of the raster data type is the key to integrate hexagons with the least work possible. In the modules themselves, this would mean transforming segments where cell neighbourhood or geometry may be hard-coded. E.g. a loop like:

for(i=0; i<8; i++)

must be transformed into something like:

for(i=0; i<NUM_NEIGHBOURS; i++)

  • In theory, all raster modules can function in exactly the same way with both square and hexagons if all geometric and neighbourhood methods/properties/functions are abstracted correctly.

  • The risk here is breaking the existing r. modules by implementing the raster abstraction. Perhaps some sort of transition may be devised to avoid it

···
  • On my side, the next step is to dive into the code and study how practical these ideas may be. But please put forward your ideas in any case.

Cheers.

–

Luís Moreira de Sousa

Im Grund 6

CH-8600 Dübendorf

Switzerland

Phone: +41 (0)79 812 62 65

Email: luis.de.sousa@protonmail.ch

URL: https://sites.google.com/site/luismoreiradesousa

-------- Original Message --------

Subject: Re: [GRASS-dev] Adding hexagonal rasters to GRASS

Local Time: July 24, 2017 1:19 AM

UTC Time: July 23, 2017 11:19 PM

From: wenzeslaus@gmail.com

To: Luí­s Moreira de Sousa luis.de.sousa@protonmail.ch

grass-dev@lists.osgeo.org grass-dev@lists.osgeo.org

Dear Luís,

On Sun, Jul 23, 2017 at 11:50 AM, Luí­s Moreira de Sousa <luis.de.sousa@protonmail.ch> wrote:

I presented hex-utils at the GISTAM conference in April, here is the video:

https://www.youtube.com/watch?v=uLO4HDCVBp0

thank you, this is very informative and exiting!

But as Luca said during the Q/A, it is probably better to start outright within GRASS. This will require the abstraction of the raster concept, together with operations like neighbourhood, number of neighbours, distance to neighbours, etc. With that done most of the raster modules would function the same way for squared and hexagonal rasters. Still, this would require a complete revision of all the raster modules.

Sounds good. I think there is a way in GRASS GIS to make it revolutionary and at the same time keeping everything in place. See below.

For a programmer, the main difference between hexagonal and squared rasters is the cell addressing system: with hexagons the axis are not orthogonal.

If there would be a way, like the abstraction you mentioned, which would, e.g. make the current rectangle-only code work with hexagonal data (e.g. by presenting converting hexagons as rectangles on the fly), that would be helpful, but on the other side, I don’t think it is necessarily the first step if there is an other way how to connect with rectangular rasters (even if it involves converting back and forth or less precision).

However, it is possible to store an hexagonal raster in a bi-dimensional array like you would store a squared raster.

That would help the implementation and hopefully also the integration and adoption, again see below.

I wrote an article last year with full details on the HexASCII file format and how to deal with hexagonal cell adressing, but it is still under review. I can not send it to the list, please send me a personal message if you wish to read it.

If you can share it, I would like to see it.

It would be great if we can take this forward. I imagine it is a load of work, but it will make GRASS an even more awesome system :wink:

Load of work and resulting code to maintain should be part of the consideration. Using existing functionality (algorithms, formats) and integrating with it will be crucial for both users and developers alike.

Can you implement it this as a layer on top of existing functionality in GRASS GIS? There is several examples and concepts in GRASS GIS of this. For example, the temporal (t.) modules work with series of rasters and vectors registered as spatio-temporal datasets and the image processing (i.) modules work with series of rasters registered as imagery groups and subgroups (“multiband image”). In both cases standard storage of rasters (or vectors) is used, so there is no new backend format in GRASS database except for the additional data (metadata) needed for these tools. What is important is that you can work with the existing tools on the data handled by temporal or imagery modules, i.e. you can use the existing tools to implement the new tools (e.g. average of spatio-temporal raster dataset can be implemented through a tool for average of multiple rasters) and if the imagery or temporal modules miss specific functionality you need, you can fallback to the standard modules (e.g. loop over members of imagery group).

I was thinking that the hexagonal rasters can be implemented in GRASS GIS using two rasters which would be shifted against each other, but aligned with the hexagonal cells, i.e. two rectangular rasters making up one hexagonal raster/grid (but I didn’t test that or examined that more). After seeing your video with slightly rotated hexagonal grid, I’m thinking if it is possible to fit only one raster but with different resolution to the hexagons. The idea is that 1) you don’t need another storage format and 2) you can use the raw data without the hexagon-aware algorithms. Of course we can settle just with re-using the storage format (1).

Another approach is to threat hexagonal rasters/grids as another basic data type next to raster maps, vector maps, and 3D raster maps (in GRASS GIS there are also the aforementioned spatio-temporal datasets and imagery groups). They would be connected to the rest where it makes sense. For example, (2D) rasters and 3D rasters are independent, but there is also several connections: there are modules for conversion in between the two types, a lot of code for handling colors is the same, and computational region applies to both and is handled from the same module.

If I may ask, what would you need to create a prototype and what do you envision as a final goal?

Best,

Vaclav

4

Dear Luí­s,
this sounds very interesting, especially the improvement for surface
flow algorithms using hexagonal grids and other mass conservation
approaches like groundwater flow, heat flow, ... .

I agree with Vaclav on this topic. I think hexagonal grids can be
stored using the compressed row based approach of GRASS GIS. In
addition the rotation of the hexagonal grid may be stored in the
metadata. The question is, do we need rotated hexagonal grids at all
or do horizontal hexagonal grids do the job? In case of "horizontal"
hexagonal grids the compressed row approach would be very fast for
horizontal access. Indexing can be easily mapped to row/column access
using the "odd-r" horizontal layout. The existing on the fly nearest
neighbor resampling algorithms will have an offset of half a cell for
odd row indices when interacting with normal raster layers in existing
modules, so they must be adjusted.
Neighborhood operations must be implemented on top of the existing
row/col approach of GRASS. All algorithms that make cell neighbor
computations must be modified. The existing r.mapcalc neighbor
operators r[y] can be reused in case of odd-r horizontal layout.
Conversion between regular grids and hexagonal grids must be
implemented. Resampling algorithms must be modified. Rendering of
hexagonal grids must be implemented in the display library. Plenty of
work do do. :slight_smile:

Best regards
Sören

2017-07-24 1:19 GMT+02:00 Vaclav Petras <wenzeslaus@gmail.com>:

Dear Luís,

On Sun, Jul 23, 2017 at 11:50 AM, Luí­s Moreira de Sousa
<luis.de.sousa@protonmail.ch> wrote:

I presented hex-utils at the GISTAM conference in April, here is the
video:
https://www.youtube.com/watch?v=uLO4HDCVBp0

thank you, this is very informative and exiting!

But as Luca said during the Q/A, it is probably better to start outright
within GRASS. This will require the abstraction of the raster concept,
together with operations like neighbourhood, number of neighbours, distance
to neighbours, etc. With that done most of the raster modules would function
the same way for squared and hexagonal rasters. Still, this would require a
complete revision of all the raster modules.

Sounds good. I think there is a way in GRASS GIS to make it revolutionary
and at the same time keeping everything in place. See below.

For a programmer, the main difference between hexagonal and squared
rasters is the cell addressing system: with hexagons the axis are not
orthogonal.

If there would be a way, like the abstraction you mentioned, which would,
e.g. make the current rectangle-only code work with hexagonal data (e.g. by
presenting converting hexagons as rectangles on the fly), that would be
helpful, but on the other side, I don't think it is necessarily the first
step if there is an other way how to connect with rectangular rasters (even
if it involves converting back and forth or less precision).

However, it is possible to store an hexagonal raster in a bi-dimensional
array like you would store a squared raster.

That would help the implementation and hopefully also the integration and
adoption, again see below.

I wrote an article last year with full details on the HexASCII file format
and how to deal with hexagonal cell adressing, but it is still under review.
I can not send it to the list, please send me a personal message if you wish
to read it.

If you can share it, I would like to see it.

It would be great if we can take this forward. I imagine it is a load of
work, but it will make GRASS an even more awesome system :wink:

Load of work and resulting code to maintain should be part of the
consideration. Using existing functionality (algorithms, formats) and
integrating with it will be crucial for both users and developers alike.

Can you implement it this as a layer on top of existing functionality in
GRASS GIS? There is several examples and concepts in GRASS GIS of this. For
example, the temporal (t.*) modules work with series of rasters and vectors
registered as spatio-temporal datasets and the image processing (i.*)
modules work with series of rasters registered as imagery groups and
subgroups ("multiband image"). In both cases standard storage of rasters (or
vectors) is used, so there is no new backend format in GRASS database except
for the additional data (metadata) needed for these tools. What is important
is that you can work with the existing tools on the data handled by temporal
or imagery modules, i.e. you can use the existing tools to implement the new
tools (e.g. average of spatio-temporal raster dataset can be implemented
through a tool for average of multiple rasters) and if the imagery or
temporal modules miss specific functionality you need, you can fallback to
the standard modules (e.g. loop over members of imagery group).

I was thinking that the hexagonal rasters can be implemented in GRASS GIS
using two rasters which would be shifted against each other, but aligned
with the hexagonal cells, i.e. two rectangular rasters making up one
hexagonal raster/grid (but I didn't test that or examined that more). After
seeing your video with slightly rotated hexagonal grid, I'm thinking if it
is possible to fit only one raster but with different resolution to the
hexagons. The idea is that 1) you don't need another storage format and 2)
you can use the raw data without the hexagon-aware algorithms. Of course we
can settle just with re-using the storage format (1).

Another approach is to threat hexagonal rasters/grids as another basic data
type next to raster maps, vector maps, and 3D raster maps (in GRASS GIS
there are also the aforementioned spatio-temporal datasets and imagery
groups). They would be connected to the rest where it makes sense. For
example, (2D) rasters and 3D rasters are independent, but there is also
several connections: there are modules for conversion in between the two
types, a lot of code for handling colors is the same, and computational
region applies to both and is handled from the same module.

If I may ask, what would you need to create a prototype and what do you
envision as a final goal?

Best,
Vaclav

_______________________________________________
grass-dev mailing list
grass-dev@lists.osgeo.org
https://lists.osgeo.org/mailman/listinfo/grass-dev

5

Hi Sören, good to have you in this discussion.

I do not know exactly what the compressed row approach is, but I am pretty positive on it being applicable to hexagonal rasters too. As I wrote initially, an hexagonal mesh can be stored in an array; from then on it is all a matter of cell indexation.

···

I added the angle rotation to the HexASCII specification since there are two ways to align an hexagon with the Cartesian axis: with two sides parallel to the x axis (North-South orientation) or with two sides parallel to y axis (East-West orientation). With an angle of 0º in HexASCII you get a North-South mesh, with 90º it is a East-West mesh. If other angles complicate matters, on a first approach only angles of 0º and 90º could be considered.

In any case, rotating a mesh by an angle is a relatively simple computation, you can see an example in this method of the hex-utils package:

https://github.com/ldesousa/hex-utils/blob/develop/hex_utils/hasc.py#L235

During my MSc thesis I developed a method to display hexagons in a squared monitor with bitmaps that may be still useful for the d. modules. But perhaps a vector approach is more interesting today.

Cheers.

–

Luís Moreira de Sousa

Im Grund 6

CH-8600 Dübendorf

Switzerland

Phone: +41 (0)79 812 62 65

Email: luis.de.sousa@protonmail.ch

URL: https://sites.google.com/site/luismoreiradesousa

-------- Original Message --------

Subject: Re: [GRASS-dev] Adding hexagonal rasters to GRASS

Local Time: July 24, 2017 9:24 PM

UTC Time: July 24, 2017 7:24 PM

From: soerengebbert@googlemail.com

To: Vaclav Petras wenzeslaus@gmail.com

Luí­s Moreira de Sousa luis.de.sousa@protonmail.ch, grass-dev@lists.osgeo.org grass-dev@lists.osgeo.org

Dear Luí­s,

this sounds very interesting, especially the improvement for surface

flow algorithms using hexagonal grids and other mass conservation

approaches like groundwater flow, heat flow, … .

I agree with Vaclav on this topic. I think hexagonal grids can be

stored using the compressed row based approach of GRASS GIS. In

addition the rotation of the hexagonal grid may be stored in the

metadata. The question is, do we need rotated hexagonal grids at all

or do horizontal hexagonal grids do the job? In case of “horizontal”

hexagonal grids the compressed row approach would be very fast for

horizontal access. Indexing can be easily mapped to row/column access

using the “odd-r” horizontal layout. The existing on the fly nearest

neighbor resampling algorithms will have an offset of half a cell for

odd row indices when interacting with normal raster layers in existing

modules, so they must be adjusted.

Neighborhood operations must be implemented on top of the existing

row/col approach of GRASS. All algorithms that make cell neighbor

computations must be modified. The existing r.mapcalc neighbor

operators r[y] can be reused in case of odd-r horizontal layout.

Conversion between regular grids and hexagonal grids must be

implemented. Resampling algorithms must be modified. Rendering of

hexagonal grids must be implemented in the display library. Plenty of

work do do. :slight_smile:

Best regards

Sören

2017-07-24 1:19 GMT+02:00 Vaclav Petras wenzeslaus@gmail.com:

Dear Luís,

On Sun, Jul 23, 2017 at 11:50 AM, Luí­s Moreira de Sousa

luis.de.sousa@protonmail.ch wrote:

I presented hex-utils at the GISTAM conference in April, here is the

video:

https://www.youtube.com/watch?v=uLO4HDCVBp0

thank you, this is very informative and exiting!

But as Luca said during the Q/A, it is probably better to start outright

within GRASS. This will require the abstraction of the raster concept,

together with operations like neighbourhood, number of neighbours, distance

to neighbours, etc. With that done most of the raster modules would function

the same way for squared and hexagonal rasters. Still, this would require a

complete revision of all the raster modules.

Sounds good. I think there is a way in GRASS GIS to make it revolutionary

and at the same time keeping everything in place. See below.

For a programmer, the main difference between hexagonal and squared

rasters is the cell addressing system: with hexagons the axis are not

orthogonal.

If there would be a way, like the abstraction you mentioned, which would,

e.g. make the current rectangle-only code work with hexagonal data (e.g. by

presenting converting hexagons as rectangles on the fly), that would be

helpful, but on the other side, I don"t think it is necessarily the first

step if there is an other way how to connect with rectangular rasters (even

if it involves converting back and forth or less precision).

However, it is possible to store an hexagonal raster in a bi-dimensional

array like you would store a squared raster.

That would help the implementation and hopefully also the integration and

adoption, again see below.

I wrote an article last year with full details on the HexASCII file format

and how to deal with hexagonal cell adressing, but it is still under review.

I can not send it to the list, please send me a personal message if you wish

to read it.

If you can share it, I would like to see it.

It would be great if we can take this forward. I imagine it is a load of

work, but it will make GRASS an even more awesome system :wink:

Load of work and resulting code to maintain should be part of the

consideration. Using existing functionality (algorithms, formats) and

integrating with it will be crucial for both users and developers alike.

Can you implement it this as a layer on top of existing functionality in

GRASS GIS? There is several examples and concepts in GRASS GIS of this. For

example, the temporal (t.*) modules work with series of rasters and vectors

registered as spatio-temporal datasets and the image processing (i.*)

modules work with series of rasters registered as imagery groups and

subgroups (“multiband image”). In both cases standard storage of rasters (or

vectors) is used, so there is no new backend format in GRASS database except

for the additional data (metadata) needed for these tools. What is important

is that you can work with the existing tools on the data handled by temporal

or imagery modules, i.e. you can use the existing tools to implement the new

tools (e.g. average of spatio-temporal raster dataset can be implemented

through a tool for average of multiple rasters) and if the imagery or

temporal modules miss specific functionality you need, you can fallback to

the standard modules (e.g. loop over members of imagery group).

I was thinking that the hexagonal rasters can be implemented in GRASS GIS

using two rasters which would be shifted against each other, but aligned

with the hexagonal cells, i.e. two rectangular rasters making up one

hexagonal raster/grid (but I didn"t test that or examined that more). After

seeing your video with slightly rotated hexagonal grid, I"m thinking if it

is possible to fit only one raster but with different resolution to the

hexagons. The idea is that 1) you don"t need another storage format and 2)

you can use the raw data without the hexagon-aware algorithms. Of course we

can settle just with re-using the storage format (1).

Another approach is to threat hexagonal rasters/grids as another basic data

type next to raster maps, vector maps, and 3D raster maps (in GRASS GIS

there are also the aforementioned spatio-temporal datasets and imagery

groups). They would be connected to the rest where it makes sense. For

example, (2D) rasters and 3D rasters are independent, but there is also

several connections: there are modules for conversion in between the two

types, a lot of code for handling colors is the same, and computational

region applies to both and is handled from the same module.

If I may ask, what would you need to create a prototype and what do you

envision as a final goal?

Best,

Vaclav

grass-dev mailing list

grass-dev@lists.osgeo.org

https://lists.osgeo.org/mailman/listinfo/grass-dev

6

Dear Luís,

2017-07-25 15:50 GMT+02:00 Luí­s Moreira de Sousa <luis.de.sousa@protonmail.ch>:

Hi Sören, good to have you in this discussion.

I do not know exactly what the compressed row approach is, but I am pretty
positive on it being applicable to hexagonal rasters too. As I wrote
initially, an hexagonal mesh can be stored in an array; from then on it is
all a matter of cell indexation.

The compressed row approach is used by GRASS GIS to store raster layer.
Each row of a raster map is stored as a compressed array. If you want
to access a single cell, you have to read the whole row that contains
the cell and uncompress it to access the cell. Many algorithms in
GRASS are programmed to access
raster layer maps by reading the first row and iterate over all cells,
then read the next row and iterate over all cells, ... . Rows are read
from top to bottom, or North to South, cell are read from west to
east. This approach has pro and cons. It allows to skip reading rows
in case of on the fly resampling for visualization and makes
visualization very fast for large raster maps.

My understanding of hexagonal grids, that is derived from this:
http://www.redblobgames.com/grids/hexagons/

So i assume that North-South orientation is equal to a horizontal aka
pointy topped orientation.

The horizontal orientation is supported in GRASS by the compressed row
approach out of the box. A single row of hexagons can be stored as
compressed raster row. Then you can use the odd-r index scheme to
address the cells in the compressed rows as hexagons. Using the odd-r
indexing means that each row with an odd index is shifted by half a
hexagon to the east.

This approach makes it easy to process hexagonal grids with existing
raster modules. The on the fly nearest neighbor resampling algorithm
in GRASS can also be modified easily. Raster to hexagon and vice versa
conversion must be solved by a statistical resampling algorithm.

The raster display library must be improved to draw hexagonal grids,
or use its vector polygon draw routines, so that the d.rast tools can
be used for visualization. AFAIU the display library draws a
rectangles for each cell and fills it with a color.

Best regards
Sören

I added the angle rotation to the HexASCII specification since there are two
ways to align an hexagon with the Cartesian axis: with two sides parallel to
the x axis (North-South orientation) or with two sides parallel to y axis
(East-West orientation). With an angle of 0º in HexASCII you get a
North-South mesh, with 90º it is a East-West mesh. If other angles
complicate matters, on a first approach only angles of 0º and 90º could be
considered.

In any case, rotating a mesh by an angle is a relatively simple computation,
you can see an example in this method of the hex-utils package:
https://github.com/ldesousa/hex-utils/blob/develop/hex_utils/hasc.py#L235

During my MSc thesis I developed a method to display hexagons in a squared
monitor with bitmaps that may be still useful for the d. modules. But
perhaps a vector approach is more interesting today.

Cheers.

--
Luís Moreira de Sousa
Im Grund 6
CH-8600 Dübendorf
Switzerland

Phone: +41 (0)79 812 62 65
Email: luis.de.sousa@protonmail.ch
URL: https://sites.google.com/site/luismoreiradesousa

-------- Original Message --------
Subject: Re: [GRASS-dev] Adding hexagonal rasters to GRASS
Local Time: July 24, 2017 9:24 PM
UTC Time: July 24, 2017 7:24 PM
From: soerengebbert@googlemail.com
To: Vaclav Petras <wenzeslaus@gmail.com>
Luí­s Moreira de Sousa <luis.de.sousa@protonmail.ch>,
grass-dev@lists.osgeo.org <grass-dev@lists.osgeo.org>

Dear Luí­s,
this sounds very interesting, especially the improvement for surface
flow algorithms using hexagonal grids and other mass conservation
approaches like groundwater flow, heat flow, ... .

I agree with Vaclav on this topic. I think hexagonal grids can be
stored using the compressed row based approach of GRASS GIS. In
addition the rotation of the hexagonal grid may be stored in the
metadata. The question is, do we need rotated hexagonal grids at all
or do horizontal hexagonal grids do the job? In case of "horizontal"
hexagonal grids the compressed row approach would be very fast for
horizontal access. Indexing can be easily mapped to row/column access
using the "odd-r" horizontal layout. The existing on the fly nearest
neighbor resampling algorithms will have an offset of half a cell for
odd row indices when interacting with normal raster layers in existing
modules, so they must be adjusted.
Neighborhood operations must be implemented on top of the existing
row/col approach of GRASS. All algorithms that make cell neighbor
computations must be modified. The existing r.mapcalc neighbor
operators r[y] can be reused in case of odd-r horizontal layout.
Conversion between regular grids and hexagonal grids must be
implemented. Resampling algorithms must be modified. Rendering of
hexagonal grids must be implemented in the display library. Plenty of
work do do. :slight_smile:

Best regards
Sören

2017-07-24 1:19 GMT+02:00 Vaclav Petras <wenzeslaus@gmail.com>:

Dear Luís,

On Sun, Jul 23, 2017 at 11:50 AM, Luí­s Moreira de Sousa
<luis.de.sousa@protonmail.ch> wrote:

I presented hex-utils at the GISTAM conference in April, here is the
video:
https://www.youtube.com/watch?v=uLO4HDCVBp0

thank you, this is very informative and exiting!

But as Luca said during the Q/A, it is probably better to start outright
within GRASS. This will require the abstraction of the raster concept,
together with operations like neighbourhood, number of neighbours,
distance
to neighbours, etc. With that done most of the raster modules would
function
the same way for squared and hexagonal rasters. Still, this would require
a
complete revision of all the raster modules.

Sounds good. I think there is a way in GRASS GIS to make it revolutionary
and at the same time keeping everything in place. See below.

For a programmer, the main difference between hexagonal and squared
rasters is the cell addressing system: with hexagons the axis are not
orthogonal.

If there would be a way, like the abstraction you mentioned, which would,
e.g. make the current rectangle-only code work with hexagonal data (e.g.
by
presenting converting hexagons as rectangles on the fly), that would be
helpful, but on the other side, I don"t think it is necessarily the first
step if there is an other way how to connect with rectangular rasters
(even
if it involves converting back and forth or less precision).

However, it is possible to store an hexagonal raster in a bi-dimensional
array like you would store a squared raster.

That would help the implementation and hopefully also the integration and
adoption, again see below.

I wrote an article last year with full details on the HexASCII file
format
and how to deal with hexagonal cell adressing, but it is still under
review.
I can not send it to the list, please send me a personal message if you
wish
to read it.

If you can share it, I would like to see it.

It would be great if we can take this forward. I imagine it is a load of
work, but it will make GRASS an even more awesome system :wink:

Load of work and resulting code to maintain should be part of the
consideration. Using existing functionality (algorithms, formats) and
integrating with it will be crucial for both users and developers alike.

Can you implement it this as a layer on top of existing functionality in
GRASS GIS? There is several examples and concepts in GRASS GIS of this.
For
example, the temporal (t.*) modules work with series of rasters and
vectors
registered as spatio-temporal datasets and the image processing (i.*)
modules work with series of rasters registered as imagery groups and
subgroups ("multiband image"). In both cases standard storage of rasters
(or
vectors) is used, so there is no new backend format in GRASS database
except
for the additional data (metadata) needed for these tools. What is
important
is that you can work with the existing tools on the data handled by
temporal
or imagery modules, i.e. you can use the existing tools to implement the
new
tools (e.g. average of spatio-temporal raster dataset can be implemented
through a tool for average of multiple rasters) and if the imagery or
temporal modules miss specific functionality you need, you can fallback to
the standard modules (e.g. loop over members of imagery group).

I was thinking that the hexagonal rasters can be implemented in GRASS GIS
using two rasters which would be shifted against each other, but aligned
with the hexagonal cells, i.e. two rectangular rasters making up one
hexagonal raster/grid (but I didn"t test that or examined that more).
After
seeing your video with slightly rotated hexagonal grid, I"m thinking if it
is possible to fit only one raster but with different resolution to the
hexagons. The idea is that 1) you don"t need another storage format and 2)
you can use the raw data without the hexagon-aware algorithms. Of course
we
can settle just with re-using the storage format (1).

Another approach is to threat hexagonal rasters/grids as another basic
data
type next to raster maps, vector maps, and 3D raster maps (in GRASS GIS
there are also the aforementioned spatio-temporal datasets and imagery
groups). They would be connected to the rest where it makes sense. For
example, (2D) rasters and 3D rasters are independent, but there is also
several connections: there are modules for conversion in between the two
types, a lot of code for handling colors is the same, and computational
region applies to both and is handled from the same module.

If I may ask, what would you need to create a prototype and what do you
envision as a final goal?

Best,
Vaclav

_______________________________________________
grass-dev mailing list
grass-dev@lists.osgeo.org
https://lists.osgeo.org/mailman/listinfo/grass-dev

7

Hi again Sören,

Yes, everything you write should be possible. The web page you link uses some unconventional names for cell address systems that have been published many years ago in scientific articles. Basically, one must use an address system for storage and another address system for computation. This requires a (simple) transformation between the two.

Note, however, that modules can not use directly what you call the odd-r system (called squared up system in the literature). The neighbourhood indexes are different from row to row. There is a section in the TGIS article dealing specifically with these issues (I’ll send you a copy of the draft).

Thank you for the input.

···

-------- Original Message --------

Subject: Re: [GRASS-dev] Adding hexagonal rasters to GRASS

Local Time: July 25, 2017 5:46 PM

UTC Time: July 25, 2017 3:46 PM

From: soerengebbert@googlemail.com

To: Luí­s Moreira de Sousa luis.de.sousa@protonmail.ch

Vaclav Petras wenzeslaus@gmail.com, grass-dev@lists.osgeo.org grass-dev@lists.osgeo.org

Dear Luís,

2017-07-25 15:50 GMT+02:00 Luí­s Moreira de Sousa luis.de.sousa@protonmail.ch:

Hi Sören, good to have you in this discussion.

I do not know exactly what the compressed row approach is, but I am pretty

positive on it being applicable to hexagonal rasters too. As I wrote

initially, an hexagonal mesh can be stored in an array; from then on it is

all a matter of cell indexation.

The compressed row approach is used by GRASS GIS to store raster layer.

Each row of a raster map is stored as a compressed array. If you want

to access a single cell, you have to read the whole row that contains

the cell and uncompress it to access the cell. Many algorithms in

GRASS are programmed to access

raster layer maps by reading the first row and iterate over all cells,

then read the next row and iterate over all cells, … . Rows are read

from top to bottom, or North to South, cell are read from west to

east. This approach has pro and cons. It allows to skip reading rows

in case of on the fly resampling for visualization and makes

visualization very fast for large raster maps.

My understanding of hexagonal grids, that is derived from this:

http://www.redblobgames.com/grids/hexagons/

So i assume that North-South orientation is equal to a horizontal aka

pointy topped orientation.

The horizontal orientation is supported in GRASS by the compressed row

approach out of the box. A single row of hexagons can be stored as

compressed raster row. Then you can use the odd-r index scheme to

address the cells in the compressed rows as hexagons. Using the odd-r

indexing means that each row with an odd index is shifted by half a

hexagon to the east.

This approach makes it easy to process hexagonal grids with existing

raster modules. The on the fly nearest neighbor resampling algorithm

in GRASS can also be modified easily. Raster to hexagon and vice versa

conversion must be solved by a statistical resampling algorithm.

The raster display library must be improved to draw hexagonal grids,

or use its vector polygon draw routines, so that the d.rast tools can

be used for visualization. AFAIU the display library draws a

rectangles for each cell and fills it with a color.

Best regards

Sören

I added the angle rotation to the HexASCII specification since there are two

ways to align an hexagon with the Cartesian axis: with two sides parallel to

the x axis (North-South orientation) or with two sides parallel to y axis

(East-West orientation). With an angle of 0º in HexASCII you get a

North-South mesh, with 90º it is a East-West mesh. If other angles

complicate matters, on a first approach only angles of 0º and 90º could be

considered.

In any case, rotating a mesh by an angle is a relatively simple computation,

you can see an example in this method of the hex-utils package:

https://github.com/ldesousa/hex-utils/blob/develop/hex_utils/hasc.py#L235

During my MSc thesis I developed a method to display hexagons in a squared

monitor with bitmaps that may be still useful for the d. modules. But

perhaps a vector approach is more interesting today.

Cheers.

–

Luís Moreira de Sousa

Im Grund 6

CH-8600 Dübendorf

Switzerland

Phone: +41 (0)79 812 62 65

Email: luis.de.sousa@protonmail.ch

URL: https://sites.google.com/site/luismoreiradesousa

-------- Original Message --------

Subject: Re: [GRASS-dev] Adding hexagonal rasters to GRASS

Local Time: July 24, 2017 9:24 PM

UTC Time: July 24, 2017 7:24 PM

From: soerengebbert@googlemail.com

To: Vaclav Petras wenzeslaus@gmail.com

Luí­s Moreira de Sousa luis.de.sousa@protonmail.ch,

grass-dev@lists.osgeo.org grass-dev@lists.osgeo.org

Dear Luí­s,

this sounds very interesting, especially the improvement for surface

flow algorithms using hexagonal grids and other mass conservation

approaches like groundwater flow, heat flow, … .

I agree with Vaclav on this topic. I think hexagonal grids can be

stored using the compressed row based approach of GRASS GIS. In

addition the rotation of the hexagonal grid may be stored in the

metadata. The question is, do we need rotated hexagonal grids at all

or do horizontal hexagonal grids do the job? In case of “horizontal”

hexagonal grids the compressed row approach would be very fast for

horizontal access. Indexing can be easily mapped to row/column access

using the “odd-r” horizontal layout. The existing on the fly nearest

neighbor resampling algorithms will have an offset of half a cell for

odd row indices when interacting with normal raster layers in existing

modules, so they must be adjusted.

Neighborhood operations must be implemented on top of the existing

row/col approach of GRASS. All algorithms that make cell neighbor

computations must be modified. The existing r.mapcalc neighbor

operators r[y] can be reused in case of odd-r horizontal layout.

Conversion between regular grids and hexagonal grids must be

implemented. Resampling algorithms must be modified. Rendering of

hexagonal grids must be implemented in the display library. Plenty of

work do do. :slight_smile:

Best regards

Sören

2017-07-24 1:19 GMT+02:00 Vaclav Petras wenzeslaus@gmail.com:

Dear Luís,

On Sun, Jul 23, 2017 at 11:50 AM, Luí­s Moreira de Sousa

luis.de.sousa@protonmail.ch wrote:

I presented hex-utils at the GISTAM conference in April, here is the

video:

https://www.youtube.com/watch?v=uLO4HDCVBp0

thank you, this is very informative and exiting!

But as Luca said during the Q/A, it is probably better to start outright

within GRASS. This will require the abstraction of the raster concept,

together with operations like neighbourhood, number of neighbours,

distance

to neighbours, etc. With that done most of the raster modules would

function

the same way for squared and hexagonal rasters. Still, this would require

a

complete revision of all the raster modules.

Sounds good. I think there is a way in GRASS GIS to make it revolutionary

and at the same time keeping everything in place. See below.

For a programmer, the main difference between hexagonal and squared

rasters is the cell addressing system: with hexagons the axis are not

orthogonal.

If there would be a way, like the abstraction you mentioned, which would,

e.g. make the current rectangle-only code work with hexagonal data (e.g.

by

presenting converting hexagons as rectangles on the fly), that would be

helpful, but on the other side, I don"t think it is necessarily the first

step if there is an other way how to connect with rectangular rasters

(even

if it involves converting back and forth or less precision).

However, it is possible to store an hexagonal raster in a bi-dimensional

array like you would store a squared raster.

That would help the implementation and hopefully also the integration and

adoption, again see below.

I wrote an article last year with full details on the HexASCII file

format

and how to deal with hexagonal cell adressing, but it is still under

review.

I can not send it to the list, please send me a personal message if you

wish

to read it.

If you can share it, I would like to see it.

It would be great if we can take this forward. I imagine it is a load of

work, but it will make GRASS an even more awesome system :wink:

Load of work and resulting code to maintain should be part of the

consideration. Using existing functionality (algorithms, formats) and

integrating with it will be crucial for both users and developers alike.

Can you implement it this as a layer on top of existing functionality in

GRASS GIS? There is several examples and concepts in GRASS GIS of this.

For

example, the temporal (t.*) modules work with series of rasters and

vectors

registered as spatio-temporal datasets and the image processing (i.*)

modules work with series of rasters registered as imagery groups and

subgroups (“multiband image”). In both cases standard storage of rasters

(or

vectors) is used, so there is no new backend format in GRASS database

except

for the additional data (metadata) needed for these tools. What is

important

is that you can work with the existing tools on the data handled by

temporal

or imagery modules, i.e. you can use the existing tools to implement the

new

tools (e.g. average of spatio-temporal raster dataset can be implemented

through a tool for average of multiple rasters) and if the imagery or

temporal modules miss specific functionality you need, you can fallback to

the standard modules (e.g. loop over members of imagery group).

I was thinking that the hexagonal rasters can be implemented in GRASS GIS

using two rasters which would be shifted against each other, but aligned

with the hexagonal cells, i.e. two rectangular rasters making up one

hexagonal raster/grid (but I didn"t test that or examined that more).

After

seeing your video with slightly rotated hexagonal grid, I"m thinking if it

is possible to fit only one raster but with different resolution to the

hexagons. The idea is that 1) you don"t need another storage format and 2)

you can use the raw data without the hexagon-aware algorithms. Of course

we

can settle just with re-using the storage format (1).

Another approach is to threat hexagonal rasters/grids as another basic

data

type next to raster maps, vector maps, and 3D raster maps (in GRASS GIS

there are also the aforementioned spatio-temporal datasets and imagery

groups). They would be connected to the rest where it makes sense. For

example, (2D) rasters and 3D rasters are independent, but there is also

several connections: there are modules for conversion in between the two

types, a lot of code for handling colors is the same, and computational

region applies to both and is handled from the same module.

If I may ask, what would you need to create a prototype and what do you

envision as a final goal?

Best,

Vaclav

grass-dev mailing list

grass-dev@lists.osgeo.org

https://lists.osgeo.org/mailman/listinfo/grass-dev

8

On Mon, Jul 24, 2017 at 11:16 AM, Luí­s Moreira de Sousa <
luis.de.sousa@protonmail.ch> wrote:

- In theory, all raster modules can function in exactly the same way with
both square and hexagons if all geometric and neighbourhood
methods/properties/functions are abstracted correctly.

- The risk here is breaking the existing r. modules by implementing the
raster abstraction. Perhaps some sort of transition may be devised to avoid
it

- On my side, the next step is to dive into the code and study how
practical these ideas may be. But please put forward your ideas in any case.

For start, I suggest implementing some prototypes from stretch rather than
rewriting/adopting existing code. Probably a conversion or visualization
module makes sense so that we can see the results. I'm sure you have much
better about this than I since you already went through that before.

I suggest that the modules store the hexagon map (maybe a correct name in
GRASS?) in raster map with some metadata on the side. I would ignore the
problem that a raster map which (perhaps) does not make any sense (for
raster modules) is created. The metadata may be stored in just in the
current directory (in future, they would go to the GRASS database).

You would need to use functions to modify computational region inside the
module to be able to store it properly (e.g. r.in.lidar modifies the
computational region for itself when -e flag is used). Standard way of
doing this is in C, but Python works as well and may be much simpler
(either through PyGRASS or ctypes directly). Importantly, this can be done
without changing the library or existing modules, so you can do any
experiments you want (e.g. in GRASS Addons, GRASS Sandbox or on GitHub).

Talking just about how this prototype could be implemented, here is an
example of user interaction and the results (the names are not final,
r.hex.to.rast would probably become h.to.rast in the future):

GRASS > g.list rast m=.
a_raster

GRASS > r.info raster_1 -g
...
res=2
...

GRASS > g.region raster=raster_1

GRASS > r.to.hex input=raster_1 output=hexagons

GRASS > g.list rast m=.
raster_1
hexagons

GRASS > r.info hexagon
something very unexpected here for the user
number of cells and perhaps even extent does not fit

GRASS > r.hex.info
raster hexagon processed as hexagons
output about hexagonal grid
(information from the raster and metadata on the side combined)

GRASS > r.hex.waterflow input=hexagons output=hexagonal_flow

GRASS > g.list rast m=.
raster_1
hexagons
hexagonal_flow

GRASS > g.list.hex m=.
hexagons
hexagonal_flow

GRASS > g.region res=0.1 # note much lower resolution

GRASS > r.hex.to.rast input=hexagonal_flow output=raster_2

GRASS > d.rast raster_2
no we see the hexagons because we oversampled them

9

Hello Luis,

I saw the video of the webinar of your colleague João P Leitão in
April about the hex version of the CADDIES model and I was asking
myself "is there any GIS software supporting hexagonal rasters?"
So I'm quite excited about the prospect of having support in GRASS :wink:
However, I'm not sure if I can be of much help about the implementation.

Regards,
Laurent Courty

2017-07-23 10:50 GMT-05:00 Luí­s Moreira de Sousa <luis.de.sousa@protonmail.ch>:

Dear friends,

I presented hex-utils at the GISTAM conference in April, here is the video:
https://www.youtube.com/watch?v=uLO4HDCVBp0

This was before the QGis plug-in was completed, but for the rest it is
pretty much the same story.

Before the FOSS4G-E, in my mind the next phase of the project would be to
code the abstraction functionalities in C++ (or C), to make it fully
portable and easier to use with other languages, particularly Java. After
that would then come a map algebra and spatial analysis.

But as Luca said during the Q/A, it is probably better to start outright
within GRASS. This will require the abstraction of the raster concept,
together with operations like neighbourhood, number of neighbours, distance
to neighbours, etc. With that done most of the raster modules would function
the same way for squared and hexagonal rasters. Still, this would require a
complete revision of all the raster modules.

For a programmer, the main difference between hexagonal and squared rasters
is the cell addressing system: with hexagons the axis are not orthogonal.
However, it is possible to store an hexagonal raster in a bi-dimensional
array like you would store a squared raster. I wrote an article last year
with full details on the HexASCII file format and how to deal with hexagonal
cell adressing, but it is still under review. I can not send it to the list,
please send me a personal message if you wish to read it.

It would be great if we can take this forward. I imagine it is a load of
work, but it will make GRASS an even more awesome system :wink:

All the best.

--
Luís Moreira de Sousa
Im Grund 6
CH-8600 Dübendorf
Switzerland

Phone: +41 (0)79 812 62 65
Email: luis.de.sousa@protonmail.ch
URL: https://sites.google.com/site/luismoreiradesousa

_______________________________________________
grass-dev mailing list
grass-dev@lists.osgeo.org
https://lists.osgeo.org/mailman/listinfo/grass-dev

10

Hi devs,

some more material on the matter:

HexASCII: A file format for cartographical hexagonal rasters - de
Sousa - 2017 - Transactions in GIS - Wiley Online Library
http://onlinelibrary.wiley.com/doi/10.1111/tgis.12304/abstract

Presentation:
https://git.osgeo.org/gogs/foss4g-europe/foss4g-europe-2017-paris/src/master/presentations/2017-07-20/general_track/foss4g-europe-2017-Introducing_hex-utils_an_haxagonal_raster_toolkit-LMdeSousa-JPLeitao.pdf

Best,
Markus

11

Thank you Markus for flagging this up.

A pre-print of the article is now available from at ResearchGate [0] and GitHub [1]. I also made a video of the presentation to the the GISTAM conference [3] (don’t recall sending it here).

Since the last message I moved from Switzerland to the Netherlands, were I started a job at ISRIC. So for now I have no spare time to dedicate to hexagons. The short term goal is to port the hex-utils library in to C++; after that starts integration with GRASS.

I will be in Bonn for the Spring code sprint. That will be a good time to get things rolling.

Cheers.

[0] https://www.researchgate.net/publication/321628606_HexASCII_A_file_format_for_cartographical_hexagonal_rasters

[1] https://github.com/ldesousa/ldesousa.github.io/raw/master/documents/HexASCII_Specification.pdf

[2] https://www.youtube.com/watch?v=uLO4HDCVBp0

···

–

Luís Moreira de Sousa

Molenweg 4

6871 CW Renkum

The Netherlands

Phone: +31 628 544 755

Email: luis.de.sousa@protonmail.ch

RingID: ring:7ca91d83f4f9dec82fec9f1144b8e5c1ef2a110c

URL: https://sites.google.com/site/luismoreiradesousa

-------- Original Message --------

Subject: Re: [GRASS-dev] Adding hexagonal rasters to GRASS

Local Time: December 7, 2017 10:05 PM

UTC Time: December 7, 2017 9:05 PM

From: neteler@osgeo.org

To: grass-dev@lists.osgeo.org grass-dev@lists.osgeo.org

Luí­s Moreira de Sousa luis.de.sousa@protonmail.ch

Hi devs,

some more material on the matter:

HexASCII: A file format for cartographical hexagonal rasters - de

Sousa - 2017 - Transactions in GIS - Wiley Online Library

http://onlinelibrary.wiley.com/doi/10.1111/tgis.12304/abstract

Presentation:

https://git.osgeo.org/gogs/foss4g-europe/foss4g-europe-2017-paris/src/master/presentations/2017-07-20/general_track/foss4g-europe-2017-Introducing_hex-utils_an_haxagonal_raster_toolkit-LMdeSousa-JPLeitao.pdf

Best,

Markus

12

Hi everybody,

I am starting at FOSSGIS an attempt at hexagons based on PyGRASS. After a lengthy discussion with Sören, he convinced me to try a pragmatic approach entirely based on Python. The first draft module is in:

https://github.com/ldesousa/hex-utils-grass

More details to follow. Thank you all for the encouragement. Cheers.

···

–

Luís Moreira de Sousa

Bowlespark 8

6701 DN Wageningen

The Netherlands

Phone: +31 628 544 755

Email: luis.de.sousa@protonmail.ch

RingID: ring:7ca91d83f4f9dec82fec9f1144b8e5c1ef2a110c

URL: https://ldesousa.github.io