Budowanie wielokąta na dostępnym obszarze

10

Obecnie pracuję w dziedzinie izochron i podstawowych algorytmów. To, co teraz powoduje problemy, to nie obliczenie samego izochronu, ale wizualizacja wyników.
Wynikiem mojego algorytmu izochronicznego są punkty i krawędzie. W rzeczywistości mam działające rozwiązanie, ale dla 3873 krawędzi i 1529 węzłów wszystko wydaje się trwać wiecznie (około 2,0 sekundy na moim laptopie Lenovo T440s, który zawiera procesor Core i7 2015 i dość szybki dysk SSD). Zamiast sekund chcę coś więcej jak msec :-).

Może ktoś może mi pomóc w skróceniu czasu obliczeń potrzebnego do zbudowania wielokątów, które wizualizują dostępne obszary.

Ale poczekaj ... najpierw najważniejsze!
Oto wizualizacja krawędzi, które są wynikiem obliczeń mojego izochronu: Wynik obliczenia izochronu (szkielet istniejący z linii) Te krawędzie są przechowywane w tabeli bazy danych PostGIS i są prostymi liniami.

To, co chcę pokazać użytkownikowi, wygląda następująco: wprowadź opis zdjęcia tutaj Zwróć uwagę na odłączone obszary na południu i na wschód od obrazu. Powinny być one narysowane jako osobne obszary (więc scalanie nie jest tutaj dozwolone :-))

Obecnie używam tego zapytania:

SELECT ST_AsGeoJson(St_Transform(ST_Multi(ST_Collect(polygons)), 4326)) AS coverage FROM (
    SELECT ST_MakePolygon(ST_ExteriorRing(ST_GeometryN(segments, generate_series(1, ST_NumGeometries(segments))))) AS polygons FROM (
        SELECT ST_Union(ST_Buffer("GEOMETRY", 20, 'quad_segs=2')) AS segments FROM my_edges AS a
    ) AS b
) AS c

Przeprowadziłem już eksperymenty i przeczytałem dużo dokumentacji, ale po prostu nie mogę znaleźć lepszego rozwiązania.
Moim zdaniem dużym problemem jest użycie ST_Union (jak stwierdzono w dokumentacji, ta funkcja może być powolna). Bardzo interesujące jest to, że zastąpienie go ST_Collect wydaje się spowalniać obliczanie ST_Buffer, dzięki czemu poniższe zapytanie trwa jeszcze dłużej, chociaż nie wypełnia obszarów między krawędziami (tworzy tylko bufor wokół linii ):

SELECT ST_AsGeoJson(St_Transform(ST_Multi(ST_Collect(polygons)), 4326)) AS coverage FROM (
    SELECT ST_Buffer(ST_Collect(ST_LineMerge("GEOMETRY")), 20, 'quad_segs=2') AS polygons FROM my_edges AS a
) AS b

W moim systemie zajmuje to około 3,8 sekundy (prawie dwa razy więcej). Mój pierwszy wniosek z tego małego testu porównawczego jest taki, że ST_Buffer staje się nieoczekiwanie powolny, jeśli chodzi o MultiLineStrings (nawet wolniej niż podczas tworzenia buforów dla każdej linii i łączenia buforów - co moim zdaniem jest po prostu dziwne)

Próbowałem także użyć kształtów alfa (używając implementacji z pgRouting), ale ponieważ nie ma żadnej wartości alfa do ustawienia (a tak naprawdę nie chciałbym teraz, do której wartości ustawić taką wartość), po prostu otrzymuję jeden wielki wielokąt ( więc straciłbym regiony na południu i wschodzie jako osobne regiony, co nie jest tym, czego chcę).
Również ST_Polygonize (co było pierwszą rzeczą, jaka przyszła mi do głowy) nie przyniosło żadnych użytecznych rezultatów, ale być może coś mi umknęło ...

Czy istnieje lepszy sposób na utworzenie obszaru pokazanego w PostGIS? Może także przy użyciu kodu java (jts) lub kodu javascript po stronie klienta (jsts)? W rzeczywistości mógłbym żyć z utratą pewnych szczegółów, o ile obszary pokazane w moim wyniku pozostaną rozdzielone, a obliczenia będą (znacznie) szybsze.

