Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > pl.comp.programming > #29379 > unrolled thread

Indeksowanie 2D

Back to article view | Back to pl.comp.programming

Contents

  Indeksowanie 2D Borneq <borneq@antyspam.hidden.pl> - 2017-02-03 08:52 +0100
    Re: Indeksowanie 2D slawek <fake@fakeemail.com> - 2017-02-03 10:47 +0100
      Re: Indeksowanie 2D Borneq <borneq@antyspam.hidden.pl> - 2017-02-03 10:58 +0100
        Re: Indeksowanie 2D slawek <fake@fakeemail.com> - 2017-02-03 16:24 +0100
          Re: Indeksowanie 2D Borneq <borneq@antyspam.hidden.pl> - 2017-02-03 16:51 +0100
    Re: Indeksowanie 2D "M.M." <mmarszik@gmail.com> - 2017-02-04 07:16 -0800

#29379 — Indeksowanie 2D

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/36808830520c059ae474061c46c282f5

[toc] | [next] | [standalone]

#29381

On Fri, 3 Feb 2017 08:52:16 +0100, Borneq <borneq@antyspam.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?

[toc] | [prev] | [next] | [standalone]

#29382

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.

[toc] | [prev] | [next] | [standalone]

#29388

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.

[toc] | [prev] | [next] | [standalone]

#29389

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>>().FirstOrDefault();
       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.

[toc] | [prev] | [next] | [standalone]

#29398

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/36808830520c059ae474061c46c282f5

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

[toc] | [prev] | [standalone]

Back to top | Article view | pl.comp.programming

csiph-web