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

“Вычислительная геометрия” это раздел олимпиадных задач, который считается одним из наиболее сложных. Сложность решения задач на вычислительную геометрию состоит в том, что необходимо обладать знаниями не только за курс средней школы, но и знать основы аналитической геометрии и высшей алгебры. Объем этих знаний достаточно велик, программы получаются большими и сложными для отладки. Необходимо знать и помнить как пишутся процедуры и функции реализующие классические задачи по вычислительной геометрии. И еще одна сложность- большинство вычислений ведутся с вещественными числами с заданной точностью и обычные геометрические понятия приобретают необычные черты. Например если точность вычислений eps=10^-3., то точка считается принадлежащей прямой, если она находится в полосе шириной 2*eps.

то есть, если расстояние

от точки до прямой <=eps,

то точка считается

принадлежащей прямой

То же самое для двух вещественных чисел на числовой прямой. Числа a и b считаются равными если расстояние между ними не превышает eps, то есть abs(a-b)<=eps. Число a больше числа b если a-b>eps.

Для сравнения вещественных чисел можно написать и использовать логические функции, а можно сравнивать их напрямую в тексте программы.

Координаты точек можно хранить в виде двух переменных x и y, уравнение прямой в виде трех чисел a,b,c или использовать свои типы Tpoint и Tline.

Структуры данных:

Const eps: real=0.5e-6; точность вычислений

Type Tpoint=record x,y:real; end; тип –точка с координатами x,y

Type Tline=record A,B,C:real; end; тип - прямая

Реализация операций сравнений:=,<,>,<=,>= имеет вид:

Begin

RealEq:=abs(a-b)<=eps;

End;

Function RealMore(a,b:real):boolean; строго больше

Begin

RealMore:=a-b>eps;

End;

Function RealLess(a,b:real):boolean; строго меньше

Begin

RealLess:=b-a>eps;

End;

Function RealMoreEq(a,b:real):boolean; больше или равно

Begin

RealMoreEq:=a-b>-eps;

End;

Function RealLessEq(a,b:real):boolean; меньше или равно

Begin

RealLessEq:=a-b>-eps;

End;

Function RealMax(a,b:real):real; максимальное из двух

вещественных чисел

Begin

If RealMore(a,b) then RealMax:=a else RealMax:=b;

End;

Function RealMin(a,b:real):real; минимальное из двух

вещественных чисел

Begin

If RealMore(a,b) then RealMin:=b else RealMin:=a;

End;

Функции реализующие элементарные задачи вычислительной геометрии:

Function EqPoint(A,B:Tpoint):boolean; функция совпадение двух точек.

Begin точки совпадают, если их

координаты совпадают

EqPoint:=RealEq(A.x,B.x)and RealEq(A.y,B.y)

End;

Function GetAngle(x,y:real):real; Определяет угол между

направлением на точку (x,y) и

положительным направлением

оси OX.

Var rs,c:real; Величина угла в

промежутке от (– до ].

Begin

If Abs(X) > eps

Then

If (X < 0)and(Y<0) A(x,y)

Then GetAngle :=ArcTan(Y / X) – Pi

Else

If (X < 0)and(Y>=0) 

Then GetAngle :=ArcTan(Y / X) + Pi

Else GetAngle :=ArcTan(Y / X)

Else

If Y > 0

Then GetAngle :=Pi / 2

Else GetAngle :=-Pi / 2;

End;

function Rast2Point(x1,y1,x2,y2:real):real; расстояние между двумя точками

begin

Rast2Point:=sqrt(sqr(x2-x1)+sqr(y2-y1));

end;

function acos:real нахождение арккосинуса угла по значению

косинуса

begin

if RealEq(cosa,0)

then acos:=pi/2

else if cosa<-eps

then acos:=pi+arctan(1/sqr(cosa)-1)

else acos:=arctan(1/sqr(cosa)-1);

end;

Procedure Point2ToLine(A,B:Tpoint;var L:Tline); определение уравнения

прямой по координатам

двух точек

Begin

L.A:=B.y-A.y;

L.B:=A.x-B.x;

L.C:=-(A.x*L.a+A.y*L.b);

End;

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

Логические функции сравнения вещественных чисел.

Площадь ориентированного треугольника, произвольного многоугольника.

Сортировка вершин произвольного многоугольника по полярному углу.

Уравнение прямой проходящей через две точки

общего вида ax+by+c=0

каноническое (x-x1)/(x2-x1)=(y-y1)/(y2-y1)

параметрическое x:=x1+t(x2-x1);

y:=y1+t(y2-y1);

