> After thinking far too long about how I can sort coordinates reliability, I chose the easy way out:
In addition to the code, please also give a plain language description: "We ensure that the first coordinate is the lexicographically smallest (i.e. most westward point). For line strings, reverse the coordinate list to make it so, and for polygons, rotate the coordinates to make it so."
Nice! Should point out that JTS geometries already have a built in normalize and equalsNorm method for computing equality regardless of coordinate starting point. I'm not sure how they compare to your implementation but the motivation is similar.
Either way, you can optimize the performance of this approach by first doing a cheaper comparison (like coordinate count) and only computing the normalized geometry when you need to.
I think the point of hashing here would be to have a high-confidence equality indicator with a fast comparison speed. Having a low-confidence indicator (like coord count) that still requires significant computation afterward that cannot be cached defeats this purpose.
In a production environment, where you deal with huge sets (think OSM), the solution may be a mix of both.
One aspect that I didn't deal with (yet) is also, that a Polygon can have redundant points (think A(1|1) B(2|2) C(3|3) D(1|2)), which you should simplify.
Ideally you would also split the map into hexagons, and compute which Geometry lays within which hexagon(s), and then only compare the geometry that shares a hexagon(s), but this information should be persisted and not computed each runtime, making it a bit out-of-scope for pure GeoJSON hashing.
Actually the flow of this project was implementing everything on my own, and at a later stage realizing that JTS already does a lot, and then refactoring and dropping most of my features :D
I was just fiddling around in Kotlin, JTS seems like a banger library though.
6 comments
[ 4.2 ms ] story [ 24.2 ms ] threadIn addition to the code, please also give a plain language description: "We ensure that the first coordinate is the lexicographically smallest (i.e. most westward point). For line strings, reverse the coordinate list to make it so, and for polygons, rotate the coordinates to make it so."
> val reordered = coordinates.subList(index, coordinates.size - 1) + coordinates.subList(0, index)
This should say + coordinates.subList(0, index + 1), and then you can get rid of the code that checks for first != last.
Either way, you can optimize the performance of this approach by first doing a cheaper comparison (like coordinate count) and only computing the normalized geometry when you need to.
One aspect that I didn't deal with (yet) is also, that a Polygon can have redundant points (think A(1|1) B(2|2) C(3|3) D(1|2)), which you should simplify.
Ideally you would also split the map into hexagons, and compute which Geometry lays within which hexagon(s), and then only compare the geometry that shares a hexagon(s), but this information should be persisted and not computed each runtime, making it a bit out-of-scope for pure GeoJSON hashing.
Actually the flow of this project was implementing everything on my own, and at a later stage realizing that JTS already does a lot, and then refactoring and dropping most of my features :D
I was just fiddling around in Kotlin, JTS seems like a banger library though.