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

n="center">Принадлежность точки полигону 
(общий случай) 

• Метод  углов:
• если из точки провести векторы во все вершины полигона и найти сумму углов между соседними векторами (с учетом знака), то для внутренней точки сумма получится равной 2, а для внешней – 0.
• Метод лучей:
• Любой луч, проведенный из внутренней точки, будет иметь нечетное число пересечений с границами полигона, а из внешней – четное.
• Все дело портят особые случаи: луч проходит через вершину, луч совпадает со стороной. Приходится проверять положение соседних вершин – по одну сторону луча или по разные?
• Метод углов надежнее.

10  

{Pⁱ} – исходный набор из N точек;

W  – стек точек.

Выбрать самую нижнюю-правую точку P⁰.

Отсортировать остальные точки по 
возрастанию угла (на самом деле, 
вместо угла удобнее проверять условие 
Left(Pⁱ, P⁰, P^j).  
Если несколько точек с одинаковыми 
углами, оставить только самую дальнюю.

Push(P⁰);

Push(P¹); 
i := 2;

while  i < N do begin 
  PT1 := точка в верхушке стека; 
PT2 := вторая сверху точка в стеке; 
  if Left(P[i], PT2, PT1) then begin  
    Push(P[i]); 
    i := i + 1; 
  end 
  else

     Pop(PT1); {Выбрасываем точку} 
end; 
{В стеке остались точки выпуклой

   оболочки} 

Выпуклая оболочка множества точек: 
метод Грэхема 

T(n) = O(n·log(n)) 

P_⁴ 

P_³ 

P_² 

P_¹ 

P_⁰ 

P_⁵ 

P_⁶ 

P_⁷ 

P_^?

11  

{Pⁱ} – исходный набор из N точек;

W  – стек точек.

Отсортировать все точки по 
возрастанию x, а при равенстве x по 
возрастанию y.  
{Для простоты рассмотрим только точки  
сверху (Left(Pⁱ, P⁰, P^n-1) = True)}

Push(P⁰);

Push(P¹); 
i := 2;

while  i < N do begin 
  PT1 := точка в верхушке стека; 
PT2 := вторая сверху точка в стеке; 
  if Right(Pⁱ, PT2, PT1) then begin  
    Push(Pⁱ); 
    i := i + 1; 
  end 
  else

     Pop(PT1); {Выбрасываем точку} 
end; 
{В стеке точки верхней половины 
выпуклой оболочки; нижняя половина 
находится аналогично, затем они  
сливаются} 

Выпуклая оболочка множества точек: 
метод Эндрю 

T(n) = O(n·log(n)) 

P_² 

P_⁵ 

P_⁸ 

P_¹⁰ 

P_⁶ 

P_⁴ 

P_¹ 

P_⁰ 

P_³ 

P_⁷ 

P_⁹

12  

Мелкие советы 

• Не  верьте в равенство вещественных  чисел.
• cos²(x) + sin²(x) = 1.0 ? Очень сомнительно...
• abs(cos²(x) + sin²(x) – 1.0)   ? Возможно, при правильном выборе .
• Забудьте формулу Герона. Для очень узких треугольников она дает нулевую площадь. Пользуйтесь векторным произведением сторон.
• Рассматривайте все случаи взаимного расположения фигур.
• Два отрезка могут лежать, например, так:

 
 

• Два круга:

 
 
 
 
 

• Обращайте внимание  на знак результата, он может иметь важный смысл (например, знак площади треугольника).