Лекция 6-7-8 Элементы вычислительной геометрии на плоскости.

В этом разделе будут рассмотрены различные геометрические объекты, способы их задания и алгоритмы для работы с ними.

Прямая на плоскости

Уравнение прямой, проходящей, через две точки. Получается из подобия треугольников.

Параметрическое уравнение , где А – произвольная точка на прямой, L – направляющий вектор. Для отрезка AB, L=(B-A) 0<=k<=1. Для луча А –начало луча, k>=0.

Общее уравнение прямой a*Px+b*Py+d=0 или или . , - расстояние до начала координат. Здесь обозначение - вектор, перпендикулярный данному. Обычно вектор нормали нормализуют, но это не обязательно.

Расстояния от точки до прямой , может быть как положительным, так и отрицательным в зависимости от того, с какой стороны от прямой лежит точка. Если вектор N не нормализован, нужно разделить на |N|.

Пересечение двух прямых и требует решения системы линейных уравнений , , откуда ,

Операция , называется perp-dot-product (т.е. скалярное произведение (dot-product) с перпендикулятным вектором). Кстати, векторное произведение называется cross-product. Величина равна , в отличие от скалярного произведения .

Если нужно найти пересечение двух отрезков, то после нахождения k₁ и k₂ нужно проверить их попадание в интервал [0,1].

Окружность

Общее уравнение

Параметрическое , 0<=<2

Проверка попадания точки в окружность

Проверка пересечения двух окружностей , здесь может быть случай, когда одна окружность лежит внутри другой, он отсеивается проверкой , если считать, что R₁< R₂.

Пересечение окружности с прямой . , отсюда квадратное уравнение

Если нужно определить сам факт пересечение с прямой, то можно просто рассчитать расстояние от центра окружности до прямой и его модуль должен быть меньше радиуса .

Полигон на плоскости

Состоит из набора вершин Сi соединенных отрезками. Отрезки объединены в замкнутые непересекающиеся контура. Это выполняется при двух условиях: каждой вершине соответствуют ровно два отрезка, и никакая пара отрезков не пересекается. Отрезки считаются направленными, их направление выбирают таким образом, что внутренняя часть полигона всегда лежит с одной стороны от отрезков (обычно с отрицательной). Так как полигон может быть как одноконтурным, так и многоконтурным (один внешний контур и несколько внутренних), то направление отрезков во внутренних контурах получается противоположным направлению во внешнем контуре. Определить, с какой стороны от контура лежит полигон можно, посчитав сумму углов между соседними ребрами , где , размер угол можно получить из косинуса, а знак взять из синуса. Если S>0 полигон слева, иначе – справа.

Из общего понятия полигон следует выделить класс выпуклых полигонов. Выпуклый полигон – полигон, все точки которого лежат с одной стороны от образующих ребра прямых. Для того, чтобы проверить полигон на выпуклость нужно чтобы для любого i имели одинаковый знак.

Определение положения точки относительно полигона.

Для решения этой задачи из точки выпускается луч, если этот луч пересекает полигон четное количество раз – точка лежит снаружи, если нечетное – внутри. Алгоритм может работать некорректно, если одна или обе вершины отрезков лежат на луче, поэтому нужно его несколько модифицировать. Во-первых, следует не проверять горизонтальные отрезки на пересечение (т.о. избавляемся от случаев, когда обе вершины лежат на луче), во вторых, случай, когда одна из вершин лежит на луче, следует засчитывать только если это верхняя вершина отрезка.

Если полигон выпуклый, то можно воспользоваться этим тем свойством, что все его лежат с одной стороны от ребер, следовательно если точка внутри, то и она должна лежать с одной стороны от всех ребер. Т.е. должна иметь одинаковый знак для всех i.

Вычисление площади полигона.

Площадь треугольника , площадь имеет знак, который зависит от положения точки A относительно ребра BC.

Площадь полигона (внутри одного контура) это сумма площадей всех треугольников образованных всеми ребрами полигона и началом координат

Если есть внутренние контуры, то их площадь нужно прибавить к площади внешнего контура.

Построение выпуклой оболочки.

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

1. Выбираем самую левую точку в наборе, она, очевидно, будет принадлежать выпуклой оболочке. Обозначим ее С₀ , в начале она будет текущей точкой С_i.

2. Берем первую точку набора и делаем ее временно следующей точкой оболочки С_i+1 .

3. Проверяем для остальных точек С_k набора условие , если оно не выполняется, то заменяем следующую точку оболочки С_i+1 на С_k и проверяем дальше.

4. Если все условия выполнены, значит, найдена корректная точка оболочки. Если это точка С₀ , завершаем работу, иначе делаем найденную точку текущей и ищем следующую.