|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
20.03.2009, 18:45 | #1 |
Форумчанин
Регистрация: 02.02.2009
Сообщений: 844
|
определение направления обхода контура
Сабжевый вопрос не совсем топичен, но реализацию алгоритма планируется в Excel, а значит он имеет отношение к этой программе.
Задача: Есть координаты вершин (X, Y) замкнутого контура, полученные методом обхода. Нужно определить направление обхода (по часовой или против часовой стрелки). Может кто знает как это реализовывается. Должно быть что-то простое, а мне на ум лезут только сверх сложные расчеты.
С уважением, Алексей.
|
20.03.2009, 19:11 | #2 |
Программист VBA
СуперМодератор
Регистрация: 13.07.2008
Сообщений: 6,858
|
А что сложного?
Перебираете в цикле координаты вершин, и вычисляете угол между 2 векторами - текущей стороной контура, и следующей. Если в течении всего цикла величины углов меньше нуля, значит, обход осуществляется по часовой стрелке, в случае же углов больше 0 - против часовой стрелки. Если знак величины угла изменяется - обход осуществляется не в порядке расположения вершин (или контур не является выпуклым). Нашел кое-что по теме: http://faqs.org.ru/forum/viewtopic.php?t=11754
__Полезные надстройки для Excel. Парсинг сайтов и файлов.
Макросы любой сложности на заказ. Мониторинг цен конкурентов Последний раз редактировалось EducatedFool; 20.03.2009 в 19:48. Причина: нашел аналогичую тему на другом форуме |
20.03.2009, 20:06 | #3 |
Участник клуба
Регистрация: 12.10.2007
Сообщений: 1,204
|
Еще можно вычислить площадь
http://programmersforum.ru/showthrea...621#post206621 и по ее знаку определить направление Последний раз редактировалось alexBlack; 20.03.2009 в 20:31. |
20.03.2009, 20:21 | #4 | ||
Форумчанин
Регистрация: 02.02.2009
Сообщений: 844
|
Цитата:
Цитата:
Я пока склоняюсь к варианту определения по четвертям. 1. Находим точку с минимальным значением по X. Это позволит избавиться от 2 нижних четвертей. 2. Находим Dy предыдущей и последующей точек. 3. Находим Dy/2 середину. Ось X. 4. If y(пред)<y(посл) then if y(посл)>Dy then обход по часовой Else Обход против часовой. Else if y(пред)>Dy then обход по часовой Else Обход против часовой. 5. Если Dy=0 тоже самое для оси X. Что мне не нравиться: слишком много разных проверок. Возможно стоит вернуться к проверке по всем четырем четвертям, тогда можно будет за основу брать любую точку. Ну конечно нужно еще все раз проверить, может я еще чего не учел.
С уважением, Алексей.
|
||
20.03.2009, 20:24 | #5 |
Форумчанин
Регистрация: 02.02.2009
Сообщений: 844
|
Но нутром чую есть более простое решение.....
С уважением, Алексей.
|
20.03.2009, 20:31 | #6 | |
Программист VBA
СуперМодератор
Регистрация: 13.07.2008
Сообщений: 6,858
|
Цитата:
В общем случае (при невыпуклом контуре) требуются более сложные алгоритмы. Ну а если для определения направления Вы не считаете нужным анализировать все координаты, то можно сделать даже так: 1) Находим самую верхнюю, самую нижнюю, а также самую правую и самую левую точки. 2) Анализируем индексы найденных точек: к примеру, если индекс самой правой меньше индекса самой нижней, значит, обход осуществляется по часовой стрелке. |
|
20.03.2009, 20:48 | #7 | ||
Форумчанин
Регистрация: 02.02.2009
Сообщений: 844
|
Цитата:
Цитата:
Уже 30 минут сижу тупо глядя на нарисованный и номерами точек по краям.... Как раз эта идея... Пытаюсь придумать случае, когда возможны сбои. Пока не нашел.... Реализую - погоняю на практике.
С уважением, Алексей.
|
||
20.03.2009, 21:19 | #8 | |
Форумчанин
Регистрация: 02.02.2009
Сообщений: 844
|
Цитата:
Вот моя функция для подсчета площади. ИМХО поудобнее, в ней заложена возможность проверки корректности переданных координат, но не реализована: Код:
С уважением, Алексей.
|
|
20.03.2009, 21:48 | #9 |
Участник клуба
Регистрация: 12.10.2007
Сообщений: 1,204
|
Почему два-три раза ?
Вообще-то я предложил это как метод определения направления обхода. Одновременно получаем и площадь. Пример для контура в виде цифры 2 (площадь 14). Код:
|
20.03.2009, 23:17 | #10 | |
Форумчанин
Регистрация: 02.02.2009
Сообщений: 844
|
А сколько у тебя в пример? :))
Нельзя этого делать. Получение отрицательной площади - ОШИБКА, черных дыр у нас пока нет. Использование ОШИБОЧНЫХ данных в работе обязательно приводит к появлению ошибок в других местах. А применение такого топорного исправление ошибка как "умножение результата на -1", как минимум указывает на халатность исполнителя и отсутствие стиля программирования, а как максимум на проф не пригодность. И как программиста и как геодезиста. Весь мой более десятилетний опыт работы говорит - Так работать нельзя. Это две разные операции, совмещать подобное ни в коем случае нельзя. Я позволяю себе подобное только при "накидном монтаже" решения задачи. Как минимум проблема в ограниченности количества точек. При решении это задачи нужно понимать что заранее сказать сколько будет точек сказать не возможно, а значит нужно по возможности уйти от любых ограничений. У нас были контура с несколькими тысячами точек. Цитата:
1. Наличие отдельной процедуры, задача не такая уж сложная задача. 2. Наличие двух циклов. Ей богу не понял зачем... если только для примера. 3. На мой взгляд сложная конструкция: функция, проверки, сложное условие цикла... Короче раздолье для появления ошибки. 4. Отсутствие комментариев. Есть простое правило, которое мало кто соблюдает: если есть переменная, она должна быть прокомментирована.
С уважением, Алексей.
|
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Определение IP | IvanLex | HTML и CSS | 6 | 28.03.2008 07:46 |
Определение IP | IvanLex | Общие вопросы по Java, Java SE, Kotlin | 1 | 19.02.2008 09:12 |