Другие языки программирования и технологии

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

есть треугольник с точками (q;w) (a;s) (z;x) нужно определить:
Лежит ли точка (d;f) в треугольнике или нет (или на его границе) .
Пересекается ли отрезок (v;b) (n;m) с треугольником, и желательно определить точки пересечений.
Пересекается ли треугольник (o;p) (k;l) (n;m) с нашим треугольником (или если находится один в другом) и найти точки пересечений.
А также пересекается ли круг (h;j) (R) с треугольником (или если находится один в другом) и точки пересечения.
Желательно все чтобы выглядего понятно.
А так же не отказался бы от подобной литературы
Для проверки принадлежности точки нужно найти площадь исходного треугольника и сумму площадей треугольников, полученных заменой каждой из вершин на данную точку.
Если модуль разности этих величин меньше заданной погрешности, то точка принадлежит треугольнику.
Abs(S([q,w], [a,s], [z,x]) - S([d,f], [a,s], [z,x]) - S([q,w], [d,f], [z,x]) - S([q,w], [a,s], [d,f])) < 0.00001

Для второго случая нужно вывести уравнения прямых для каждой из сторон треугольника и данного отрезка.
Затем найти точки пересечения данных прямых и определить где эти точки лежат: внутри заданных отрезков или снаружи.

Для отрезка [q,w][a,s] :
A1 = w-s
B1 = a-q
C1 = q*s-a*w

Для отрезка [v,b][n,m] :
A2 = b-m
B2 = n-v
C2 = v*m-n*b

Проверяем на параллельность:
если коэффициенты равны, значит прямые совпадают
если A1*B2-A2*B1= 0, значит прямые парралельны и не пересекаются
иначе они пересекаются в точке:
x = (B1*C2-B2*C1)/(A1*B2-A2*B1)
y = (C1*A2-C2*A1)/(A1*B2-A2*B1)

Остаётся выяснить положение точки [x,y] отрезку…
По анологии с треугольниками и точкой:
Если модуль разности длины отрезка и суммы длин отрезков от данной точки до концов отрезка меньше заданной погрешности, то точка лежит внутри отрезка.

Ну и далее по анологии…

Что касается литературы, то Загугли!
ДN
Денис Nr
70 864
Лучший ответ
По большому счету - решение подобных задач есть в любом учебнике по ЛинАлу.
1) проведите прямую через точку и вершины, посмотрите - пересекает ли она сторону треугольника противоположную вершине. (если да, то точка внутри) . если одна из других вершин при этом лежат на этой прямой, то точка на границе.
2)составьте уравнения прямых проходящих через стороны треугольника, посмотрите точки пересечения этих прямых и прямой содержащей отрезок, принадлежат ли эти точки отрезку.
3)задача аналогичная предыдущей, только прямых-больше
4)если все вершины треугольника находятся на меньшем расстоянии от центра оклужности, чем радиус, то треугольник внутри. иначе опять же составляете уравнения прямых и ищите точки пересечения путем решения системы уравнений.
Шикин и Боресков - Компьютерная графика, динамика, реалистичные изображения.

Я не уверен что там есть именно решение этой задачи но изложены общие
основы аналитической геометрии в том объёме чтобы это всё решить.
Айдар Карамов
Айдар Карамов
1 533