[FEATURE] Replace the polylabel dependency with an own implementation

[josxha]

What do you want implemented?

The current integration of polylabel is not very well performance optimized. By implementing our own port of polylabel, we can:

• have better performance
• decrease our dependance on 3rd party packages

What other alternatives are available?

No response

Can you provide any other information?

Current usage of the polylabel package:

LatLng _computePolylabel(List<LatLng> points) {
  final labelPosition = polylabel(
    [
      List<math.Point>.generate(points.length,
          (i) => math.Point(points[i].longitude, points[i].latitude)),
    ],
    // "precision" is a bit of a misnomer. It's a threshold for when to stop
    // dividing-and-conquering the polygon in the hopes of finding a better
    // point with more distance to the polygon's outline. It's given in
    // point-units, i.e. degrees here. A bigger number means less precision,
    // i.e. cheaper at the expense off less optimal label placement.
    precision: 0.000001,
  );
  return LatLng(
    labelPosition.point.y.toDouble(),
    labelPosition.point.x.toDouble(),
  );
}

Severity

Minimum: Not required for my use

[mootw]

i noticed this while working on #1750 and added a comment //TODO does this really need to be changed to a math.Point type?

[JosefWN]

Maybe better to be inspired rather than straight-up porting, perhaps a bit touchy since it's a commercial company, and porting counts as redistribution from a legal point of view. In their licensing terms:

The software and files in this repository (collectively, "Software") are
licensed under the Mapbox TOS for use only with the relevant Mapbox product(s)
listed at [www.mapbox.com/pricing](http://www.mapbox.com/pricing).

...
* Redistributions of source code must retain the above copyright notice,
  this list of conditions and the following disclaimer.
* Redistributions in binary form must reproduce the above copyright notice,
  this list of conditions and the following disclaimer in the documentation
  and/or other materials provided with the distribution.
...

https://github.com/mapbox/mapbox-gl-js?tab=License-1-ov-file#readme

Other than Your Content, all content displayed on the site or accessible
through the Services, including text, images, maps, software or source code,
are the property of Mapbox and/or third parties and are protected by
United States and international intellectual property laws.

https://www.mapbox.com/legal/tos/

Porting would be a violation of the TOS, and even if it weren't, only dependencies are managed automatically by flutter (bundling the licenses with the binary), so it could be a bit cumbersome 😅

I think it's quite a bit different to port things from Mapbox than it is from, say, Leaflet.

[JaffaKetchup]

(It is possible to use LicenseBinding to add licenses to the Flutter app: https://api.flutter.dev/flutter/foundation/LicenseRegistry/addLicense.html)

[JosefWN]

Ah, thanks, didn't know! If we could automate that it would certainly simplify things for the users of flutter_map, I'm still doubtful that porting is allowed within the scope of the TOS though?

[josxha]

I'm still doubtful that porting is allowed within the scope of the TOS though

Good point, in that case we should see that as an encouragement to remove the dependency to the polylabel package anyways.

[navispatial]

Maybe a late comment on TOS problems mentioned above but MapBox has published their polylabel implementation as JavaScript code in a separate repository: https://github.com/mapbox/polylabel

The license https://github.com/mapbox/polylabel/blob/master/LICENSE should allow any kind of ports (however this is not a legally verified comment...) as long as license text is provided in all copies.

This is the JavaScript file that covers the whole polylabel algorithm: https://github.com/mapbox/polylabel/blob/master/polylabel.js

It has a dependency to a very simple TinyQueue implementation (with a very permissive license too):
https://github.com/mourner/tinyqueue/blob/main/index.js

Instead of that it's possible to use PriorityQueue class from the Dart package:collection package (as flutter_map seems to already have a dependency on it).

There's also an another port of polylabel to Dart in the geobase package, but maybe that's not an answer either to this issue (as transformation between polyline data structures would be needed also when using it):

• https://github.com/navibyte/geospatial/blob/main/dart/geobase/lib/src/geometric/cartesian/areal/polylabel.dart
• https://pub.dev/packages/geobase