Уравнение прямой перпендикулярной данной ax+by+c=0 и проходящей через данную точку (x0,y0).

Принадлежность точки отрезку

Взаимное расположение двух отрезков (все случаи).

Нахождение точки пересечения отрезка и прямой или выяснения того факта, что они не пересекаются.

Нахождение уравнения касательной к окружности (x-x₀)²+(y-y₀)²=r² , проходящей через данную точку (x₀,y₀).

Является ли точка (x₀,y₀) внутренней для данного произвольного многоугольника.

Формула деления отрезка в данном отношении.

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

Расстояние от точки до отрезка.

Расстояние между двумя параллельными прямыми.

Выяснить, какие стороны выпуклого многоугольника видны из данной точки.

Дано множество точек. Найти его выпуклую оболочку.

Некоторые сведения из аналитической геометрии.

Измерение величин углов

Величины углов измеряются в градусах и радианах.

Опр. Один градус это 1/360 часть полного угла.

Опр. Один радиан это величина центрального угла, опирающегося на дугу, длина которой

р авна радиусу окружности.

1 рад= величине угла AOB

Если взять угол в n раз больше

то и длина дуги будет в n раз

A больше ,т.е. мы имеем прямо-

пропорциональную зависимость между величиной

центрального угла и длиной дуги на которую он опирается.

1 рад - R

360- 2R

Отсюда 1 рад=180/ и 1=  /180

При решении задач вычислительной геометрии градусы всегда переводятся в радианы.

Векторы.

Опр. Вектор – это направленный отрезок или параллельный перенос.

Вектор определяется длиной и направлением.

Для того чтобы найти координаты вектора по координатам начала и конца надо из координат конца вычесть координаты начала.

А(x1,y1) B(x2,y2) AB(x2-x1,y2-y1).

Длина вектора AB=SQRT((x2-x1)* (x2-x1)+(y2-y1)* (y2-y1)).

Опр. Векторы называются коллинеарными, если они лежат на одной прямой или на параллельных прямых.

Условие коллинеарности векторов:

Векторы коллинеарны тогда и только тогда когда их координаты пропорциональны.

a(x1,y1) коллинеарен b(x2,y2) x1/x2=y1/y2.

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

Скалярное произведение векторов через длины векторов

(ab)=a*b*cos(@)

Скалярное произведение векторов через координаты векторов

Если a(x1,y1), b(x2,y2) то (ab)=x1*x2+y1*y2.

Условие перпендикулярности векторов.

Векторы перпендикулярны тогда и только тогда когда их скалярное произведение равно нулю.

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

Опр.Векторное произведение векторов a и b это вектор c удовлетворяющий трем условиям:

1) он перпендикулярен плоскости, в которой лежат вектора a и b.

2) его длина численно равна площади параллелограмма, построенного на

векторах a и b.

Он образует с векторами a и b правую тройку векторов, т.е. если смотреть с конца вектора с, то поворот от a к b будет против часовой стрелки.

Обозначается векторное произведение [ab] или aхb. Модуль вектора c равен absin и численно совпадает с площадью параллелограмма, построенного на этих векторах.

Векторное произведение в координатах в пространстве.

Пусть a(x1,y1,z1), b(x2,y2,z2), тогда

[ab]=(y1*z2-y2*z1)*i+(x2*z1-x1*z2)*j+(x1*y2-x2*y1)*k.

Где i,j,k координатные единичные векторы или орты.

На плоскости [ab]=(x1*y2-x2*y1)*k. (1)

Найдем площадь треугольника, используя векторное произведение.

Пусть дан треугольник ABC. Координаты его вершин A(x1,y1),B(x2,y2), C(x3,y3). Рассмотрим векторы AB(x2-x1,y2-y1) и AC(x3-x1,y3-y1).

По формуле (1) [AB AC]=(( x2-x1)*( y3-y1)- ( x3-x1)*( y2-y1))*k.

Если обозначить координаты векторов АВ (a1,b1) и АС(a2,b2), то векторное произведение на плоскости запишется в виде

[AB AC]=a1*b2-b1*a2. Его вычисление можно оформить в виде функции.

Function VectMul(a1, b1, a2, b2: Longint): Longint;

Begin

VectMul := a1 * b2 - a2 * b1;

End;

Число 0.5*( x2-x1)*( y3-y1)- ( x3-x1)*( y2-y1) имеет положительный знак, если обход треугольника ABC происходит против часовой стрелки, и отрицательный знак, если по часовой, и модуль его равен площади треугольника ABC.

