Как найти ближайшие точки к заданной точке

Вычисляем ближайшие объекты по координатам

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

Исследование

Итак для решения задачи началось «гугление». И первое что было нагуглено это алгоритм расчета расстояний между двумя точками на шаре, статья уходила в Wikipedia. Статья конечно интересное, но как она поможет в моем деле!? Как выяснилось от нее будет толк, но не сразу. Смысл в том, что просчет расстояний по координатам хорош, но как делать выборку из базы и рассчитывать координаты «на ходу»!? Вероятно данным способом никак. Конечно, решение в лоб было каким то образом просчитать насколько можно сдвинуться от координаты чтобы получить нужное расстояние и запросить через какой-нибудь SQL BETWEEN.

Снова гуглим и нагугливаем ВОПРОС на Хабр Q&A. В лучшем ответе решение есть, но оно указывает, что у нас длина одного градуса в километрах равно 111 км, но это далеко не всегда так. Отсюда было понятно, что решение слишком не точное. Читаем дальше и там некий @alex40 предлагает решение как раз с between но выбирать по квадрату. Суть его решения заключается в том, чтобы взять диапазон координат по квадрату а не по окружности и запросить выборку как раз с оператором BETWEEN. И глядя на элегантность этого решения, я понял, что надо делать как то так, но оставался вопрос, что квадрат вносит слишком большую неточность.

Схема решения

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

Если соединить эти точки, на которые мы прибавили изначальную координату получится квадрат (простите не ровно нарисовал).

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

Расчеты

Приступаем к расчетам. Из открытых источников нам известно, что:

• Средний радиус Земли R = 6371210 м.

• Экваториальный радиус Земли R_Э = 6378,245 м.

• Полярный радиус Земли R_П = 6356,830 м.

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

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

Код для проверки

const EART_RADIUS = 6371210; //Радиус земли
const DISTANCE = 20000; //Интересующее нас расстояние

//https://en.wikipedia.org/wiki/Longitude#Length_of_a_degree_of_longitude
function computeDelta(degrees) {
  return Math.PI / 180 * EART_RADIUS * Math.cos(deg2rad(degrees));
}

function deg2rad(degrees) {
  return degrees * Math.PI / 180;
}

const latitude = 55.460531; //Интересующие нас координаты широты
const longitude = 37.210488; //Интересующие нас координаты долготы

const deltaLat = computeDelta(latitude); //Получаем дельту по широте
const deltaLon = computeDelta(longitude); // Дельту по долготе

const aroundLat = DISTANCE / deltaLat; // Вычисляем диапазон координат по широте
const aroundLon = DISTANCE / deltaLon; // Вычисляем диапазон координат по долготе

console.log(aroundLat, aroundLon);

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

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

1 градус — 63046.689652997775 метров
X градусов — 200000 метров

select
	name,
	latitude,
	longitude
from
	villages
where
	latitude between 55.460531 - 0.31722522007226484 and 55.460531 + 0.31722522007226484
	and longitude between 37.210488 - 0.22583381380662185 and 37.210488 + 0.22583381380662185;

Ну и в моей выборке оказалось 7 объектов. Конечно я взял эту выборку и проверил координаты с помощью линейки на Яндекс Картах. В моем случае все попали в радиус обозначенных 20км. Но мы же помним, что взяли квадрат, а не окружность для вычисления?! Я там даже схему нарисовал в начале, что за квадрат. Итак, если сделать окружность, внутри этого квадрата, она как раз будет радиусом примерно те же 20 км.

Я добавил картинку для наглядности. Видно, что если высота квадрата 40 км, и в нем окружность, то радиус ее тоже будет соответствовать 20 км. Остаются лишние области — углы квадрата, которые я закрасил зеленым. Это то что у нас может попасть в выборку, но они уже не соответствуют именно радиусу в 20 км. Т.е. это лишние данные. И вот тут приходит на помощь та самая формула, о которой я говорил в начале — Расчет расстояния между координатами. С помощью этой формулы можно сравнить исходную точку с координатами из выборки и отсечь те, что будут превышать те самые 20 км, поставленные в задаче.

Итог

Задача решена. Алгоритм придуман. Осталось упаковать это в «красивый» и «чистый» код, чтобы все было по феншую. Надеюсь статья была полезной, потому что когда я искал решения задачи, я наткнулся на множество формул, на множество идей, но не нашел места, где это было бы собрано вот так, как попытался собрать я в рамках данной статьи.

