flutter_map
flutter_map copied to clipboard
fleaflet
feat: change label placement configuration, add new 'signed area centroid' algorithm, and use new polylabel implementation
This PR updates the logic used to compute the center of a label by replacing the previous average-based approach with a more accurate polygon centroid calculation.
Motivation Previously, the centroid was calculated by simply averaging all latitudes and longitudes of the polygon points. While this works for simple shapes, it often results in inaccurate label placement for complex or non-convex polygons. The new approach computes the geometric centroid using the signed area formula, which takes the shape of the polygon into account and gives a more accurate center for label placement.
Changes
Replaced the averaging method with a proper polygon centroid computation that: Uses the shoelace formula to calculate the signed area. Computes the weighted average of all vertices to determine the centroid. Falls back to averaging in the rare case of zero area (e.g., collinear points). Handles edge cases such as empty or single-point input.
Reproduction
Attached is a screenshot showing the issue with the previous approach. The following sample coordinates help reproduce the difference:
[ { "lat": -6.148970663625812, "lng": -80.00502973729147 }, { "lat": -6.151999579408217, "lng": -80.00502266917418 }, { "lat": -6.151996562581506, "lng": -80.00344874575943 }, { "lat": -6.148972613882413, "lng": -80.00346259720905 }, { "lat": -6.148970663625812, "lng": -80.00502973729147 } ]
[ { "lat": -6.148979805893571, "lng": -80.00337467617543 }, { "lat": -6.151993401453232, "lng": -80.00337910858363 }, { "lat": -6.151989815157336, "lng": -80.00179839899332 }, { "lat": -6.148963739527827, "lng": -80.00180957676228 }, { "lat": -6.148979805893571, "lng": -80.00337467617543 } ]
Hi @JaffaKetchup this MR requires your attention please review and let me know your feedback Thanks
Hi @tidu090, we can't promise any timelines (I'm particularly busy atm), but we'll see what we can do.
It looks like you've got a formatting issue. Can you run the formatter, push, then I can test it out?
@JaffaKetchup ran the formatter should pass now, thank you for your attention!
@tidu090 I've made some of the changes I suggested. Your new algorithm is in 'centroid.dart'. The changes have resolved a TODO, and made the label placement system much more extensible.
The only part remaining is whether this can support multi-worlds. Do you think this is possible with your algorithm? If not, I think I'm OK with this.
This will now need a review from another @fleaflet/maintainers since I've made a lot of changes.
@JaffaKetchup thank you for your feedback I will declare a new enum set for user to switch between old & new algo, those changes I will be doing tomorrow. Thank you once again happy to contribute!
Btw I have this question if you can't review this PR anymore who will merge it then?
No need to make a new enum anymore, just need the multi-world implementation if possible. You can copy CentroidCalculator and call the new copy MultiWorldCentroidCalculator. Then change the implementation of call in the new one.
The other maintainers are a little busy at the moment, but hopefully at some point quite soon we can get through this backlog of PRs and release v8.2. i.e. the other maintainers can review and merge.
@fleaflet/maintainers I've also changed the polylabel implementation to my own new port (https://github.com/JaffaKetchup/dart_polylabel2). Its similar to the first, but fixes the licensing issue & performance issues (and doesn't rely on 'dart:math's Point). It still requires that list generation to convert from latlong to xy, but I didn't want to tie it to latlong, so I think it's a good middle ground.
It also fixes the TODO of allowing the 'precision'/'threshold' to be customized externally.