Detectar si un punto pertenece a un cuadro delimitador con distancias

Question

Tengo una caja con coordenadas límite conocidos (latitudes y longitudes): latN, latS, lonW, lonE .

Tengo un misterio point P con coordenadas desconocidas. La única información disponible es la distancia desde P a cualquier punto de p . dist(p,P) . `

Necesito una función que me dice si este punto está dentro o fuera de la caja.

Answer 1

Una vez que conocemos las coordenadas de P , entonces el problema de invertir en un bien conocido respuesta. Para obtener las coordenadas de $P=(x, y)$ tomamos tres mediciones. Me ha movido el sistema de coordenadas en una esquina y el nombre de los objetos en consecuencia, con $a$ el lado horizontal y $b$ el lado vertical. Además, vamos a hallar las coordenadas de P en notación polar, con la distancia $r$ y el ángulo de $\theta$.

La medición de $\vec{AP}$ obtenemos la distancia $r$. La medición de $\vec{BP}$ nos da el coseno y la medición de $\vec{DP}$ nos da el seno, por medio de la ley de los cosenos.

$$ \cos\theta = \frac{r^2+a^2-d_{BP}^2}{2 a r} $$ $$ \sin\theta = \frac{r^2+b^2-d_{DP}^2}{2 b r} $$

So the location of P is

$$ x = r \cos\theta = d_{AP} \frac{r^2+a^2-d_{BP}^2}{2 a r} $$ $$ y = r \sin\theta = d_{AP} \frac{r^2+b^2-d_{DP}^2}{2 b r} $$

The point is inside if $x>=0$ and $x<=$ and $y>=0$ and $y<=b$.

He comprobado esto con la anterior C# código

static void Main(string[] args)
{

    double a=2;
    double b=1;

    Point A=new Point(0, 0);
    Point B=new Point(a, 0);
    Point D=new Point(0, b);

    for(double x=-5; x<=5; x+=0.5)
    {
        for(double y=-5; y<=5; y+=0.5) 
        {
            Point P=new Point(x, y);

            double d_AP=A.DistanceTo(P);
            double d_BP=B.DistanceTo(P);
            double d_DP=D.DistanceTo(P);

            double r=d_AP;
            double cos=(a*a+r*r-d_BP*d_BP)/(2*a*r);
            double sin=(b*b+r*r-d_DP*d_DP)/(2*b*r);                    

            double x_P=r*cos;
            double y_P=r*sin;

            P.inside=(x_P>=0&&x_P<=a)&&(y_P>=0&&y_P<=b);

            Point Q=new Point(x_P, y_P);
            if(P.DistanceTo(Q)>1e-6)
            {
                Console.WriteLine("({0},{1}) - ({2},{3})", x, y, x_P, y_P);
            }
        }
    }

}

public struct Point
{
    double x, y;  //private, not visible
    public bool inside;

    public Point(double x, double y)
    {
        this.x=x;
        this.y=y;
        this.inside=false;
    }

    public double DistanceTo(Point p)
    {
        return Math.Sqrt((p.x-x)*(p.x-x)+(p.y-y)*(p.y-y));
    }
}

y todos los cheques aceptar. No hay necesidad de verificar si hay signos y cuadrantes. Todo funciona correctamente.

Answer 2

Hay una forma geométrica a hacerlo también.

Dibuje un rectángulo y un punto en su interior. Usted puede hacer cuatro triángulos orientados al conectar el punto a las diagonales, y luego uniformemente dibujo de las flechas en los bordes de manera que todos ellos "el flujo de las agujas del reloj" o "flujo de la izquierda".

Ahora si usted se imagina que arrastrar el punto sobre un borde, vas a ver que tres de los triángulos conservar su orientación, pero el uno cuyo borde se ha cruzado le dará la vuelta a la orientación. Si usted va a través de una esquina en su lugar, dos de los cuatro triángulos se flip orientación.

Así, por uniformemente la representación de estos cuatro triángulos con los vectores, usted sólo tendrá que comprobar sus productos cruzados para ver si son todos el mismo signo. Si los dos no está de acuerdo con los otros dos, usted sabe que el punto se encuentra en una diagonal en el exterior. Si uno no está de acuerdo con el resto, se encuentra fuera de uno de los bordes. Si todos están de acuerdo, el punto está en el interior.

Aquí está el programa de instalación. Suponga que se dan $(a_1,a_2),(b_1,b_2),(c_1,c_2),(d_1,d_2)$ como las esquinas del rectángulo (en orden cíclico, digamos, a la derecha), y $(e_1,e_2)$ es el punto.

Un triángulo vector de bordes (en este orden) $(a_1,a_2)-(e_1,e_2)$$(b_1,b_2)-(a_1,a_2)$. Los otros tres serán: $(b_1,b_2)-(e_1,e_2)$ $(c_1,c_2)-(b_1,b_2)$ $(c_1,c_2)-(e_1,e_2)$ $(d_1,d_2)-(c_1,c_2)$ $(d_1,d_2)-(e_1,e_2)$ $(a_1,a_2)-(d_1,d_2)$

Todos ellos han sido configurada de tal forma que si el punto está en el interior, a continuación, tomar la cruz de producto del primer vector con el segundo lugar en cualquiera de estos cuatro pares, todos ellos tienen el mismo signo (todos positivos o todos negativos).

Dado cualquiera de los cuatro puntos en un orden cíclico, como este, usted puede llenar las cuatro ecuaciones y comprobar todos sus productos cruzados.

Answer 3

Entiendo tu pregunta, de alguna manera es similar a esta:Cómo comprobar si un punto está dentro de un rectángulo. Veo que mi respuesta (aunque no obtuvo voto alguno), puede ser correcto y puede aplicarse simplemente en su caso.

Answer 4

Uno (lejos del óptimo, pero sencillo) manera de hacerlo: ya que tienes el cuadro de coordenadas disponibles, también es de suponer que las cuatro esquinas de la caja disponible. Ahora, sabiendo $P$'s distancias desde los dos puntos a lo largo de un borde le permite reducir la localización del punto a uno de los dos puntos de $i_1$ $i_2$ (desde los dos círculos $|P-p_1|=r_1$ $|P-p_2|=r_2$ tiene a lo más dos puntos de intersección). Del mismo modo, a sabiendas de $P$'s distancia de los dos puntos a lo largo de la otra orilla se reduce su ubicación en uno de los dos puntos de $i_3$$i_4$. (Si usted realmente desea, me puede dar forma con las ecuaciones de esos dos puntos, pero es sencillo encontrar a ti mismo; es sólo un poco de álgebra o alternativamente un poco de geometría) Ahora, el trampolín: los dos conjuntos de dos puntos no puede ser el mismo, porque el $i_2$ es el reflejo de $i_1$ sobre el borde de la $p_1p_2$ $i_3$ es el reflejo de $i_4$ sobre una diferente edge $p_3p_4$. Esto significa que usted puede comparar para determinar cuál de los puntos de $i_1,i_2$ es idéntica a la que el punto de $i_3,i_4$ y eso es suficiente para obtener su punto exacto. Una vez que tienes eso, el estándar de punto en el rectángulo de pruebas debería ser suficiente.

Tenga en cuenta que para algorítmica de los motivos, una vez que usted ha $i_1$ $i_2$ desea realizar el punto en el rectángulo de la prueba en ambos de ellos; no pueden estar ambos en el rectángulo, pero es posible que ambos están fuera del rectángulo, en el que caso de que usted no tiene que preocuparse de ir y encontrar a $i_3$$i_4$.

Answer 5

La medida de la distancia desde cualquier punto le da un círculo alrededor de ese punto como un lugar geométrico de las posiciones posibles de $P$. Realizar cualquier medición desde un punto de $A$. Si la cuestión no se resuelve después de esto (es decir, si el círculo cruza la frontera del rectángulo), hacer una medición desde cualquier otro punto de $B$. Los dos círculos en intersección dejar sólo dos posibilidades para la ubicación de $P$. Si tienes suerte, ambas opciones están dentro o fuera de la rectnagle y hemos terminado. De lo contrario, una tercera medición, tomar la forma de cualquier punto de $C$ no colineal con $A$ $B$ va a resolver la cuestión de la posición exacta de $P$ (y después de eso se ve fácilmente si $P$ está dentro o no.

Uno puede elegir el primer punto de $A$ "óptima" faschion tal manera que la probabilidad de una respuesta definitiva está maximizada. Mientras esto requiere el conocimiento acerca de algunos un prioi distribución donde se $P$ podría ser, el centro de la rechtangle parece una buena idea. El resultado es nondecisive sólo si la medición de la distancia es la que separa la mitad de la menor de los lados del rectángulo y la mitad de la diagonal del rectángulo.