Trouvez la plus longue ligne droite entre deux points sur la surface du polygone

8

Ma forme est un polygone légèrement concave, et j'aimerais connaître le diamètre maximal. J'imagine une ligne droite entre deux points sur la surface du polygone, de telle sorte que la ligne ne passe pas en dehors du polygone.

Existe-t-il un algorithme général pour cela?

Dans mon cas, je m'intéresse à la 2D. Mes formes sont des tumeurs dans les images médicales. On peut donc aussi supposer: 1 le centroïde est toujours à l'intérieur du polygone. 2 une densité de sommets élevée, c'est-à-dire que le sommet suivant est toujours proche du précédent.

mathematics computational-geometry polygon jiggunjer
la source
1
Il y a des étriers rotatifs mais cela ne fonctionne que pour les polygones convexes. Sinon, vous pouvez l'utiliser comme base pour une solution de force brute.
ratchet freak
3
Eh bien, si O (n ^ 2) n'est pas un problème, testez toutes les paires de points
joojaa
2
En fait, c'est un peu plus compliqué: imaginez 2 chambres reliées par un couloir étroit. Le plus grand diamètre se terminera sur les murs des différentes pièces et ne se terminera sur aucun point.
ratchet freak
1
Vous recherchez un algorithme qui fonctionne dans le cas le plus général ou peut-il être limité par exemple au cas 2D? Cela pourrait être plus facile à résoudre avec plus d'informations ou de restrictions sur l'entrée. Vous utilisez le mot polygone qui peut faire allusion à 2D uniquement, également la question que vous avez liée suggère le cas 2D. En outre, est-ce suffisant de considérer les distances vertex-vertex ou avez-vous besoin de résultats corrects pour des cas comme le phénomène de cliquet mentionné dans son commentaire ?
Nero
2
De plus, je suis préoccupé par une forme en C qui a une épaisseur très étroite, mais un grand intérieur ouvert; et donc un grand rayon de courbure. Son diamètre (comme vous le définissez) serait très petit car ce ne serait qu'un court qui suit la courbure du C. Pourtant, un nodule cancéreux de la taille de la taille intérieure serait assez préoccupant. C'est peut-être la coque convexe dont vous voulez calculer le diamètre.
Wyck

Réponses:

1

Je n'ai pas de réponse exacte à cela, car la réponse est loin d'être triviale. Je suggérerais que vous examiniez la géométrie informatique, car il s'agit clairement d'un problème de visibilité - je suppose qu'une solution existe déjà. Ma propre idée serait: pour chaque segment de ligne dans un polygone, trouver les parties visibles des autres segments de ligne, puis choisir la paire de points les plus éloignés. Lien inspirant: Wikipedia sur le «polygone de visibilité» .

au-delà
la source