Jak opisać specjalną zależność między połączonymi krawędziami?

11

Rozważ tę prostą sytuację, w której trzy krawędzie łączą się w węźle:

relacje brzegowe

Chciałbym napisać zwięzły i jasny opis związku między A i B w taki sposób, aby odróżnić go od związku między A i C. Coś w rodzaju „gdy przemierza się węzeł w kierunku zgodnym z ruchem wskazówek zegara, A sąsiaduje? do B, ale A nie sąsiaduje? do C. ” Ale to nie jest tak naprawdę sąsiedztwo.

Powiedziane inaczej: wyobraź sobie, że stoisz na węźle i patrzysz w stronę A. Zaczynasz wirować zgodnie z ruchem wskazówek zegara. Następną krawędzią, do której dojdziesz, jest B, a nie C.

Czy istnieje sposób na opisanie tego związku między A i B w bardziej zwięzły, formalny lub poprawny sposób, niż napisałem powyżej?

Musi być kierunkowy (jedna relacja tego typu istnieje w kierunku zgodnym z ruchem wskazówek zegara od A, a druga w kierunku przeciwnym do ruchu wskazówek zegara). I musi być skalowany do przypadków, w których więcej niż trzy krawędzie są połączone w węźle. Może ma to coś wspólnego z routingiem? (Myślę o tym w kontekście sieci drogowych).

Dwa podejścia, które próbowałem już, ale nie zaszedłem daleko:

  1. Odniesienia do topologii podobnej do 9IM : Spojrzałem na DE-9IM i chociaż nie jestem matematykiem, sądzę, że nadal mogę stwierdzić na podstawie diagramów i terminów, że nie obejmuje on tego rodzaju relacji. Nie znajduję go jeszcze w opisach topologii w pomocy ESRI lub Oracle . (Może coś tam jest, ale jeszcze tego nie znalazłem!)

  2. Twarze : bawiłem się faktem, że twarz po „północnej” stronie A może również być ograniczona przez B, ale nie C. Jednak, jak widać na schemacie tutaj, nie zawsze jest to prawdą. Wyobraź sobie, że mój schemat jest wyciągiem z sieci dróg, w której A i C to drogi arterialne, a B to krótka ślepa droga.

Podejrzewam, że nie może istnieć ani jeden termin na to, co próbuję powiedzieć; przynajmniej chciałbym móc opisać taki związek w prostszy sposób niż wcześniej. To pytanie niezależne od platformy. W tej chwili szukam właściwych słów. Później postaram się zaimplementować tę koncepcję w pythonie (pyqgis lub arcpy) na pliku kształtu, więc wszelkie odpowiedzi z tym punktem końcowym będą szczególnie interesujące, ale nie konieczne.

andytilia
źródło
Dlaczego nie dołączasz do każdego węzła listy krawędzi z nim połączonych uporządkowanych według kierunku?
Julien
1
Wygląda na to, że szukasz DCEL . Zauważ, że podczas dualizacji wykresu płaskiego ściany stają się węzłami. Na ilustracji są kawałki trzech ścian alfa , beta i gamma , z krawędzią A oddzielającą beta od gamma , krawędzią B oddzielającą gamma od alfa i krawędzią C oddzielającą alfa od beta . Daje to cykliczny wykres, który zawiera wszystkie informacje, których szukasz - i tak naprawdę jest to sąsiedztwo na podwójnym wykresie.
whuber
@julien, dzięki - to dobry pomysł na wdrożenie; Wypróbuję to. Ale najpierw ... szukam słowa lub wyrażenia opisującego ten rodzaj relacji.
andytilia
@ whuber, dzięki za wskazówkę. Nie spotkałem wcześniej DCEL. Wygląda na to, że B jest „następną” połową krawędzi północnej strony, zachodnią połową krawędzi A. Hm: to jeśli chcę jechać przeciwnie do ruchu wskazówek zegara, to rozważam południową krawędź A. I „zachodnią” jest implikowany przez wspólny węzeł. Zastanawiam się, czy zadziała, gdy B nie jest granicą twarzy (tj. Ślepa droga). Przyjrzę się temu dalej.
andytilia
@julien, ponownie czytam twój komentarz. Widzę, że teraz sugerujesz mi także frazowanie. :-) Może mógłbym użyć „uporządkowanego według kierunku”, aby opisać związek. Muszę się z tym trochę pobawić.
andytilia

