Encuentre la línea recta más larga entre dos puntos en la superficie del polígono

8

Mi forma es un polígono ligeramente cóncavo, y me gustaría saber el diámetro máximo. Me imagino una línea recta entre dos puntos en la superficie del polígono, de modo que la línea no pase fuera del polígono.

¿Hay un algoritmo general para esto?

En mi caso estoy interesado en 2D. Mis formas son tumores en imágenes médicas. Entonces también podemos suponer: 1 el centroide siempre está dentro del polígono. 2 una alta densidad de vértices, es decir, el siguiente vértice siempre está cerca del anterior.

mathematics computational-geometry polygon jiggunjer
fuente
1
Hay pinzas giratorias, pero eso solo funciona para polígonos convexos. De lo contrario, puede usarlo como base para una solución de fuerza bruta.
Ratchet Freak
3
Bueno, si O (n ^ 2) no es un problema, pruebe todos los pares de puntos
joojaa
2
En realidad es un poco más complicado: imagina 2 habitaciones conectadas por un pasillo estrecho. El diámetro más grande terminará en las paredes de las diferentes habitaciones y no terminará en ningún punto.
monstruo trinquete
1
¿Está buscando un algoritmo que funcione en el caso más general o puede restringirse, por ejemplo, al caso 2D? Esto podría ser más fácil de resolver con más información o restricciones sobre la entrada. Utiliza la palabra polígono que puede insinuar solo en 2D, también la pregunta que vinculó sugiere el caso en 2D. Además, ¿es suficiente considerar las distancias de vértice a vértice o necesita resultados correctos para casos como el fenómeno de trinquete mencionado en su comentario ?
Nero
2
Además, me preocupa una forma de C que tiene un grosor muy estrecho, pero un interior grande y abierto; y así un gran radio de curvatura. Su diámetro (como lo define) sería muy pequeño porque solo sería un corto que siga la curvatura de la C. Sin embargo, un nódulo de cáncer del tamaño del tamaño interior sería bastante preocupante. Entonces, tal vez sea el casco convexo del que desea calcular el diámetro.
Wyck el

Respuestas:

1

No tengo una respuesta exacta para esto, ya que la respuesta está lejos de ser trivial. Sugeriría que eche un vistazo a la geometría computacional, ya que esto claramente es un problema de visibilidad, supongo que ya existe una solución. Mi propia idea sería: para cada segmento de línea en el polígono encontrar las partes visibles de los otros segmentos de línea y luego elegir el par de puntos que están más separados. Enlace inspirador: Wikipedia sobre 'polígono de visibilidad' .

más allá
fuente