Лабораторный практикум по информатике
жүктеу/скачать 1,1 Mb.
|
| Задача 3. «Заяц» [3]. Недалеко от города Х находится зоосад. Здешний житель, заяц, хаотично прыгая, оставил след в виде замкну- той самопересекающейся ломаной, охватывающей территорию его владения. Найти площадь минимального по площади выпуклого много- угольника, описанного вокруг этой территории.
В данной задаче необходимо не только найти выпуклую оболочку множества точек, но и вычислить площадь выпуклого многоугольника с заданным набором вершин. Исходные данные: N – количество вершин выпуклого многоуголь- ника, (xi, yi) – координаты вершин, i = 1, 2, …, N. Требуется определить площадь выпуклого N-угольника. Площадь N-угольника может быть вычислена как сумма площадей треугольников, из которых N-угольник составлен. Для нахождения пло- щади треугольника используем векторное произведение. Длина векторно- го произведения векторов, как известно, равна удвоенной площади тре- угольника, построенного на этих векторах. Пусть вершины треугольника расположены в точках A = (x1, y1), B = (x2, y2), C = (x3, y3). Совместим начало координат с первой точкой. Векторное произведение равно [AB × AC] = i x2 x1 x3 x1 j k y2 y1 0 , y3 y1 0 следовательно, площадь треугольника равна SABC = 1/2 ((x2 – x1) (y3 – y2) – (y2 – y1)(x3 – x2)). Значение величины SABC может быть как положительным, так и от- рицательным числом, так как оно зависит от взаимной ориентации век- торов AB и AC, поэтому говорят, что площадь ориентированная. Для нахождения площади N-угольника последний требуется раз- бить на треугольники и найти сумму ориентированных площадей этих треугольников. Разбиение N-угольника на треугольники можно провес- ти так: зафиксировать одну из вершин N-угольника, например первую, A1 = (x1, y1) и рассматривать все треугольники A1Ai Ai+1, i = 2, 3,…, N – 1. А2 А3 А1 А5 А Рис. 16.4. Иллюстрация к задаче «Заяц» Заметим, что аналогичным способом можно находить площадь произвольного многоугольника. Рис. 16.5. Нахождение площади произвольного многоугольника Использование свойства ориентации площади треугольника, вы- численной по векторному произведению, позволяет определить, являет- ся ли заданный многоугольник выпуклым. Для выпуклого многоуголь- ника все треугольники, образованные тройками соседних вершин в порядке их обхода, имеют одну ориентацию. Поэтому проверка много- угольника на выпуклость может быть проведена с помощью последова- тельного сравнения знаков векторных произведений для всех пар сосед- них сторон многоугольника. жүктеу/скачать 1,1 Mb. Достарыңызбен бөлісу:
|