Odpowiedzi:

1

Wiem, że jestem tu trochę spóźniony na imprezę, ale to całkiem interesujące rzeczy i mam nadzieję, że moja odpowiedź może się przydać.

Pytasz o relację jakościową; często ignorował rodzeństwo relacji ilościowej. Rozumowanie jakościowe pojawia się dość często w naukach geoprzestrzennych. Przykładowe zapytania obejmują: Które działki sąsiadują z tym? Jakie funkcje pokrywają się z regionem A i regionem B? Które regiony są wklęsłe? Która droga jest po lewej? Relacje są: przylegające do, wewnątrz, wklęsłe i po lewej stronie. Zapytania jakościowe są często pomijane lub niedoceniane w porównaniu z pytaniami ilościowymi, takimi jak to, które jest większe, krótsze lub większe.

Relacja jakościowa, która wymaga dwóch danych wejściowych, nazywana jest relacją binarną. Istnieją w tym celu dwa typowe oznaczenia: - isLeftOf (A, B) To jest zapis przedrostka. - A isLeftOf B To jest notacja infiksowa.

W powyższych przykładach istniała również jedność: isConcave. Ta relacja odnosi region do siebie i zwróciłaby wartość logiczną.

Wszystkie predykaty przestrzenne Egenhofera w modelu 9-przecięciowym (przywołane w 9EIM) są relacjami binarnymi między dwoma regionami. Mogą Cię również zainteresować RCC Randell, Cui i Cohna (http://en.wikipedia.org/wiki/Region_connection_calculus). Relacje jakościowe (topologiczne) podane w tym obszarze badań dotyczą regionów do regionów, a późniejsze prace dotyczą linii do regionów i linii do linii. Jednak nie do końca tego szukasz.

OK, przepraszam za dygresję, ale mam nadzieję, że to pomaga w aspekcie terminologicznym twojego pytania.

@whuber był na dobrej drodze, sugerując podwójnie połączoną listę krawędzi (DCEL). Jest to bliski krewny map kombinatorycznych, często używanych pod pokrywami w systemach CAD i skrzydlatych krawędziach. Koncepcja skrzydlatej krawędzi (http://en.wikipedia.org/wiki/Winged_edge) polega na tym, jak standard znanego tekstu definiuje dziurę w wielokącie (http://en.wikipedia.org/wiki/Well-known_text #Geometric_objects). Zwróć uwagę na wielokąt, że kolejność punktów zewnętrznych jest zgodna z ruchem wskazówek zegara, a dla punktów wewnętrznych zgodnie z ruchem wskazówek zegara. Mała wróżka idąca wzdłuż granicy w tej kolejności zawsze widziała wnętrze regionu po lewej stronie.

W przypadku map kombinatorycznych i DCEL kluczową kwestią jest to, że obiekty te są zdefiniowane na powierzchni, która jest orientowalna. Nie musimy zajmować się formalnościami matematycznymi - pomysł jest dość prosty: jeśli możesz zdefiniować kierunek na powierzchni, jak w przypadku dowolnego systemu odniesienia przestrzennego w GIS, to masz orientowaną powierzchnię. Jeśli więc możesz zdefiniować kierunek, możesz zdefiniować uporządkowanie kierunkowe wokół dowolnego punktu na powierzchni. Dzięki uporządkowaniu kierunkowemu możesz zdefiniować isLeftOf (A, B), isRotationallyAdjacentTo (A, B) i tak dalej.

Definiowanie porządku wokół wierzchołka na wykresie osadzonym na powierzchni wymaga dwóch przypisań: 1) przypisania etykiet do punktów końcowych krawędzi i 2) przypisania konwencji porządku wokół wierzchołka. Jeśli kolejność elementów w tablicy (np. [A, B, C] na zdjęciu) jest zgodna z ruchem wskazówek zegara, możemy stwierdzić, która krawędź znajduje się po lewej stronie B.

