Вычислительная геометрия

План лекции: 

автор: С.Н. Дроздов 

Вычислительная геометрия 

• Векторы
• Прямые
• Отрезки
• Полигоны
• Выпуклые оболочки

2  

Векторы и операции над ними 

• Векторы:

    r  = (r.x, r.y);

    r.x  = x_¹ – x_⁰, r.y = y_¹ – y_⁰;

    q  = (q.x, q.y);

    q.x  = x_² – x_⁰, q.y = y_² – y_⁰; 

• Скалярное  произведение:

r·q = r.x·q.x + r.y·q.y ;

Длина вектора: |r| = Sqrt(r·r);

Вид угла между  векторами:

r·q > 0  – острый;

r·q = 0  – прямой;

r·q < 0  – тупой.

• Векторное произведение:

rq = (x_^ry_^q – x_^qy_^r)z;

(z – единичный вектор оси Z).

Площадь треугольника  со сторонами r и q: S = ½ |rq|.

Знак векторного  произведения указывает направление  поворота от r к q.

• Угол между векторами:

sin() = |rq| / (|r|·|q|) – со знаком!

cos() = |r·q| / (|r|·|q|)

3  

Прямые 

• Прямая определяется  двумя точками: 
   P = (x1, y1), Q = (x2, y2).
• Уравнение прямой:

          dx·(y – y1) = dy·(x – x1),

          где dx = x2 – x1, dy = y2 – y1 
или  Ax + By – C = 0 
 где A = dy, B = – dx, C = dy·x1 – dx·y1

• Удобно использовать нормальный вектор n – вектор единичной длины, перпендикулярный к прямой.

    n = (–dy / dxy, dx / dxy)

где dxy = sqrt(dx² + dy²)

• Тогда уравнение прямой:

    R · n = w

    где

R = (x, y) – радиус-вектор текущей точки,

w = (x2·y1 – x1·y2). 

dxy = sqrt(dx² + dy²) 

P (x1, y1) 

Q (x2, y2) 

dx 

dy 

n 

dxy

4  

Прямые (продолжение) 

• Еще одна  удобная форма – параметрическое задание прямой:

x = x1 +  dx·t

y = y1 +  dy·t

• Расстояние от точки до прямой:

d = |R · n – w|

или

d = |dx·(y0 – y1) - dy·(x0 – x1)|

• Положение точки относительно прямой: если задано направление прямой от P к Q, то можно ввести предикат, означающий, что точка R лежит слева от прямой:

    Left(R, P, Q) = (R · n > w)

или 

    dx·(y0 – y1) - dy·(x0 – x1) > 0

Аналогично

    Right(R, P, Q) = (R · n < w)

или 

    dx·(y0 – y1) - dy·(x0 – x1) < 0 

P (x1, y1) 

Q (x2, y2) 

dx 

dy 

n 

d 

d 

Left 

Right 

R (x0, y0)

5  

Взаимное расположение прямых 

• A¹x + B¹y – C¹ = 0 
  A²x + B²y – C² = 0
• Две прямые на плоскости могут:
• пересекаться;
• быть параллельны;
• совпадать.
• Условие пересечения:

    A¹B² – A²B¹  0

• Координаты пересечения равны:

x = (A¹C² – C¹A²) / (A¹B² –  A²B¹)

y = (C¹B² – B¹C²) / (A¹B² –  A²B¹)

• Уравнение перпендикуляра к прямой A¹x + B¹x – C¹ = 0 из точки 
  R (x0, y0):

    B¹x – A¹y + (A¹y0 – B¹x0) = 0 
 
 

P (x1, y1) 

Q (x2, y2) 

dx 

dy 

n 

R (x0, y0)

6  

Отрезки 

• Отрезок определяется  уравнением прямой и условием:

    min(x1,  x2)  x  max(x1, x2)

• а для вертикальной прямой

    min(y1, y2)  y  max(y1, y2)

• В параметрической форме проще:

    0  t  1

• Для определения расстояния от точки до отрезка надо опустить перпендикуляр из этой точки на прямую и проверить, попадает ли проекция точки на отрезок. Соответственно, расстояние до отрезка равно либо расстоянию до прямой, либо расстоянию до ближайшего конца отрезка.

 

dxy = sqrt(dx² + dy²) 

P (x1, y1) 

Q (x2, y2) 

dx 

dy 

dxy 

R¹ 

R²

7  

Полигоны (многоугольники) 

• Площадь  полигона:
• выбрать произвольную точку (например, начало координат) и провести из нее векторы во все вершины;
• суммировать площади всех n треугольников, образованных двумя векторами и стороной, с учетом знака векторного произведения.

    Это  правильно работает и в случае  невыпуклого полигона.

    В  примере: знаки площади двух заштрихованных треугольников противоположные. 

• Проверка  выпуклости полигона:
• при обходе границы полигона знак векторного произведения соседних сторон должен быть одним и тем же.
• В примере: знаки q¹ q² и q¹ q² противоположные.

 

q¹ 

q² 

q³

8  

Полигоны (продолжение) 

• Направление  обхода границы:

сумма углов поворота  при обходе границы может быть  равна:

    2 - внутренняя область полигона слева от контура обхода;

    - 2 - внутренняя область полигона справа от контура обхода. 

• Принадлежность  точки выпуклому полигону:
• при обходе границы полигона точка должна быть либо всегда слева, либо всегда справа.

9