|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
12.06.2009, 19:24 | #1 |
Пользователь
Регистрация: 29.03.2009
Сообщений: 22
|
Подскажите идею алгоритма
Произвольный многоугольник без самопересечений и самокасаний ( не обязательно выпуклый) задан координатами своих вершин в порядке обхода по часовой стрелке.
Внутри этого многоугольника находится произвольное количество "дыр" - произвольных многоугольников без самопересечений и самокасаний ( не обязательно выпуклых), заданных координатами своих вершин в порядке обхода против часовой стрелки. Требуется разбить основной многоугольник на минимальное число многоугольников без "дыр". Подскажите, пожалуйста, идею алгоритма.... |
12.06.2009, 21:01 | #2 |
Старожил
Регистрация: 20.04.2008
Сообщений: 5,527
|
1 соединяем внутренние многоугольники непересекающимися линиями в кольцо
2.одно из соединений заменяем на два соединения к вершинам (вершине) внешнего. итого получили ДВА невыпуклых многоугольника
программа — запись алгоритма на языке понятном транслятору
|
12.06.2009, 21:28 | #3 |
Пользователь
Регистрация: 29.03.2009
Сообщений: 22
|
Спасибо evg_m.
А как строить эти непересекающиеся линии? или как узнать порядок, в котором внутренние многоугольники нужно соединять? |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Как воплотить идею? Помогите! | Mitya1 | Свободное общение | 25 | 21.12.2014 14:40 |
Может кто хочет работать на идею? | synet | Свободное общение | 23 | 15.02.2009 14:10 |
подскажите свежую идею для смо | Барби | Помощь студентам | 3 | 30.10.2008 12:03 |
Подкиньте идею, пожайлуста | frankk | Общие вопросы C/C++ | 2 | 08.06.2008 19:15 |
Подскажите,как составить схему алгоритма к этой проге? | drakon803 | Помощь студентам | 4 | 21.12.2007 03:34 |