algorithm - que - algoritmos de agrupamiento clustering

¿Qué algoritmo puede encontrar eficientemente un conjunto de puntos dentro de una cierta distancia de un camino?

Question

Dado un conjunto de puntos s (un conjunto de coordenadas x, y) y una ruta compuesta por segmentos de línea que unen un conjunto de puntos l , describa un algoritmo eficiente que puede usarse para encontrar un subconjunto de puntos de s que están dentro de la distancia especificada d de la ruta l .

Una aplicación práctica de esto puede ser encontrar una lista de restaurantes dentro de 10 millas en cualquier lugar a lo largo de un camino entre las ciudades.

Por ejemplo, en el siguiente diagrama, los puntos en verde se incluirán en los resultados de búsqueda.

Las soluciones serían preferidas en C #, pero se pueden dar puntos de bonificación para un enfoque basado en SQL :-)

Answer 1

1. Defina un "camino izquierdo" y un "camino derecho": para cada segmento de línea del camino original, cree un segmento de línea d unidades a la "izquierda" y una unidad d a la "derecha" del segmento.

2. Conecte la carretera izquierda y la derecha en los extremos para hacer un polígono.

3. Aplique un algoritmo estándar para determinar qué puntos de interés se encuentran dentro del polígono.

Answer 2

¿Podría usar un árbol cuádruple para dividir el espacio en segmentos, y luego solo para puntos en los segmentos cercanos a su camino?

Answer 3

Deberías ser capaz de lograr esto a través de vectores de matemáticas y trigonometría, aunque los métodos exactos me escapan.

Para cada segmento de línea, calcule los valores necesarios para transformar un punto de coordenadas mundiales en coordenadas locales relativas al segmento de línea (de modo que cualquier punto que se ejecute a través del cálculo sería relativo a un sistema de coordenadas donde el segmento de línea es el eje x)

Para cada punto, ejecute las siguientes comprobaciones:

1- Si el punto está dentro de la distancia de cualquier punto final, sabemos que debe incluirse. Esto se logra mediante un cálculo simple de distancia ^ 2 <= (x2 - x1) ^ 2 + (y2 - y1) ^ 2 entre cada punto final y el punto objetivo.

2- Ejecutar el punto objetivo a través de la transformación. Después de la transformación si x> = 0 yx <= (longitud del segmento de línea) y | y | <= distancia, entonces el punto objetivo debe incluirse; de ​​lo contrario, debe excluirse.

Mi vector de matemáticas está un poco oxidado, así que no puedo proporcionar un código / ejemplos mejor, ¡lo siento! Pero tal vez mi publicación inspire a otra persona a escribir la forma correcta de hacerlo.

Answer 4

Dificultad para la tarea ¿eh?

Tal vez un buen comienzo sea observar algoritmos de pathfinding en primer lugar; tal vez sería útil algo como un enfoque de inundación para esto.

Editar: Entonces, si parece una tarea para casa, tal vez pueda ser más útil ...

Primero buscaría definir un rectángulo que contenga la línea y los puntos que podrían estar dentro de él, ya que eso nos puede permitir deshacernos de una gran cantidad de puntos que no están cerca de nuestra línea.

Para cada punto, podría crear un cuadrado que represente la lista de puntos dentro del radio de ese punto. Esta es nuevamente una forma de reducir la cantidad de elementos para buscar.

Desafortunadamente, no conozco la geometría suficiente como para ser consciente de una forma inteligente de decidir si una lista de puntos cae dentro o fuera de un círculo, además de simplemente calcular la distancia entre ellos y el centro del círculo a través de trigonométrico básico. seguro que hay uno. Al usar la subdivisión simple mencionada anteriormente o alguna variante de la misma, debería encontrar que puede reducir de manera preventiva la cantidad de puntos posibles que deben buscarse.

También si mantiene todos sus puntos para buscar en una lista y elimina los que son éxitos para el primer círculo, cuando se trata de medir las formas posteriores. He usado una versión de fuerza bruta de esto para hacer comprobaciones simples de distancia de código postal basadas en datos de ubicación, que está documentado en bastantes lugares en línea, pero correrlo por un camino probablemente sería bastante costoso desde el punto de vista computacional.

Este enfoque geométrico probablemente sería mejor para una situación en la que no estuvieras haciendo muchas búsquedas repetidas; si hay muchas seguidas, podrías organizar tus ponts en una red para que puedas usar pathfinding estándar sobre ellos. Merece la pena hacer algunas protografías para ver cuál es más eficiente, pero esperaría que si creara una red apropiada para representar sus datos, pudiera ser más flexible en la forma de buscarlo.

Answer 5

También pensé en esto hace algún tiempo. Creo que eficiente es engañoso. Solo probar todos los segmentos de línea para cada punto es suficiente. Es muy barato calcular la distancia . Si hay muchos puntos, también puede pensar en refinar la estrategia que apunta a elegir usando un enfoque de conjunto de niveles. es decir

