Mam punkty 2D na płaszczyźnie 256x256, może być większa 1000x1000 a
nawet 10 tys x 10 tys. Chciałbym mieć indeks taki, by od razu znaleźć
punkty odległe we wszystkich kierunkach o 10 od wskazanego punktu.
Wybieram powiedzmy 137,168
Jest rozwiązanie polegające na tym że liczbom x i y mającym bity
x0x1x2..x7 i y0y1y2..y7 daje się bity wstawione jedne w drugie
x0y0x1y1..x7y7.
Potem porządkujemy po tych bitach otrzymując 0..65535.
To jest jakieś rozwiązanie, ale dla jakiejś liczby np. 30'000 gdy
zaczniemy od liczba-100 do liczba+100 to zarówno otrzymamy dalsze niż 10
jak i bliższe wszystkie niż 10 nie będą.
Co do dalszych, to możemy dodatkowo filtrować po odległości. Drugi
przypadek - należy wystartować z inną pozycją indeksu. Jak to można zrobić?
Testowy program:
https://gist.github.com/borneq/36808830520c059ae4740
61c46c282f5

do góry

On Fri, 3 Feb 2017 08:52:16 +0100, Borneq <b...@a...hidden.pl>
wrote:
> nawet 10 tys x 10 tys. Chciałbym mieć indeks taki, by od razu
znaleźć
> punkty odległe we wszystkich kierunkach o 10 od wskazanego punktu.

Jaka metryka? Miejska czy euklidesowa? Tj. kwadrat czy koło? Brzeg
czy figura z wnętrzem? Tj. okrąg czy koło? Ile punktów? Czy dwa
punkty mogą mieć te same współrzędne (matematycznie to nonsens, ale
wiadomo o co chodzi)? Ile punktów: kilkaset, 1000, parę milionów,
więcej?

Czy ta odległość zawsze będzie 10, czy może być nawet większa niż
rozmiar całej bitmapy? Na przykład 10000? Czy współrzędne są int czy
mogą być float?

do góry

W dniu 03.02.2017 o 10:47, slawek pisze:
> Jaka metryka? Miejska czy euklidesowa? Tj. kwadrat czy koło? Brzeg czy
> figura z wnętrzem? Tj. okrąg czy koło? Ile punktów? Czy dwa punkty mogą
> mieć te same współrzędne (matematycznie to nonsens, ale wiadomo o co
> chodzi)? Ile punktów: kilkaset, 1000, parę milionów, więcej?

Najlepiej euklidesowa ale miejska też się przyda, z miejskiej czyli
kwadratu wokół punktu można dostać koło po odpowiednim odfiltrowaniu.
Punktów raczej dużo, aby nie opłacało się wszystkich szukać w pamięci.

do góry

Spróbowałbym dwóch trików:

1. Podzielić cały obszar na części porównywalne z promieniem r. Wtedy
na szybko można szukać nie wszędzie, ale wśród kilku fragmentów.

1b. Jak wyżej, ale rekursja.

2. Posortować po x i po y. Szukane punkty leżą na przecięciu dwóch
pasów.

Jeszcze jeden pomysł: punkty tworzą siatkę. Najpierw wybieramy jeden
z nich. To powoduje propagację sygnału po siatce. Czyli każdy punkt
wie jakie inne są w pobliżu.

do góry

W dniu 03.02.2017 o 16:24, slawek pisze:
> Spróbowałbym dwóch trików:
>
> 1. Podzielić cały obszar na części porównywalne z promieniem r. Wtedy na
> szybko można szukać nie wszędzie, ale wśród kilku fragmentów.

Koło wokół szukanego punktu może leżeć na styku na przykład dwóch ale aż
do czterech kwadratów. Może właśnie tak zrobili w przykładzie
GeoHashSample od VelocityDB. Bo tam jest:
GeoHashCircleQuery query = new GeoHashCircleQuery(center,
radius); // radius in meters
BoundingBox bbox = query.BoundingBox;
var btreeSet =
session.AllObjects<BTreeSet<GeoObj>>().FirstOrDefaul
t();
foreach (GeoHash hash in query.SearchHashes)
{

pętla foreach wykonywała się 4 i 2 razy
To pytanie zresztą nie jest takie ważne, tylko z ciekawości, bardziej
zależy mi na kilku poprzednich pytaniach.

do góry

On Friday, February 3, 2017 at 8:52:13 AM UTC+1, Borneq wrote:
> Mam punkty 2D na płaszczyźnie 256x256, może być większa 1000x1000 a
> nawet 10 tys x 10 tys. Chciałbym mieć indeks taki, by od razu znaleźć
> punkty odległe we wszystkich kierunkach o 10 od wskazanego punktu.
> Wybieram powiedzmy 137,168
> Jest rozwiązanie polegające na tym że liczbom x i y mającym bity
> x0x1x2..x7 i y0y1y2..y7 daje się bity wstawione jedne w drugie
> x0y0x1y1..x7y7.
> Potem porządkujemy po tych bitach otrzymując 0..65535.
> To jest jakieś rozwiązanie, ale dla jakiejś liczby np. 30'000 gdy
> zaczniemy od liczba-100 do liczba+100 to zarówno otrzymamy dalsze niż 10
> jak i bliższe wszystkie niż 10 nie będą.
> Co do dalszych, to możemy dodatkowo filtrować po odległości. Drugi
> przypadek - należy wystartować z inną pozycją indeksu. Jak to można zrobić?
> Testowy program:
> https://gist.github.com/borneq/36808830520c059ae4740
61c46c282f5

Myślałeś nad zastosowaniem KD-Tree?
Pozdrawiam

do góry