Ссылки

Расчет длины градуса

Расчет дистанции между координатами на сфере

Статья, которая помогла вникнуть в тему расчетов

Тоже полезная статья, в ней есть данные для расчетов

Я почему-то понял вопрос не правильно и подумал про N ближайших точек. Как уже ответил господин @AnT разбиение Вороного для этого намного лучше подойдет, собрал пример на d3.js в котором реализовано разбиение Вороного:

Для поиска нескольких точек можно воспользоваться деревьями

Есть квадродерево алгоритмы на нем достаточно просты и есть готовые реализации.

Вот пример использования d3-quadtree от автора d3.js

желтые — узлы которые обошел алгоритм поиска

красные — найденные ближайшие узлы узлы

Вот пример испольлзующий kd-дерево и поиск ближайших соседей из этого примера на d3.v3 под последнюю версию d3.v5

I needed to do this rather heavily for the many nearest neighbors search in a real time environment, and hit on a better algorithm both in terms of simplicity and speed.

Take all your points and put a copy into d lists where d is the dimensionality of the space. In your case 3. Sort those three lists according to their dimension. This costs d(nlog(n)) time. And that’s it for the data structure.

We maintain these properly sorted lists in each dimension for all the points in question. The trick is that by definition the distance in one direction must be less than or equal to the euclidean distance. So if the distance in one direction is greater than our current closest distance of the closest known point then that point cannot be closer, and more importantly all points in that direction cannot be greater. Once this is true for the 2*d directions we have we by definition have the closest point.

For each particular element we can binarysearch into the sorted lists to find the nearest position where the required point could be in the two different dimensions. Mathematically we know that if the distance in the +x -x +y -y (other dimensions are easy to add) directions exceeds smallest known Euclidean distance to a point, that that point must exceed the distance, and since it’s a sorted array, by definition, when we exceed that distance in that direction, we know we can abort that direction, because there can be no better answer in that direction. But, as we expand out in these four directions we can reduce our value of m because it is equal to the euclidean distance of the closest point we found.

So we only need sorted lists for each axis sorted according to that axis. Which is pretty simple.

Then to query the list:

• We binary search into each of the lists (dlog(n)).
• We find our current minimum distance, m. (initially it can be infinity)
• For each list, we travel in the positive and negative directions.
• For each of the 2*d directions we have,
  • We transverse the lists, lowering m when we find closer points.
• When a direction proves itself to be mathematically fruitless, we stop searching that way.
• When no direction remains we have found our closest point.

We have sorted lists and need to find the point we are searching for in each direction in the list. We binary search in to keep our time complexity log(n). Then we have our best current distance (possibly infinity) and then we move in each direction we have available to us. As we find new points, we update the closest point so far we have. The trick is that we quit as soon as the distance in just that one direction is further than our current known closest point.

So if we have a point at a known closest distance of 13 then we can abort checking in the +x, -x, +y, -y, directions as soon as the distance in just that direction exceeds our closest known distance. Because if it is further +x than our current m, all the remaining values of +x can be mathematically be proven to be further away. As we get better and better closest points, the amount of space we need to search gets smaller and smaller.

If we run out of points in a direction, that direction is finished.
If the distance to a point along just that one dimension of the line is itself greater than m, that direction is finished.

The solution is m when all directions proven to only have points that must be farther than our best point so far.

— Since we progressively reduce m, the distance in each dimension needed as a whole drops quickly, though like all algorithms it drops off less quickly in higher dimensions. But, if the distance in just one dimension is greater than the best we have thus far, it must necessarily be the case that all the rest of those points, in that direction, can’t be better.

In time complexity seems on par with the better ones. But, in simplicity of the datastructures, this algorithm clearly wins. There’s a lot of other properties that make this algorithm a serious contender. When you update stuff, you can resort the lists with really good performance because you are very often sorting already sorted lists or nearly sorted lists. You are iterating arrays. In actual terms of real performance most datastructures suck. Generally because of caching and how memory is laid out, we are supposed to be agnostic about such things but it matters a lot. The data right next to your current relevant data is much faster to actually access. If we already know where the point we’re going to be looking for it in the lists, we can solve it even faster (since we wouldn’t have to find it with a binary search). And other permitted tricks reusing the information from the previous iteration here and there. And additional dimensions are basically free (save that then the value doesn’t converge faster, but that’s because there’s more randomly distributed points in a sphere than a circle of the same radius).

