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

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

Координаты треугольника
Координаты точки
Вы ввели следующие координаты многоугольника
Введенное выражение

 

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

Итак, существует достаточно много вариантов определения принадлежности точки треугольнику. Могу порекомендовать ссылку. Написано достаточно подробно и рассмотрены практически все варианты.

Мы в своей реализации будем придерживаться следующего алгоритма

Пусть у нас есть треугольник

 

Высчитаем значение трех нижеуказанных выражений

(20132013X201300Y0)mod(2014)=0

 

где x0,y0 - координаты произвольной точки

Если все три значения одинакового знака, то точка внутри треугольника,

если значение равно нулю, значит точка лежит на стороне треугольника

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

 

Теперь проверим наше предположение

Точка D

(4.6 - 7.78) * (4.38 +1.02) - (6.3 - 4.6) * (-1.02 - 2.38) (6.3 - 7.78) * (2.58 - 4.38) - (12.14 - 6.3) * (4.38 - 2.38) (12.14 - 7.78) * (-1.02 - 2.58) - (4.6 - 12.14) * (2.58 -2.38)

Точка лежит внутри треугольника так как  результат трех вычислений одинаков по знаку ( все они отрицательные)

Точка F

(4.6 - 4.72) * (4.38 +1.02) - (6.3 - 4.6) * (-1.02 - 0.24)=1.494(6.3 - 4.72) * (2.58 - 4.38) - (12.14 - 6.3) * (4.38 - 0.24)= -27.0216(12.14 - 4.72) * (-1.02 - 2.58) - (4.6 - 12.14) * (2.58 -0.24)=-9.0684

В этом случае точка F  лежит вне треугольника, так как знаки результирующих вычислений различны.

Хотелось бы заметить, что в случае точки Е наш бот, скажет что точка также находится внутри треугольника, хотя и находится на стороне треугольника( или как вариант в одной из вершин) . Это как уже было сказано связано с использованием этого бота, для расчета центра тяжести многоугольников.

 

Удачных расчетов!

 

 
 
 
Поиск по сайту