Determinar si un punto se encuentra dentro de la curva o fuera de una curva al azar usando lápiz y escala

Question

Decir, que me dan un punto y una cerrada curva. No sé nada acerca de la curva (de dónde es, qué es, su tamaño, etc.;dicen que está oculto en algún lugar)."No puedo ver la curva, pero puedo ver el punto donde está." Estoy suministra con un lápiz y una regla sin marcas de medición en ella, o en otras palabras, no se puede solo dibujo de líneas rectas con la regla, nada más que puedo hacer con la regla.

¿Cuál es el procedimiento que debo seguir para determinar si el punto se encuentra en el interior de la curva o fuera de ella, con independencia de la naturaleza, el tamaño, la forma o de cualquier otro parámetro de la curva?

Answer 1

Lo que el OP quiere realmente, creo, es un cruce de número algoritmo para un simple cerrado continuo de la curva. Esta curva puede ser considerado, sin embargo, como el caso límite de un polígono simple, por sus bordes convertirse en infinitesimalmente pequeño. Una referencia pertinente, por tanto, puede ser esta la Wikipedia uno:

• Punto en el polígono

y sobre todo el cruce de número de algoritmo.
Pero hay mucho más para decir sobre el Dentro / Fuera Problema, una vez que usted tome una buena mirada en ella.
Después de algunos (en vano) intenta responder a la pregunta de una manera sucinta, y aunque también muchos duplicados del material existente, he decidido simplemente redirigir a mi mejor tiro hasta el momento:

• Dentro / Fuera Problema

Si los puntos de la curva cerrada simple son considerados como píxeles (es decir, coordenadas enteras), entonces podemos siquiera concebir una que nunca falla algoritmo (sólo suponiendo que nuestra imagen no es demasiado grande).

Se ve en la foto de abajo que, por una curva continua, simple y directo de la aplicación de la travesía número algoritmo va a estar bien para los puntos de $A$$B$, pero que sin duda va a ir mal para los puntos de $C$$D$. De acuerdo a la ley de Murphy , si Algo puede salir mal, saldrá mal. Lo que significa que ignorar casos especiales, sobre todo en una geometría computacional medio ambiente, tarde o temprano, va a ser desastroso. Es de notar que el "mal" de los casos tiene que ver con los rayos que son tangentes a la curva.

Answer 2

Por la orden de intersección entre la curva y una línea de corte que produce dos puntos de intersección $P,Q$.

Si se les da punto es $O$, los cortes de línea curva cerrada en puntos extremos $P$ y $Q$, y luego continuar en una dirección sin volver a trazar ruta,

está fuera de si la orden es % o $ O,P, Q $ $ Q,P,O $y el interior si la orden es $ P,O,Q $ o $ Q,O,P.$

Ignorar (todos número de) puntos de intersección entre los puntos extremos.