Подскажите идею алгоритма - Помощь студентам

Ok-ei · 12.06.2009, 19:24

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

evg_m · 12.06.2009, 21:01

1 соединяем внутренние многоугольники непересекающимися линиями в кольцо
2.одно из соединений заменяем на два соединения к вершинам (вершине) внешнего.

итого получили ДВА невыпуклых многоугольника

Ok-ei · 12.06.2009, 21:28

Спасибо evg_m.
А как строить эти непересекающиеся линии? или как узнать порядок, в котором внутренние многоугольники нужно соединять?

12.06.2009, 19:24	#1
Ok-ei Пользователь Регистрация: 29.03.2009 Сообщений: 22	Подскажите идею алгоритма Произвольный многоугольник без самопересечений и самокасаний ( не обязательно выпуклый) задан координатами своих вершин в порядке обхода по часовой стрелке. Внутри этого многоугольника находится произвольное количество "дыр" - произвольных многоугольников без самопересечений и самокасаний ( не обязательно выпуклых), заданных координатами своих вершин в порядке обхода против часовой стрелки. Требуется разбить основной многоугольник на минимальное число многоугольников без "дыр". Подскажите, пожалуйста, идею алгоритма....

12.06.2009, 21:01	#2
evg_m Старожил Регистрация: 20.04.2008 Сообщений: 5,543	1 соединяем внутренние многоугольники непересекающимися линиями в кольцо 2.одно из соединений заменяем на два соединения к вершинам (вершине) внешнего. итого получили ДВА невыпуклых многоугольника программа — запись алгоритма на языке понятном транслятору

Опции темы	Поиск в этой теме
Версия для печати Отправить по электронной почте	Поиск в этой теме: Расширенный поиск

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
Как воплотить идею? Помогите!	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

12.06.2009, 21:28	#3
Ok-ei Пользователь Регистрация: 29.03.2009 Сообщений: 22	Спасибо evg_m. А как строить эти непересекающиеся линии? или как узнать порядок, в котором внутренние многоугольники нужно соединять?