|
|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail | |||||||
| Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
||||
 |
|
|
Опции темы | Поиск в этой теме |
12.06.2009, 19:24
|
#1 |
|
Пользователь
Регистрация: 29.03.2009
Сообщений: 22
|
Подскажите идею алгоритма
Произвольный многоугольник без самопересечений и самокасаний ( не обязательно выпуклый) задан координатами своих вершин в порядке обхода по часовой стрелке.
Внутри этого многоугольника находится произвольное количество "дыр" - произвольных многоугольников без самопересечений и самокасаний ( не обязательно выпуклых), заданных координатами своих вершин в порядке обхода против часовой стрелки. Требуется разбить основной многоугольник на минимальное число многоугольников без "дыр". Подскажите, пожалуйста, идею алгоритма.... |
|
|
|
12.06.2009, 21:01
|
#2 |
|
Старожил
Регистрация: 20.04.2008
Сообщений: 5,526
|
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 |
