Odległość obiektu punktowego do najbliższego wielokąta w R

Question

Pracuję nad projektem w tym momencie, w którym mam funkcję punktową - funkcja punktowa zawiera 142 punkty - i wielokąt (około 10). Chcę obliczyć odległość między każdym pojedynczym punktem i najbliższą funkcją wielokąta w R.

Moje obecne podejście jest żmudne i trochę długotrwałe. Obecnie planuję obliczyć odległość między każdym pojedynczym punktem i każdym pojedynczym wielokątem. Na przykład, obliczyłbym odległość między 142 punktami a wielokątem A, odległością między 142 punktami a wielokątem B, odległością między 142 punktami a wielokątem C itd. Oto przykładowy kod jednego z poniższych obliczeń odległości:

dist_cen_polya <- dist2Line(centroids_coor, polygonA_shp) 

Po wykonaniu tych obliczeń, napiszę kod, aby wybrać minimalną/najbliższą odległość między każdym pojedynczym punktem a najbliższym wielokątem. Problem polega na tym, że ta procedura jest żmudna.

Czy ktoś zna pakiet/kod, który zminimalizuje wysiłek/czas obliczeniowy obliczeń? Czy naprawdę chciałbym użyć pakietu, który porównuje pojedyncze, aby wskazywał na najbliższą funkcję wielokąta lub oblicza odległość między punktem a wszystkimi poligonami będącymi przedmiotem zainteresowania?

Dziękuję.

Answer 1

Tutaj używam funkcji gDistance w bibliotece topologii rgeos. Używam podwójnej pętli brutalnej siły, ale jest zaskakująco szybko. Zajmuje mniej niż 2 sekundy dla 142 punktów i 10 wielokątów. Jestem pewien, że istnieje bardziej elitarny sposób na wykonanie pętli.

require(rgeos) 

    # CREATE SOME DATA USING meuse DATASET 
    data(meuse) 
     coordinates(meuse) <- ~x+y 
     pts <- meuse[sample(1:dim(meuse)[1],142),] 
    data(meuse.grid) 
     coordinates(meuse.grid) = c("x", "y") 
     gridded(meuse.grid) <- TRUE 
      meuse.grid[["idist"]] = 1 - meuse.grid[["dist"]]  
     polys <- as(meuse.grid, "SpatialPolygonsDataFrame") 
      polys <- polys[sample(1:dim(polys)[1],10),] 
    plot(polys) 
     plot(pts,pch=19,cex=1.25,add=TRUE)  

    # LOOP USING gDistance, DISTANCES STORED IN LIST OBJECT 
    Fdist <- list() 
     for(i in 1:dim(pts)[1]) { 
     pDist <- vector() 
      for(j in 1:dim(polys)[1]) { 
      pDist <- append(pDist, gDistance(pts[i,],polys[j,])) 
      } 
     Fdist[[i]] <- pDist 
     } 

    # RETURN POLYGON (NUMBER) WITH THE SMALLEST DISTANCE FOR EACH POINT 
    (min.dist <- unlist(lapply(Fdist, FUN=function(x) which(x == min(x))[1]))) 

    # RETURN DISTANCE TO NEAREST POLYGON 
    (PolyDist <- unlist(lapply(Fdist, FUN=function(x) min(x)[1]))) 

    # CREATE POLYGON-ID AND MINIMUM DISTANCE COLUMNS IN POINT FEATURE CLASS 
    pts@data <- data.frame(pts@data, PolyID=min.dist, PDist=PolyDist) 

    # PLOT RESULTS 
    require(classInt) 
    (cuts <- classIntervals(pts@data$PDist, 10, style="quantile")) 
     plotclr <- colorRampPalette(c("cyan", "yellow", "red"))(20) 
     colcode <- findColours(cuts, plotclr) 
    plot(polys,col="black") 
     plot(pts, col=colcode, pch=19, add=TRUE) 

Wektor min.dist reprezentuje numer wiersza wielokąta. Na przykład możesz podzbiorować najbliższe wielokąty, używając tego wektora jako takiego.

