Swap to better 'label point' map bubble placement (incircle / convex hull)

[brendanheywood]

To better handle cases like this where the shape is like a banana and the marker ends up outside the shape:

http://www.thecrag.com/area/184165659/locate

I think I want the 'incircle' of the polygon instead of the centroid.

Either of these would work:

• find the largest circle which is inside the polygon, and then return that circles center
• imagine that the shape is like the edges of the roof of a house with gables, now find the point on the roof which is the highest

In fact I think they are actually identical see: http://stackoverflow.com/questions/4279478/maximum-circle-inside-a-non-convex-polygon

Perfect: https://github.com/mapbox/polylabel

https://www.thecrag.com/climbing/australia/blue-mountains/celebrity-crag

[brendanheywood]

Done a bunch more reading on this, some of the better things I found:

https://www.spatialanalysisonline.com/HTML/index.html?centroids_and_centers.htm

Essentially for most normalish shapes like a rough rectangle, the sort of shapes we often have for clifffs, probably the best algorithm is the simple center of mass. This is also really fast to calculate and easy to port to any language if there wasn't an implementation already.

https://en.wikipedia.org/wiki/Centroid#Of_a_polygon

http://demonstrations.wolfram.com/CenterOfMassOfAPolygon/

But this fails really badly on banana shapes where the centroid will be outside. The next best method that most people talk about is the incircle but it also has many drawbacks, in particular it 'slides' up to one end of a not-quite-perfect rectangle which will be worse for the majority use case.

The incircle is also quite hectic to calculate. mapbox have come up with a heuristic which is much faster to calculate and their is an implementation in js and c++:

https://blog.mapbox.com/a-new-algorithm-for-finding-a-visual-center-of-a-polygon-7c77e6492fbc

https://github.com/mapbox/polylabel/blob/master/polylabel.js

The incircle point is also the highest point of a straight skeleton, ie if you turn each polygon into a floor flan and then add a gable room, the incircle is the highest part of the roof.

https://en.wikipedia.org/wiki/Straight_skeleton

Which lead me to the medial axis:

https://en.wikipedia.org/wiki/Medial_axis or https://en.wikipedia.org/wiki/Topological_skeleton

This produces not a point or even a line but a tree graph. If you then worked back from all the ends to find the point furthest from any edge then I think this would be a more natural center than any of the above and it would work in all cases. eg a slightly tapered rectangle would only have it's center very slightly shifted to the fatter end by this method. No implementations that I can see yet.

[brendanheywood]

On reflection, given the new aspect work for the maps I think there is a reasonable argument that really banana or m shaped cliffs should actually be broken up into sub cliffs. This will solve probably half of these issues.

Secondly the parent wrapper areas shouldn't really be shrink wrapped so tightly around all of its children (eg the 'where are you' test: https://www.thecrag.com/en/article/geolocation#how-this-data-is-used), like this:

Before:

After:

Similar, this cliff could probably just include the car park area and be more of a rectangle

I've noticed a lot of the cliffs in the blue mountains are very thin strips directly over the rock face but this isn't very forgiving of an inaccurate gps signal so many of these might correctly be 'here' if you are at the base etc.

There are still some legitimate cases that are left but generally they are actually fairly rare. Given we've lived with it for this long I'm happy to just sit on this for a while.

[rouletout]

I'm not so sure that this conclusion is correct but I agree we can sit on it. look at this example and there are quite a few - mostly "canyon based" crags where there are significant differences in access and climbing between left and right side of a river. Example here: https://www.thecrag.com/climbing/united-states/west-virginia/area/12595123

[brendanheywood]

Please dump as many examples as you can here. That example is actually useful to explain a bit why this isn't actually so important. There is another issue in trello about moving the center to be weighted based on it's children, which is being done for other reasons but positively impacts this issue. This other issue fixes a bug where you see a cluster and then zoom in and it jumps around because it has really lopsided children:

ie https://trello.com/c/9xGquqyq fixes this:

eg the 'upper meadow' has it's label is currently outside the S where the red x is, but after we weight it it will probably sit more around where 'second buttress' at the blue cross:

If Cambodia suddenly got another 100 routes then it would pull the center back to the right and possibly outside again.

Likewise the 'southside crags' anchor point is way out in the middle of nowhere, but after being weighted will end up pretty well over Area 51 because none of it's other crags have any routes in them.

The incircle or something similar will still help in some cases, and even when we combine them both I suspect there will still be cases where the label ends up somewhere odd, but I just want to attack the issues in the right order. The weighting will fix the most by far and will be done first.

[brendanheywood]

More literature scanning, stumbled onto the magic keywords: 'convex hull' and 'label point' and finally hit pay dirt.

http://proceedings.esri.com/library/userconf/proc01/professional/papers/pap388/p388.htm

There is a conceptually similar version inspired by this written in R here:

https://stat.ethz.ch/pipermail/r-sig-geo/2012-July/015693.html Examples are red dots, yellow is simple centroid:

This looks perfect. almost perfect - This will still strongly favor the fat end of a banana instead of nearer to the middle.

No perl port I can find, but porting this should be ok. The key bits are a function to buffer (shrink) a polygon, convert that smaller polygon to a convex hull, check that the shrunk convex poly is inside then original on, if so get its centroid, if not keep shrinking. I think we have everything we need:

https://metacpan.org/pod/Geo::OGC::Geometry#Buffer($distance) https://metacpan.org/pod/Math::ConvexHull https://metacpan.org/pod/Geo::OGC::Geometry#Contains($geometry) https://metacpan.org/pod/Math::Polygon#$obj-%3Ecentroid()