public class EuclideanNeighborSearch2D {
    public static final int INVALID = -1;
    static final Comparator<Point> xsort = new Comparator<Point>() {
        @Override
        public int compare(Point o1, Point o2) {
            return Double.compare(o1.x, o2.x);
        }
    };
    static final Comparator<Point> ysort = new Comparator<Point>() {
        @Override
        public int compare(Point o1, Point o2) {
            return Double.compare(o1.y, o2.y);
        }
    };

    ArrayList<Point> xaxis = new ArrayList<>();
    ArrayList<Point> yaxis = new ArrayList<>();

    boolean dirtySortX = false;
    boolean dirtySortY = false;

    public Point findNearest(float x, float y, float minDistance, float maxDistance) {
        Point find = new Point(x,y);

        sortXAxisList();
        sortYAxisList();

        double findingDistanceMaxSq = maxDistance * maxDistance;
        double findingDistanceMinSq = minDistance * minDistance;

        Point findingIndex = null;

        int posx = Collections.binarySearch(xaxis, find, xsort);
        int posy = Collections.binarySearch(yaxis, find, ysort);
        if (posx < 0) posx = ~posx;
        if (posy < 0) posy = ~posy;

        int mask = 0b1111;

        Point v;

        double vx, vy;
        int o;
        int itr = 0;
        while (mask != 0) {
            if ((mask & (1 << (itr & 3))) == 0) {
                itr++;
                continue; //if that direction is no longer used.
            }
            switch (itr & 3) {
                default:
                case 0: //+x
                    o = posx + (itr++ >> 2);
                    if (o >= xaxis.size()) {
                        mask &= 0b1110;
                        continue;
                    }
                    v = xaxis.get(o);
                    vx = x - v.x;
                    vy = y - v.y;
                    vx *= vx;
                    vy *= vy;
                    if (vx > findingDistanceMaxSq) {
                        mask &= 0b1110;
                        continue;
                    }
                    break;
                case 1: //+y
                    o = posy + (itr++ >> 2);
                    if (o >= yaxis.size()) {
                        mask &= 0b1101;
                        continue;
                    }
                    v = yaxis.get(o);
                    vx = x - v.x;
                    vy = y - v.y;
                    vx *= vx;
                    vy *= vy;
                    if (vy > findingDistanceMaxSq) {
                        mask &= 0b1101;
                        continue;
                    }
                    break;
                case 2: //-x
                    o = posx + ~(itr++ >> 2);
                    if (o < 0) {
                        mask &= 0b1011;
                        continue;
                    }
                    v = xaxis.get(o);
                    vx = x - v.x;
                    vy = y - v.y;
                    vx *= vx;
                    vy *= vy;
                    if (vx > findingDistanceMaxSq) {
                        mask &= 0b1011;
                        continue;
                    }
                    break;
                case 3: //-y
                    o = posy + ~(itr++ >> 2);
                    if (o < 0) {
                        mask = mask & 0b0111;
                        continue;
                    }
                    v = yaxis.get(o);
                    vx = x - v.x;
                    vy = y - v.y;
                    vx *= vx;
                    vy *= vy;
                    if (vy > findingDistanceMaxSq) {
                        mask = mask & 0b0111;
                        continue;
                    }
                    break;
            }
            double d = vx + vy;

            if (d <= findingDistanceMinSq) continue;

            if (d < findingDistanceMaxSq) {
                findingDistanceMaxSq = d;
                findingIndex = v;
            }

        }
        return findingIndex;
    }

    private void sortXAxisList() {
        if (!dirtySortX) return;
        Collections.sort(xaxis, xsort);
        dirtySortX = false;
    }

    private void sortYAxisList() {
        if (!dirtySortY) return;
        Collections.sort(yaxis,ysort);
        dirtySortY = false;
    }

    /**
     * Called if something should have invalidated the points for some reason.
     * Such as being moved outside of this class or otherwise updated.
     */
    public void update() {
        dirtySortX = true;
        dirtySortY = true;
    }

