Какой алгоритм может эффективно найти набор точек на определенном расстоянии пути?

Question

Учитывая набор точек s (набор координат x, y) и путь, который состоит из отрезков, соединяющих набор точек l , описывают эффективное алгоритм, который можно использовать для поиска подмножества точек из s , которые находятся в пределах указанного расстояния d пути l .

Практическое применение этого может состоять в том, чтобы найти список ресторанов в пределах 10 миль в любом месте вдоль дорожной поездки между городами.

Например, на следующей диаграмме точки зеленого цвета будут включены в результаты поиска.

Решения предпочтительнее в C #, но бонусные баллы могут быть предоставлены для подхода на основе SQL: -)

Answer 1

Я тоже думал об этом некоторое время назад. Я думаю, эффективный вводит в заблуждение. Достаточно просто протестировать все отрезки для каждой точки. очень дешево рассчитать расстояние . Если есть много точек, вы также можете подумать о том, чтобы уточнить стратегию, которая указывает на выбор, используя подход с набором уровней. т.е.

• идите вдоль линии, ширина шага в 2 раза больше расстояния, которое вы хотите проверить (больше или меньше?), И создайте искусственные точки, которые «близки».
• itereate: выбирайте новые точки вокруг точек, которые «близки» (не рассчитывайте евклидово расстояние, просто 1-норму и просто проверяйте координаты x и y) - затем проверяйте их расстояние (вы даже можете наследовать отрезок линии от искусственных точек до найденных «близких» точек и сначала выберите эту для тестирования, но расширите поиск, поскольку могут быть перекосы!)

это, возможно, не завершено, но должно быть быстрым и избегать контрольных точек далеко и вполне нормально.

Answer 2

1. Определите «левую дорогу» и «правую дорогу»: для каждого отрезка линии исходного пути создайте отрезок линии на d единиц «левее» и один d на «правее» сегмента .

2. Соедините левую и правую дороги на концах, чтобы сделать многоугольник.

3. Примените стандартный алгоритм, чтобы определить, какие точки интереса находятся внутри многоугольника.

Answer 3

1.) Сохраняйте свои точки в таблице SQL Server 2008, используя тип данных geometry (или географию, если они определены с использованием координат lat / long) Вот скрипт для создания 100 выборочных точек, распределенных случайным образом между (0,0) и (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.) Определите свою линию как строку, используя тот же тип данных и SRID, что и для ваших точек:

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

3.) Используйте метод STDistance () в предикате запроса SELECT к таблице точек. Например, чтобы выбрать все точки в пределах 5 единиц линии:

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

