Как мне описать особые отношения между связанными ребрами?

Рассмотрим простую ситуацию, когда три ребра соединяются в узле:

Я хотел бы написать краткое и четкое описание отношений между A и B таким образом, чтобы отличать их от отношений между A и C. Что-то вроде «при прохождении узла по часовой стрелке A соседствует? к Б, но А не соседствует? в C. » Но это не совсем смежность.

Сказано по-другому: представьте, что вы стоите на узле и обращены к А. Вы начинаете вращаться по часовой стрелке. Следующее преимущество - B, а не C.

Есть ли способ описать эти отношения между A и B более кратким, формальным или правильным способом, чем я написал выше?

Оно должно быть направленным (одно отношение этого типа существует в направлении по часовой стрелке от A, а другое существует в направлении против часовой стрелки). И это должно масштабироваться до случаев, когда в узле соединено более трех ребер. Может быть, это как-то связано с маршрутизацией? (Я думаю об этом в контексте дорожных сетей.)

Два подхода, которые я уже пробовал, но не продвинулись далеко:

1. 9IM-подобные ссылки на топологию : я посмотрел на DE-9IM , и, хотя я не математик, я думаю, что я все еще могу сказать по диаграммам и терминам, что он не охватывает этот тип отношений. Я также пока не нахожу его в описании топологии в справке ESRI или справке Oracle . (Может быть, там что-то есть, но я пока не нахожу это!)

2. Лица : я играл с тем фактом, что лицо на «северной» стороне A также может быть ограничено также B, но не C. Однако, как вы можете видеть на диаграмме, это не всегда верно. Представьте, что моя диаграмма - это фрагмент дорожной сети, где A и C - магистральные дороги, а B - короткий тупиковый путь.

Я подозреваю, что не может быть единственного термина для того, что я пытаюсь сказать; как минимум, я бы хотел описать такие отношения проще, чем я делал выше. Это независимый от платформы вопрос. Прямо сейчас я просто ищу правильные слова. Позже я попытаюсь реализовать концепцию в python (pyqgis или arcpy) в шейп-файле, поэтому любые ответы с этой конечной точкой будут особенно интересными, но не обязательными.

Я знаю, что немного опаздываю на вечеринку, но это довольно интересная вещь, и я надеюсь, что мой ответ может быть полезным.

То, о чем вы спрашиваете, это качественное отношение; часто игнорируется родной брат количественного отношения. Качественные рассуждения довольно часто встречаются в геопространственной науке. Примеры запросов включают: какие участки находятся рядом с этой? Какие особенности находятся в перекрытии области A и области B? Какие области вогнуты? Какая дорога слева? Отношения: смежные, внутри, вогнутые и левые. Качественные запросы часто упускаются из виду или недооцениваются по сравнению с количественными вопросами, такими как, которые больше, короче или больше в количестве.

Качественное отношение, которое принимает два входа, называется бинарным отношением. Для этого есть два общих обозначения: - isLeftOf (A, B) Это префиксное обозначение. - A isLeftOf B Это инфиксная запись.

В приведенных выше примерах также было одинарное отношение: isConcave. Это отношение связывает регион с собой и возвращает логическое значение.