    /**
     * Called to add a point to the sorted list without needing to resort the list.
     * @param p Point to add.
     */
    public final void add(Point p) {
        sortXAxisList();
        sortYAxisList();
        int posx = Collections.binarySearch(xaxis, p, xsort);
        int posy = Collections.binarySearch(yaxis, p, ysort);
        if (posx < 0) posx = ~posx;
        if (posy < 0) posy = ~posy;
        xaxis.add(posx, p);
        yaxis.add(posy, p);
    }

    /**
     * Called to remove a point to the sorted list without needing to resort the list.
     * @param p Point to add.
     */
    public final void remove(Point p) {
        sortXAxisList();
        sortYAxisList();
        int posx = Collections.binarySearch(xaxis, p, xsort);
        int posy = Collections.binarySearch(yaxis, p, ysort);
        if (posx < 0) posx = ~posx;
        if (posy < 0) posy = ~posy;
        xaxis.remove(posx);
        yaxis.remove(posy);
    }
}

Update: With regard to, in the comments, the k-points problem. You will notice that very little changed. The only relevant thing was if the point v is found be be less than the current m (findingDistanceMaxSq), then that point is added to the heap, and the value for m is set to be equal to euclidean distance between the finding position and the kth element. The regular version of the algorithm can be seen as the case where k = 1. We search for the 1 element we want and we update m to equal the only (k=1) element when v is found to be closer.

Keep in mind, I only ever do distance comparatives in the distance squared form, since I only ever need to know if it’s farther away, and I don’t waste clock cycles on square root functions.

And I know there is a perfect data structure for storing the k-elements in a size limited heap. Obviously an array insertion is not optimal for that. But, other than too much java dependent apis there simply wasn’t one for that particular class though apparently Google Guava makes one. But, you won’t really notice at all given that odds are good your k is likely not that big. But, it does make the time complexity for an insertion in points stored in k-time. There are also things like caching the distance from the finding-point for the elements.

Finally, and likely most pressingly, the project I would use to test the code is in transition so I haven’t managed to test this out. But, it certainly shows how you do this: You store the k best results thus far, and make m equal to the distance to the the kth closest point. — All else remains the same.

Example source.

public static double distanceSq(double x0, double y0, double x1, double y1) {
    double dx = x1 - x0;
    double dy = y1 - y0;
    dx *= dx;
    dy *= dy;
    return dx + dy;
}
public Collection<Point> findNearest(int k, final float x, final float y, float minDistance, float maxDistance) {
    sortXAxisList();
    sortYAxisList();

    double findingDistanceMaxSq = maxDistance * maxDistance;
    double findingDistanceMinSq = minDistance * minDistance;
    ArrayList<Point> kpointsShouldBeHeap = new ArrayList<>(k);
    Comparator<Point> euclideanCompare = new Comparator<Point>() {
        @Override
        public int compare(Point o1, Point o2) {
            return Double.compare(distanceSq(x, y, o1.x, o1.y), distanceSq(x, y, o2.x, o2.y));
        }
    };

    Point find = new Point(x, y);
    int posx = Collections.binarySearch(xaxis, find, xsort);
    int posy = Collections.binarySearch(yaxis, find, ysort);
    if (posx < 0) posx = ~posx;
    if (posy < 0) posy = ~posy;

    int mask = 0b1111;

    Point v;

    double vx, vy;
    int o;
    int itr = 0;
    while (mask != 0) {
        if ((mask & (1 << (itr & 3))) == 0) {
            itr++;
            continue; //if that direction is no longer used.
        }
        switch (itr & 3) {
            default:
            case 0: //+x
                o = posx + (itr++ >> 2);
                if (o >= xaxis.size()) {
                    mask &= 0b1110;
                    continue;
                }
                v = xaxis.get(o);
                vx = x - v.x;
                vy = y - v.y;
                vx *= vx;
                vy *= vy;
                if (vx > findingDistanceMaxSq) {
                    mask &= 0b1110;
                    continue;
                }
                break;
            case 1: //+y
                o = posy + (itr++ >> 2);
                if (o >= yaxis.size()) {
                    mask &= 0b1101;
                    continue;
                }
                v = yaxis.get(o);
                vx = x - v.x;
                vy = y - v.y;
                vx *= vx;
                vy *= vy;
                if (vy > findingDistanceMaxSq) {
                    mask &= 0b1101;
                    continue;
                }
                break;
            case 2: //-x
                o = posx + ~(itr++ >> 2);
                if (o < 0) {
                    mask &= 0b1011;
                    continue;
                }
                v = xaxis.get(o);
                vx = x - v.x;
                vy = y - v.y;
                vx *= vx;
                vy *= vy;
                if (vx > findingDistanceMaxSq) {
                    mask &= 0b1011;
                    continue;
                }
                break;
            case 3: //-y
                o = posy + ~(itr++ >> 2);
                if (o < 0) {
                    mask = mask & 0b0111;
                    continue;
                }
                v = yaxis.get(o);
                vx = x - v.x;
                vy = y - v.y;
                vx *= vx;
                vy *= vy;
                if (vy > findingDistanceMaxSq) {
                    mask = mask & 0b0111;
                    continue;
                }
                break;
        }
        double d = vx + vy;
        if (d <= findingDistanceMinSq) continue;
        if (d < findingDistanceMaxSq) {
            int insert = Collections.binarySearch(kpointsShouldBeHeap, v, euclideanCompare);
            if (insert < 0) insert = ~insert;
            kpointsShouldBeHeap.add(insert, v);
            if (k < kpointsShouldBeHeap.size()) {
                Point kthPoint = kpointsShouldBeHeap.get(k);
                findingDistanceMaxSq = distanceSq(x, y, kthPoint.x, kthPoint.y);
            }
        }
    }
    //if (kpointsShouldBeHeap.size() > k) {
    //    kpointsShouldBeHeap.subList(0,k);
    //}
    return kpointsShouldBeHeap;
}