W twoim przykładzie każdy element sąsiaduje z innymi. Fakt ten jest również widoczny w tablicy, ponieważ tablica faktycznie reprezentuje permutację, tzn. Kolejność ma znaczenie, ale który element jest pierwszy, nie ma znaczenia. Zatem [A, B, C] jest równoważne z [C, A, B]. Innymi słowy, tablica owija się wokół ostatniego elementu przylegającego do pierwszego.

katahdin
źródło
Dzięki! Podoba mi się termin „obrotowo przylegający”. Po prostu trzeba go rozszerzyć, jak mówisz, zgodnie z konwencją porządkowania wokół wierzchołka. W moim przypadku muszę zdefiniować tę konwencję dla każdego przypadku, więc będę pracował nad kodowaniem czegoś takiego jak isRotationallyAdjacentTo (A, B, Direction) przy użyciu permutacji, jak sugerujesz. Lub w odniesieniu do powyższego przypadku „A jest obrotowo zgodny z ruchem wskazówek zegara do B, a A nie jest obrotowo zgodny z ruchem wskazówek zegara do C”.
andytilia
Nawiasem mówiąc, nie sprawdziłem jeszcze rachunku połączeń regionalnych. Chociaż nie do końca rozwiązuje ten problem (jak wspominasz), jest jednak interesujący. Czy możesz wskazać mi „późniejsze dzieła”, o których myślisz Randell, Cui i Cohn? (hm: postacie RC&C stworzyły framework o nazwie RCC)
andytilia
4

Kiedy spojrzysz na wykresy topologii i połączeń, które otrzymujesz od dostawców takich jak Teleatlas, Navteq, ESRI itp., Zaczniesz widzieć wzór (oczywiście każdy ma swój „specjalny” sposób robienia rzeczy).

Osobiście , chociaż 1) topologia geoprzestrzenna i 2) wykresy routingu są tylko wykresami i mogą być uogólnione, aby były reprezentowane w tej samej strukturze danych, staram się tego unikać w jak największym stopniu.

Staram się rozróżniać w mojej głowie.

  • Kiedy mówię „topologia geoprzestrzenna” (1), mam na myśli strukturę graficzną reprezentującą geometryczne relacje cech (np. To, co pozostało z krawędzi A, jaka powierzchnia jest utworzona przez krawędzie [A, B, C], co jest zawarte przez twarz B itp.).
  • Kiedy mówię „Wykres routingu” (2), mam na myśli strukturę graficzną do rozwiązywania problemów z routingiem (np. Najkrótsza ścieżka do uzyskania z A-> B z ograniczeniami / warunkami [X])

Są tylko wykresami i należą do szerokiej gamy nauki , ale istnieje wyraźna korzyść, ponieważ nie uogólnia się tak samo. Służą one różnym celom i znacznie łatwiej jest zoptymalizować i zastosować operacje, gdy specjalizują się w tym konkretnym celu.

ESRI to robi. Mają strukturę graficzną dla topologii geoprzestrzennej (TopologyGraph) i inną strukturę graficzną dla problemów z routingiem (zestaw danych sieciowych). Do diabła, mają nawet starszą strukturę grafów - sieci geometryczne - która dobrze służy do problemów z przepływem w sieciach użyteczności publicznej.

Prawdopodobnie w świecie PostgreSQL / PostGIS również to spotykamy. Istnieje struktura danych dla routingu i inna dla topologii geoprzestrzennej .