Говорят , что число 0.5*( x2-x1)*( y3-y1)- ( x3-x1)*( y2-y1) есть площадь ориентированного треугольника. Формулу можно записать в другом виде:

S=0.5*(x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2))

Рассмотрим основные элементарные задачи вычислительной геометрии.

1. Общее уравнение прямой

2. Уравнение прямой, проходящей через две точки A(x1,y1) и B(x2,y2)

3. Найти уравнение прямой, зная координаты точки на прямой и координаты вектора , перпендикулярного этой прямой

4. Уравнение прямой проходящей через точку М(х0у0) перпендикулярной прямой ax+by+c=0

5. Уравнение прямой проходящей через точку M(x0,y0) параллельно вектору t(m,n)

6. Параметрическое уравнение прямой

7. Полярный угол точки

8. Угол между векторами

9. Площадь треугольника

10. Найти уравнение прямой, параллельной данной и отстоящей от нее на заданное расстояние

11. Принадлежность точки отрезку

12. Принадлежность точки прямой

13. Принадлежность точки лучу

14. Положение двух точек и прямой

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

16. Расстояние от точки до луча

17. Расстояние от точки до отрезка

18. Замки

19. Пересечение двух отрезков

20. Пересечение двух прямых

21. Биссектриса угла

22. Касательная к окружности

23. Окружность и прямая

24. Две окружности

25. Длина дуги

26. Параллельный перенос на вектор AB

27. Поворот вокруг точки на угол 

28. Центральная симметрия

29. Осевая симметрия относительно прямой ax+by+c=0

30. Гомотетия

31. Симметричная точка

32. Неизвестная вершина квадрата

33. Треугольник симметричный относительно точки

34. Треугольник симметричный относительно прямой

35. Калейдоскоп

36. Заполнение экрана

37. Восстановление координат вершин треугольника

38. Задание множества точек на плоскости неравенствами

39. Множество точек

40. Продолжение отрезка

41. Куда идем мы с Пятачком?

42. Ломаная линия

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

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

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

46. Прямая и окружность

47. Соединение точек простой замкнутой ломаной

48. Нахождение длины общей касательной для двух окружностей

49. Тропинка

50. Повороты

51. Точка и треугольник

52. Выпуклость многоугольника

53. Площадь произвольного многоугольника

54. Деление отрезка в данном отношении

55. Разделить площадь данного треугольника АВС в отношении равном k

56. Окружность и треугольник

57. Коза на привязи

58. Анамейтронная звезда

59. Кролик и бобер

60. Остров

61. Целые точки

62. Правильный многоугольник

63. Кратчайшее расстояние 1

64. Кратчайшее расстояние 2

65. Нахождение точки Штейнера аналитическим методом

66. Станция

67. Нахождение точки Штейнера методом скорейшего спуска

68. Теорема Альхазена

69. Сад

70. Лента из трапеций

71. Голова на плечах

72. Метеоритный дождь

73. Окружности

74. Индейские бои

75. Фонарики

1. Общее уравнение прямой

Общее уравнение прямой имеет вид a*x+b*y+c=0, где a,b – координаты вектора перпендикулярного прямой.

n(a,b)

2. Уравнение прямой, проходящей через две точки A(x1,y1) и B(x2,y2)

Возьмем на прямой произвольную точку С

В(х2,у2)

С(х,у)

А(х1,у1)

Находим координаты векторов

АС(х-х1,у-у1);

АВ(x2-x1,y2-y1);

Т ак как AC AB, то их координаты пропорциональны

(x-x1)/(x2-x1)=(y-y1)/(y2-y1); т.е. (x-x1)*(y2-y1)=(y-y1)*(x2-x1);

(y2-y1)*x+(x1-x2)*y +x1*y2-y1*x2 =0

Следовательно ax+by+c=0 искомое уравнение прямой и

a=y2-y1

b=x1-x2

c=x1*y2-y1*x2

Входные данные:

Четыре целых числа — координаты двух различных точек .

Выходные данные:

Три целых числа — коэффициенты А, В и С общего уравнения этой прямой.

Пример

Input.txt	Output.txt
12 3 1	-1 -2 5

Program urprjmoi;

Var X1, Y1, X2, Y2,A,B,C: Longint;

Begin

assign(input, 'input.txt'); reset(input);

assign(output, 'output.txt'); rewrite(output);

Read(X1, Y1, X2, Y2);

A:= Y2 - Y1;

B:= X1 - X2;

C:= Y1*X2 - X1*Y2;

Write(A, ' ', B, ' ', C);

Close(Input);

Close(Output);

End.