Нравится ресурс? Помоги проекту!

Поиск ближайшей точки?
, подскажите формулу для нахождения ближайшей точки

• Подписаться на тему
• Сообщить другу
• Скачать/распечатать тему

Сообщ. #1 , 08.01.09, 23:41

Приветствую! Если не сложно подскажите формулу для вычисления ближайшей точки. Т.е. есть некоторое множество точек на плоскости, среди них нужно найти ближайшую к заданной точке. Входные параметры, N кол-во точек с координатами (x, y) Заданная точка S (x, y). Нужно найти ближайшую к S точку. Мне б формулу этого дела. А то искал в сети — ничего понятного не нашел, одни какие-то абстракции, теории… Спасибо!

Der_Meister	Сообщ. #2 , 08.01.09, 23:50
	Имхо стоит упорядочить точки по параметру (x + y). Тогда искать нужно будет только в окрестностях данной точки. Возможно сам критерий (x + y) ошибочен, но извлечение квадратного корня использовать нельзя. Есть еще алгоритмы быстрой оценки расстояния… Сообщение отредактировано: Der_Meister — 08.01.09, 23:51

albom

Сообщ. #3 , 09.01.09, 00:29

Senior Member Рейтинг (т): 20

Цитата Der_Meister @ 08.01.09, 23:50 Имхо стоит упорядочить точки по параметру (x + y). Тогда искать нужно будет только в окрестностях данной точки. Что в окрестности искать надо — это точно, но вот только проблема раз: в метрике l1 ближайшая точка может не совпадать с ближайшей в метрике l2 (т.е. придется всё равно перебирать всё элементы множества заданных точек), и проблема два: только само по себе упорядочивание займет больше времени, чем поиск в лоб. Цитата Der_Meister @ 08.01.09, 23:50 но извлечение квадратного корня использовать нельзя Кто сказал? Цитата @POLL @ 08.01.09, 23:41 Мне б формулу этого дела. Если тебя интересует именно формула, то её можно записать, например, так (в TEX нотации): T = argmin_{x in P }{rho(x, S)} P — множество заданных точек, T — ответ, искомая точка, а ρ — метрика, естественно.

Der_Meister	Сообщ. #4 , 09.01.09, 00:32
	Цитата albom @ 09.01.09, 00:29 Кто сказал? Я ретроград и привык, что операция извлечения квадратного корня крайне медленна.

albom	Сообщ. #5 , 09.01.09, 00:37
Senior Member Рейтинг (т): 20	А я и не утверждаю обратное, но тем не менее мне совершенно непонятно как скорость извлечения корня может быть связана вот с этим утвержением: Цитата Der_Meister @ 08.01.09, 23:50 извлечение квадратного корня использовать нельзя