W swoim pytaniu mówisz o wykresach i poruszaniu się po nich zgodnie z ruchem wskazówek zegara i przeciwnie do ruchu wskazówek zegara, a także o twarzach, co czyni mnie rzeczą, dla której potrzebujesz specjalnej struktury (1).

W przypadku „Topologii geoprzestrzennej” uważam, że dobrym sposobem przedstawienia tego rodzaju topologii jest sposób, w jaki brytyjski Urząd Hydrograficzny robi to w opisie pełnej topologii S57 .

Pełna topologia UKHO

Bardzo podobny do tego, co robią wszystkie główne implementacje.

Teraz, jeśli szukasz routingu, wykres staje się inny w zależności od tego, czy potrzebujesz łączności jednokierunkowej czy dwukierunkowej. Na koniec sprowadza się do:

  • Posiadanie FROM węzłów połączonych z węzłami TO, które tworzą Krawędzie
  • Na Krawędzi mieć atrybuty dla lewej i prawej strony (np zakresów adresów).
  • W Skrzyżowania (czyli węzły, gdzie krawędzie łączenia) może mieć szereg ograniczeń. Zasadniczo miałbyś więc pozycję głównego połączenia reprezentującą samo połączenie, a pojedyncze wpisy z pozycjami FROM i TO reprezentujące ograniczenia przepływu.

Powodzenia i daj nam znać, jak Twój projekt się potoczy.

Ragi Yaser Burhum
źródło
Wielkie dzięki za wyraźne rozróżnienie między dwoma rodzajami wykresów. Czy uważasz, że sprawiedliwym rozróżnieniem jest stwierdzenie, że wykresy routingu zazwyczaj zawierają pewne informacje na krawędziach i / lub węzłach, podczas gdy topologia geoprzestrzenna nigdy nie wymaga przypisania na krawędziach i węzłach (opiera się tylko na relacjach przestrzennych między obiektami)? Wydaje mi się, że mój problem pasuje solidnie do dziedziny topologii geoprzestrzennej: związek między krawędziami A i B istnieje niezależnie od jakiegokolwiek przypisania na krawędziach. Ale wciąż brakuje mi zwięzłego sposobu nazwania tego związku ...
andytilia,
Uważam, że jest to zbyt mocne stwierdzenie, by powiedzieć, że „Topologia geoprzestrzenna nigdy nie wymaga przypisania na krawędziach i węzłach”, tak naprawdę dzieje się to w poszczególnych przypadkach. Widziałem wykresy topologii zawierające atrybucję, która jest wspólna dla funkcji mających ten węzeł. Przykładami są wartości Z lub temperatura. Powiedziałbym, że po prostu nazwij go węzłem i dokonaj rozróżnienia podłączonego węzła, jeśli to konieczne, ale oczywiście nie mam wystarczającego kontekstu ogólnego problemu, który próbujesz rozwiązać.
Ragi Yaser Burhum
Ach, racja, dzięki: płaski wykres dwóch dróg przecinających most. Może istnieć jeden węzeł z czterema krawędziami, ale nie wszystkie krawędzie łączą się ze sobą. Zatem węzeł musi zawierać informacje o poziomach przekraczania, aby odróżnić tę sytuację od przekroczenia na poziomie.
andytilia
1
Dokładnie :). Dlatego wspominam Połączenia. Myślałem o tej sprawie. Jednym ze sposobów jest przedstawienie węzła jako „węzła głównego” z wpisami FROM-TO. Wiadukty / przejścia podziemne występują cały czas. Nawet najgorsze są przypadki takie jak Bay Bridge lub w Chicago, gdzie masz krawędzie, które pasują do siebie w przestrzeni 2D (są one skutecznie jedna nad drugą) z zestawem krawędzi przepływających w jedną stronę, podczas gdy drugi zestaw płynie w drugą stronę.
Ragi Yaser Burhum,