Discussion on improving grid functions

[twelch]

Capturing some grid function related things I've been researching in one place for discussion and just awareness.

I noticed there's been some changes in behavior for at least the squareGrid/rectangleGrid functions in 2021 where something seems off/incorrect, or just don't do quite what the docs imply (for example that specifying units for cellSide will return cells that are equidistant in those units).
#2638
#2136
#2203

In addition, across all issues open/closed I see a call for the grid functions (hexGrid, squareGrid, rectangleGrid, triangleGrid, pointGrid?), to construct grids that meet different constraints. For example:

1. Grids that fit perfectly within bounding box provided (exactFit), rather than just the maximum cells that still fit within the bounding box without going over, and then centering the grid (current)
2. Grids whose cells are exactly the same height/width in the units specified (currently optimized for degrees but many/most? users want fixed unit lengths like kilometers, miles) squareGrid result is only square in the unit of degree #2638
3. Grids that are rotated to a given bearing (edge case)
4. Aligning different grids and/or producing sub-grids (edge case) Aligning grids with different cellSides #2013

Possible solutions include:

• Start with improving the grid function docs to more specifically describe their behavior, so people know what they can expect.
• Fix the functions to do what they were intended to do (be able to provide units and the resulting grid cells will be equidistant in those units)
• If needed, support multiple methods within each function rather than a one-size-fits-all approach that doesn't meet most needs. Or if the different options needed are too varied, create multiple functions.

[smallsaucepan]

Two areas to maybe address before deciding on an approach:

First is to decide what exactly are we giving someone when they ask for a rectangle? Is it the corners of a spherical rectangle like you'd see on the surface of the Earth? Or a planar rectangle on a 2D projection? Those points will differ more and more as you get further toward the poles. The former is more accurate and consistent, whereas the latter will "look nicer" on a map. I'm firmly team "spherical earth" - I'd want this to work as well in Sweden as it does in Kenya.

Second is that the way we define the API seems odd. We have a bounding box, and then a cell width - which isn't guaranteed to be an exact multiple of the bbox edge, so we fudge that by re-centering which then leads to issues like #2013 . Would seem neater to choose between:

• starting point, number of cells, and cell width - leaving the overall bounding box undefined
• bbox, number of cell divisions - width is calculated making sure to fit an exact number of cells

I can imagine use cases for both, so perhaps warrants splitting into two functions.

[smallsaucepan]

Here's my proposal. What do you think @twelch?

As soon as possible roll back #2106. This would close #2638 but reopen #2079. Update the docs for the grid functions to warn the bounding box must span less than 180 degrees latitude.

There might still be a simple enough fix for 2079? Suspect we'd need to somehow infer the winding of the bbox to figure out the user wants us to take the "long way round". Maybe the original reporter @stollc could weigh in?

Then for v8 as it would be a breaking change, we simplify the behaviour of the grid functions so that the user provides either:

• starting point, number of cells, and cell width - leaving the overall bounding box undefined
• bbox, number of cell divisions - width is calculated making sure to fit an exact number of cells

Overall we aim to have Turf do a couple of basic functions predictably and correctly, and push any remaining calculations and complexity back onto the user. Trying to cater to all potential use cases (rotations, centering, subgrids) is only going to lead to us doing none of them well.

[Pitouli]

Hello, my two cents about this topic 😄

About the "perfect fit"

I feel like there can be situations where the user wants a perfect fit, and other where he wants a perfect size of cells. So ideally, the functions should allow for both (for example, if provided parameters cols: int, rows: int, it will do a perfect fit, and if we provide cellWidth: float, cellHeight: float it will respect the cells dimensions).

But if we want to keep it simple, and only have one "way of working", I would keep the current one (define cells dimensions) because it is easier to do cellsWidth = (bbox.x2 - bbox.x1) / cols than recomputing the four coordinates of the bbox to be a multiple of the desired cells dimensions centered around the original bbox.

And for the "cellsWidth" scenario, I think it is important to provide a contain / cover parameter where the user can express if he wants the cells to completely cover the bbox (or the mask if provided) or to the contrary to keep only the cells that are contained in the bbox (or the mask if provided). Cf this discussion: #2822

Note that for hexa grid, perfect fit to a bounding box will be hard to achieve 😛

About the degrees vs km/miles