MBo	Сообщ. #6 , 09.01.09, 06:08
	>операция извлечения квадратного корня крайне медленна необязательно извлекать корень, при нахождении минимального евклидова расстояния достаточно сравнения суммы квадратов @POLL Операцию нужно выполнить один раз или много раз находить ближайшие к заданным точкам?

@POLL

Сообщ. #7 , 09.01.09, 08:23

Цитата albom @ 09.01.09, 00:29 Цитата @POLL @ 08.01.09, 23:41 Мне б формулу этого дела. Если тебя интересует именно формула, то её можно записать, например, так (в TEX нотации): T = argmin_{x in P }{rho(x, S)} P — множество заданных точек, T — ответ, искомая точка, а ρ — метрика, естественно. Ой, а можно эту формулу немного подробнее описать, как получить метрики каждой точки, что такое rho, argmin_ Я не особо был силен в высшей математике, а счас тем более мало что припомню. -Added 09.01.09, 08:59 Цитата MBo @ 09.01.09, 06:08 @POLL Операцию нужно выполнить один раз или много раз находить ближайшие к заданным точкам? Один раз. Вообще, я думал решить задачу как-то так. Брать заданную точку (x, y) за центр/ось. Вокруг этой оси «рисовать» окружность радиусом 1. И смотреть попадают в неё точки или нет. Если попадает одна точка => это искомая ближайшая точка. Если попадает несколько точек => считаем расстояние от каждой точки до оси, у точки которой меньшее расстояние — искомая. Если в получившейся окружности точек нет, увеличиваем радиус окружности — 2, 3, 4 и т.д. И снова пробегаем по циклу. Правда я не уверен, что такой цикл лучше/производительнее представленной выше формул с метриками. Этот алгоритм мне нужен для моего веб-приложения прогноза погоды. Там так. Пользователь заходит на сайт, при этом определяется его географическая привязка, координаты (широта/долгота т.е. x, y). По этим координатам пользователю выдается прогноз погоды его города. При этом возможны 2 ситуации. 1) Для его координат есть прогноз 2) Для его координат прогноза нет. Вот, во втором случае мне и нужно определить ближайшую точку. Есть точка пользователя (S) и есть точки с погодой (P). Среди P нужно найти ближайшую. Вот, как-то так.

OpenGL	Сообщ. #8 , 09.01.09, 10:12
	Посмотри здесь, в пятой главе то, что нужно.

@POLL

Сообщ. #9 , 09.01.09, 11:32

Цитата Konigsberg @ 09.01.09, 09:38 @POLL, это жесть… Вам нужно написать один простой цикл пробегающий по всем точкам в котором из координат вашей точки вычесть координаты каждой точки в цикле, возвести их в квадрат, сложить и найти меньшее значение это величины (x0, y0) //ваша точка min = MAX_VALUE; // заведомо очень большое значение (xs, ys) //искомая точка for each ((x, y) in points) {     distance = (x0 — x)^2 + (y0 — y)^2;     if (distance < min) {         min = distance;         xs = x;         ys = y;     } } Ой, спасибо ОООгромное — как все просто и главное работает Конечно, для производительности было б неплохо использовать какие-нить расчетные индексы, но это мне нужно теорию почитать Вот для теста можно поюзать. $sx, $sy — заданная точка, $px и $py — искомая. Цитата <?php $sx = 80; $sy = -40; $min = 1000; $px = 0; $py = 0; $points = array( array(0, 0), array(-100, 50), array(90, 100), array(50, 50), array(70, -30), array(10, 10) ); foreach ($points as $point) { $d1 = pow(($sx — $point[0]), 2); $d2 = pow(($sy — $point[1]), 2); $distance = $d1 + $d2; if ($distance < $min) { $min = $distance; $px = $point[0]; $py = $point[1]; } } echo ‘<hr>’ . $px . ‘ : ‘ . $py; ?> ?> -Added 09.01.09, 11:47 Цитата OpenGL @ 09.01.09, 10:12 Посмотри здесь, в пятой главе то, что нужно. Спасибо за ссылку!, там интересные способы описаны, правда там больше теоретическая часть и мало практических примеров. Почитаю, мож чего пойму

0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)

0 пользователей:

• Предыдущая тема
• Алгоритмы
• Следующая тема

[ Script execution time: 0,0890 ]   [ 15 queries used ]   [ Generated: 26.05.23, 02:02 GMT ]