Все пространственные предикаты Эгенхофера в модели 9-пересечений (на которые ссылается 9EIM) являются бинарными отношениями между двумя регионами. Вас также может заинтересовать RCC Рэнделла, Цуя и Кона (http://en.wikipedia.org/wiki/Region_connection_calculus). Качественные (топологические) отношения, приведенные в этой области исследования, связывают регионы с регионами, а более поздние работы связывают линии с регионами и линии с линиями. Тем не менее, это не совсем то, что вы ищете.

Хорошо, извините за отступление, но, надеюсь, это поможет с терминологическим аспектом вашего вопроса.

@whuber был прав, предложив список двунаправленных ребер (DCEL). Это близкий родственник комбинаторных карт, часто используемых под прикрытиями в системах САПР, и крылатых ребер. Концепция крылатого края (http://en.wikipedia.org/wiki/Winged_edge) - это то, как стандарт хорошо известного текста определяет отверстие в многоугольнике (http://en.wikipedia.org/wiki/Well-known_text #Geometric_objects). Обратите внимание на многоугольник, что порядок внешних точек против часовой стрелки и по часовой стрелке для внутренних точек. Маленькая фея, идущая вдоль границы в таком порядке, всегда будет видеть область слева от нее.

При использовании комбинаторных карт и DCEL ключевой момент заключается в том, что эти объекты определены на ориентируемой поверхности. Нам не нужно вдаваться в математические формальности - идея довольно проста: если вы можете определить направление на поверхности, как вы можете с любой системой пространственной привязки в ГИС, то у вас есть ориентируемая поверхность. Итак, если вы можете определить направление, то вы можете определить направленное упорядочение вокруг любой точки на поверхности. С помощью направленного упорядочения вы можете определить isLeftOf (A, B), isRotationallyAdjacentTo (A, B) и так далее.

Определение порядка вокруг вершины в графе, внедренном в поверхность, требует двух назначений: 1) назначение меток конечным точкам ребер и 2) назначение соглашения для порядка вокруг вершины. Если порядок элементов в массиве (например, [A, B, C] на изображении) по часовой стрелке, то мы можем определить, какое ребро находится слева от B.

В вашем примере каждый элемент соседствует с остальными. Этот факт также виден в массиве, потому что массив фактически представляет перестановку, т. Е. Порядок имеет значение, но какой элемент является первым, нет. Таким образом, [A, B, C] эквивалентно [C, A, B]. Другими словами, массив оборачивается вокруг последнего элемента рядом с первым.

Когда вы посмотрите на графики топологии и связности, которые вы получаете от таких поставщиков, как Teleatlas, Navteq, ESRI и т. Д., Вы начнете видеть шаблон (конечно, у каждого есть свой «особый» способ действий).

Лично , хотя 1) геопространственная топология и 2) маршрутные графы - это просто графики, которые можно обобщенно представить в одной структуре данных, я стараюсь избегать этого в максимально возможной степени.

Я пытаюсь сделать различие в моей голове.

• Когда я говорю «Геопространственная топология» (1), я имею в виду структуру графа для представления геометрических отношений элементов (например, то, что осталось от края A, какая грань образована ребрами [A, B, C], что содержится в гранях). Б и т. Д.).
• Когда я говорю «Routing Graph» (2), я имею в виду структуру графа для решения задач маршрутизации (например, кратчайший путь для получения из A-> B с [X] ограничениями / условиями)

Это просто графики, и они принадлежат к сфере науки , но есть явное преимущество, поскольку они не обобщают одно и то же. Они служат различным целям, и гораздо проще оптимизировать и применять операции, когда они специализированы для этой конкретной цели.

ESRI делает это. У них есть структура графика для геопространственной топологии (TopologyGraph) и другая структура графика для задач маршрутизации (набор сетевых данных). Черт возьми, у них даже есть старая структура графов - геометрические сети, которая хорошо подходит для проблем потоков в инженерных сетях.

Возможно, в мире PostgreSQL / PostGIS мы также сталкиваемся с этим. Существует структура данных для маршрутизации и еще одна для геопространственной топологии .

В своем вопросе вы говорите о графиках и навигации по ним по часовой стрелке и против часовой стрелки, а также о гранях, что делает меня нужным для специализированной структуры (1).

Что касается "геопространственной топологии", я думаю, что хороший способ представления этого вида топологии - это способ, которым Гидрографическое управление Великобритании делает в своем описании топологии S57 полной топологии .

Очень похоже на то, что делают все основные реализации.

Теперь, если вы ищете маршрутизацию, тогда график станет другим в зависимости от того, требуется ли вам однонаправленное или двунаправленное соединение. В конце концов, это сводится к:

• Наличие узлов FROM, связанных с узлами TO, которые создают края
• В Ребре имеет атрибуты для левой и правой стороны (например , диапазоны адресов).
• В Junctions (то есть узлы , где ребра соединяют) может иметь множество ограничений. Таким образом, у вас в основном будет запись главного соединения для представления самого соединения и отдельные записи с записями FROM и TO для представления ограничений потока.

Удачи, и дайте нам знать, как получается ваш проект.