• ir a lo largo de la línea, paso ancho 2 veces la distancia que desea comprobar (más o menos?) y crear puntos artificiales que están "cerca".
• itereate: elija nuevos puntos alrededor de puntos que estén "cerca" (no calcule una distancia eucledian, solo una norma 1 y simplemente pruebe las coordenadas xey) - luego pruebe su distancia (incluso puede heredar el segmento de línea específico de los puntos artificiales a los puntos "cercanos" encontrados y seleccione ese primero para probar, pero amplíe la búsqueda, ¡ya que podría haber giros!)

es posible que no sea completo, pero debe ser rápido y evitar revisar puntos muy lejos y bastante bien.

Answer 6

No estoy seguro si entiendo la pregunta correctamente, pero ¿no encajaría el algoritmo de Dijkstra ? Encuentra las rutas más cortas desde un nodo de origen, y puedes abortar después de alcanzar tu distancia máxima y verificar qué puntos de s ya se han encontrado. Aunque no estoy seguro de lo bien que juega con SQL.

Answer 7

Creo que estas dos clases responderán a tu pregunta. Construí la función GetArea () usando Heron''s Formula . Asegúrese de que los puntos de segmento siempre se pasen primero al IsPointWithinDistanceToLineSegment y el TestPoint siempre pase el tercero.

EDITAR: usé estúpidamente Point, que solo permite enteros para X e Y. Tendrás que arreglar esto con otra clase que tome dobles o flotantes como X e Y ...

public class Geometry
{
    public static double GetDistanceBetweenTwoPoints(Point SegmentStart, Point SegmentEnd)
    {
        return Math.Sqrt(Math.Pow(SegmentEnd.X - SegmentStart.X, 2) + Math.Pow(SegmentEnd.Y - SegmentStart.Y, 2));
    }

    public static bool IsPointWithinDistanceToLineSegment(Point SegmentStart, Point SegmentEnd, Point TestPoint, double TestDistance)
    {
        if (GetDistanceBetweenTwoPoints(SegmentStart,SegmentEnd) <= TestDistance || GetDistanceBetweenTwoPoints(SegmentEnd,TestPoint) <= TestDistance)
        {
            return true;
        }
        var T = new Triangle(SegmentStart, SegmentEnd, TestPoint);
        var BaseLength = GetDistanceBetweenTwoPoints(SegmentStart, SegmentEnd);
        var Area = T.GetArea();
        var TriangleHeight = 2* Area / BaseLength;
        return T.AB >= T.BC && T.AB >= T.AC && TriangleHeight <= TestDistance;
    }
}

public class Triangle
{
    public Triangle(Point a, Point b, Point c)
    {
        this.a = a;
        this.b = b;
        this.c = c;
    }

    public Point a
    {
        get;
        set;
    }

    public Point b
    {
        get;
        set;
    }

    public Point c
    {
        get;
        set;
    }

    //Lengths of Sides
    public double AB
    {
        get
        {
            return Geometry.GetDistanceBetweenTwoPoints(a, b);
        }
    }

    public double AC
    {
        get
        {
            return Geometry.GetDistanceBetweenTwoPoints(a, c);
        }
    }

    public double BC
    {
        get
        {
            return Geometry.GetDistanceBetweenTwoPoints(b, c);
        }
    }

    public double GetArea()
    {
        var Term1 = Math.Pow((Math.Pow(AB, 2) + Math.Pow(AC, 2) + Math.Pow(BC, 2)), 2);
        var Term2 = 2 * (Math.Pow(AB, 4) + Math.Pow(AC, 4) + Math.Pow(BC, 4));
        var result = .25 * Math.Sqrt(Term1 - Term2);
        return result;
    }
}

Answer 8

Si desea hacer al menos parte del trabajo en SQL, puede calcular un cuadro delimitador para la ruta, luego incorporar a su consulta la condición de que la ubicación se encuentre dentro del cuadro delimitador. Ejecuta uno de los otros algoritmos solo contra las filas devueltas.

Esto al menos evita que tengas que descargar toda la base de datos para cada ruta.

Answer 9

Dadas las herramientas informáticas generales, su mejor algoritmo va a ser una variación en el filtrado de puntos obviamente poco interesantes y la búsqueda de la distancia desde cada segmento de línea hasta cada punto restante. (La solución de polígono sugerida es incorrecta: el área de interés es la unión de ese polígono con el círculo de radio d alrededor de cada punto en l ) y en realidad es menos eficiente que simplemente encontrar la distancia desde cada punto hasta cada segmento de línea).

Qué filtros son mejores dependerá de la naturaleza de sus datos; por ejemplo, en el diagrama de muestra, el filtrado en el cuadro delimitador de l (más d ) será muy útil.

Un filtro interesante sería: dado el punto p que define l , tome un círculo de radio r , donde r es la longitud máxima de los dos segmentos definidos en parte por p más d . Solo los puntos dentro de este círculo pueden estar lo suficientemente cerca de esos dos segmentos para estar en nuestro conjunto de soluciones, por lo que podemos determinar rápidamente si podemos omitir esos dos cálculos de distancia de segmento de línea. (Esto será menos eficiente si algunos segmentos de línea son muy largos, pero si lo son, esos segmentos de línea se pueden dividir fácilmente en trozos más pequeños).

Answer 10

