Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: 1 [2]  Все   Вниз
  Печать  
Автор Тема: Направление ввода полигона  (Прочитано 26506 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #30 : 27-12-2010 09:44 » 

Нарисуйте, пожалуйста. Непонятно, какое отношение два треугольника имеют к замкнутому полигону.
Записан

Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
Kivals
Команда клуба

us
Offline Offline
Пол: Мужской

WWW
« Ответ #31 : 27-12-2010 09:45 » 

sss, просто попробуй нарисовать "замкнутый односвязный полигон" одной линией. Неужели будут сомнения в том по часовой стрелке он рисовался или против?

Dale, Улыбаюсь)
Записан
sss
Специалист

ru
Offline Offline

« Ответ #32 : 27-12-2010 09:46 » 

Записан

while (8==8)
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #33 : 27-12-2010 09:49 » 

При обходе вдоль всего контура внутренняя область полигона остается слева. Вывод: обход против часовой стрелки, несмотря на то, что в точках 2 и 5 углы внутренние.
Записан

Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
Kivals
Команда клуба

us
Offline Offline
Пол: Мужской

WWW
« Ответ #34 : 27-12-2010 09:50 » 

Для всего полигона обход против часововой, т.к. вся площадь полигона всегда находится слева от контура. А вот если воспользоваться предложеным методом оптимизации "по первым трем точкам" - то он даст неверный результат.
Записан
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #35 : 27-12-2010 09:52 » 

А вот если воспользоваться предложеным методом оптимизации "по первым трем точкам" - то он даст неверный результат.

Я бы даже уточнил - по любому собственному подмножеству множества вершин контура результат может быть неверным. Как повезет.
Записан

Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
sss
Специалист

ru
Offline Offline

« Ответ #36 : 27-12-2010 09:54 » 

А если точка 2 окажется левее точки 5?
Записан

while (8==8)
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #37 : 27-12-2010 10:01 » 

Без разницы. До тех пор, пока контур не имеет самопересечений, ничего не меняется. А когда появляются самопересечения, само понятие внутренней области (и заодно полигона) становится неопределенным.
Записан

Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #38 : 27-12-2010 10:04 » 

А вот если воспользоваться предложеным методом оптимизации "по первым трем точкам" - то он даст неверный результат.

Я бы даже уточнил - по любому собственному подмножеству множества вершин контура результат может быть неверным. Как повезет.

Вот попытался проиллюстрировать эту мысль наглядно:



Единственная точка N полностью определяет направление контура в целом.

* Poly.png (3.55 Кб - загружено 750 раз.)
Записан

Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
sss
Специалист

ru
Offline Offline

« Ответ #39 : 27-12-2010 10:11 » 

Я сдаюсь.. Если выбор будет сделан на основе отнимем площадь треугольников по часовой и против - у кого больше тот и победил... Только один вопрос - вот вы нашли направление обхода для не выпуклого полигона - и как его применить? Для расчетов нормалей и биссектрис не годится..
Записан

while (8==8)
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #40 : 27-12-2010 10:16 » 

Dale, если я правильно понял, то только для выпуклых многоугольников.
Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #41 : 27-12-2010 10:18 » 

Только один вопрос - вот вы нашли направление обхода для не выпуклого полигона - и как его применить? Для расчетов нормалей и биссектрис не годится..

Например, я когда-то решал задачу заливки внутренней области полигона прямоугольниками. Это нужно для проектирования фотошаблонов при производстве микросхем. Важно знать, слева или справа от данного отрезка контура находится внутренняя область. А для этого необходимо знать направление обхода.

Добавлено через 34 секунды:
Dale, если я правильно понял, то только для выпуклых многоугольников.

Что именно? Приведенная формула?
« Последнее редактирование: 27-12-2010 10:19 от Dale » Записан

Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #42 : 27-12-2010 12:27 » 

Цитата: Dale
Что именно? Приведенная формула?
Нет, метод определения по трём вершинам. При этом знание о выпуклости должно быть априорным.
Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
sss
Специалист

ru
Offline Offline

« Ответ #43 : 27-12-2010 13:02 » 

...слева или справа от данного отрезка контура находится внутренняя область. А для этого необходимо знать направление обхода.

Так вот, тогда, в месте локального треугольника, имеющего направление отличное от вычисленного общего, вы получите ошибку в определении направления.
« Последнее редактирование: 27-12-2010 13:29 от sss » Записан

while (8==8)
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #44 : 27-12-2010 13:35 » 

Так вот, тогда, в месте локального треугольника, имеющего направление отличное от вычисленного общего, вы получите ошибку в определении направления.

Можно иллюстрацию?

Нет, метод определения по трём вершинам. При этом знание о выпуклости должно быть априорным.

Да, в таком случае можно и по трем, если мы точно знаем, что в каждой точке поворот производится в одном направлении. Тогда остальные точки не дадут нам никакой новой информации. Но это слишком частный случай.
Записан

Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
sss
Специалист

ru
Offline Offline

« Ответ #45 : 28-12-2010 02:24 » 

Посидел, посчитал площадь так и сяк. Признаю, для невыпуклых полигонов, был не прав . Пошел переделывать (добавлять) код..
Записан

while (8==8)
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #46 : 28-12-2010 04:44 » 

sss, полигон у меня может быть не то чтобы даже выпуклым, а совсем впуклым )) Собственно, вот для чего делалось - в аттаче экзешник. В меню кнопка "отсечение линии". Отрезок разбивается полигоном на кусочки, и какие отрезки будут лежать внутри полигона - зависит от направления обхода (красным окрасятся, когда полигон ЧС, синим - ~ЧС)

Не работает только когда конец линии находится внутри полигона - не стал пока разбираться.



Добавлено через 2 минуты:
Без разницы. До тех пор, пока контур не имеет самопересечений, ничего не меняется. А когда появляются самопересечения, само понятие внутренней области (и заодно полигона) становится неопределенным.
при самопересечениях придётся разбивать полигон на несколько и считать их разными, соответственно

* GrafEdit_0012.rar (702.2 Кб - загружено 280 раз.)
« Последнее редактирование: 28-12-2010 04:46 от Алексей1153 » Записан

Страниц: 1 [2]  Все   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines