[GRASS-dev] Adding hexagonal rasters to GRASS

Tue Jul 25 09:23:05 PDT 2017

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.
--
Luís Moreira de Sousa
Im Grund 6
CH-8600 Dübendorf
Switzerland
Phone: +41 (0)79 812 62 65
Email: luis.de.sousa at protonmail.ch
URL: https://sites.google.com/site/luismoreiradesousa

>> -------- 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 at googlemail.com
>> To: Luís Moreira de Sousa <luis.de.sousa at protonmail.ch>
>> Vaclav Petras <wenzeslaus at gmail.com>, grass-dev at lists.osgeo.org <grass-dev at lists.osgeo.org>
>> Dear Luís,
>> 2017-07-25 15:50 GMT+02:00 Luís Moreira de Sousa <luis.de.sousa at 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 at 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 at googlemail.com
>>> To: Vaclav Petras <wenzeslaus at gmail.com>
>>> Luís Moreira de Sousa <luis.de.sousa at protonmail.ch>,
>>> grass-dev at lists.osgeo.org <grass-dev at 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[x][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. :)
>>>
>>> Best regards
>>> Sören
>>>
>>> 2017-07-24 1:19 GMT+02:00 Vaclav Petras <wenzeslaus at gmail.com>:
>>>> Dear Luís,
>>>>
>>>> On Sun, Jul 23, 2017 at 11:50 AM, Luís Moreira de Sousa
>>>> <luis.de.sousa at 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 ;)
>>>>>
>>>>
>>>> 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 at lists.osgeo.org
>>>> https://lists.osgeo.org/mailman/listinfo/grass-dev
>>>
>>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/grass-dev/attachments/20170725/ad31ae01/attachment-0001.html>