Указание. Решение этой задачи описано в книге Л. Аммерала [1]. Сначала выбирается порядок обхода вершин P0 , P1 ,… , P n = P 0 , при котором многоугольник находится слева от отрезков границы. Затем рассматриваются треугольники Pi-1Pi Pi+1 , ориентированные против часовой стрелки. Среди них выбирается треугольник P i-1P iPi+1, для которого длина отрезка Pi-1Pi+1 минимальна. Далее производится переход к разбиению оставшегося многоугольника P0P1…Pi-1 Pi+1…Pn-1 на треугольники. Реализация алгоритма приведена в [1, с. 60-65].
4.
(Теорема о картинной галерее.) Пусть простой многоугольник задан
вершинами (P0 ,P1
,…,Pn-1 ) . Согласно
теореме Жордана замкнутая ломаная, состоящая из отрезков P0P1 , P1P2 , …, Pn-1P0 , разбивает плоскость на две
связные области. Одна из этих областей ограничена. Точки, принадлежащие этой
ограниченной области, вместе с точками замкнутой ломаной, называются точкам
многоугольника. Точка N многоугольника
называется видимой из точки M, если
отрезок MN состоит из
точек многоугольника. Доказать, что существуют 
точек
многоугольника, из которых видны все точки многоугольника.
Указание. Доказательство
приведено в книге Рурка [18]. Сначала производится триангуляция простого
многоугольника. Рассматривается граф, вершинами которого служат точки P0 , P1
, … , P n-1
, а ребрами – стороны треугольников, разбивающих многоугольник. Легко
видеть, что вершины этого графа можно раскрасить в три цвета, таким образом,
что любые две вершины, имеющие общее ребро, будут раскрашены в различные цвета.
Далее применяется принцип k карманов,
согласно котрому, если n предметов
положить в k ящиков, то в одном
из ящиков будет не более 
предметов. Из этого
принципа вытекает, что существует цвет, в который будут раскрашены не более,
чем вершин. Эти вершины будут составлять
множество точек, из которых видны все точки многоугольника.
5. Написать программу, строящую выпуклую оболочку множества точек методом Эндрю.
1. Аммерал Л. Принципы программирования в машинной графике. – М.: «Сол Систем», 1992. – 224с.
2. Аммерал Л. Машинная графика на персональных компьютерах. – М.: «Сол Систем», 1992, – 232с.
3. Аммерал Л. Интерактивная трехмерная машинная графика. - М.: «Сол Систем», 1992, – 317 с.
4. Архангельский А.Я. C++ Builder 6. Справочное пособие. Книга 1. Язык C++. – М.: Бином-Пресс, 2004. – 544 с.
5. Архангельский А.Я. C++ Builder 6. Справочное пособие. Книга 2. Классы и компоненты. – М.: Бином-Пресс, 2004. - 528 с.
6. Архангельский А.Я. Программирование в C++ Builder 6. – М.: ЗАО «Издательство БИНОМ», 2002. – 1152 с.
7. Дейкстра Э. Дисциплина программирования. – М.: Мир, 1978. – 275 с.
8. Ласло М. Вычислительная геометрия и компьютерная графика на Си++. – М.: Бином, 1997. – 304с.
9. Мусин О.Р. Эффективные алгоритмы для теста принадлежности точки многоугольнику и многограннику // Программирование. 1991. №4. С. 72–81.
10. Никулин Е.А. Компьютерная геометрия и алгоритмы машинной графики. – СПб.: БХВ-Петербург, 2003. – 560 с.
11. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. – М.: Мир, 1989. – 478 с.
12. Роджерс Д. Алгоритмические основы машинной графики. – М.: Мир, 1989. – 503 с.
13. Шамис В.А. Borland C++ Bulider 6. Для профессионалов. – СПб.: Питер, 2004. – 798 с.
14. Шикин Е.В., Боресков А.В. Компьютерная графика. Динамика, реалистические изображения. – М.: «ДИАЛОГ-МИФИ», 1995. – 288 с.
15. Шикин Е.В., Боресков А.В. Компьютерная графика. Полигональные модели. – М.: «ДИАЛОГ-МИФИ», 2000. – 464 с.
16. de Berg M., Kreveld M., Overmars M., Schwarzkopf O. Computer Geometry: Algorithms and Applications . — Berlin, Heidelberg, New York: Springer, 2000. — 377 p.
17. Handbook of Discrete and Computional Geometry /ed. J.E. Goodman and J. O’Rourke. — New York: CRC Press LLC, 1997. — 955 p.
18. O’Rourke J. Computational Gemetry in C. – Cambridge University Press, 1998. – 350p.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.