Более того, поскольку пространственные методы SQL Server доступны в распространяемой dll (Microsoft.SqlServer.Types.dll - часть пакета возможностей SQL Server http://www.microsoft.com/downloads/en/details.aspx?FamilyID=ceb4346f-657f-4d28-83f5-aae0c5c83d52),, этот же подход можно использовать в любом C # или напрямую в SQL Server.

Answer 4

Если вы хотите выполнить хотя бы часть работы в SQL, вы можете вычислить ограничивающую рамку для пути, а затем включить в свой запрос условие, что местоположение находится внутри ограничительной рамки. Вы запускаете один из других алгоритмов только для возвращаемых строк.

Это, по крайней мере, избавляет вас от необходимости загружать всю базу данных для каждого пути.

Answer 5

Я не совсем уверен, правильно ли я понял вопрос, но Алгоритм Дейкстры не подходит? Он находит кратчайшие пути от исходного узла, и вы можете просто прервать его после достижения максимального расстояния и проверить, какие точки из s уже найдены. Я не уверен, насколько хорошо он играет с SQL.

Answer 6

Единственное решение этого заключается в следующем:

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

Внутренний цикл может быть завершен досрочно, как только найдена точка, лежащая в пределах ограничения. Обратите внимание, что внутреннюю и внешнюю петли можно транспонировать.

Тогда возникает вопрос о том, находится ли точка в пределах ограничения. mbeckish предлагает использовать простой тест прямоугольника, где прямоугольник формируется вытягиванием вдоль перпендикуляра линии, но это не удастся для точек около конечных точек, но за пределами этого прямоугольника. Выдавливание прямоугольника также вдоль направления линии также не удастся, поскольку точки в конце должны действительно использовать точку в круговом тесте:

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

, где * находится внутри расширенного прямоугольника, но за пределами закругленной торцевой крышки, что будет более строгим тестом.

Теперь тест на расстояние может быть не тестом «по прямой линии», а графическим поиском, например, точек в пределах x миль от дороги, используя только дороги для их соединения:

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

На приведенной выше схеме цель находится в зоне поиска, но добраться до цели по доступным дорогам будет больше, чем допустимое расстояние.

Однако, если вы решите реализовать тест, потребуется базовый цикл в алгоритме цикла.

Способы проверки ограничения, где ограничение является ограничением «по прямой линии»:

1. Геометрически: сначала определите расстояние от точки P до линии. Затем, если точка находится внутри ограничения, спроецируйте точку P на отрезок, где линия определяется как:

   L = P1 + (P2-P1).n
   

   где P1 и P2 - конечные точки, а n - параметрическая переменная. Если значение n для прогнозируемого P находится в диапазоне 0 <= n <= 1, то точка находится между P1 и P2. Наконец, выполните проверку точки в кругах для окружностей с центрами P1 и P2. </p>

2. Преобразования. Создайте матрицу преобразования для каждого отрезка, чтобы P1 преобразовывался в начало координат, а P2 - в (| P1-P2 |, 0). Затем примените каждое преобразование ко всем точкам, а затем проверьте каждую точку в прямоугольнике (0, -ограничение) - (| P1-P2 |, ограничение). Этот метод может быть сильно оптимизирован с использованием SIMD или графического процессора

3. Графически: нарисуйте отрезки линии в растровом изображении, используя перо с закругленными концевыми заглушками и шириной, пропорциональной расстоянию ограничения. Затем для каждой контрольной точки проверьте пиксель в растровом изображении, соответствующий этой точке. Это не точно (но большие растровые изображения создают более точные результаты, но требуют больше памяти), но довольно быстро после создания растрового изображения.

   Если ограничение определяется маршрутом вдоль графика, оно становится более сложным. Вы должны посмотреть на поиск в ширину, где начальные точки - это конец каждого отрезка, а конечная точка - потенциальная цель. Если линейный сегмент имеет соединения по своей длине, то разбейте линейный сегмент на сегменты без соединений.

Answer 7

Трудное домашнее задание, а?

Возможно, хорошим началом может быть рассмотрение алгоритмов поиска путей в ширину - может быть, для этого будет полезен какой-то подобный подход с заливкой?

Редактировать: Так что если это просто выглядит как домашнее задание, может быть, я могу быть более полезным ...

Сначала я хотел бы определить прямоугольник, содержащий линию и точки, которые могут быть внутри нее, так как это может позволить нам избавиться от большого количества точек, которые находятся далеко от нашей линии.

Для каждой точки вы можете создать квадрат, представляющий список точек в радиусе этой точки. Это снова способ сокращения количества элементов для поиска.

К сожалению, я не знаю достаточно геометрии, чтобы знать, как правильно определить, находится ли список точек внутри или снаружи круга, помимо простого вычисления расстояния между ними и центром круга с помощью базового триггера. Я уверен, что есть один. Используя упомянутое выше простое подразделение или какой-либо другой вариант, вы обнаружите, что вы можете упреждающим образом сократить количество возможных точек, которые необходимо найти.

Также, если вы сохраняете все свои точки для поиска в одном списке и удаляете те, которые являются попаданиями для первого круга, когда дело доходит до измерения последующих фигур. Я использовал версию этого перебора для простой проверки почтового индекса на основе данных о местоположении - это задокументировано во многих местах в Интернете, но запуск его по пути, вероятно, будет довольно вычислительно дорогим.

Этот геометрический подход, вероятно, был бы лучше для ситуации, когда вы не выполняли много повторных поисков - если их много, вы можете организовать свои мосты в сеть, чтобы вы могли использовать стандартный поиск пути на их. Было бы целесообразно сделать несколько прототипов, чтобы увидеть, какой из них более эффективен, но я ожидаю, что если вы создадите подходящую сеть для представления ваших данных, вы сможете более гибко подходить к ее поиску.

Answer 8

Я удивлен, что никто не упомянул A * alogirithm для этого. Похоже, идеально подходит. Что мне здесь не хватает? Если вы не знакомы с ним, Google, и вы найдете =). (Да, это происходит из игрового мира ...)

Answer 9

Учитывая общие вычислительные инструменты, ваш лучший алгоритм будет состоять в том, чтобы отфильтровать заведомо неинтересные точки и найти расстояние от каждого отрезка линии до каждой оставшейся точки. (Предложенное решение о многоугольнике неверно - интересующей областью является объединение этого многоугольника с окружностью радиуса d вокруг каждой точки на l - и на самом деле менее эффективно, чем просто найти расстояние от каждой точки до каждого отрезка.)

Какие фильтры будут наилучшими, зависит от характера ваших данных - например, в примере диаграммы фильтрация ограничивающего прямоугольника l (плюс d ) будет очень полезно.

Интересным фильтром будет: заданная точка p , определяющая l , взять окружность радиуса r , где r - это максимальная длина двух сегментов, частично определенная как p плюс d . Только точки в этом круге могут быть достаточно близко к этим двум сегментам, чтобы быть в нашем наборе решений, поэтому мы можем быстро определить, можем ли мы пропустить эти два вычисления расстояния сегмента линии. (Это будет менее эффективно, если некоторые линейные сегменты будут очень длинными, но если они есть, эти линейные сегменты можно легко разбить на более мелкие куски.)

Answer 10

Я верю, что эти два класса ответят на ваш вопрос. Я построил функцию GetArea (), используя Формула Херона . Убедитесь, что точки сегмента всегда передаются первыми в IsPointWithinDistanceToLineSegment, а TestPoint всегда передаются третьими.

РЕДАКТИРОВАТЬ: я тупо использовал Point, который позволяет целые числа только для X и Y. Вам нужно будет исправить это с другим классом, который принимает удваивается или плавает как X и 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;
    }
}