|
Dale
|
 |
« Ответ #30 : 27-12-2010 09:44 » |
|
Нарисуйте, пожалуйста. Непонятно, какое отношение два треугольника имеют к замкнутому полигону.
|
|
|
|
|
Записан
|
Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.
Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard
Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
|
|
|
|
Kivals
|
|
« Ответ #31 : 27-12-2010 09:45 » |
|
sss, просто попробуй нарисовать "замкнутый односвязный полигон" одной линией. Неужели будут сомнения в том по часовой стрелке он рисовался или против? Dale,  )
|
|
|
|
|
Записан
|
|
|
|
sss
Специалист
 Offline
|
|
« Ответ #32 : 27-12-2010 09:46 » |
|
|
|
|
|
|
Записан
|
while (8==8)
|
|
|
|
Dale
|
|
« Ответ #33 : 27-12-2010 09:49 » |
|
При обходе вдоль всего контура внутренняя область полигона остается слева. Вывод: обход против часовой стрелки, несмотря на то, что в точках 2 и 5 углы внутренние.
|
|
|
|
|
Записан
|
Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.
Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard
Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
|
|
|
|
Kivals
|
|
« Ответ #34 : 27-12-2010 09:50 » |
|
Для всего полигона обход против часововой, т.к. вся площадь полигона всегда находится слева от контура. А вот если воспользоваться предложеным методом оптимизации "по первым трем точкам" - то он даст неверный результат.
|
|
|
|
|
Записан
|
|
|
|
|
Dale
|
|
« Ответ #35 : 27-12-2010 09:52 » |
|
А вот если воспользоваться предложеным методом оптимизации "по первым трем точкам" - то он даст неверный результат. Я бы даже уточнил - по любому собственному подмножеству множества вершин контура результат может быть неверным. Как повезет. |
|
|
|
|
Записан
|
Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.
Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard
Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
|
|
|
sss
Специалист
Offline
|
|
« Ответ #36 : 27-12-2010 09:54 » |
|
А если точка 2 окажется левее точки 5?
|
|
|
|
|
Записан
|
while (8==8)
|
|
|
|
Dale
|
|
« Ответ #37 : 27-12-2010 10:01 »  |
|
Без разницы. До тех пор, пока контур не имеет самопересечений, ничего не меняется. А когда появляются самопересечения, само понятие внутренней области (и заодно полигона) становится неопределенным.
|
|
|
|
|
Записан
|
Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.
Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard
Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
|
|
|
|
Dale
|
|
« Ответ #38 : 27-12-2010 10:04 » |
|
А вот если воспользоваться предложеным методом оптимизации "по первым трем точкам" - то он даст неверный результат. Я бы даже уточнил - по любому собственному подмножеству множества вершин контура результат может быть неверным. Как повезет. Вот попытался проиллюстрировать эту мысль наглядно: Единственная точка N полностью определяет направление контура в целом. |
 Poly.png (3.55 Кб - загружено 1971 раз.)
|
|
|
Записан
|
Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.
Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard
Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
|
|
|
sss
Специалист
Offline
|
|
« Ответ #39 : 27-12-2010 10:11 » |
|
Я сдаюсь.. Если выбор будет сделан на основе отнимем площадь треугольников по часовой и против - у кого больше тот и победил... Только один вопрос - вот вы нашли направление обхода для не выпуклого полигона - и как его применить? Для расчетов нормалей и биссектрис не годится..
|
|
|
|
|
Записан
|
while (8==8)
|
|
|
Dimka
Деятель
Команда клуба
Offline
Пол: 
|
|
« Ответ #40 : 27-12-2010 10:16 » |
|
Dale, если я правильно понял, то только для выпуклых многоугольников.
|
|
|
|
|
Записан
|
Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
|
|
|
|
Dale
|
|
« Ответ #41 : 27-12-2010 10:18 » |
|
Только один вопрос - вот вы нашли направление обхода для не выпуклого полигона - и как его применить? Для расчетов нормалей и биссектрис не годится.. Например, я когда-то решал задачу заливки внутренней области полигона прямоугольниками. Это нужно для проектирования фотошаблонов при производстве микросхем. Важно знать, слева или справа от данного отрезка контура находится внутренняя область. А для этого необходимо знать направление обхода. Добавлено через 34 секунды:Dale, если я правильно понял, то только для выпуклых многоугольников. Что именно? Приведенная формула? |
|
|
|
« Последнее редактирование: 27-12-2010 10:19 от Dale »
|
Записан
|
Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.
Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard
Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
|
|
|
Dimka
Деятель
Команда клуба
Offline
Пол:
|
|
« Ответ #42 : 27-12-2010 12:27 » |
|
Что именно? Приведенная формула? Нет, метод определения по трём вершинам. При этом знание о выпуклости должно быть априорным. |
|
|
|
|
Записан
|
Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
|
|
|
sss
Специалист
Offline
|
|
« Ответ #43 : 27-12-2010 13:02 » |
|
...слева или справа от данного отрезка контура находится внутренняя область. А для этого необходимо знать направление обхода.
Так вот, тогда, в месте локального треугольника, имеющего направление отличное от вычисленного общего, вы получите ошибку в определении направления. |
|
|
|
« Последнее редактирование: 27-12-2010 13:29 от sss »
|
Записан
|
while (8==8)
|
|
|
|
Dale
|
|
« Ответ #44 : 27-12-2010 13:35 » |
|
Так вот, тогда, в месте локального треугольника, имеющего направление отличное от вычисленного общего, вы получите ошибку в определении направления. Можно иллюстрацию? Нет, метод определения по трём вершинам. При этом знание о выпуклости должно быть априорным. Да, в таком случае можно и по трем, если мы точно знаем, что в каждой точке поворот производится в одном направлении. Тогда остальные точки не дадут нам никакой новой информации. Но это слишком частный случай. |
|
|
|
|
Записан
|
Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.
Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard
Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
|
|
|
sss
Специалист
Offline
|
|
« Ответ #45 : 28-12-2010 02:24 » |
|
Посидел, посчитал площадь так и сяк. Признаю, для невыпуклых полигонов, был не прав . Пошел переделывать (добавлять) код..
|
|
|
|
|
Записан
|
while (8==8)
|
|
|
Алексей++
глобальный и пушистый
Глобальный модератор
Offline
Сообщений: 13
|
|
« Ответ #46 : 28-12-2010 04:44 » |
|
sss, полигон у меня может быть не то чтобы даже выпуклым, а совсем впуклым )) Собственно, вот для чего делалось - в аттаче экзешник. В меню кнопка "отсечение линии". Отрезок разбивается полигоном на кусочки, и какие отрезки будут лежать внутри полигона - зависит от направления обхода (красным окрасятся, когда полигон ЧС, синим - ~ЧС) Не работает только когда конец линии находится внутри полигона - не стал пока разбираться. Добавлено через 2 минуты:Без разницы. До тех пор, пока контур не имеет самопересечений, ничего не меняется. А когда появляются самопересечения, само понятие внутренней области (и заодно полигона) становится неопределенным.
при самопересечениях придётся разбивать полигон на несколько и считать их разными, соответственно
|
|
|
« Последнее редактирование: 28-12-2010 04:46 от Алексей1153 »
|
Записан
|
|
|
|
|