I indeed feel like most of the time what the user cares about is to have a square that looks like a square in real life.
But I think that the "unit" parameters is exactly what we need for that. If I explicitly ask for "degrees", then I should have a square in degrees (so it looks like a square near the equator, and is stretched like a rectangle near the poles). But if I ask for kilometers (or meters?) or miles, then we should convert them to degrees based on the lon/lat of the center of the bbox.

Note that we could imagine a grid where the height of the cells differ on each row so if the grid is applied on the full earth each cell is the same dimension in kilometers. But I feel like it is a lot more complex, especially for hexa grids, and I question myself if it could not be an issue for the devs to not have celles that are placed on a multiple of their dimension. On the other hand, it is because it is a lot more complex that it is interesting to have the feature out of the box. Perhaps it could be driven by a parameter?

Aligning differents grids

This would be easily solved with a "perfect fit" solution (either by pre-computing the cellWidth or with a parameter). But note that with a hexa grid I do not think you can have "sub grids" anyway...

Rotating grid

I do not think it should be part of the grid component considering we already have transformRotate() : https://turfjs.org/docs/api/transformRotate

About "what is a rectangle"

That is indeed a good question ! :D But I sincerely think we can keep it "simple", especially for the squarish grids. For me, the rectangle" should be equal to its bounding box, which I believe means a rectangle has square angles on the mercator projection.

Indeed, I think that one of the very useful usage of the grids (at least the square / rectangular ones) is to partition the plan in smaller pieces, and the ability of defining if something is inside or outside of it by simply comparing the x1,y1, x2,y2 coordinates is extremely precious.

About "bbox vs start point"

My personal use case (which I imagine is not unusual) is that I have a polygon (in my case a city boundaries) that I want to divide in a grid of 500 meters cells. So my bbox is simply the bbox of my polygon, the width is 0.5km (in my specific scenario I do not really care about the exact size of the cell so I could technically do a cols = round(widthInKm(bbox) / 0.5km), but I can imagine that for others it could be more of a concern), so I quite like the "bbox + mask" current approach.

I feel like it is less usual to have a "starting point" and a "number of cells" with a "cells width" unrelated to any other polygon. So I would prefer one of the solution described in the "About the perfect fit" section above

[smallsaucepan]

Thanks for that @Pitouli. Taking your comments and @twelch's here's what I suggest we do:

1. Stick with bbox as the overall way of expressing the grid size - start point will be too confusing

2. Stick with cell size as the way of expressing the cell size

3. Drop the rotation functionality - there's already transformRotate so keep the boundaries of responsibility clean. Unless this is a spherical / mercator thing.

4. Change the behaviour to guarantee the grid is at least as big as the bbox - number of cells is rounded UP if the cell size doesn't divide evenly into the grid size. This might mean the grid is larger than the bbox on the east and south sides. This simplifies hex and triangle grids as well, as we aren't having to distort them to fit.

5. Change the behaviour to NOT center the grid - this seems to be the most confusing aspect of current grid behaviour. Users wonder why their grid doesn't align with any side of their bbox. Being more predictable would also make it possible to align grids.

6. Stop or warn users from using degrees or radians for cell size - this causes headaches because a degree of latitude equates to different lengths depending on what latitude you measure it at.

7. Admit grids will only render well on mercator projections for the time being - once we figure out all the above we can look into displaying well on a sphere.

8. Change mask functionality to be more in line with @turf/mask - that is only the cells that are entirely visible through the mask would be kept. Know you're keen on a covers / contains option @Pitouli, however I think that muddies the waters of how masks work. For some of the use cases you describe there might be more appropriate Turf functions (such as overlap) that would give you the result you want without adding additional options to gridWhatever.

For example, this is what I believe a grid masked by a polygon should look like:

And this is what a grid overlapped with the same polygon should give you:

Should we drop the mask parameter too, and just get the user to use turf-mask?

All this would be a breaking change. Thoughts?

[Pitouli]

I really like your ideas and agree on most of them!

Few comments nonetheless

5. Change the behaviour to NOT center the grid - this seems to be the most confusing aspect of current grid behaviour. Users wonder why their grid doesn't align with any side of their bbox. Being more predictable would also make it possible to align grids.

There's something I don't really like about the idea of not distributing overruns fairly; why should we favor one direction more than the other?

The "subgrid" argument feels a bit weird: if you want to create "subgrids", should not the subgrids be INSIDE the cells of the bigger grid? For example with this kind of algorithm:

