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

Ответ 1

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

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

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

Ответ 2

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

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

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

Ответ 3

Жесткое домашнее задание eh?

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

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

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

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

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

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

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

Ответ 4

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

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

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

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

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

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

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

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

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

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

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

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

  L = P1 + (P2-P1).n
  

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

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

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

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

Ответ 5

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

Ответ 6

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

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

Ответ 7

1.) Храните свои точки в таблице SQL Server 2008 с использованием геостатического типа данных (или географии, если они определены с использованием координат lat/long) Здесь script для создания 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.) Определите свою линию как linestring, используя тот же тип данных и 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), вы можете использовать этот же подход в С# или прямо в SQL Server.

Ответ 8

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

Ответ 9

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

Для каждого сегмента линии вычислять значения необходимо преобразовать точку из мировых координат в локальные координаты относительно отрезка (так что любая точка, проходящая через вычисление, будет относиться к системе координат, где отрезок линии является осью x )

Для каждой точки используйте следующие проверки:

1- Если точка находится на расстоянии от любой конечной точки, мы знаем, что она должна быть включена. Это достигается простым вычислением расстояния между каждой конечной точкой и точкой-мишенью ^ 2 = (x2 - x1) ^ 2 + (y2 - y1) ^ 2.

2- Запустите целевую точку через преобразование. После преобразования if x >= 0 и x <= (длина отрезка) и | y | <= расстояние, тогда необходимо указать целевую точку, в противном случае ее следует исключить.

Моя векторная математика немного ржавая, поэтому я не могу предоставить лучший код/​​примеры извините! Но, может быть, мой пост вдохновит кого-то другого на то, чтобы написать правильный способ сделать это.

Ответ 10

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

EDIT: я тупо использовал 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;
    }
}

Ответ 11

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

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

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

Ответ 12

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