J'ai été chargé de déterminer comment trouver la ligne médiane d'un polygone. Mes recherches Google m'ont conduit à croire que ce dont j'ai besoin est appelé "Axe médial". Comme ceci:
Selon ce que j'ai lu, ce dont j'ai besoin peut être produit en utilisant un algorithme de construction de diagramme de Voronoi 2D pour segments.
J'ai trouvé une version C # de l'algorithme Voronoi sur CodePlex (Fortunevoronoi) et après l'application de mon polygone, je me retrouve avec ceci:
(source: kiev.ua )
3 Réponses :
wow. Je vais sortir sur un membre ici et suggérer que l'algorithme est peut-être confondu à propos de l'intérieur contre l'extérieur du polygone. Lorsque vous définissez les bords et les sommets de votre polygone d'origine, vous devez vous assurer qu'ils sont définis de manière à ce que "à l'intérieur" soit toujours trouvé en utilisant quelque chose comme la "règle de droite". En regardant juste le polygone dans le coin inférieur droit, on dirait que le bord de votre polygone se traverse réellement. Peut-être que l'algorithme consiste à voir cette section et d'autres, comme "à l'intérieur". Le même en bas à gauche.
C'est mon sentiment d'intestin, que l'algorithme ne semble pas être capable de déterminer quelle direction est à l'intérieur et ce qui est à l'extérieur.
Je pense qu'une approche naïve serait de filtrer tous les "nœuds" voroni qui sont en dehors du polygone, mais je ne pense pas que cela ressemblerait. En regardant de plus près votre diagramme, il semble que chaque nœud ait 3 bords qui le connectent à d'autres nœuds. Peut-être que vous pouvez filtrer les nœuds où l'un des 3 bords est connecté à des nœuds en dehors du polygone. Cela fonctionnerait-il?
En effet. L'ensemble Voronoi généré est défini à la fois à l'intérieur et à l'extérieur du polygone. (Pour cette affaire, l'algorithme Set Voronoi n'exige pas que le jeu de génération soit un polygone, voire d'être un ensemble connecté continu.) L'affiche originale ne s'intéresse que dans les limites des régions Voronoi Set telle que ces limites sont à l'intérieur de la poly. Donc, construisez un algorithme qui filtre les frontières définies Voronoi qui ne sont pas à l'intérieur du Poly. Déterminer si un point donné est à l'intérieur d'un poly n'est pas très difficile.
Une solution simple serait aussi suggérée dans les commentaires:
Si vous avez des données énormes, les intersections peuvent être assez coûteuses.
alors vous pouvez faire une approche similaire comme dans le question , et Cette solution pourrait également fonctionner pour vous. La façon dont je le ferais:
ps. Notez que les deux solutions donnent des l'approximation de l'axe médial, l'informatique, il est exactement beaucoup plus coûteux, mais comme un teaser ... Vous pouvez obtenir des résultats comme celui-ci pour les points d'échantillons d'entrée noirs:
Une construction similaire est le squelette droite , qui peut être construite en rétrécissant le polygone dans lui-même et tracer les sommets lorsqu'ils s'approchent au centre. Cela peut être un peu plus facile à construire, bien que ce ne soit pas tout à fait la même courbe que l'axe médial.
Une de vos images a disparu