near.polys <- polys[unique(min.dist),] 

Wektor PolyDist zawiera rzeczywiste minimalne odległości kartezjańskie w jednostkach projekcji obiektów.

Answer 2

W wielokącie masz dość dużo linii. Odległość między wielokątami wynosi zero, jeśli punkt leży w obrębie wielokąta lub leży na krawędzi.

Więc rzeczywiście szukasz dwóch przypadkach:

1. sprawdź, czy punkt leży wewnątrz dowolnego wielokąta (pamiętacie może to być więcej niż jednym wielokąta
2. Uzyskaj zbiór wszystkich krawędzi i obliczyć każdy odległość punktu od krawędzi. Najbliższa odległość daje dystans wielokąta krawędź należy też.

jest to więc prosty algorytm, że jeśli weźmiemy pod uwagę 10 krawędzie za wielokąta zajmuje o (10 * 10) * 142 dla wszystkie twoje punkty. To sprawia, że ​​100 * 142 = 14200 operacji. => O (m * deltaE) * n (m to liczba wielokątów, deltaE to średnia liczba krawędzi na wielokąt, n to liczba punktów).

Teraz sprawdzamy, czy możemy to przyspieszyć. Pierwszą rzeczą, która przychodzi do głowy, jest to, że możemy użyć sprawdzania obwiedni lub okręgów ograniczających dla każdego wielokąta.

Innym pomysłem jest przygotowanie najbliższych krawędzi dla każdego wielokąta dla zestawu kątów.Na przykład, jeśli masz 8 kątów (co 45 °), możesz usunąć wszystkie krawędzie z listy, które są zastąpione przez inną krawędź (dlatego każdy punkt usuniętej krawędzi da zawsze większą odległość niż jakikolwiek punkt drugiej krawędzi tego samego wielokąt:

W ten sposób zwykle możesz zmniejszyć złożoność z dużym marginesem.Jeśli myślisz o prostokącie, masz tylko jedną lub dwie krawędzie zamiast 4. Jeśli myślisz o zwykłym wielokącie o krawędzi 8, możesz skończyć z zwykle jeden lub dwa i maksymalnie 3 krawędzie na wielokąt:

Jeśli dodasz normalny wektor do każdej krawędzi, możesz obliczyć, czy punkt może być w środku i musisz wykonać linię skanowania lub cokolwiek sprawdzić (lub znasz jego konvex), aby mieć pewność,

Dostępne są również indeksy odwzorowań, takie jak oddzielenie przestrzeni dwuwymiarowej przez xiy w równorzędnym mannor. W związku z tym wystarczy przetestować poligony leżące w 9 sektorach.

Następna wersja może wykorzystywać drzewo R, że każda ramka ograniczająca (okrąg) każdego węzła musi być sprawdzona pod kątem minimalnej oczekiwanej odległości i maksymalnej oczekiwanej odległości. Nie trzeba więc sprawdzać poligonów węzła, które powodują znacznie większe minimalne odległości niż maksymalne odległości innego węzła.

Inną rzeczą jest, jeśli posiadasz dane drzewo, takie jak w przypadku danych map. Na mapie ulic zawsze masz świat -> region -> kraj -> region -> miasto -> sektor miejski -> ...

Dzięki temu możesz wyszukać najbliższą lokalizację na mapie całego świata zawierającej miliony wielokątów w rozsądnym czasie, głównie < 10 ms.

Można powiedzieć, że masz tu wiele opcji. Przetwarzaj listę wieloboków i wyodrębniaj odpowiednie krawędzie, korzystając z binarnych drzewek z partycjami przestrzennymi wielokątów lub użyj podejścia kątowego, a nawet przejdź z czymś jeszcze bardziej wyszukanym. To zależy od Ciebie. Spodziewam się, że skończysz, robiąc coś w zakresie logarytmicznym, takim jak O (log (n) * log (deltaE)), który staje się O (log (n)) jako średnia złożoność.