Алгоритм нахождения всех точек на двумерной сетке на некотором расстоянии от другой точки - PullRequest
Новая
       42

Алгоритм нахождения всех точек на двумерной сетке на некотором расстоянии от другой точки

6 голосов
/ 31 декабря 2011

У меня есть точка на 2D-сетке (x, y), и мне нужно найти все точки, которые находятся на расстоянии n от этой точки.Я измеряю расстояние, используя формулу расстояния между двумя точками.Кто-нибудь знает, как это сделать?

Редактировать: просто для справки, я пытаюсь написать какой-нибудь поиск пути ИИ, который будет находиться на некотором расстоянии от цели в системе, которая использует местоположения на основе сетки.,В настоящее время я использую поиск пути A *, но я не уверен, имеет ли это значение или имеет значение, так как я немного новичок в этом.

Ответы [ 5 ]

2 голосов
/ 01 января 2012

Вот что я бы сделал:

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

  2. Вы также можете использовать внутреннюю оптимизацию ограничивающего прямоугольника.Если точки ближе, чем D * sqrt (2) / 2 по x или y, то они, безусловно, находятся внутри круга радиуса D. Это также дешевле, чем вычисление формулы расстояния.

  3. Тогда у вас есть меньшее количество точек-кандидатов, которые могут находиться внутри круга радиуса D. Для них используйте формулу расстояния.Помните, что если D = sqrt (Δx 2 + Δy 2 ), то D 2 = Δx 2 + Δy 2.
    Таким образом, вы можете пропустить стоимость вычисления квадратного корня.

Итак, в псевдокоде вы можете сделать следующее: 

for each point
begin
    if test 1 indicates the point is outside the outer bounding box, 
    then skip this point

    if test 2 indicates the point is inside the inner bounding box, 
    then keep this point

    if test 3 indicates the point is inside the radius of the circle, 
    then keep this point
end
0 голосов
/ 16 июля 2012

Java-реализация: 

public static Set<Point> findNearbyPoints(Set<Point> pts, Point centerPt, double radius) {
    Set<Point> nearbyPtsSet = new HashSet<Point>();
    double innerBound = radius * (Math.sqrt(2.0) / 2.0);
    double radiusSq = radius * radius;
    for (Point pt : pts) {
        double xDist = Math.abs(centerPt.x - pt.x);
        double yDist = Math.abs(centerPt.y - pt.y);
        if (xDist > radius || yDist > radius)
            continue;
        if (xDist > innerBound || yDist > innerBound)
            continue;
        if (distSq(centerPt, pt) < radiusSq)
            nearbyPtsSet.add(pt);
    }
    return nearbyPtsSet;
}
0 голосов
/ 01 января 2012

Это не будет использовать формулу расстояния, но если вы ищете точки точно на расстоянии n, возможно, вы могли бы использовать sin / cos?

В псевдокоде: 

for degrees in range(360):
    x = cos(degrees) * n
    y = sin(degrees) * n
    print x, y

Это напечатало бы каждую точку n с шагом 360 градусов.

0 голосов
/ 01 января 2012

Это называется поиск ближайшего соседа. Больше на http://en.wikipedia.org/wiki/Nearest_neighbor_search

Для этого есть открытые библиотеки. Я использовал один, написанный для C, и рекомендую его: http://www.cs.umd.edu/~mount/ANN/. ANN означает Приблизительный ближайший сосед, однако вы можете отключить приближение и найти точных ближайших соседей.

0 голосов
/ 01 января 2012

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

алгоритм грубой силы является O (N ^ 2),Однако существуют более эффективные алгоритмы, которые используют пространственные индексы для уменьшения сложности алгоритма и количества вычислений расстояния.Например, вы можете использовать R-Tree для индексации ваших очков.

...