Рассмотрим простую на первый взгляд задачу о треугольнике:
Даны координаты трех точек. Определить, лежит ли центр координат внутри треугольника?
Как определить, что точка координатами (x,y) лежит внутри треугольника? Для этого можно рассмотреть два варианта:
1. Если найти уравнения прямых (которые образуют стороны треугольника) по двум вершинам (x1,y1) и (x2,y2): Ax+By+C=0 или (x-x2)/(x1-x2)=(y-y2)/(y1-y2) или (x-x2)*(y1-y2)-(y-y2)*(x1-x2)=0 (тоже самое, но без деления), то, подставив в это уравнение координаты точки, получим либо положительное, либо отрицательное значение (равно нулю будет, если точка лежит на прямой). Методом подстановки можно определить, какой знак будет, если точка внутри треугольника.
Этот вариант немного сложнее из-за дополнительного поиска уравнения прямой (что не всегда тревиально) или может возникнуть деление на ноль. Но, используя третье уравнение без деления, можно легко применить этот вариант.
2. Если точка лежит внутри, то проверяем на равенство площади треугольника и суммы маленьких треугольников, образованных с помощью этой точки. Возникает вопрос: как найти площадь треугольника по координатам его вершин? Обычно школьник знают формулу S=a*h/2 или по формуле Геррона S=sqrt(p*(p-a)*(p-b)*(p-c)), где p=(a+b+c)/2. В этом случае приходится каждый раз искать длину стороны треугольника по формуле a=sqrt((x1-x2)^2+(y1-y2)^2), что дает погрешность в вычислениях при дальнейших сравнениях.
Предлагаю самим вывести формулу для площади треугольника, используя формулу площади прямоугольника и формулу площади прямоугольного треугольника S=a*b/2, заключив треугольник в квадрат:
Тогда площадь треугольника будет равна раности площади прямоугольника и сумме площадей маленьких треугольников:
S=(x2-x1)*(y3-y2)-((x2-x1)*(y1-y2)+(x2-x3)*(y3-y2)+(x3-x1)*(y3-y1))/2.
Если треугольник не существует, то площадь=0.
Для вычисления треугольников от центра координат (0,0) достаточно подставить в эту же формулу нули в первом случае - вместо (x2,y2), во втором - вместо (x1,y1), и в третьев - вместо (x3,y3).
Даны координаты трех точек. Определить, лежит ли центр координат внутри треугольника?
Как определить, что точка координатами (x,y) лежит внутри треугольника? Для этого можно рассмотреть два варианта:
1. Если найти уравнения прямых (которые образуют стороны треугольника) по двум вершинам (x1,y1) и (x2,y2): Ax+By+C=0 или (x-x2)/(x1-x2)=(y-y2)/(y1-y2) или (x-x2)*(y1-y2)-(y-y2)*(x1-x2)=0 (тоже самое, но без деления), то, подставив в это уравнение координаты точки, получим либо положительное, либо отрицательное значение (равно нулю будет, если точка лежит на прямой). Методом подстановки можно определить, какой знак будет, если точка внутри треугольника.
Этот вариант немного сложнее из-за дополнительного поиска уравнения прямой (что не всегда тревиально) или может возникнуть деление на ноль. Но, используя третье уравнение без деления, можно легко применить этот вариант.
2. Если точка лежит внутри, то проверяем на равенство площади треугольника и суммы маленьких треугольников, образованных с помощью этой точки. Возникает вопрос: как найти площадь треугольника по координатам его вершин? Обычно школьник знают формулу S=a*h/2 или по формуле Геррона S=sqrt(p*(p-a)*(p-b)*(p-c)), где p=(a+b+c)/2. В этом случае приходится каждый раз искать длину стороны треугольника по формуле a=sqrt((x1-x2)^2+(y1-y2)^2), что дает погрешность в вычислениях при дальнейших сравнениях.
Предлагаю самим вывести формулу для площади треугольника, используя формулу площади прямоугольника и формулу площади прямоугольного треугольника S=a*b/2, заключив треугольник в квадрат:
S=(x2-x1)*(y3-y2)-((x2-x1)*(y1-y2)+(x2-x3)*(y3-y2)+(x3-x1)*(y3-y1))/2.
Если треугольник не существует, то площадь=0.
Для вычисления треугольников от центра координат (0,0) достаточно подставить в эту же формулу нули в первом случае - вместо (x2,y2), во втором - вместо (x1,y1), и в третьев - вместо (x3,y3).
При сравнении используйте функцию abs(), так как могут быть отрицательные значения. Если точка вне треугольника, то сумма не будет равна площади прямоугольника. При сравнении действительных чисел используйте модуль разности с точностью 0.1Е-6, так как действительные числа могут давать погрешность при арифметических операциях.
Итак, всего четыре формулы без дополнительных переменных и вычислений и программа готова.
В каких задачах это может быть использовано:
1. Найти наибольшую (наименьшую) площадь треугольника, образованную тремя точками. При решении используется три цикла
For i:=1 to n-2 do
For j:=i+1 to n-1 do
For k:=j+1 to n do
2. Найти треугольник с наименьшим количеством содержащихся в нем точек (или вообще без точек).
3. Найти площадь многоугольника, образованного обходом n-точек.
4. Найти выпуклый многоугольник по заданным n-точкам (здесь используется та же формула для вычисления площади треугольника с тем фактом, что при обходе точек по часовой стрелке она отрицательна, а при обходе против - положительная, кроме того эта задача использует рекурсию).
Комментариев нет:
Отправить комментарий