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

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

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.

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.

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 .

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.