Me sorprende que nadie haya mencionado el A * alogirithm para esto. Parece un ajuste perfecto. ¿Que me estoy perdiendo aqui? Si no estás familiarizado con esto, google y ye encontrarán =). (Sí, viene del mundo de los videojuegos ...)

Answer 11

1.) Almacene sus puntos en una tabla de SQL Server 2008 usando el tipo de datos de geometría (o geografía, si están definidos usando coordenadas de lat / long) Aquí hay un script para crear 100 puntos de muestra distribuidos aleatoriamente entre (0,0) y ( 40,20):

DECLARE @Points table (
  id int,
  position geometry
  );

DECLARE @i int = 0, @x int, @y int;
WHILE (@i < 100)
BEGIN
  INSERT INTO @Points VALUES 
    (@i, geometry::Point(RAND() * 40, RAND() * 20, 0))
  SET @i = @i + 1;
END

2.) Defina su línea como una cadena de líneas, utilizando el mismo tipo de datos y SRID en cuanto a sus puntos:

DECLARE @line geometry = ''LINESTRING(0 10, 10 15, 20 8, 40 10)'';

3.) Use el método STDistance () en un predicado de una consulta SELECT contra la tabla de puntos. Por ejemplo, para seleccionar todos los puntos dentro de 5 unidades de la línea:

SELECT * FROM @Points
WHERE @line.STDistance(position) < 5;

Además, dado que los métodos espaciales de SQL Server están disponibles en un dll redistribuible (Microsoft.SqlServer.Types.dll - parte del paquete de características de SQL Server http://www.microsoft.com/downloads/en/details.aspx? FamilyID = ceb4346f-657f-4d28-83f5-aae0c5c83d52 ), puede usar este mismo enfoque en C # o directamente en SQL Server.

Answer 12

La única solución para esto es la siguiente:

for each point
  for each line
    is distance to line within constraints

El ciclo interno puede terminarse temprano una vez que se encuentra un punto que se encuentra dentro de la restricción. Tenga en cuenta que los bucles internos y externos se pueden transponer.

La pregunta entonces es la de determinar si un punto está dentro de la restricción. mbeckish sugiere usar una prueba de rectángulo simple, donde el rectángulo se forma mediante la extrusión a lo largo de la línea perpendicular, pero esto fallará en los puntos cercanos a los puntos finales pero fuera de este rectángulo. Extruir también el rectángulo a lo largo de la dirección de la línea también fallará ya que los puntos cerca del final realmente deberían usar una prueba de punto en círculo:

|-------------
| *    /
|    --
|   /
|  /
| |
| |
|/
|         |--------| <- the line segment

donde * está dentro del rectángulo expandido pero fuera del extremo redondeado que sería una prueba más estricta.

Ahora, la prueba de distancia podría no ser una prueba "en línea recta" sino una búsqueda de gráficos, por ejemplo, puntos dentro de x millas de una carretera usando solo caminos para conectarlos entre sí:

--------------------------------------------------- < the road
   |
   |              * <- target
...|..............|................................ < check distance
   |              |
   |--------------| <- roads to target

En el diagrama anterior, el objetivo se encuentra dentro del área de búsqueda, pero para llegar al objetivo a lo largo de las carreteras disponibles sería mayor que la distancia permitida.

Independientemente de cómo elija implementar la prueba, se requerirá el bucle básico en un algoritmo de bucle.

Maneras de verificar la restricción donde la restricción es una restricción ''en línea directa'':

1. Geométricamente: Primero, determine la distancia desde el punto P hasta la línea. Luego, si el punto está dentro de la restricción, proyecte el punto P sobre el segmento de línea, donde la línea se define como:

   L = P1 + (P2-P1).n

   donde P1 y P2 son los puntos finales yn es la variable paramétrica. Si el valor de n para el P proyectado está en el rango 0 <= n <= 1, entonces el punto está entre P1 y P2. Finalmente, haga un punto en la prueba circular para círculos centrados en P1 y P2.

2. Transformaciones: cree una matriz de transformación para cada segmento de línea de modo que P1 se transforme en el origen y P2 se transforme en (| P1-P2 |, 0). Luego aplique cada transformación a todos los puntos y luego pruebe cada punto en el rectángulo (0, restricción) - (| P1-P2 |, restricción). Este método puede ser altamente optimizado usando SIMD o una GPU

3. Gráficamente: dibuje los segmentos de línea en un mapa de bits usando un lápiz con tapas redondeadas y un ancho proporcional a la distancia de restricción. Luego, para cada punto de prueba, verifique el píxel en el mapa de bits correspondiente al punto. Esto no es exacto (pero los mapas de bits más grandes crean resultados más precisos pero necesitan más memoria) pero es bastante rápido una vez que se crea el mapa de bits.

   Si la restricción está definida por la ruta a lo largo de un gráfico, se vuelve más compleja. Debe buscar las primeras búsquedas de amplitud donde los puntos de inicio son el final de cada segmento de línea y el punto final es el objetivo potencial. Si un segmento de línea tiene uniones a lo largo de su longitud, divida el segmento de línea en segmentos sin uniones.