Компьютерная геометрия и графика. Лекция 2. План занятия: Проверка многоугольника на выпуклость. Нахождение площади произвольного многоугольника. Принадлежность. - презентация

1 Компьютерная геометрия и графика. Лекция 2

2 План занятия: Проверка многоугольника на выпуклость. Нахождение площади произвольного многоугольника. Принадлежность точки выпуклому многоугольнику. Принадлежность точки произвольному многоугольнику.

3 Проверка многоугольника на выпуклость.

4 N 2 N Дано: многоугольник P, он задан двумерным массивом координат вершин. Нулевая и n-ая координаты будут совпадать P[0]=P[N]

5 Методы решения этой задачи: 1. Для любой стороны многоугольника проверяем условие, что все вершины находятся с одной стороны от прямой проходящей через эту сторону, проверяя, например, знак точек при подстановке их в уравнение прямой для этой стороны. 2. Для каждой вершины проверяем, что поворот происходит все время в одном направлении. Для этого находим знак векторного произведения сторон, исходящих из рассматриваемой вершины - если для всех вершин он одинаковый, то многоугольник выпуклый.

6 Воспользуемся вторым методом.

7 i-1i+1iba a X a Y a X a Y a x b = b X b Y b X b Y В переменную Z будем помещать знак векторного произведения двух векторов а и b Формула для вычисления произведения выглядит так:

8 Единственный сложный случай: считается векторное произведение первой и последней стороны многоугольника. Будем считать его отдельно, а все остальные векторные произведения - в цикле. N-1 1Nba

9 Алгоритм: z=(P[N,1]-P[N-1,1])*(P[1,2]-P[N,2])- -(P[N,2]-P[N-1,2])*(P[1,1]-P[N,1]); for (i=1;i<=N;i++) {zi=(P[i,1]-P[i-1,1]*(P[i,2]-P[i+1,2])- -(P[i,2]-P[i-1,2])*(P[i,1]-P[i+1,1]); if (zi*z<0) {НЕВЫПУКЛЫЙ; break} } if (zi*z>0) {ВЫПУКЛЫЙ;}

10 Вычисление площади произвольного многоугольника.

11 Площадь фигуры, которую мы ищем, обозначим S. В начале работы алгоритма S=0 Переходя каждый раз от вершины N к N+1 мы находим площадь криволинейной трапеции, сверху ограниченной отрезком (N, N+1), снизу осью Ох, а слева и справа перпендикулярами опущенными из N и N+1 на ось Ох

12 Рассматриваем отрезок 1-2 За S1 обозначим площадь криволинейной трапеции, которая выделена красным цветом на рисунке

13 Рассматриваем отрезок 2-3 Аналогично вычисляем площадь S2, но ее мы вычитаем из площади

14 Результат выполнения двух шагов алгоритма показан на рисунке: найдена площадь выделенного участка

15 Если вектор выходящий из вершины N к вершине N+1 образует с осью Ох острый угол (то есть векторное произведение положительно), то S=S+SN Если этот вектор образует с Ох тупой угол (то есть векторное произведение отрицательно), то S=S-SN. Сделав N шагов мы получаем площадь данного многоугольника S.

16 Принадлежность точки выпуклому многоугольнику.

17 Дано: выпуклый многоугольник, координаты некоторой точки. Существует несколько способов определения принадлежности точки многоугольнику. Рассмотрим два из них.

18 Первый способ: Соединяем все вершины многоугольника с данной точкой и ищем сумму площадей всех получившихся треугольников. Отдельно считаем площадь самого многоугольника. Если получившиеся площади совпадают, то точка внутри, иначе снаружи.

19 Второй способ: Двигаемся по всем вершинам многоугольника. Если данная точка С по отношению к текущей точке многоугольника все время слева (или все время справа), то точка внутренняя, иначе внешняя. А СВ То есть опять считаем векторное произведение двух векторов АВ х АС. Если знаки разные, то точка снаружи, иначе внутри.

20 Принадлежность точки произвольному многоугольнику.

21 Дано: произвольный многоугольник, координаты некоторой точки.

22 Из данной точки выпускаем луч в произвольном направлении. Считаем, сколько точек пересечения этого луча со сторонами наблюдается. Если число точек четное, то точка снаружи. Если число нечетное, то точка внутри. Но это правило не абсолютно. Существует ряд исключений:

23 Первое исключение: луч может пройти через вершину многоугольника: В таком случае надо проверить дополнительное условие - если соседние вершины В и С этого многоугольника находятся с разных сторон от луча, то считаем А точкой пересечения. (рис 2) - если с одной стороны, то не считаем. (рис 1) В С А В С А рисунок 1 рисунок 2

24 Второе исключение: луч совпадает с одной из сторон: - в случае показанном на (рис 1) считается, что луч имеет только одно пересечение с многоугольником (точка D) - в случае показанном на (рис 2) весь отрезок MN считается одним пересечением (как будто одна вершина) и применяем предыдущее исключение. В С А В С А рисунок 1 рисунок 2 D N M

25 Например, на этом рисунке многоугольник имеет 4 пересечения с лучом А: A

26 Еще один недостаток этого алгоритма: Алгоритм некорректно работает с границами. Следует отдельно проверять принадлежность точки границе многоугольника. В этом случае векторное произведение равно нулю.

27 КОНЕЦ