Je travaille sur un fabricant de carte HTML, et j'aimerais offrir à nos utilisateurs la possibilité de créer des formes rapidement en cliquant dans une zone au lieu de les avoir définir la forme manuellement.
Tout d'abord, regardons ce que nous faisons pour le moment. L'utilisateur souhaite mapper la zone A. Ce qu'il doit faire est de cliquer plusieurs fois sur chaque point pour définir les limites de la forme.
J'aimerais savoir, c'est s'il y a un algorithme qui permettrait à l'utilisateur de cliquer dans la zone d'une zone et pourrait déterminer les points à éliminer afin de créer une forme presque optimale après les limites de la forme - basée sur le Contraste d'image.
Ma première idée à gérer ceci était de déterminer les points les plus éloignés, à gauche, en bas, à partir du point cliqué. Définissez ces quatre points comme nos points de départ. Ensuite, pour chaque segment, subdiviser avec un nouveau point et déplacez le nouveau point le long du vecteur normal jusqu'à ce que je frappe un bord contrasté.
Bien sûr, cette approche présente certaines limitations, mais voici ce que je peux assumer
Si l'un d'entre vous connaît un tel alogrement, ce serait vraiment génial.
3 Réponses :
Cela semble être un problème difficile (BTW, je ne connais pas d'algorithme spécifique pour cela). Mes 2 cents:
Utilisez un Remplissage d'inondation algorithme, mais au lieu d'obtenir toute la surface, Obtenez seulement le périmètre.
Prendre un point de départ du périmètre et aller d'une manière Lorsque vous détectez que l'erreur quadratique accumulée entre le segment virtuel (point de point de courant - point initial) et le périmètre réel dépassent un seuil, mettez-y un point et recommencez jusqu'à ce que vous arriviez au point de départ.
La première étape semble assez facile, la seconde est plus difficile.
Oui, ça ressemble à un problème difficile. Je ne suis pas sûr de ce que vous entendez dans la deuxième partie, cependant. Au début, j'avais le sentiment que vous parliez de marcher sur le périmètre de n'importe quel point, vérifiant après chaque étape si le nouveau point correspond aux points précédents en termes d'inclinaison (), mais après avoir réfléchi à votre réponse, je ne suis pas sûr de la signification. de "point initial" dans votre réponse. Voulez-vous dire "point de graine", c'est-à-dire le point que vous cliquez au départ?
@samy, pas le point de départ mais un point de départ du périmètre calculé. Vous devez marcher le périmètre de n'importe quel point et décider où sont les "virages". Cette détection est délicate, d'une part, vous devez détecter des changements soudains d'angles (imaginez une forme de polygone), mais également de petits changements continus (imaginez une forme de circonférence). Une combinaison de ces deux critères devrait vous donner de bons résultats.
Ok, c'est ce que je pensais. Franchement, je ne me dérangerais pas avec la forme de la circonférence; Je n'essaie pas de couvrir toutes les bases au début, mais plutôt des 90% des cas qui comptent. Je vais essayer de construire quelque chose pour cela.
@samy: Si vous ne vous souciez pas de changement continu des changements localisés dans des angles dans des fragments relativement petits. Vous aurez besoin de math.atan2
Eh bien, je vais mordre la balle et considérer qu'il n'y a pas d'algue existante pour déterminer les points d'un périmètre; J'ai essayé de tricher et d'examiner la détection de Harris Corner, mais cela ne correspond pas à la facture sur certains points.
Jetez un coup d'œil à Région en croissance algorithmes. Ceci est essentiellement la même chose que l'algorithme de remplissage d'inondation décrit ci-dessus par Tokland dans le cas de base.
L'algorithme de culture de la région est très bon pour construire la zone initiale qui servira de base à découvrir le périmètre, mais d'après ce que je lis, cela ne permet pas de trouver les points de composition du périmètre.
Vous pouvez utiliser un Algorithme de détection de bord (EDA).
Dans JavaScript, vous pouvez utiliser pixastic ou rouler le vôtre.
Après avoir été traitée par l'EDA, votre image devient:
Après cela, jetez simplement n'importe quelle ligne dans n'importe quelle direction de votre point intérieur sur le premier pixel blanc et suivez le contour.
Oui, je pourrais suivre le contour, mais comment puis-je déterminer qu'un changement de direction dans la ligne correspond à un nouveau point dans le polygone et non un escalier dans la ligne. Ensuite, il y a des artefacts à gérer (par exemple dans votre image, certaines lignes de l'EDA sont de deux pixels de large). Je suis donc d'accord sur ce que votre asnwer suggère, c'est juste que la partie "suivre le contour" n'est pas si triviale. Au moins, je ne vois pas comment le faire trvitait :)
Les lignes de connexion sont-elles connues pour chaque nœud? Si oui, peuvent-ils être navigués jusqu'au prochain nœud, même s'il est à mi-chemin du côté (comme le deuxième point, dans votre troisième image)? Si tel est le cas, vous pouvez simplement utiliser le style de routage "Gardez la gauche" ou "Garder la droite" pour trouver la forme de connexion la plus interne.
En fait, l'objectif est de déterminer les nœuds de créer la polyligne. Je modifie le titre de la question pour le rendre plus clair
Je suis désolé, je supposais que l'image soit basée sur des vecteurs. Est-ce en fait un bitmap?
J'imagine que cela nécessite de convertir l'image en toile afin de lire la couleur des pixels. Peut-être que vous pouvez ajouter «Toile» pour attirer l'attention de la gourée de la toile sur cette question;)
Comment la carte est-elle représentée en premier lieu? Est-ce que quelque chose vous empêche de compiler toutes les zones possibles du serveur et d'envoyer simplement les données traitées au client?
@MissingNo La carte pourrait être n'importe quel type d'image avec des zones. Ce n'est pas généré et cela pourrait même être une image JPG. Cependant, notre usage principal est pour les cartes avec des zones clairement délimitées. Cette amélioration permettrait de gagner du temps pour presque tous les utilisateurs
VPPVG en effet, c'est un bitmap, pas de vecteur