Wypukły kadłub

Wypukły kadłub kształtu jest zdefiniowany jako:

W matematyce wypukły kadłub lub wypukła obwiednia dla zbioru punktów X w prawdziwej przestrzeni wektorowej V jest minimalnym wypukłym zestawem zawierającym X ( Wikipedia )

Wikipedia ładnie wizualizuje to za pomocą analogii gumki i istnieją pewne dobre algorytmy do jej obliczenia .

Wklęsły kadłub

Wklęsły kadłub jest wizualizowany za pomocą czerwonej linii na obrazku poniżej (niebieska linia wizualizuje wypukły kadłub). Intuicyjnie jest to wielokąt, który obejmuje wszystkie punkty, ale ma mniej (minimalny?) Obszar w porównaniu do wypukłego kadłuba. W rezultacie długość granicy wielokąta jest dłuższa.

Wklęsły kadłub może być rozwiązaniem niektórych rzeczywistych problemów (np. Znalezienie rozsądnej granicy miasta).

Nie udało mi się znaleźć właściwej definicji, algorytmu i praktycznego rozwiązania dla pojęcia kadłuba wklęsłego. Trawa Wiki ma jakieś opisy i obrazy , i nie jest to rozwiązanie komercyjne w concavehull.com .

Wszelkie pomysły, algorytmy i linki?

Jak wskazuje scw , potrzebujesz implementacji kształtów α .

Kształty alfa można uznać za uogólnienie wypukłego kadłuba. Po raz pierwszy opisano je w 1981 r .:

Edelsbrunner, H .; Kirkpatrick, D .; Seidel, R .; , „O kształcie zestawu punktów w płaszczyźnie”, Teoria informacji, Transakcje IEEE, t. 29, nr 4, s. 551–559, lipiec 1983 r.

Istnieją implementacje typu open source dla środowisk, którymi jesteś zainteresowany:

PostGIS

Jeśli korzystasz ze stosu PostGIS, opcjonalne rozszerzenie pgRouting ujawnia implementację kształtu alfa. Nie jestem jednak pewien, czy możesz zmienić parametr alfa.

Użycie jest poniżej:

SELECT the_geom AS alpha_shape 
FROM 
  points_as_polygon(
    'SELECT id, ST_X(your_geom) AS x, ST_Y(your_geom) AS y FROM your_table');

Pyton

Prawdopodobnie jest wiele modułów Pythona, których możesz użyć. Słyszałem dobre rzeczy o CGAL , bibliotece geometrii obliczeniowej C ++. Owijarki pytona istnieją części CGAL oraz wystawienie CGAL za realizację kształtu alfa do Pythonie .

Pamiętaj, że części CGAL są licencjonowane na licencji QPL, co oznacza, że ​​jeśli rozpowszechniasz swój program, powiązany z CGAL, być może będziesz musiał go wydać na licencji QPL. Dobrze jest zachować swój kod zastrzeżony, jeśli nie rozpowszechniasz kodu programu ani plików binarnych.

Oto czego szukasz.

Możesz pobrać i przetestować program: (w java, na licencji GPL)

Artykuł przedstawiający algorytm jest tam:

Duckham, M., Kulik, L., Worboys, MF, Galton, A. (2008) Wydajne generowanie prostych wielokątów do charakteryzowania kształtu zbioru punktów w płaszczyźnie. Rozpoznawanie wzoru v41, 3224-3236

Wydaje się, że jest to specyficzne zastosowanie kształtów alfa , które z mojego czytania są bardziej ogólną formą tego problemu. R ma moduł alphahull , który ma doskonałą dokumentację dotyczącą obliczania kształtów alfa . Sprawdź także to szczegółowe tło na temat kształtów alfa. Jeśli chcesz tylko obliczać kadłuby wypukłe / wklęsłe, sprawdź lasboundary , część Lastools , dobrze się skaluje i może obsłużyć miliony punktów wejściowych.

Wreszcie, ta interesująca aplikacja kształtów alfa autorstwa Flickr dokonała obchodów jakiś czas temu, pokazując ich użyteczność do agregowania treści punktowej generowanej przez użytkownika:

Istnieje implementacja ST_ConcaveHull w pniu PostGIS. http://postgis.net/docs/ST_ConcaveHull.html

Stworzyłem bardzo wydajne narzędzie o nazwie [lasboundary] [1,2], które oblicza wklęsły kadłub dla LIDAR w formacie LAS / LAZ / SHP / ASCII i zapisuje wynik jako wielokąt granicy wektorowej w formacie ESRI Shapefile lub geo plik KML.

Oto przykładowy przebieg:

C:\lastools\bin>lasboundary -i SerpentMound.las -o SerpentMound_boundary.shp
reading 3265110 points and computing convex hull for 3265110 points
growing inward towards concave hull (with concavity = 50)
outputting the concave hull
concave hull has 1639 points

Niektóre zdjęcia wynikowe są tutaj .