Nikolaus Krismer
źródło
Czy nie możesz po prostu użyć ST_Exteriorring (ST_Dump (ST_Union (ST_Buffer (geom, ...)))). Geom widzi jako wszystko buforowane będzie wielokątem, a ST_Union połączy wszystkie przecinające się geometrie, więc nie ma potrzeby MakePolygon ani GeometryN. Może być konieczne przetestowanie Linestrings, które czasami wynikają z ST_Union po buforze, ale jest to łatwe dzięki ST_GeometryType (geom). Jeśli chodzi o korzystanie z Java lub jsts, możesz, ale jest mało prawdopodobne, aby było szybsze, biorąc pod uwagę, że duża część funkcji Postgis (GEOS) to przede wszystkim porty JTS C / C ++
John Powell,
Masz rację, to działa, ale w rzeczywistości nie jest szybsze (zajmuje ~ 3,1 sekundy, podczas gdy używanie GeometryN zajmuje 2 sekundy). Oto, czego użyłem: SELECT ST_AsGeoJson (ST_Transform (ST_Exteriorring ((ST_Dump (ST_Union (ST_Buffer („GEOMETRY”, 20))), geom), 4326)) FROM my_edges;
Nikolaus Krismer,
@ john-barça: Oh .. Mylę część quad_segs = 2 w ST_Buffer podczas próby podejścia ... przy tej zmianie zapytania są równe (oba na około 2 sekundy). Jednak nadal jest to bardzo powolne (w moich oczach), czy jest inny sposób, aby spróbować?
Nikolaus Krismer,
Ciekawy problem… czy chcesz udostępnić jakieś dane testowe?
dbaston
Jeśli to pomoże, chętnie podzielę się niektórymi danymi. Wszystkie rzeczy, które tu robię, mają charakter open source, więc nie powinno to stanowić dużego problemu. Pierwsza uwaga: aplikacja internetowa do testowania znajduje się na stronie dbis-isochrone.uibk.ac.at:8080/testing . Więcej informacji o rzeczach, nad którymi pracuję, można znaleźć na stronie dbis-isochrone.uibk.ac.at . W sekcji „linki” na stronie znajdują się dalsze odniesienia (w tym niektóre dane testowe)
Nikolaus Krismer

Odpowiedzi:

5

Pomijając serializację GeoJSON, na moim laptopie trwa około 6,3 sekundy:

SELECT
  ST_MakePolygon(
    ST_ExteriorRing(
      (ST_Dump(
        ST_Union(
          ST_Buffer(geom, 20, 2)))).geom))
FROM bz_edges

Patrząc na dane w OpenJUMP, zauważyłem sporo szczegółów w segmentach ulic w stosunku do pożądanego poziomu szczegółowości na wyjściu. Wydaje się, że nawet uproszczenie tych linii w locie może spowodować duże przyspieszenie w PostGIS:

SELECT
  ST_MakePolygon(
    ST_ExteriorRing(
      (ST_Dump(
        ST_Union(
          ST_Buffer(ST_Simplify(geom, 10), 20, 2)))).geom))
FROM bz_edges

co sprowadza rzeczy do 2,3 sekundy. Pomyślałem, że mógłbym zrobić lepiej, przechowując uogólnioną geometrię w osobnej kolumnie zamiast obliczać ją w locie, ale tak naprawdę nie przyniosło to żadnych dodatkowych korzyści.

W zależności od tego, ile kodu chcesz napisać, prawie na pewno możesz zrobić lepiej w Javie, jeśli nic więcej, ponieważ możesz skorzystać z wielu rdzeni. (Za ile jest warte, JTS wykonuje powyższą operację w 2,8 sekundy). Jednym z podejść może być rozszerzenie, CascadedPolygonUnionaby niektóre operacje związkowe odbywały się równolegle. (aktualizacja - tutaj jest ParallelCascadedPolygonUnion )

Zauważyłem w przykładowych danych, że krawędzie są przechowywane wraz z odniesieniami do ich początkowych i końcowych węzłów, tj. Masz wcześniej zbudowany wykres. Podejrzewam, że możesz generować te wielokąty znacznie szybciej, jeśli pracujesz na wykresie zamiast używać ogólnych operacji geometrii. Na przykład myślę, że można by coś takiego:

  1. zidentyfikować połączone elementy wykresu
  2. dla każdego podłączonego komponentu znajdź węzeł o minimalnej współrzędnej X (z pewnością na zewnątrz komponentu)
  3. przejdź po krawędziach komponentu, zawsze skręcając w lewo (lub w prawo), jeśli to możliwe. To da ci zewnętrzny pierścień każdego elementu.
  4. odpowiednio poligonizować zewnętrzny pierścień i bufor.
dbaston
źródło
Dzięki ... uproszczenie to świetne, a nawet „proste” ulepszenie. Czas potrzebny na moim laptopie zajął do 1,5 sekundy. To nie tam, gdzie chcę być, ale trochę lepiej.
Nikolaus Krismer,
Jeśli chodzi o proponowane rozwiązanie (punkty 1-4). Brzmi również bardzo prosto i warto spróbować. Myślałem o czymś podobnym, ale utknąłem w punkcie 1 (tak bardzo wcześnie :-)). Jak można zidentyfikować połączone komponenty (jedyne, o czym myślę, to zapytanie rekurencyjne, które może być również bardzo wolne).
Nikolaus Krismer
@NikolausKrismer Używam zarówno JGraphT, jak i krosna do takich zadań. Jeśli zamiast tego napiszesz własne metody wykresów (niezły pomysł na najlepszą wydajność), wyszukiwanie w głębi pozwoli znaleźć składniki. (Można je znaleźć w nadchodzącym PostGIS 2.2 z, ST_ClusterIntersectingale myślę, że i tak chcesz, aby przetwarzanie danych odbywało się poza bazą danych, więc prawdopodobnie nie jest to przydatne).
dbaston
to kilka świetnych wskazówek. Spojrzałem na JGraphT i to z pewnością mogłoby pomóc rozwiązać mój problem. Jednak spojrzałem również na Postgis 2.2 i funkcję ST_ClusterIntersecting -> identyfikacja różnych klastrów w powyższym przypadku zajmuje około 200-250 ms. Nie przeszkadza mi to (JGraphT z pewnością mógłby zrobić coś lepszego). Teraz mam do czynienia z tworzeniem zewnętrznego pierścienia zewnętrznego (ST_ExteriorRing zawodzi, ponieważ ST_MakePolygon mówi, że moje linki nie mają powłoki)
Nikolaus Krismer
Widzę dwa komplikacje: (a) potrzebujesz nie tylko zewnętrznego pierścienia, ale także wszelkich odcinków, które rozciągają się na zewnątrz od tego pierścienia, i (b) wygląda na to, że twoje linie w rzeczywistości nie przecinają się na niektórych skrzyżowaniach. Będziesz musiał naprawić (b), jeśli spróbujesz skonstruować geometrię na podstawie wyników przejścia po wykresie.
dbaston