But there is probably situation where "independent" subgrid makes sense, and since I do not have a "good" argument against aligning the grid to the top left corner instead of centering it except "elegance"... so perhaps it is the way to go...

2. Stick with cell size as the way of expressing the cell size

If we have to chose between columns and cellSize, I agree that cellSize seems the best considering it is easier to go from col to cellSize than the opposite.

This being said, it could have side effects due to the javascript approximation of numbers. For example, if the bbox is 1 unit large and you want 3 columns, then each cellSize would be 0.3333333333333333 unit wide. So you will potentially end up with 4 columns instead of 3 (with one column being extremely narrow; with a width of 0.0000000000000001 unit).

Or at least it is a particular case to be taken into account : if the last column/row is extremely small compared to the other columns , then we should "merge it" with the last column.

Note that with a = 1/3; b = a * a we in fact have b === 1 but for example with a = Math.sqrt(2); b = a * a we do not have b === 2 so my "3 columns" example is perhaps not the best example but there could be others situations that are buggy

Should we drop the mask parameter too, and just get the user to use turf-mask?

Now that you speak of it, I indeed think we should completely remove the mask option, and let other packages take care of "cover/contain mask".

But note that turf.mask and turf.lineOverlap do not seem to be a good match currently. Mask is doing "holes" and can only takes a simple polygon as input, and lineOverlap I did not completely understood how it work but I tested it and it does not return the expected result.

So probably there should be a new package for this "inside", "outside", "intersect" scenario that takes a featureCollection of (multi)polygons, and a (multi)polygon mask, and it returns the featureCollection with a new property "position" valued at "inside", "outside" or "intersect". And there would be an option to specify if you want to keep only some of the positions -- for example only those inside and intersecting -- in the return)

BONUS

I was about to propose an helper function for those who want a "number of columns / rows" based grid. But in fact my helper function is almost more verbose to use than the small snippet I add written in my previous answer.

turf.bboxSize = (geojson, options = { recomputeBbox: boolean = false, units: degrees | radians | miles | kilometers = kilometers }) => {
  const bbox = turf.bbox(geojson, { recompute: options.recomputeBbox });
  const width = turf.distance(turf.point([ bbox[0], (bbox[1] + bbox[3]) / 2], turf.point([ bbox[2], (bbox[1] + bbox[3]) / 2]), { units: options.units });
  const height = turf.distance(turf.point([ (bbox[0] + bbox[2]) / 2, bbox[1] ], turf.point([ (bbox[0] + bbox[2]) / 2, bbox[3] ]), { units: options.units });
  return { width, height }
}

cellSize = turf.bboxSize(area).width / cols

Unrelated to this grid topic, do you think I should open a conversation about the creation of such package?

Note that I assumed in my algorithm that the "width" should be taken at the center of the bbox, but perhaps the "width" should be taken at the nearest point of the equator (at the equator if the bbox crosses it, or bottom of the bbox if it is in the north side and top if it is on the south side)

[smallsaucepan]

There's something I don't really like about the idea of not distributing overruns fairly; why should we favor one direction more than the other?

My point of view would be at least one side of the grid lines up with the bbox, as opposed to neither. This behaviour seems unexpected to many people. An example. Another. One more.

The "subgrid" argument feels a bit weird: if you want to create "subgrids", should not the subgrids be INSIDE the cells of the bigger grid?

I would say yes, I agree with that. Except because the grid has now been re-centered by Turf the user has to reset their understanding of where the grid lines run.

Subgrids might not be that significant a use case to argue anyway. I'm more pushing for Turf to not recenter based on the level of surprise many users have when it happens.

This being said, it could have side effects due to the javascript approximation of numbers. For example, if the bbox is 1 unit large and you want 3 columns, then each cellSize would be 0.3333333333333333 unit wide. So you will potentially end up with 4 columns instead of 3 (with one column being extremely narrow; with a width of 0.0000000000000001 unit).

Yeah, we'll almost certainly run into problems with floating point remainders.

if the last column/row is extremely small compared to the other columns , then we should "merge it" with the last column.

So, if the next grid cell would be super narrow we make the current grid cell a fraction bigger? I don't actually mind that. I imagine the threshold should be quite small though. Less than 1% of the cell width maybe? Smaller even?

But note that turf.mask and turf.lineOverlap do not seem to be a good match currently.

Understood. These are the things we need to coordinate at a higher level to make sure interdependent functionality works correctly.