Официальный сайт геоинформационной системы (ГИС) ObjectLandОфициальный сайт геоинформационной системы (ГИС) ObjectLand
  
 
ПОИСК ПО САЙТУ:
yandex.ru
КАРТА САЙТА
 
главная / поддержка / форум
E-MAIL:ПАРОЛЬ: 
регистрация

Обсуждение

 обход контураобход контура [ VAK ]
Среда, 28 августа 2002, 15:24

Задача на топологию:
обхожу массив смежных отрезков (граф на плоскости) по правилу правой руки (все время забираю вправо). Таким образом формирую контура.
Если иду изнутри графа, то образуется внутренний контур с обходом против стрелки. Если начинаю с внешнего отрезка, то образуется внешний контур с обходом по часовой стрелки.
Как понять, какой контур получил?

 обход контура [ Andrey ]
Четверг, 5 сентября 2002, 14:58

Внешний контур является границей области содержащей все отрезки(вершины графа).
Внешний контур все вершины отрезков принадлежат области. И наоборот, внутренний контур любая вершина, не принадлежащая контуру, находится вне области.
Задача сводится к вопросу о принадлежности точки области.

 обход контура [ VAK ]
Пятница, 6 сентября 2002, 15:57

Андрей, благодарен, что вы откликнулись.
В процессе анализа проблемной области, выяснилось, что это не связанный граф, а несколько подграфов. И надо в конце обхода по контуру понять: охватывает он подграф, или нет.
Решение пришло совсем с необычной стороны (для меня) - смотрю знак интеграла площади. Если отрицательный - охватывает.
А главное, не надо перебирать точки на принадлежность области контура. Этот алгоритм, кажется, сложности n^2.

 обход контура [ Andrey ]
Понедельник, 9 сентября 2002, 08:53

Моё сообщение было слегка обрезано - пропал знак "тогда и только тогда, когда" и смысл алгоритма стал не совсем понятен.
Идея в том, что не надо перебирать все точки - достаточно проверить любую не принадлежащую контуру. Если она лежит внутри - внешний контур, в противном случае - внутренний.
Но это, естественно, верно только для связного графа.

 обход контура [ VAK ]
Вторник, 10 сентября 2002, 13:00

Andrey,
тогда попутный вопрос.
Где изучить быстрый алгоритм проверки расположения точки внутри контура?
Я изобрел один, но не учерен, что он хороший.

VAK


 обход контура [ ObjectLand Development Team ]
Вторник, 10 сентября 2002, 15:34

Изобрести в этой сфере что-то новое сложно, проще использовать готовые проверенные алгоритмы, известные как алгоритм заметания или алгоритм секущих.
На указанном сайте эти алгоритмы изложены концептуально, а также имеется псевдокод и код на С++:
http://geometryalgorithms.com/Archive/algorithm_0103/algorithm_0103.htm

 обход контура [ VAK ]
Вторник, 17 сентября 2002, 11:48

Благодарю всех, кто помогал писать программу сборки контуров участков из массива отрезков границ. Программа готова. Язык программировани C#.
Желающие получить исходники могут писать по E-mail.

 обход контура [ аня ]
Четверг, 13 апреля 2006, 23:01

есть прога на С# калькулятор!!!!!!

Ответить

Знаком «*» отмечены обязательные для заполнения поля.
Ваше имя:  *
Адрес электронной почты:  
Тема:  *
Сообщение:
 *
Подтверждение:
(не требуется для зарегистрированных пользователей)
 *
 



Copyright © 1999–2023 ГИС ObjectLand
ГИС ObjectLand ® ООО «Радом-АйТи»
Информация о лицензировании
главная | о продукте | скачать | купить | поддержка | новости