¿Siempre es posible ampliar un polígono 2D simple con cualquier punto?

Question

Dado un polígono 2D simple P = ( M1 .. Mn ) y un punto M, ¿es siempre posible construir un nuevo polígono simple P' "añadiendo" M a P como un nuevo vértice?

Si es así, ¿es siempre posible sin alterar el orden de los vértices de P?

Creo que la respuesta a esas 2 preguntas es sí, pero he intentado probarlo y he fracasado.

Mi planteamiento era tratar de definir algún tipo de distancia entre M y cada uno de los lados de P, por lo que el lado más "cercano" sería el que se rompería para insertar a M como nuevo vértice. Obviamente, la habitual distancia ortogonal de un punto a una línea no funciona.

El contexto más amplio es un programa de dibujo que estoy escribiendo en el que permito al usuario añadir vértices a sus polígonos, pero en el que me esfuerzo por mantener los polígonos simples.

(polígono simple: un polígono en el que no se cruzan dos lados).

P.D.: El inglés es una lengua extranjera para mí, especialmente cuando hablo de matemáticas. Pido disculpas si mi pregunta está mal formulada.

Answer 1

Una palabra clave que le ayudará a buscar ideas es poligonización . Escribí un artículo sobre el tema, cuya idea probablemente le proporcionaría un algoritmo adecuado, pero quizás sea demasiado complicado para sus propósitos. Voy a ilustrar el algoritmo en el contraejemplo inteligente de Henning.

Quieres conectar $(0,0)$ el centro de su polígono, al lado más cercano. Introduce dos nuevos pseudovértices en ese lado y estira el límite hasta alcanzarlo (figura de la izquierda). Ahora quita los dos pseudovértices, dejando que el límite se repliegue como una goma elástica: ¡wang! Desgraciadamente, ahora el límite se autotoca por la izquierda y ya no tienes un polígono simple (figura del medio). En el vértice que se ha producido, vuelve a hacer un "twang" para eliminar el doble contacto del límite. El resultado se El resultado se muestra en la figura de la derecha, que es quizás lo mejor que se puede esperar dadas las circunstancias.

Si quieres seguir con esto, a pesar de su complejidad, ver " Conexión de poligonizaciones mediante estiramientos y torsiones ."

Answer 2

Un contraejemplo es el octógono (no convexo) con vértices

(1,2), (1,3), (2,-1), (3,-1),
(-1,-2), (-1,-3), (-2,1), (-3,1)

No se puede añadir el punto (0,0) entre dos de los puntos sin crear una intersección.

Answer 3

Es cierto siempre y cuando $M$ y $P$ están separados por una línea. En este caso, al menos un lado de $P$ es completamente visible desde $M$ y se puede sustituir este lado por dos lados que pasan por $M$ .

En general, un conjunto de segmentos de línea que no se cruzan (excepto posiblemente en sus extremos) puede ordenarse parcialmente con respecto a un punto lejano sin ciclos. Esta ordenación puede encontrarse mediante un barrido de líneas polares centrado en ese punto.

Véase, por ejemplo Localización óptima de puntos en una subdivisión monótona , TR disponible aquí .