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

Quadtrees are nice, but BSP trees are guaranteed to run in O(log n) time. I think quadtrees require a finite bounding volume, and and there are some degenerate cases where quadtrees fail miserably, such as when a large number of points occupy the same relatively small space.

That being said, Quadtrees are arguably easier to implement and quite effective in most common situations. It's what UPS uses in their routing algorithms, because it's drawbacks don't pose significant problems in practice, probably because cities tend to be spread out over the region of interest.

You want to use a structure like a Quad tree, or an RTree. These are multidimensional index structures.

The key is using a good "space filling curve", which is what helps define the nearness of points. A simple space filling curve is a Zorder, but you would be more interested in something like a hilbert curve.

http://en.wikipedia.org/wiki/Space_filling_curve

I don't know of any prepackaged implementations of this stuff. I recently implemented my own RTree in 2 dimensions that only supports bulk loading and searches (via a provided bounding box).

One drawback here is that your points have to be contained in a finite region. There know there are space filling curves that work for spaces that are not finite, but I do not know anything about them.

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

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

I assume the points are in a database or some searchable indexed location? If so it should be pretty quick. From the given point you can have a range on the x and y axis and get all locations within that range (i.e. specify the top left most corner x(a) and y(b) and bottom most right corner x(c) and y(d)).

Then do a query where for points where y >= b AND y <= d AND x >= a AND x <=c. this will be quick assuming you have indexes on the x and y coordinates seperatly. (assuming origin is 0,0 at top left).

You can then increase (or decrease if result is huge) this range by z until the number of points within the result set is >= 1000. Through some trial runs you should be able to come up with a standard deviation and other statistical numbers that will help you determine the size of the rectangle to start with. Your program can also tune its self for this based on the results it gets.

Once you have the rough data set its pretty simple maths to work out the distance between each point and the source point.

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

Я надеюсь, что это поможет кому-то :)

CREATE PROCEDURE [dbo].[getstores] @lat float,  @lng float AS
DECLARE @radius float, @DegToRad float
SET @DegToRad = 57.29577951
SET @radius = 25000
SELECT TOP 10
    name
    ,sto_lat
    ,sto_lng
    ,postcode
    ,ROUND((ACOS((SIN(@lat/57.2958) * SIN(sto_lat/@DegToRad)) +(COS(@lat/@DegToRad) * COS(sto_lat/@DegToRad) *COS(sto_lng/@DegToRad - @lng/@DegToRad))))* 6387.7, 2) AS distance
FROM store
WHERE (sto_lat >= @lat - (@radius/111))
And (sto_lat <= @lat + (@radius/111))
AND (sto_lng >= @lng - (@radius/111))
AND (sto_lng <= @lng + (@radius/111))
AND (
     ISNUMERIC(sto_lat) = 1
    AND
    ISNUMERIC(sto_lat) = 1
)
ORDER BY distance

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