Лабораторный практикум по информатике



бет72/83
Дата06.01.2022
өлшемі1.1 Mb.
#15674
түріПрактикум
1   ...   68   69   70   71   72   73   74   75   ...   83
Задача 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)(x3x2)).

Значение величины 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   ...   68   69   70   71   72   73   74   75   ...   83




©emirsaba.org 2022
әкімшілігінің қараңыз

    Басты бет