O implementacji R Alpha-Shapes, jest artykuł na temat „Konwertowania Alpha-Shapes na obiekty SP”

Opiera się na alphahull, sp i spgrass6 http://casoilresource.lawr.ucdavis.edu/drupal/node/919

Oto funkcja R, która implementuje model Alpha Hull. Dane wyjściowe to obiekt wielokąta sp. Zobacz przykład w nagłówku. Wymaga pakietów sp, alphahull i maptools.

** Aktualizacja (01-15-2018) Dokonano wielu zmian w wynikowych obiektach wytworzonych przez pakiet alphahull. W związku z tym musiałem przepisać tę funkcję. Dodałem funkcję convexHull do pakietu spatialEco. Jednak z powodu ograniczeń licencyjnych w pakiecie alphahull ta funkcja jest dostępna tylko w wersji programistycznej na GitHub. Wersję rozwojową można zainstalować za pomocą:

library(devtools)
install_github("jeffreyevans/spatialEco")

Oto przykład użycia funkcji

library(sp)
library(spatialEco)
data(meuse)
 coordinates(meuse) = ~x+y
a <- convexHull(meuse, alpha=100000)
  plot(a)
    points(meuse, pch=19)

Konwertuj wynikowy SpatialLinesDataFrame na SpatialPolygonsDataFrame

library(sf)
a <- sf::st_as_sf(a) 
a <- sf::st_polygonize(a)
class( a <- as(a, "Spatial") )
  plot(a)

Przetestuj wiele wartości alfa

par(mfcol=c(2,2))
   for (a in c(500, 1500, 5000, 100000)) {
   ch <- convexHull(meuse, alpha = a)
     plot(ch)
      points(meuse, pch=19)
        title( paste0("alpha=", a))      
   }

JTS ( http://tsusiatsoftware.net/jts/main.html ) zapewnia implementację wypukłego kadłuba. Martin Davies wspomniał także o posiadaniu algorytmu Alpha Shape w toku prac, więc możesz chcieć sprawdzić repozytorium SVN, aby zobaczyć, czy jest jeszcze w nim, jeśli tego właśnie chcesz.

Mówiąc o JTS, możesz używać Geoscript do manipulowania biblioteką JTS. http://geoscriptblog.blogspot.com/2010/06/unwrapped-jts-with-python.html dla artykułu na temat wypukłego kadłuba. Implementacje GeoScript są dostępne w JavaScript, Python, Scala i Groovy. Oficjalna strona internetowa: http://geoscript.org

Oto program napisany w C, który oblicza wypukłe kadłuby, kształty alfa, triangluacje Delauneya i tomy Voronoi:

• Hull - Ken Clarkson (2002)

Kolejny algorytm wypukłego kadłuba z implementacjami C i Java znajduje się tutaj:

• Wypukły kadłub (2D) - geometria obliczeniowa w C , Joseph O'Rourke (1998)

Aby dodać do poprzednich odpowiedzi na ten post, przynajmniej od QGIS 2.6 ma wklęsły algorytm kadłuba

Parametry
Warstwa punktu wejściowego [wektor: punkt]
umieść tutaj opis parametru

Próg (0-1, gdzie 1 jest równoważne wypukłemu kadłubowi) [liczba]
wstaw opis parametru tutaj
Domyślnie: 0.3

Zezwalaj na otwory [boolean]
wstaw opis parametru tutaj
Domyślnie: True

Podziel geometrię wieloczęściową na geometrie jednoelementowe [logiczne]
Domyślnie: False

Wyjścia Wklęsły kadłub [wektor]
umieść tutaj opis wyjścia

Przetwarzanie użycia konsoli.runalg ('qgis: concavehull', wejście, alfa, dziury, no_multigeometry, wyjście)

Ponadto Esri ma narzędzie Minimalna ograniczona geometria (zarządzanie danymi)

Co pozwala wybrać typ geometrii, w tym wypukły kadłub

Dostępny jest nowy dodatek do GRASS GIS 7: v.concave.hull . Zobacz także http://grasswiki.osgeo.org/wiki/Create_concave_hull

Aby pomóc w części „właściwej definicji” pytania; mogłeś spojrzeć na https://en.wikipedia.org/wiki/Convex_hull i uzyskać coś, co można by uznać za „właściwą” definicję, ale okazało się, że jej brakuje, więc być może bardziej „użyteczną” definicją jest:

Dla każdego punktu w wypukłym kadłubie linia prosta do dowolnego punktu poza kadłubem przecina kadłub tylko raz.

Jest to przydatne, ponieważ biorąc pod uwagę punkt, można przez niego zbudować linię i przetestować tę zbudowaną linię przecinającą segmenty kadłuba.

• Brak skrzyżowania punkt nie znajduje się w kadłubie.
• Jedno skrzyżowanie punkt znajduje się na kadłubie.
• Dwa skrzyżowania punkt znajduje się w kadłubie
• Linia prosta nie może przecinać wypukłego kadłuba więcej niż dwa razy