Détection de "coque concave" sur l'image de carte

Question

Je développe le plugin JavaScript open-source pour Waze - navigateur GPS gratuit bien connu - spécifiquement pour online editor. L'idée de ce script est de permettre de sélectionner rapidement de grandes zones de cartes colorées uniformes pour les convertir en points de repère. Jusqu'à présent, j'ai successfully implemented l'outil que vous appelez "Magic Wand" dans les éditeurs graphiques comme Photoshop: l'utilisateur clique quelque part sur la carte (disons, sur le lac ou la forêt) et le script sélectionne toute la zone couverte par la même couleur et crée un polygone pour point de repère.

Tout fonctionne très bien, sauf que j'utilise l'algorithme de la coque convexe pour obtenir le ... eh bien ... :) coque convexe C'est: le polygone reliant les points les plus externes du nuage de points trouvés.

Mais comme tout le monde ne comprennent que quelques points de repère ont une forme convexe alors que la plupart des objets du monde réel ont une forme de polyligne avec des zones concaves. Sur la photo ci-dessus, vous pouvez voir que la zone a peu de bords tranchants et un champ de ferme dans le coin inférieur droit couvert par la coque convexe - c'est faux.

Je cherchais un algorithme approprié et je cherchais des documents mathématiques, mais je n'avais toujours pas de chance d'en trouver un. The most popular question sur les coques concaves ici sur Stackoverflow se réfère aux formes Alpha avec les triangles Delaunay. Bien que je ne comprenne pas comment l'utiliser dans le cas: tous les points sont connectés les uns aux autres formant une polyligne continue donc il semble que je ne peux pas trouver le rayon alpha approprié comme cercle pair avec un rayon égal à 1 pixel avec alpha.

Toutes les idées pour archiver l'objectif de construire une coque concave seront très appréciées! Peut-être que je me déplace dans une mauvaise direction et que j'ai besoin de regarder des algorithmes de vectorisation bitmap?

Answer 1

Vous pouvez lire comment implémenter l'algorithme de coque concave dans du papier this. L'idée de base est de construire la coque convexe et les bords flexibles (concaves) vers l'intérieur. Il existe une implémentation JavaScript de cet algorithme: hull.js.

Answer 2

Les formes alpha sont définies en recherchant la triangulation delaunay d'un ensemble de points, puis en supprimant les arêtes qui dépassent alpha. Vous avez besoin de la triangulation delaunay mais pas des cercles. Cela fonctionne aussi avec des lignes. Pour calculer la forme avec JS, vous pouvez utiliser TopoJSON ou essayer cette réponse: Calculate bounding polygon of alpha shape from the Delaunay triangulation. Vous pouvez également essayer mon paquet php http://concavehull.codeplex.com/.