| |  обход контура [ 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
| есть прога на С# калькулятор!!!!!! |
|
ОтветитьЗнаком «*» отмечены обязательные для заполнения поля. |
