WarCraft 3

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

Добавлен MpW, опубликован

Алгоритмы, Наработки и Способности

Способ реализации:

Lua

Тип:

Алгоритм

часть 1
часть 2

решил разбить на 2 части.

ПЕРЕСЕЧЕНИЯ

12. Проверка bool: пересекаются ли два отрезка

онлайн

краткий курс

Примечание. Это урок с задачами по информатике (раздел алгоритмы). Если Вам необходимо решить задачу по информатике, которой здесь нет - пишите об этом в форуме. Скорее всего ее решение дополнит данный курс с задачами по информатике.

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

Обозначения:
Отрезок 1 обозначим как AB и пусть он имеет координаты A(x1;y1) B(x2; y2)
Отрезок 2 обозначим как CD и пусть он имеет координаты C(x3;y3) B(x4; y4)

Шаг 1. Ввод данных (x1;y1) (x2; y2) (x3;y3) (x4; y4)

Чтобы вычислить правильные угловые коэффициенты, должно выполняться условие x1 ≤ x2; x3 ≤ x4;
Если нет - то меняем местами пары координат отрезков.

Шаг 2. Если x1 ≥ x2 то меняем между собой значения x1 и x2 и y1 и y2
Шаг 3. Если x3 ≥ x4 то меняем между собой значения x3 и x4 и y3 и y4 ;

Шаг 4. Проверяем, равны ли между собой у2 и у1,
если у2 = у1 да, то принимаем k1 = 0 иначе
Определяем угловой коэффициент в уравнении прямой:
k1 = ( у2 - у1 ) / ( x2 - x1 )

Шаг 5. Проверяем, равны ли между собой у3 и у4,
если у3 = у4 да, то принимаем k2 = 0 иначе
Определяем угловой коэффициент в уравнении прямой:
k2 = ( у4 - у3 ) / ( x4 - x3 )

Шаг 6. Проверим отрезки на параллельность.
Если k1 = k2 , то прямые параллельны и отрезки пересекаться не могут. Решение задачи прекращаем.
Шаг 7. Вычисляем значения свободных переменных
Определяем свободные члены в уравнении прямой:
b1 = у1 - k1 * x1
b2 = у3 - k2 * x3

Шаг 8. Решаем систему уравнений:
y = k1 x + b1
y = k2 x + b2

Если прямые имеют точку пересечения, то
k1 x + b1 = k2 x + b2

Откуда и вычисляем точку пересечения прямых
x = ( b2 - b1 ) / ( k1 - k2 )
y = k1 x + b1.

Шаг 9.Учтем, что точка пересечения прямых может лежать вне отрезков, принадлежащих этим прямым. Таким образом, если отрезки пересекаются, то, поскольку
x1 ≤ x2; x3 ≤ x4;
должны выполняться условия:
x1 ≤ x4 и x4 ≤ x2
или
x1 ≤ x3 и x3 ≤ x2

Если одно из двух условий верно, то отрезки имеют точку пересечения, иначе - отрезки не пересекаются.

1. вариант.

источник

Первый способ: ориентированная площадь треугольника

function area(a,b,c)
	return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
end
 
function intersect_1 (a,b,c,d)
	if (a > b)then
		a,b=b,a --swap
	end
	if (c > d)then
		c,d=d,c --swap
	end
	return math.max(a,c) <= math.min(b,d);
end
 
function intersect(a,b,c,d)
	return intersect_1 (a.x, b.x, c.x, d.x)
		and intersect_1 (a.y, b.y, c.y, d.y)
		and area(a,b,c) * area(a,b,d) <= 0
		and area(c,d,a) * area(c,d,b) <= 0;
end

--отрезок ab пересекает отрезок cd (некоторые функции взятые с интернета выдает false, ибо из-за нулевых координат знаменатель становится 0)
a1={x=0,y=0};b1={x=0,y=100};c1={x=50,y=50};d1={x=-50,y=50}
print('p1 =>1 '..tostring( intersect(a1,b1,c1,d1))..' пересечение с учетом нуль координатами')
--отрезок ab не пересекает отрезок cd (некоторые функции взятые с интернета выдает пересечение прямых, а не отрезков)
a1={x=0,y=0};b1={x=100,y=0};c1={x=200,y=-100};d1={x=200,y=100}
print('p2 =>0 '..tostring(intersect(a1,b1,c1,d1))..' проверка, что это пересечение отрезков, а не прямых')
--конец одного отрезка ab касается другого отрезка cd (в некоторых функциях подобное касание отрезков лишь вершинами не учитывают)
a1={x=0,y=0};b1={x=100,y=0};c1={x=0,y=0};d1={x=0,y=100}
print('p3.1 =>1 '..tostring(intersect(a1,b1,c1,d1))..' лежат на одной линии, касание концом отрезка, у обоих отрезков общий конец')
--отрезок ab лежит внутри другого отрезка, т.е лежат на одной линии (в некоторых функциях вернет 0, тк отрезки параллельны)
a1={x=0,y=0};b1={x=100,y=0};c1={x=0,y=0};d1={x=50,y=0}
print('p3.2 =>1 '..tostring(intersect(a1,b1,c1,d1))..' лежат на одной линии, конец лежит внутри другого')
--отрезки лежат на одной линии, но концы не касаются (некоторые функции проверки выдают ошибку)
a1={x=150,y=450};b1={x=200,y=450};c1={x=450,y=450};d1={x=450,y=450}
print('p3.3 =>0 '..tostring(intersect(a1,b1,c1,d1))..' лежат на одной линии, концами не касаются')
--отрезки не должны пересекаться, отрезок ab параллельный отрезку cd (некоторые функции выдают положительный результат)
a1={x=0,y=0};b1={x=100,y=0};c1={x=0,y=200};d1={x=50,y=200}
print('p4 =>0 '..tostring(intersect(a1,b1,c1,d1))..' паралельны, нет пересечении')
--отрезки ab, cd вырождаются в одну точку
a1={x=0,y=0};b1={x=0,y=0};c1={x=0,y=0};d1={x=0,y=0}
print('p5 =>1 '..tostring(intersect(a1,b1,c1,d1))..' все концы отрезков вырождены в одну точку')
--отрезки ab, вырожденный в точку, лежит на отрезке cd
a1={x=0,y=0};b1={x=0,y=0};c1={x=-100,y=0};d1={x=220,y=0}
print('p6 =>1 '..tostring(intersect(a1,b1,c1,d1))..' концы отрезка вырождены в одну точку, и лежит внутри другого')
--отрезки направленные в разные стороны
a1={x=0,y=0};b1={x=100,y=0};c1={x=100,y=0};d1={x=0,y=0}
print('p7 =>1 '..tostring(intersect(a1,b1,c1,d1))..' векторы, направленные в разные стороны')
--параллельные отрезки направленные в разные стороны не должны пересекаться
a1={x=0,y=0};b1={x=100,y=0};c1={x=100,y=4};d1={x=0,y=4}
print('p8 =>0 '..tostring(intersect(a1,b1,c1,d1))..' парралельные отрезки направленные в разные стороны')

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

function area(x1,y1,x2,y2,x3,y3)
	return (x2-x1) * (y3-y1) - (y2-y1) * (x3-x1);
end
 
function intersect_1 (a,b,c,d)
	if (a > b)then a,b=b,a end
	if (c > d)then c,d=d,c end
	return math.max(a,c) <= math.min(b,d);
end
 
function intersect(x1,y1,x2,y2,x3,y3,x4,y4)
	return intersect_1 (x1, x2, x3, x4)
		and intersect_1 (y1, y2, y3, y4)
		and area(x1,y1,x2,y2,x3,y3) * area(x1,y1,x2,y2,x4,y4) <= 0
		and area(x3,y3,x4,y4,x1,y1) * area(x3,y3,x4,y4,x2,y2) <= 0;
end

Второй способ: пересечение двух прямых


EPS = 1E-9;
 
function det(a,b,c,d)
	return a * d - b * c;
end
 
function between(a,b,c)
	return math.min(a,b) <= c + EPS and c <= math.max(a,b) + EPS;
end
 
function intersect_1 (a,b,c,d)
	if (a > b)then
		a,b=b,a --swap
	end
	if (c > d)then
		c,d=d,c --swap
	end
	return math.max(a,c) <= math.min(b,d);
end
 
function intersect(a,b,c,d)
local A1,B1 = (a.y-b.y),(b.x-a.x);
local A2,B2 = (c.y-d.y),(d.x-c.x);
local C1,C2 = (-A1*a.x - B1*a.y),(-A2*c.x - B2*c.y);
local zn = det(A1, B1, A2, B2);
if (zn ~= 0)then
	local x = - det(C1, B1, C2, B2) * 1./ zn;
	local y = - det(A1, C1, A2, C2) * 1./ zn;
	return between (a.x, b.x, x) and between (a.y, b.y, y)
				and between (c.x, d.x, x) and between (c.y, d.y, y);
else
	return det (A1, C1, A2, C2) == 0 and det (B1, C1, B2, C2) == 0
			and intersect_1 (a.x, b.x, c.x, d.x)
			and intersect_1 (a.y, b.y, c.y, d.y);
end
end



--отрезок ab пересекает отрезок cd (некоторые функции взятые с интернета выдает false, ибо из-за нулевых координат знаменатель становится 0)
a1={x=0,y=0};b1={x=0,y=100};c1={x=50,y=50};d1={x=-50,y=50}
print('p1 =>1 '..tostring( intersect(a1,b1,c1,d1))..' пересечение с учетом нуль координатами')
--отрезок ab не пересекает отрезок cd (некоторые функции взятые с интернета выдает пересечение прямых, а не отрезков)
a1={x=0,y=0};b1={x=100,y=0};c1={x=200,y=-100};d1={x=200,y=100}
print('p2 =>0 '..tostring(intersect(a1,b1,c1,d1))..' проверка, что это пересечение отрезков, а не прямых')
--конец одного отрезка ab касается другого отрезка cd (в некоторых функциях подобное касание отрезков лишь вершинами не учитывают)
a1={x=0,y=0};b1={x=100,y=0};c1={x=0,y=0};d1={x=0,y=100}
print('p3.1 =>1 '..tostring(intersect(a1,b1,c1,d1))..' лежат на одной линии, касание концом отрезка, у обоих отрезков общий конец')
--отрезок ab лежит внутри другого отрезка, т.е лежат на одной линии (в некоторых функциях вернет 0, тк отрезки параллельны)
a1={x=0,y=0};b1={x=100,y=0};c1={x=0,y=0};d1={x=50,y=0}
print('p3.2 =>1 '..tostring(intersect(a1,b1,c1,d1))..' лежат на одной линии, конец лежит внутри другого')
--отрезки лежат на одной линии, но концы не касаются (некоторые функции проверки выдают ошибку)
a1={x=150,y=450};b1={x=200,y=450};c1={x=450,y=450};d1={x=450,y=450}
print('p3.3 =>0 '..tostring(intersect(a1,b1,c1,d1))..' лежат на одной линии, концами не касаются')
--отрезки не должны пересекаться, отрезок ab параллельный отрезку cd (некоторые функции выдают положительный результат)
a1={x=0,y=0};b1={x=100,y=0};c1={x=0,y=200};d1={x=50,y=200}
print('p4 =>0 '..tostring(intersect(a1,b1,c1,d1))..' паралельны, нет пересечении')
--отрезки ab, cd вырождаются в одну точку
a1={x=0,y=0};b1={x=0,y=0};c1={x=0,y=0};d1={x=0,y=0}
print('p5 =>1 '..tostring(intersect(a1,b1,c1,d1))..' все концы отрезков вырождены в одну точку')
--отрезки ab, вырожденный в точку, лежит на отрезке cd
a1={x=0,y=0};b1={x=0,y=0};c1={x=-100,y=0};d1={x=220,y=0}
print('p6 =>1 '..tostring(intersect(a1,b1,c1,d1))..' концы отрезка вырождены в одну точку, и лежит внутри другого')
--отрезки направленные в разные стороны
a1={x=0,y=0};b1={x=100,y=0};c1={x=100,y=0};d1={x=0,y=0}
print('p7 =>1 '..tostring(intersect(a1,b1,c1,d1))..' векторы, направленные в разные стороны')
--параллельные отрезки направленные в разные стороны не должны пересекаться
a1={x=0,y=0};b1={x=100,y=0};c1={x=100,y=4};d1={x=0,y=4}
print('p8 =>0 '..tostring(intersect(a1,b1,c1,d1))..' парралельные отрезки направленные в разные стороны')

2. вариант

источник

Этот код проверяет пересечение отрезков <=0. Учитывает касание вершин отрезков, принадлежность одного отрезка другому, отрезки выраженные в точку.

Если изменить условия на <0, то это более строгая проверка. будет проверять только пересечение отрезков. Не учитывает касание концов отрезков, отрезки не могут лежат на одной прямой.

Недостаток: не выполняется пункт p3.3 в дебагах. проверка <=0 может ошибаться, если параллельны или лежат на одной линии вернет 0. Если отрезки лежат на одной прямой, и при этом не касаются друг друга, то будет ошибкой.

Вывод: можно применить функцию только для строгой проверки <0.

function CrossLines(x1,y1,x2,y2,x3,y3,x4,y4)
    return ( ( ((x3-x1)*(y2-y1) - (y3-y1)*(x2-x1)) * ( (x4-x1)*(y2-y1) - (y4-y1)*(x2-x1) )) <= 0 ) and ( ( ((x1-x3)*(y4-y3) - (y1-y3)*(x4-x3)) * ((x2-x3)*(y4-y3) - (y2-y3)*(x4-x3)) ) <= 0 )
end

--отрезок ab пересекает отрезок cd (некоторые функции взятые с интернета выдает false, ибо из-за нулевых координат знаменатель становится 0)
print('p1 =>1 '..tostring( CrossLines(0,0 ,0,100, 50,50, -50,50))..' пересечение с учетом нуль координатами')


--отрезок ab не пересекает отрезок cd (некоторые функции взятые с интернета выдает пересечение прямых, а не отрезков)
print('p2 =>0 '..tostring(CrossLines(0,0, 100,0, 200,-100, 200,100))..' проверка, что это пересечение отрезков, а не прямых')

--конец одного отрезка ab касается другого отрезка cd (в некоторых функциях подобное касание отрезков лишь вершинами не учитывают)
print('p3.1 =>1 '..tostring(CrossLines(0,0, 100,0, 0,0, 0,100))..' лежат на одной линии, касание концом отрезка, у обоих отрезков общий конец')

--отрезок ab лежит внутри другого отрезка, т.е лежат на одной линии (в некоторых функциях вернет 0, тк отрезки параллельны)
print('p3.2 =>1 '..tostring(CrossLines(0,0, 100,0, 0,0, 50,0))..' лежат на одной линии, конец лежит внутри другого')

--отрезки лежат на одной линии, но концы не касаются (некоторые функции проверки выдают ошибку)
print('p3.3 =>0 '..tostring(CrossLines(150,450, 200,450, 450,450, 600,450))..' лежат на одной линии, концами не касаются')

--отрезки не должны пересекаться, отрезок ab параллельный отрезку cd (некоторые функции выдают положительный результат, видимо при коллинерности =0 как то неправильно учли)
print('p4 =>0 '..tostring(CrossLines(0,0, 100,0, 0,200, 50,200))..' паралельны, нет пересечении')

--отрезки ab, cd вырождаются в одну точку
print('p5 =>1 '..tostring(CrossLines(0,0, 0,0, 0,0, 0,0))..' все концы отрезков вырождены в одну точку')

--отрезки ab, вырожденный в точку, лежит на отрезке cd
print('p6 =>1 '..tostring(CrossLines(0,0, 0,0, 100,0, 220,0))..' концы отрезка вырождены в одну точку, и лежит внутри другого')

--отрезки направленные в разные стороны
print('p7 =>1 '..tostring(CrossLines(0,0, 100,0, 100,0, 0,0))..' векторы, направленные в разные стороны')

--параллельные отрезки направленные в разные стороны не должны пересекаться
print('p8 =>0 '..tostring(CrossLines(0,0, 100,0, 100,4, 0,4))..' парралельные отрезки направленные в разные стороны')

3. вариант

Проверяет пересечение отрезков. Плюс, учитывает концы отрезков. Однако, в учет не входит, если отрезки коллинеарны =0 (параллельны или лежат на одной прямой).

function IsLinePartsIntersected(x1,y1,x2,y2,x3,y3,x4,y4)
	local common = (x2 - x1)*(y4 - y3) - (y2 - y1)*(x4 - x3);
	if (common == 0) then return false end
    local rH = (y1 - y3)*(x4 - x3) - (x1 - x3)*(y4 - y3);
    local sH = (y1 - y3)*(x2 - x1) - (x1 - x3)*(y2 - y1);
    local r = rH / common;
    local s = sH / common;

    if (r >= 0 and r <= 1 and s >= 0 and s <= 1)then
        return true;
    else
        return false;
	end

end

--отрезок ab пересекает отрезок cd (некоторые функции взятые с интернета выдает false, ибо из-за нулевых координат знаменатель становится 0)
print('p1 =>1 '..tostring( IsLinePartsIntersected(0,0 ,0,100, 50,50, -50,50))..' пересечение с учетом нуль координатами')

--отрезок ab не пересекает отрезок cd (некоторые функции взятые с интернета выдает пересечение прямых, а не отрезков)
print('p2 =>0 '..tostring(IsLinePartsIntersected(0,0, 100,0, 200,-100, 200,100))..' проверка, что это пересечение отрезков, а не прямых')

--конец одного отрезка ab касается другого отрезка cd (в некоторых функциях подобное касание отрезков лишь вершинами не учитывают)
print('p3.1 =>1 '..tostring(IsLinePartsIntersected(0,0, 100,0, 0,0, 0,100))..' лежат на одной линии, касание концом отрезка, у обоих отрезков общий конец')

--отрезок ab лежит внутри другого отрезка, т.е лежат на одной линии (в некоторых функциях вернет 0, тк отрезки параллельны)
print('p3.2 =>1 '..tostring(IsLinePartsIntersected(0,0, 100,0, 0,0, 50,0))..' лежат на одной линии, конец лежит внутри другого')

--отрезки лежат на одной линии, но концы не касаются (некоторые функции проверки выдают ошибку)
print('p3.3 =>0 '..tostring(IsLinePartsIntersected(150,450, 200,450, 450,450, 600,450))..' лежат на одной линии, концами не касаются')

--отрезки не должны пересекаться, отрезок ab параллельный отрезку cd (некоторые функции выдают положительный результат, видимо при коллинерности =0 как то неправильно учли)
print('p4 =>0 '..tostring(IsLinePartsIntersected(0,0, 100,0, 0,200, 50,200))..' паралельны, нет пересечении')

--отрезки ab, cd вырождаются в одну точку
print('p5 =>1 '..tostring(IsLinePartsIntersected(0,0, 0,0, 0,0, 0,0))..' все концы отрезков вырождены в одну точку')

--отрезки ab, вырожденный в точку, лежит на отрезке cd
print('p6 =>1 '..tostring(IsLinePartsIntersected(0,0, 0,0, 100,0, 220,0))..' концы отрезка вырождены в одну точку, и лежит внутри другого')

--отрезки направленные в разные стороны
print('p7 =>1 '..tostring(IsLinePartsIntersected(0,0, 100,0, 100,0, 0,0))..' векторы, направленные в разные стороны')

--параллельные отрезки направленные в разные стороны не должны пересекаться
print('p8 =>0 '..tostring(IsLinePartsIntersected(0,0, 100,0, 100,4, 0,4))..' парралельные отрезки направленные в разные стороны')

4. вариант

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

Недостаток точно такой же, как и во 2 варианте: пункт p3.3 не выполняется

function IsLinePartsIntersected2(x1,y1,x2,y2,x3,y3,x4,y4)
    local Ua, Ub, numerator_a, numerator_b, denominator;

    denominator=(y4-y3)*(x1-x2)-(x4-x3)*(y1-y2);
    if (denominator == 0)then
        if ( (x1*y2-x2*y1)*(x4-x3) - (x3*y4-x4*y3)*(x2-x1) == 0 and (x1*y2-x2*y1)*(y4-y3) - (x3*y4-x4*y3)*(y2-y1) == 0) then 			
			--print("Отрезки пересекаются");
			return true
		else 
			--print("Отрезки не пересекаются");
			return false
		end
    
	else
        numerator_a=(x4-x2)*(y4-y3)-(x4-x3)*(y4-y2);
        numerator_b=(x1-x2)*(y4-y2)-(x4-x2)*(y1-y2);
        Ua=numerator_a/denominator;
        Ub=numerator_b/denominator;
        if (Ua >=0 and Ua <=1 and Ub >=0 and Ub <=1)then   
			--print("Отрезки пересекаются");
			return true
		else
			--print("Отрезки не пересекаются");
			return false
		end
    end
end

--отрезок ab пересекает отрезок cd (некоторые функции взятые с интернета выдает false, ибо из-за нулевых координат знаменатель становится 0)
print('p1 =>1 '..tostring( IsLinePartsIntersected2(0,0 ,0,100, 50,50, -50,50))..' пересечение с учетом нуль координатами')

--отрезок ab не пересекает отрезок cd (некоторые функции взятые с интернета выдает пересечение прямых, а не отрезков)
print('p2 =>0 '..tostring(IsLinePartsIntersected2(0,0, 100,0, 200,-100, 200,100))..' проверка, что это пересечение отрезков, а не прямых')

--конец одного отрезка ab касается другого отрезка cd (в некоторых функциях подобное касание отрезков лишь вершинами не учитывают)
print('p3.1 =>1 '..tostring(IsLinePartsIntersected2(0,0, 100,0, 0,0, 0,100))..' лежат на одной линии, касание концом отрезка, у обоих отрезков общий конец')

--отрезок ab лежит внутри другого отрезка, т.е лежат на одной линии (в некоторых функциях вернет 0, тк отрезки параллельны)
print('p3.2 =>1 '..tostring(IsLinePartsIntersected2(0,0, 100,0, 0,0, 50,0))..' лежат на одной линии, конец лежит внутри другого')

--отрезки лежат на одной линии, но концы не касаются (некоторые функции проверки выдают ошибку)
print('p3.3 =>0 '..tostring(IsLinePartsIntersected2(150,450, 200,450, 450,450, 600,450))..' лежат на одной линии, концами не касаются')

--отрезки не должны пересекаться, отрезок ab параллельный отрезку cd (некоторые функции выдают положительный результат, видимо при коллинерности =0 как то неправильно учли)
print('p4 =>0 '..tostring(IsLinePartsIntersected2(0,0, 100,0, 0,200, 50,200))..' паралельны, нет пересечении')

--отрезки ab, cd вырождаются в одну точку
print('p5 =>1 '..tostring(IsLinePartsIntersected2(0,0, 0,0, 0,0, 0,0))..' все концы отрезков вырождены в одну точку')

--отрезки ab, вырожденный в точку, лежит на отрезке cd
print('p6 =>1 '..tostring(IsLinePartsIntersected2(0,0, 0,0, 100,0, 220,0))..' концы отрезка вырождены в одну точку, и лежит внутри другого')

--отрезки направленные в разные стороны
print('p7 =>1 '..tostring(IsLinePartsIntersected2(0,0, 100,0, 100,0, 0,0))..' векторы, направленные в разные стороны')

--параллельные отрезки направленные в разные стороны не должны пересекаться
print('p8 =>0 '..tostring(IsLinePartsIntersected2(0,0, 100,0, 100,4, 0,4))..' парралельные отрезки направленные в разные стороны')

5. вариант

источник

Определяет пересечение отрезков A(ax1,ay1,ax2,ay2) и B (bx1,by1,bx2,by2)}. функция возвращает TRUE - если отрезки пересекаются, а если пересекаются в концах или вовсе не пересекаются, возвращается FALSE (ложь)

также не учитывает, если отрезки лежат на одной линии
Очень похож на 2 вариант.

function Intersection(ax1,ay1,ax2,ay2,bx1,by1,bx2,by2)
	local v1,v2,v3,v4
   v1=(bx2-bx1)*(ay1-by1)-(by2-by1)*(ax1-bx1);
   v2=(bx2-bx1)*(ay2-by1)-(by2-by1)*(ax2-bx1);
   v3=(ax2-ax1)*(by1-ay1)-(ay2-ay1)*(bx1-ax1);
   v4=(ax2-ax1)*(by2-ay1)-(ay2-ay1)*(bx2-ax1);
   return (v1*v2<0) and (v3*v4<0);
end

--отрезок ab пересекает отрезок cd (некоторые функции взятые с интернета выдает false, ибо из-за нулевых координат знаменатель становится 0)
print('p1 =>1 '..tostring( Intersection(0,0 ,0,100, 50,50, -50,50))..' пересечение с учетом нуль координатами')

--отрезок ab не пересекает отрезок cd (некоторые функции взятые с интернета выдает пересечение прямых, а не отрезков)
print('p2 =>0 '..tostring(Intersection(0,0, 100,0, 200,-100, 200,100))..' проверка, что это пересечение отрезков, а не прямых')

--конец одного отрезка ab касается другого отрезка cd (в некоторых функциях подобное касание отрезков лишь вершинами не учитывают)
print('p3.1 =>1 '..tostring(Intersection(0,0, 100,0, 0,0, 0,100))..' лежат на одной линии, касание концом отрезка, у обоих отрезков общий конец')

--отрезок ab лежит внутри другого отрезка, т.е лежат на одной линии (в некоторых функциях вернет 0, тк отрезки параллельны)
print('p3.2 =>1 '..tostring(Intersection(0,0, 100,0, 0,0, 50,0))..' лежат на одной линии, конец лежит внутри другого')

--отрезки лежат на одной линии, но концы не касаются (некоторые функции проверки выдают ошибку)
print('p3.3 =>0 '..tostring(Intersection(150,450, 200,450, 450,450, 600,450))..' лежат на одной линии, концами не касаются')

--отрезки не должны пересекаться, отрезок ab параллельный отрезку cd (некоторые функции выдают положительный результат, видимо при коллинерности =0 как то неправильно учли)
print('p4 =>0 '..tostring(Intersection(0,0, 100,0, 0,200, 50,200))..' паралельны, нет пересечении')

--отрезки ab, cd вырождаются в одну точку
print('p5 =>1 '..tostring(Intersection(0,0, 0,0, 0,0, 0,0))..' все концы отрезков вырождены в одну точку')

--отрезки ab, вырожденный в точку, лежит на отрезке cd
print('p6 =>1 '..tostring(Intersection(0,0, 0,0, 100,0, 220,0))..' концы отрезка вырождены в одну точку, и лежит внутри другого')

--отрезки направленные в разные стороны
print('p7 =>1 '..tostring(Intersection(0,0, 100,0, 100,0, 0,0))..' векторы, направленные в разные стороны')

--параллельные отрезки направленные в разные стороны не должны пересекаться
print('p8 =>0 '..tostring(Intersection(0,0, 100,0, 100,4, 0,4))..' парралельные отрезки направленные в разные стороны')

В итоге самая идеал функции это в первом варианте, человек хорошо написал функцию. В остальные функции видимо надо внутри писать доп проверки

пересечение луча и прямой

источник
Пересечения луча и прямой на плоскости могут иметь общие и частные варианты: луч и прямая пересекаются, луч и прямая параллельны и не пересекаются, луч и прямая параллельны и совпадают, луч и прямая расположены под углом друг к другу и не пересекаются. Выведем уравнения и вычисления теоретически и затем воплотим их в практический программный код

Определение наличия пересечения
В тетраде мы можем видеть явное пересечение когда луч пересекает прямую. Но можно нарисовать луч и прямую так что они почти параллельны, тогда как узнать пересекаются или нет? В программном коде все случаи необходимо скрупулезно разбирать, вслепую полагаясь только на вычисления. Определить наличие пересечения можно решив систему из уравнений луча и прямой.

Возьмем параметрические уравнения для луча и с коэффициентами для прямой. Параметрическое уравнение луча отличается важным параметром t идентифицирующий направление луча. Только при t >=0 уравнение определяет множество точек луча. Если же к лучу добавить точки при t < 0 тогда луч превратится в прямую и это будет параметрическое уравнение прямой
Параметрические уравнения луча:

x = x0 + v*t
y = y0 + w*t
где v и w координаты вектора направления луча, t >= 0

Система уравнений, 3 уравнения и 3 неизвестных: система решаема.
| x = x0 + vt
| y = y0 + wt (у.1)
| ax + by + c = 0

Выведем подробно определение t из системы уравнений:

a(x0 + vt) + b(y0 + wt) + c = 0 =>
ax0 + avt + by0 + bwt + c = 0 =>
t(av + bw) + ax0 + by0 + c = 0 =>
t(av + bw) = -ax0 - by0 - c =>
t = (-ax0 - by0 - c) / (av + bw) (у.2)

При t >= 0 луч и прямая пересекаются, если t < 0 луч и прямая не имеют общих точек.

особый момент

Деление на ноль

Как видно из выражения вывода параметра t нам не удалось избавится от деления. В случае если знаменатель будет равен нулю, то результат будет бесконечность. В каких случаях знаменатель может быть равен нулю?

Направление луча неопределенно:
тогда v = 0 и w = 0

Направление прямой неопределенно:
тогда a = 0 и b = 0

Когда луч и прямая параллельны друг другу, а их векторы коллинеарны. В нашем случае когда соблюдается условие:

-b a
---- = ---- => av + bw = 0 (наш знаменатель)
v w

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

--rayX,rayY -координаты точки начала луча, dirX,dirY - координаты точки направления луча
--a,b,c - коэ-ты уравнения прямой
function IsRayIntersectLine(rayX,rayY,dirX,dirY,a,b,c) 
	
	local x0,y0=rayX,rayY
	local v,w = dirX - rayX, dirY - rayY
	local t 
	if (a*v + b*w)~=0 then --проверка на ноль
		t = (-a*x0 - b*y0 - c) / (a*v + b*w)
		return t >= 0
	end
	return false
end
--rayX,rayY -координаты точки начала луча, dirX,dirY - координаты точки направления луча
--x1,y1,x2,y2 - координаты точек, описывающую прямую
function IsRayIntersectLine2(rayX,rayY,dirX,dirY,x1,y1,x2,y2) 
    --приводим коэ-ты уравнения прямой ax+by+c=0
    local a = y2 - y1
    local b = x1 - x2
    local c = -x1 * y2 + y1 * x2
    
    return IsRayIntersectLine(rayX,rayY,dirX,dirY,a,b,c)
end
    
print(IsRayIntersectLine2(4,5,11,6,1,5,0,3)) --вернет false (не пересекаются)
print(IsRayIntersectLine2(0,0,0,1,1,0,1,1)) --вернет false (коллинеарны)
print(IsRayIntersectLine2(1,6,11,4,3,2,9,8)) --вернет true

пересекает ли луч отрезок

проверка пересечения луча и отрезка (собственный вариант)

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

function InterLineLine(x1,y1,x2,y2,a1,b1,a2,b2)
    local p = (x2-x1)*(b2-b1)-(y2-y1)*(a2-a1)
    local x,y

    if ( p == 0 ) then --отрезки параллельны
        return false
    end

    x =  ((x2-x1)*(a2-a1)*(y1-b1)+(x2-x1)*(b2-b1)*a1-(y2-y1)*(a2-a1)*x1)/p
    y = -((y2-y1)*(b2-b1)*(x1-a1)+(y2-y1)*(a2-a1)*b1-(x2-x1)*(b2-b1)*y1)/p
    return x,y
end
function IsPointOnBeam2(x,y,x1,y1,x2,y2)
	return ((x-x1)*(y2-y1) == (x2-x1)*(y-y1)) and ((x-x1) * (x2-x1) >= 0) and ((y-y1)*(y2-y1) >= 0)
end

function IsPointInSegment(x,y,x1,y1,x2,y2)
	return((x1-x)^2+(y1-y)^2)^0.5 + ((x2-x)^2+(y2-y)^2)^0.5 == ((x2-x1)^2+(y2-y1)^2)^0.5 
end

function RayIntersectSegment(rayx,rayy,dirx,diry,x1,y1,x2,y2)
	--находим точку пересечения прямых
	local x,y=InterLineLine(rayx,rayy,dirx,diry,x1,y1,x2,y2)
	
	if x then
		--проверка, что точка пересечения на отрезке, и принадлежит лучу
		return IsPointInSegment(x,y,x1,y1,x2,y2)and IsPointOnBeam2(x,y,rayx,rayy,dirx,diry)
	else
		--иначе, если прямые не пересекаются, то точки пересечения нет.
		--если луч и отрезок лежат на одной линии
		return IsPointOnBeam2(x1,y1,rayx,rayy,dirx,diry) and IsPointOnBeam2(x2,y2,rayx,rayy,dirx,diry)
	end
	
	return false
end
print('p1=1: '..tostring(RayIntersectSegment(0,0,0,1,100,0,-100,0))..' луч направлен вверх, луч пересекает горизонтальный отрезок') 
print('p1=0: '..tostring(RayIntersectSegment(0,0,0,1,100,-1,-100,-1))..' луч направлен вверх, луч не пересекает горизонтальный отрезок, расположенный ниже'')

пересечение луча и отрезка (вариант 2)

источник

EPS = 1E-9;

--скалярное произведение
function scalar_product(x1,y1,x2,y2)
	return x1*x2 + y1*y2 --скалярное произведение векторов |a|*|b|*cos alpha. cos 0 = 1. 3 опер
end
--псевдовекторное произведение
function cross(x1,y1,x2,y2)
	return x1*y2 - y1*x2 
end

--тест пересечения луча ab и отрезка cd
--если пересекаются, возвращает параметр t
--точка пересечения P(t) = A + t * (B - A)
function testRaySegment(rayX,rayY,dirX,dirY,x1,y1,x2,y2)

    local result,t1,t2 = false;
	local denom = cross(x2-x1,y2-y1,dirX-rayX,dirY-rayY);
        if (math.abs(denom) > EPS)then --прямые не коллинеарны
            t2 = cross(dirX-rayX,dirY-rayY, x1-rayX,y2-rayY) / denom;
			
            if (0 - EPS < t2 and t2 < 1 + EPS)then -- точка на отрезке

				if math.abs(dirX-rayX) > EPS then
					t1=(x1-rayX + x2-x1 * t2) / (dirX-rayX)
				else
					t1=(y1-rayY + y2-y1 * t2) / (dirY-rayY) --если луч вертикальный
				end		
				
                if (t1 > 0)then -- точка впереди луча
                    result = true;
                    t = t1;
                end
            end
        end
        return result;
end
print('p1=1: '..tostring(testRaySegment(0,0,0,1,100,1,-100,1))..' луч направлен вверх t1>0, луч пересекает верхний горизонтальный отрезок') 
print('p1=0: '..tostring(testRaySegment(0,0,0,1,100,0,-100,0))..' луч направлен вверх, луч не пересекает отрезок. точка начала луча и отрезок лежат на одной линии t1==0') 
print('p1=0: '..tostring(testRaySegment(0,0,0,1,100,-1,-100,-1))..' луч направлен вверх, луч не пересекает горизонтальный отрезок снизу')

пускаем луч горизонтально вправо

function GetRayX(y,x1,y1,x2,y2)
	return(y-y1)*(x2-x1)/(y2-y1)+x1
end

function GetRayXRight(x,y,x1,y1,x2,y2)
	s2 = (y-y1)/(y2-y1) 
	s1 = x1-x + s2*(x2-x1)
	--принадлежит отрезку (0 <= s2 <= 1) и на луче (s1 >= 0)
	return (s1 >= 0) and (s2 >= 0) and (s2 <= 1)
end
print('p1=1: '..tostring(GetRayXRight(0,0,0,200,0,-200))..' 3 точки лежат на линии s1=0') 
print('p2=1: '..tostring(GetRayXRight(0,0,1,200,1,-200))..' проверка, что отрезок справа s1>0') 
print('p3=0: '..tostring(GetRayXRight(0,0,-1,200,-1,-200))..' проверка, что отрезок слева s1<0') 
print('p4=0: '..tostring(GetRayXRight(0,0,-1,200,-1,100))..' отрезок подняли выше точки луча, и справа не попадает')

пускаем луч горизонтально влево

function GetRayXLeft(x,y,x1,y1,x2,y2)
	s2 = (y-y1)/(y2-y1) 
	s1 = x1-x + s2*(x2-x1)
	return (s1 <= 0) and (s2 >= 0) and (s2 <= 1)
end
print('p1=1: '..tostring(GetRayXLeft(0,0,0,200,0,-200))..' 3 точки лежат на линии s1=0') 
print('p2=0: '..tostring(GetRayXLeft(0,0,1,200,1,-200))..' проверка, что отрезок справа s1>0') 
print('p3=1: '..tostring(GetRayXLeft(0,0,-1,200,-1,-200))..' проверка, что отрезок слева s1<0') 
print('p4=0: '..tostring(GetRayXLeft(0,0,-1,200,-1,100))..' отрезок подняли выше точки луча, и слева не попадает')

пускаем луч вертикально вверх

function GetRayYTop(x,y,x1,y1,x2,y2)
	s2 = (x-x1)/(x2-x1) 
	s1 = y1-y + s2*(y2-y1)
	return (s1 >= 0) and (s2 >= 0) and (s2 <= 1)
end
print('p1=1: '..tostring(GetRayYTop(0,0,200,0,-200,0))..' 3 точки лежат на линии s1=0') 
print('p2=1: '..tostring(GetRayYTop(0,0,200,1,-200,1))..' проверка, что отрезок находится выше s1>0') 
print('p3=0: '..tostring(GetRayYTop(0,0,200,-1,-200,-1))..' проверка, что отрезок находится снизу s1<0') 
print('p4=0: '..tostring(GetRayYTop(0,0,-1,-1,-1,1))..' отрезок расположен левее точки луча, и выше не пересекаются')

пускаем луч вертикально вниз

function GetRayYBottom(x,y,x1,y1,x2,y2)
	s2 = (x-x1)/(x2-x1)
	s1 = y1-y + s2*(y2-y1)
	return (s1 <= 0) and (s2 >= 0) and (s2 <= 1)
end
print('p1=1: '..tostring(GetRayYBottom(0,0,200,0,-200,0))..' 3 точки лежат на линии s1=0') 
print('p2=0: '..tostring(GetRayYBottom(0,0,200,1,-200,1))..' проверка, что отрезок находится выше s1>0') 
print('p3=1: '..tostring(GetRayYBottom(0,0,200,-1,-200,-1))..' проверка, что отрезок находится снизу s1<0') 
print('p4=0: '..tostring(GetRayYBottom(0,0,-1,-1,-1,1))..' отрезок расположен левее точки луча, и выше не пересекаются')

Пересекаются ли два луча

Даны два луча: AB и CD (A и C - вершины лучей, B и D лежат на лучах). Проверьте, пересекаются ли они.

Программа получает на вход координаты точек A,B,C,D. Все координаты - целые числа, не превосходят 100 по модулю.

Программа должна вывести слово yes, или no

Вводные данные
0,1
1,2
1,-1
1,0
Ответ: yes

0,0
1,0
0,1
1,2
Ответ: no

собственный вариант

находим точку пересечения прямых, затем проверяем принадлежит ли эта точка обоим лучам

function InterLineLine(x1,y1,x2,y2,a1,b1,a2,b2)
    local p = (x2-x1)*(b2-b1)-(y2-y1)*(a2-a1)
    local x,y

    if ( p == 0 ) then --отрезки параллельны
        return false
    end
    x =  ((x2-x1)*(a2-a1)*(y1-b1)+(x2-x1)*(b2-b1)*a1-(y2-y1)*(a2-a1)*x1)/p
    y = -((y2-y1)*(b2-b1)*(x1-a1)+(y2-y1)*(a2-a1)*b1-(x2-x1)*(b2-b1)*y1)/p
    return x,y
end
function IsPointOnBeam2(x,y,x1,y1,x2,y2)
	return ((x-x1)*(y2-y1) == (x2-x1)*(y-y1)) and ((x-x1) * (x2-x1) >= 0) and ((y-y1)*(y2-y1) >= 0)
end
function RayIntersectRay(x1,y1,x2,y2,x3,y3,x4,y4)
	--находим точку пересечении прямых линии
	local x,y=InterLineLine(x1,y1,x2,y2,x3,y3,x4,y4)
	if x then
		--проверяем, что точка принадлежит лучам a и b
		return IsPointOnBeam2(x,y,x1,y1,x2,y2)and IsPointOnBeam2(x,y,x3,y3,x4,y4)
	end
	return false
end

print(RayIntersectRay(0,1,1,2,1,-1,1,0))
print(RayIntersectRay(0,0,1,0,0,1,1,2))

точки пересечения прямых,отрезков,лучей и пр

точка пересечения отрезков / линии

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

1. вариант (пересечение прямых линии, не отрезков!!!)

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

function InterLineLine(x1,y1,x2,y2,a1,b1,a2,b2)
    local p = (x2-x1)*(b2-b1)-(y2-y1)*(a2-a1)
    local x,y

    if ( p == 0 ) then --отрезки параллельны
        return false
    end

    x =  ((x2-x1)*(a2-a1)*(y1-b1)+(x2-x1)*(b2-b1)*a1-(y2-y1)*(a2-a1)*x1)/p
    y = -((y2-y1)*(b2-b1)*(x1-a1)+(y2-y1)*(a2-a1)*b1-(x2-x1)*(b2-b1)*y1)/p
    return x,y
end

--отрезок ab пересекает отрезок cd (некоторые функции взятые с интернета выдает false, ибо из-за нулевых координат знаменатель становится 0)
print(InterLineLine(0,0 ,0,100, 50,50, -50,50))

--отрезок ab не пересекает отрезок cd (некоторые функции взятые с интернета выдает пересечение прямых, а не отрезков)
print(InterLineLine(0,0, 100,0, 200,-100, 200,100))

--конец одного отрезка ab касается другого отрезка cd (в некоторых функциях подобное касание отрезков лишь вершинами не учитывают)
print(InterLineLine(0,0, 100,0, 0,0, 0,100))

--отрезок ab лежит внутри другого отрезка, т.е лежат на одной линии (в некоторых функциях вернет 0, тк отрезки параллельны)
print(InterLineLine(0,0, 100,0, 0,0, 50,0))

--отрезки не должны пересекаться, отрезок ab параллельный отрезку cd (некоторые функции выдают положительный результат, видимо при коллинерности =0 как то неправильно учли)
print(InterLineLine(100,0, 100,200, 30,0, 30,200))

--отрезки не должны пересекаться, отрезок ab параллельный отрезку cd (некоторые функции выдают положительный результат, видимо при коллинерности =0 как то неправильно учли)
print(InterLineLine(0,0, 100,0, 0,200, 50,200))

--отрезки ab, cd вырождаются в одну точку
print(InterLineLine(0,0, 0,0, 0,0, 0,0))

--отрезки ab, вырожденный в точку, лежит на отрезке cd
print(InterLineLine(0,0, 0,0, 100,0, 220,0))

--отрезки направленные в разные стороны
print(InterLineLine(0,0, 100,0, 100,0, 0,0))

--параллельные отрезки направленные в разные стороны не должны пересекаться
print(InterLineLine(0,0, 100,0, 100,4, 0,4))
print(InterLineLine(150,180, 150,450, 600,450, 600,180))

2. вариант (пересечение прямых линии)

код, кажется из одной близзардской карты. Тут тоже не отрезки, а прямые.

function LineIntersect(x1,y1,x2,y2,x3,y3,x4,y4)

local LDetLineA,LDetLineB = (x1*y2-y1*x2),(x3*y4-y3*x4)
local LDiffLAx,LDiffLAy = (x1-x2),(y1-y2)
local LDiffLBx,LDiffLBy = (x3-x4),(y3-y4)
local p = ((LDiffLAx*LDiffLBy) - (LDiffLAy*LDiffLBx))
if p == 0 then
	return false
else
	local LDetDivInv = 1 / p
	local real x = ((LDetLineA*LDiffLBx) - (LDiffLAx*LDetLineB)) * LDetDivInv
	local real y = ((LDetLineA*LDiffLBy) - (LDiffLAy*LDetLineB)) * LDetDivInv
	print('точка пересечения: '..x..' , '..y)
	return x,y
end
end

--отрезок ab пересекает отрезок cd (некоторые функции взятые с интернета выдает false, ибо из-за нулевых координат знаменатель становится 0)
print(LineIntersect(0,0 ,0,100, 50,50, -50,50))

--отрезок ab не пересекает отрезок cd (некоторые функции взятые с интернета выдает пересечение прямых, а не отрезков)
print(LineIntersect(0,0, 100,0, 200,-100, 200,100))

--конец одного отрезка ab касается другого отрезка cd (в некоторых функциях подобное касание отрезков лишь вершинами не учитывают)
print(LineIntersect(0,0, 100,0, 0,0, 0,100))

--отрезок ab лежит внутри другого отрезка, т.е лежат на одной линии (в некоторых функциях вернет 0, тк отрезки параллельны)
print(LineIntersect(0,0, 100,0, 0,0, 50,0))

--отрезки не должны пересекаться, отрезок ab параллельный отрезку cd (некоторые функции выдают положительный результат, видимо при коллинерности =0 как то неправильно учли)
print(LineIntersect(100,0, 100,200, 30,0, 30,200))

--отрезки не должны пересекаться, отрезок ab параллельный отрезку cd (некоторые функции выдают положительный результат, видимо при коллинерности =0 как то неправильно учли)
print(LineIntersect(0,0, 100,0, 0,200, 50,200))

--отрезки ab, cd вырождаются в одну точку
print(LineIntersect(0,0, 0,0, 0,0, 0,0))

--отрезки ab, вырожденный в точку, лежит на отрезке cd
print(LineIntersect(0,0, 0,0, 100,0, 220,0))

--отрезки направленные в разные стороны
print(LineIntersect(0,0, 100,0, 100,0, 0,0))

--параллельные отрезки направленные в разные стороны не должны пересекаться
print(LineIntersect(0,0, 100,0, 100,4, 0,4))
print(LineIntersect(150,180, 150,450, 600,450, 600,180))

3. вариант. точка пересечение линии (данные ведены через коэ-ты a,b,c линейных уравнении ax+by+c=0)

Пересечение двух прямых - 1
Дано шесть чисел: коэффициенты нормальных уравнений двух непараллельных прямых.
Программа должна вывести два числа: координаты точки пересечения данных прямых.
Ввод
1 1 -1
1 -1 0
Ответ 0.5 0.5

источник

function LinesIntersect(a1,b1,c1, a2,b2,c2)
	local x = (b1 * c2 - b2 * c1) / (a1 * b2 - a2 * b1);
	local y = (a2 * c1 - a1 * c2) / (a1 * b2 - a2 * b1);
	return x,y
end
print(LinesIntersect(1, 1, -1, 1, -1, 0))

4. вариант (Пересечения двух прямых)

На плоскости даны две прямые. Каждая прямая задается парой точек, через которые она проходит. Требуется установить, пересекаются ли эти прямые, и найти координаты точки пересечения.

Вводятся сначала координаты двух различных точек, через которые проходит первая прямая, а затем - координаты еще двух различных (но, быть может, совпадающих с первыми двумя) точек, через которые проходит вторая прямая. Координаты каждой точки - целые числа, по модулю не превышающие 1000.

Если прямые не пересекаются, выведите одно число 0. Если прямые совпадают, выведите 2. Если прямые пересекаются ровно в одной точке, то выведите сначала число 1, а затем два вещественных числа - координаты точки пересечения.
Ввод

1 1
2 2
1 10
2 11
Ответ: 0

0 0
1 1
1 0
-1 2
Ответ: 1 0.5 0.5

function InLines2(ax1,ay1,ax2,ay2,bx1,by1,bx2,by2)	
	--составляем коэффициенты уравнения прямой ax1+by1+c1=0
	local a1,b1=ay2-ay1,ax1-ax2
	local c1=ax1*(ay1-ay2)+ay1*(ax2-ax1)
	--составляем коэффициенты уравнения прямой ax2+by2+c2=0
	local a2,b2=by2-by1,bx1-bx2
	local c2=bx1*(by1-by2)+by1*(bx2-bx1)
	
	local e,x,y=0
	--коллинеарны ли линии
	if(a1 * b2 - a2 * b1) == 0 then
	    --проверка совпадают ли они
		if(a1 * b2 == b1 * a2 and a1 * c2 == a2 * c1 and b1 * c2 == c1 * b2)then
			e=2
		end
	else
		--линии пересекаются
		e=1
		x = (b1 * c2 - b2 * c1) / (a1 * b2 - a2 * b1);
		y = (a2 * c1 - a1 * c2) / (a1 * b2 - a2 * b1);
		return e,x,y
	end
	return e
end
print( InLines2(1,1,2,2,1,10,2,11))
print( InLines2(0,0,1,1,1,0,-1,2))

5. вариант (пересечение отрезков)

Не учитываются отрезки, если лежат на одной прямой (коллинеарность =0)

Находит даже касающие концы отрезков, если они не коллинеарны.

function getPointOfIntersection(x1,y1,x2,y2,x3,y3,x4,y4)
	local d,da,db,ta,tb,dx,dy
	
	d = (x1 - x2) * (y4 - y3) - (y1 - y2) * (x4 - x3);
	da = (x1 - x3) * (y4 - y3) - (y1 - y3) * (x4 - x3);
	db = (x1 - x2) * (y1 - y3) - (y1 - y2) * (x1 - x3);
 
	if d==0 then
		return false
	end
 
	ta = da / d;
	tb = db / d;
 
	if (ta >= 0 and ta <= 1 and tb >= 0 and tb <= 1) then
		dx = x1 + ta * (x2 - x1);
		dy = y1 + ta * (y2 - y1);
 
		return dx,dy
	end
 
	return false
end

--отрезок ab пересекает отрезок cd (некоторые функции взятые с интернета выдает false, ибо из-за нулевых координат знаменатель становится 0)
print(getPointOfIntersection(0,0 ,0,100, 50,50, -50,50))

--отрезок ab не пересекает отрезок cd (некоторые функции взятые с интернета выдает пересечение прямых, а не отрезков)
print(getPointOfIntersection(0,0, 100,0, 200,-100, 200,100))

--конец одного отрезка ab касается другого отрезка cd (в некоторых функциях подобное касание отрезков лишь вершинами не учитывают)
print(getPointOfIntersection(0,0, 100,0, 0,0, 0,100))

--отрезок ab лежит внутри другого отрезка, т.е лежат на одной линии (в некоторых функциях вернет 0, тк отрезки параллельны)
print(getPointOfIntersection(0,0, 100,0, 0,0, 50,0))

--отрезки не должны пересекаться, отрезок ab параллельный отрезку cd (некоторые функции выдают положительный результат, видимо при коллинерности =0 как то неправильно учли)
print(getPointOfIntersection(100,0, 100,200, 30,0, 30,200))

--отрезки не должны пересекаться, отрезок ab параллельный отрезку cd (некоторые функции выдают положительный результат, видимо при коллинерности =0 как то неправильно учли)
print(getPointOfIntersection(0,0, 100,0, 0,200, 50,200))

--отрезки ab, cd вырождаются в одну точку
print(getPointOfIntersection(0,0, 0,0, 0,0, 0,0))

--отрезки ab, вырожденный в точку, лежит на отрезке cd
print(getPointOfIntersection(0,0, 0,0, 100,0, 220,0))

--отрезки направленные в разные стороны
print(getPointOfIntersection(0,0, 100,0, 100,0, 0,0))

--параллельные отрезки направленные в разные стороны не должны пересекаться
print(getPointOfIntersection(0,0, 100,0, 100,4, 0,4))
print(getPointOfIntersection(150,180, 150,450, 600,450, 600,180))

точка пересечения прямой с осью абсцисс

Найти точку пересечения прямой с осью абсцисс, если эта прямая проходит через введенные точки.
Пример
Дано:
А (-3; 2); В (-1; 3); X=0.
Найти:
Точку С, лежащую на оси ординат
Ответ: С( 0 ; 3,5).

уравнение прямой, проходящей через 2 точки
x-xA/xB-xA = y-yA/yB-yA
у точки пересечения прямой с осью абцисс ордината равна 0
x-xA/xB-xA = 0-yA/yB-yA
отсюда получаем абциссу
x= -yA/yB-yA * (xB-xA)+xA

Если прямая выражена уравнением ax+by+c=0, то найти можно так:
абцисса ось x => y=0
ax+by+c=0 => ax+c=0 => x=-c/a
Получается, что точка x,y = (-c/a, 0)

function crossLineAbsiss(x, x1,y1,x2,y2)
	if (x2-x1 ~= 0) then
		y = (((-x1) * (y2 - y1) / (x2 - x1)) + y1)
	else
		print("Данная прямая не пересекает ось Y.")
	end
	return x,y
end
print(crossLineAbsiss(0, -3, 2,-1, 3))

Точка пересечения луча и прямой

источник
определим на примере точку пересечения луча и прямой. Сформируем необходимые данные для системы уравнений (у.1) и сначала определим факт пересечения уравнение (у.2), затем получим координаты точки С.
x = x0 + v*t
y = y0 + w*t (у.1)
ax + by + c = 0

t = (-a*x0 - b*y0 - c) / (a*v + b*w) (у.2)

function PointIntersectBetweenRayAndLine(rayX,rayY,dirX,dirY,a,b,c)
	local x0,y0=rayX,rayY
	local v,w = dirX - rayX, dirY - rayY
	local t

	local p=(a*v + b*w)
	if p~=0 then --проверка на ноль
		t = (-a*x0 - b*y0 - c) / p
		if t > 0 then --луч и прямая пересекаются, имеют общую точку
			local x = x0 + v*t
			local y = y0 + w*t
			return x,y
		end
	end
	return false
end

function PointIntersectBetweenRayAndLine2(rayX,rayY,dirX,dirY,x1,y1,x2,y2) 
    --приводим коэ-ты уравнения прямой ax+by+c=0
    local a = y2 - y1
    local b = x1 - x2
    local c = -x1 * y2 + y1 * x2
	
	return PointIntersectBetweenRayAndLine(rayX,rayY,dirX,dirY,a,b,c)
end

print(PointIntersectBetweenRayAndLine2(1,6,11,4,3,2,9,8)) --вернет 6,5

Основание перпендикуляра

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

Программа должна вывести два числа: координаты основания перпендикуляра, опущенного из данной точки на данную прямую
Ввод Вывод

1 1
1 1 -1
Ответ: 0.5 0.5

источник

--наименьший общий делитель между a,b gcd>0
function gcd(a, b)
	return b==0 and a or gcd(b,a%b)
end
--наименьший общий делитель между a,b,c
function nod(a, b, c)
	return gcd(gcd(a,b),c)
end

function EquationIntCoefficients(Px,Py,Qx,Qy)
	--находим коэ-ты уравнения
	local A,B = Py-Qy, Qx-Px
	local C = -A*Px - B*Py
	--далее нормируем коэ-ты
	
	--находим наибольший общий делитель 3 чисел
	local Z = nod(A,B,C)
	
	--коэф-ты делить на НОД
	A,B,C=A/Z,B/Z,C/Z
	
	--произведем нормировку знака
	if A<0 or (A==0 and B<0) then
		return -A,-B,-C
	end
	return A,B,C
end
function EquationCoefficients(Px,Py,Qx,Qy)
	local A,B = Qy-Py, Px-Qx
	C = -(A*Px + B*Py)
	return A,B,C
end

function PerpendicularPointBetweenTwoLine(x0,y0,A,B,C)
	x=(B^2*x0 - A*B*y0 - A*C)/(A^2+B^2)
	y=(A^2*y0 - A*B*x0 - B*C)/(A^2+B^2)
	
	--для проверки находим уравнение перпендикулярной прямой ax1+by1+c1=0
	local a1,b1,c1 = EquationIntCoefficients(x,y,x0,y0)

    --проверяем правильно ли подобрано точка x,y
	if (x-x0)*a1 + (y-y0)*b1 ==0 then

	    print("основание перпедикулярно "..(x-x0)*a1 + (y-y0)*b1)
	else
	    print("основание не перпедикулярно "..(x-x0)*a1 + (y-y0)*b1)
	end
	
	return x,y
end
print(PerpendicularPointBetweenTwoLine(1,1,1,1,-1))

середина отрезка

коорды точки середина отрезка

function midpoint(xa,ya,xb,yb)
	return (xa+xb)/2,(ya+yb)/2
end

Точка пересечения медиан (centroid of a triangle - центр тяжести тр-ка)

Дан треугольник. Найдите точку пересечения его медиан.
Ввод
0 0
1 0
0 1
0.333333 0.333333

0 0
3 0
3 6
2.0 2.0

Медиа́на треуго́льника (лат. mediāna — средняя) ― отрезок, соединяющий вершину треугольника с серединой противоположной стороны. Иногда медианой называют также прямую, содержащую этот отрезок. Точка пересечения медианы со стороной треугольника называется основанием медианы.

Точка пересечения медиан треугольника является его центром тяжести. Таким образом искомые координаты (x, y) можно найти по формулам:
x = (x1 + x2 + x3) / 3;
y = (y1 + y2 + y3) / 3;

Точка пересечения биссектрис (incenter of triangle)

Центр вписанной окружности — это центр вписанной окружности для многоугольника или сферы для многогранника (если они существуют). Соответствующий радиус вписанной окружности или сферы называется внутренним радиусом. Центр вписанной может быть построен как пересечение биссектрис угла

Дан треугольник. Найдите точку пересечения его биссектрис.

Тесты

0 0
1 0
0 1
Ответ: 0.292893 0.292893

0 4
3 0
0 0
Ответ: 1.00 1.00

0 -4
-3 0
0 0
Ответ: -1.00 -1.00
-5 -1
0 -13
-5 -13
Ответ: -3.00 -11.00

1 1
5 1
3 4
Ответ: 3.00 2.07

источник

--задаем координаты треугольника
function TriangleIncenter(x1,y1,x2,y2,x3,y3);
 
   --найдем длинны сторон, чтобы воспользоваться формулой
   local c=math.sqrt((x1-x2)^2+(y1-y2)^2);
   local a=math.sqrt((x2-x3)^2+(y3-y2)^2);
   local b=math.sqrt((x1-x3)^2+(y1-y3)^2);
 
   --найдем координаты биссектрисы
   local x=(a*x1+b*x2+c*x3)/(a+b+c);
   local y=(a*y1+b*y2+c*y3)/(a+b+c);

	return x,y;
end
print(TriangleIncenter(0,0,1,0,0,1)) --Ответ: 0.292893 0.292893
print(TriangleIncenter(0,4,3,0,0,0)) --Ответ: 1.00 1.00
print(TriangleIncenter(0,-4,-3,0,0,0)) --Ответ: -1.00 -1.00
print(TriangleIncenter(-5,-1,0,-13,-5,-13)) --Ответ: -3.00 -11.00
print(TriangleIncenter(1,1,5,1,3,4)) --Ответ: 3.00 2.07

Точка пересечения высот (ортоцентр orthocenter)

Дан треугольник. Найдите точку пересечения его высот.
Ввод
0 0
1 0
0 1
Ответ: 0.0 0.0

0 0
3 0
0 4
Ответ: 0.0 0.0

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

Три высоты в треугольнике пересекаются в одной точке и эту точку называют ортоцентром треугольника.

Решение

источник
Пусть A(xa, ya), B(xb, yb), C(xc, yc) – три вершины треугольника. Проведем высоты AK и BL. Точка их пересечения H будет искомой.

Напишем уравнение прямой AK: она должна проходить через вершину A и быть перпендикулярной прямой BC. Пусть уравнение прямой AK имеет вид a1x + b1y = c1. Тогда вектор (a1, b1) совпадает с направлением вектора BC и можно положить (a1, b1) = (xc – xb, yc – yb). Уравнение прямой AK примет вид

(xc – xb)x + (yc – yb)y = c1

Поскольку прямая AK проходит через точку А, то подставив в ее уравнение координаты точки A(xa, ya), найдем значение c1:

(xc – xb) xa + (yc – yb) ya = c1

Аналогично находим уравнение прямой BL. Пусть оно имеет вид
a2x + b2y = c2.
Вектор (a2, b2) совпадает с направлением вектора АC и можно положить (a2, b2) = (xc – xa, yc – ya). Точка B лежит на прямой BL, следовательно

(xc – xa) xb + (yc – ya) yb = c2

Точка пересечения высот треугольника находится решением системы уравнений
ax1 + by1 = c1
ax2 + by2 = c2
методом Крамера.

Реализация алгоритма
Функция kramer находит решение (x, y) системы уравнений

function kramer(a1,b1,c1,a2,b2,c2)
  local d = a1 * b2 - a2 * b1;
  local dx = c1 * b2 - c2 * b1;
  local dy = a1 * c2 - a2 * c1;
  local x,y = dx / d, dy / d;
  return x,y
end

Теперь находим точку пересечения высот

function kramer(a1,b1,c1,a2,b2,c2)
  local d = a1 * b2 - a2 * b1;
  local dx = c1 * b2 - c2 * b1;
  local dy = a1 * c2 - a2 * c1;
  local x,y = dx / d, dy / d;
  return x,y
end
function TriangleOrthocenter(xa,ya,xb,yb,xc,yc)
	--Находим уравнение прямой AK: a1x + b1y = c1.
	local a1 = xc - xb;
	local b1 = yc - yb;
	local c1 = xa * (xc - xb) + ya * (yc - yb);

	--Находим уравнение прямой BL: a2x + b2y = c2.
	local a2 = xc - xa;
	local b2 = yc - ya;
	local c2 = xb * (xc - xa) + yb * (yc - ya);

	--Находим и выводим точку пересечения высот треугольника.
	return kramer(a1,b1,c1,a2,b2,c2);
end
print(TriangleOrthocenter(0,0,1,0,0,1))
print(TriangleOrthocenter(0,0,3,0,0,4))

Точка пересечения срединных перпендикуляров (описанная окружность тремя точками - circumcenter of triangle)

Около любого треугольника можно описать окружность, и только одну. Центром окружности, описанной около треугольника, является точка пересечения серединных ерпендикуляров к сторонам треугольника.

Расположение центра описанной окружности

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

Радиус описанной окружности треугольника

Радиус описанной окружности треугольника ABC может быть вычислен по формулам:
R = a / 2 SinA, R = b / 2 SinB, R = c / 2 SinC, R = abc / 4S,
где a, b и c – длины сторон треугольника ABC, S – его площадь.

Синус угла – это отношение противолежащего (дальнего) катета к гипотенузе в прямоугольном тр-ке. А как быть с произвольными тр-ками?
про синусы и косинусы

Дан треугольник. Найдите точку пересечения его срединных перпендикуляров.
Ввод
0 0
1 0
0 1
Ответ: 0.5 0.5

Срединный перпендикуляр треугольника (медиатриса треугольника) - прямая, которая перпендикулярна к стороне треугольника, ипроходит через ее середину.

собственный вариант решения (не верный)

Тут свои сложности. Так и не смог точно расчитать. Надо получить 0.5,0.5, при всех расчетах получаю 1,1. Видимо это из-за целых коэффициентов.

Действия:

находим точки. координаты середины отрезков AB,BC,CA
опускаем перпендикуляры из середин отрезков. Достаточно найти два уравнения прямых перпендикуляров. могут подойти примеры уравнений серединных перпендикуляров (поиск гугл)
находим точку пересечения перпендикуляров-прямых

пример

Вычислить координаты точки пересечения перпендикуляров, проведенных через середины сторон треугольника, вершинами которого служат точки A(2;3); B(0;–3); C(6;–3).

Найдем координаты середин сторон:

для AB точка A1:
Ax1 = (Bx+Cx)/2 = (0+6)/2 = 3
Ay1 = (By+Cy)/2 = (-3 -(-3))/2 = -3
A1(3; -3)

для BC точка B1:
Bx1=(Ax+Cx)/2=(2+6)/2=4
By1=(Ay+Cy)/2=(3-3)/2=0
B1(4;0)

для CA точка C1:
Cx1=(Ax+Bx)/2=(2+0)/2=1
Cy1=(Ay+By)/2=(3-3)/2=0
C1(1;0)

Тогда уравнения серединных перпендикуляров будут иметь следующий вид:

(x-x1)(y2-y1)-(y-y1)(x2-x1)=0 - косое произведение коллинеарности
или
(y2-y1)x + (x1-x2)y + x1(y1-y2)+y1(x2-x1)=0
или
ax+by+c=0
где a=y2-y1, b=x1-x2, c=x1(y1-y2)+y1(x2-x1)=a*x1+b*y1

--перпендикуляр из середины отрезка CA - черех точку C1
x-Cy1 / By-Ay = y-Cy1 / Ax-Bx
(x - 1) / (-3 - 3) = (y - 0) / (2 - 0)
x + 3y - 1 = 0;

--перпендикуляр из середины отрезка BC - черезку точку B1
x-Bx1 / Cy-Ay = y-Cy1 / Ax-Cx
(x - 4) / (-3 - 3) = (y - 0) / (2 - 6)
2x - 3y - 8 = 0;

--перпендикуляр из середины отрезка AB - через точку A1
x-Ax1 / Cy-By = y-Ay1 / Bx-Cx
(x - 3) / ( -3 + 3) = (y + 3) / (0 - 6)
x - 3 = 0.

Найдем точки пересечения:
x = 3
3 + 3y - 1 = 0
y = -2/3.

3 * 2 - 3y - 8 = 0
y = -2/3
M(3; -2/3).

Минусы: какие-то не точности. допускаю, что решено не правильно, видимо уравнение перпендикуляра найдено не верно. Я брал разные треугольники и вершины, и результат - радиусы одинаковые, но нет общей точки пересечения у разных пар перпендикуляров (это правильно?). Одна точка совпадала с тестом.

function midpoint(xa,ya,xb,yb)
	return (xa+xb)/2,(ya+yb)/2
end
--вектор нормали (перпендикулярный)
function NormalVectorLine(a,b,c)
	return a,b
end
--наименьший общий делитель между a,b gcd>0
function gcd(a, b)
	return b==0 and a or gcd(b,a%b)
end
--наименьший общий делитель между a,b,c
function nod(a, b, c)
	return gcd(gcd(a,b),c)
end

function EquationIntCoefficients(Px,Py,Qx,Qy)
	--находим коэ-ты уравнения
	local A,B = Py-Qy, Qx-Px
	local C = -A*Px - B*Py
	--далее нормируем коэ-ты
	
	--находим наибольший общий делитель 3 чисел
	local Z = nod(A,B,C)
	
	--коэф-ты делить на НОД
	A,B,C=A/Z,B/Z,C/Z
	
	--произведем нормировку знака
	if A<0 or (A==0 and B<0) then
		return -A,-B,-C
	end
	return A,B,C
end

--вектор нормали (перпендикулярный)
function NormalVectorLine(a,b,c)
	return a,b
end
EPS = 1E-9;
function EquationFloatCoefficients(Px,Py,Qx,Qy)
    local A,B = Py-Qy,Qx-Px
    local C,Z = -A*Px-B*Py , (A^2 + B^2)^0.5
    
	if A< EPS or (math.abs(A)<EPS and B<-EPS) then
		return -A/Z,-B/Z,-C/Z
	end
    return A/Z,B/Z,C/Z
end
function PerpendicularLine(x1,y1,a,b,c)

	--снимаем вектор нормали из ax+by+c=0
	local x2,y2=NormalVectorLine(a,b,c)
	
	--уравнение составим по точке x1,y1 и направляющему вектору x2,y2
	
	--уравнение перпендикулярной линии ax1+by1+c1=0 
	local a1,b1,c1 = EquationIntCoefficients(x2,y2,x1,y1)
	
    --проверка, что линия перпендикулярна
	if a1*(x1-x2) + b1*(y1-y2)==0 then 
	    print("перпедикулярны "..a1*(x1-x2) + b1*(y1-y2))
	else
	    print("не перпедикулярны "..a1*(x1-x2) + b1*(y1-y2))
	end
	
	return a1,b1,c1
end
--[[
function PerpendicularLine(x1,y1,a,b,c)

	--снимаем вектор нормали из ax+by+c=0
	local x2,y2=NormalVectorLine(a,b,c)
	
	--уравнение составим по точке x1,y1 и направляющему вектору x2,y2
	
	--уравнение перпендикулярной линии ax1+by1+c1=0 
	local a1,b1,c1 = (y2-y1),(x1-x2),a*(y2-y1)+b*(x2-x1)
	
    --проверка, что линия перпендикулярна
	local p = a1*(x2-x1) + b1*(y2-y1)
	if p==0 then 
	    print("перпедикулярны "..p)
	else
	    print("не перпедикулярны "..p)
	end
	
	return a1,b1,c1
end
]]
function LinesIntersect(a1,b1,c1, a2,b2,c2)
	local x = (b1 * c2 - b2 * c1) / (a1 * b2 - a2 * b1);
	local y = (a2 * c1 - a1 * c2) / (a1 * b2 - a2 * b1);
	return x,y
end


--треу-к можно обозначить вершинами A(x1,y1),B(x2,y2),C(x3,y3)
function PointCrossTriangularMediatrixs(x1,y1,x2,y2,x3,y3)
	
	--преобразуем запись в уравнение ax1+by1+c1=0
	local a1,b1 = y2-y1, x1-x2
	local c1 = -a1*x1 -b1*y1
	--преобразуем запись в уравнение ax2+by2+c2=0
	local a2,b2 = y3-y2, x2-x3
	local c2 = -a2*x2 -b2*y2
	--преобразуем запись в уравнение ax3+by3+c3=0
	local a3,b3 = y1-y3, x3-x1
	local c3 = -a3*x3 -b3*y3
	
	--находим точку середины отрезка AB
	local ax1,ay1=midpoint(x1,y1,x2,y2)
	--находим точку середины отрезка BC	
	local ax2,ay2=midpoint(x2,y2,x3,y3)
	--находим точку середины отрезка CA	
	local ax3,ay3=midpoint(x3,y3,x1,y1)

	--находим уравнения перпендикуляров, опущенных из середин
	local Ax1,By1,C1 = PerpendicularLine(ax1,ay1,a1,b1,c1)
	local Ax2,By2,C2 = PerpendicularLine(ax2,ay2,a2,b2,c2)
	local Ax3,By3,C3 = PerpendicularLine(ax3,ay3,a3,b3,c3)
	
	--находим точку пересечения серединных перпендикуляров O
	local px1,py1 = LinesIntersect(Ax1,By1,C1, Ax2,By2,C2)
	local px2,py2 = LinesIntersect(Ax2,By2,C2, Ax3,By3,C3)
	local px3,py3 = LinesIntersect(Ax3,By3,C3, Ax1,By1,C1)
	
	print(px1..','..py1)
	print(px2..','..py2)
	print(px3..','..py3)
	
	local d1 = ((x1-px1)^2 + (y1-py1)^2)^0,5
	local d2 = ((x2-px1)^2 + (y2-py1)^2)^0,5
	local d3 = ((x3-px1)^2 + (y3-py1)^2)^0,5
	print(d1..','..d2..','..d3)
	
end
print(PointCrossTriangularMediatrixs(0,0,1,0,0,1)) --Ответ: 0.5 0.5
print(PointCrossTriangularMediatrixs(2,3,0,-3,6,3)) --Ответ: 3; -2/3

вариант 1

источник

function TriangleCircumcenter(Ax,Ay,Bx,By,Cx,Cy)
local d = (2*(Ax*(By-Cy) +Bx*(Cy-Ay) +Cx*(Ay-By)))
local ux=((Ax^2+Ay^2)*(By-Cy) +(Bx^2+By^2)*(Cy-Ay) +(Cx^2+Cy^2)*(Ay-By))/d
local uy=((Ax^2+Ay^2)*(Cx-Bx) +(Bx^2+By^2)*(Ax-Cx) +(Cx^2+Cy^2)*(Bx-Ax))/d

return ux,uy
end
print(TriangleCircumcenter(0,0,1,0,0,1)) --Ответ: 0.5 0.5
print(TriangleCircumcenter(2,3,0,-3,6,3)) --Ответ: 3; -2/3

2 (укороченный)

источник

function TriangleCircumcenter2(Ax,Ay,Bx,By,Cx,Cy)
local d = 2*(Bx*Cy -By*Cx)
local ux=(Cy*(Bx^2+By^2)-By*(Cx^2+Cy^2))/d
local uy=(Bx*(Cx^2+Cy^2)-Cx*(Bx^2+By^2))/d
return ux,uy	
end
print(TriangleCircumcenter2(0,0,1,0,0,1)) --Ответ: 0.5 0.5
print(TriangleCircumcenter2(2,3,0,-3,6,3)) --Ответ: 3; -2/3

точки пересечения прямой и окружности

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

Здесь из рисунков и так все понятно. Мы имеем две точки пересечения, если расстояние от центра окружности до прямой меньше радиуса окружности. Одну точку касания, если расстояние от центра до прямой равно радиусу. И наконец, ни одной точки пересечения, если расстояние от центра окружности до прямой больше радиуса окружности.

Даны шесть чисел: координаты центра окружности, ее радиус (в первой строке), коэффициенты нормального уравнения прямой (во второй строке).

В первой строке одно число K, равное количеству точек пересечения прямой с окружностью. Далее в K строках координаты самих точек.
Ввод
1 1 1
1 -1 0
Ответ: 2 точки: (1.70711, 1.70711), (0.29289, 0.29289)
источник

EPS = 1E-9
function PointsIntersectBetweenLineAndCircle(r,cx,cy, a, b, c)

--найдём ближайшую к центру точку прямой
local x0,y0 = -a*c/(a*a+b*b), -b*c/(a*a+b*b);

if (c*c > r*r*(a*a+b*b)+EPS) then
	print("no points");
	return 0
elseif (math.abs(c*c - r*r*(a*a+b*b)) < EPS)then
	print("1 point");
	return 1,cx+x0,cy+y0
else
	local d = r*r - c*c/(a*a+b*b);
	local mult = math.sqrt(d / (a*a+b*b));
	local ax,ay,bx,by;
	ax = x0 + b * mult;
	bx = x0 - b * mult;
	ay = y0 - a * mult;
	by = y0 + a * mult;
	print("2 points");
	return 2,cx+ax,cy+ay,cx+bx,cx+by
end
end
print(PointsIntersectBetweenLineAndCircle(1,1,1,1,0,-2)) --Ответ: нет точек пересечении: 0
print(PointsIntersectBetweenLineAndCircle(1,1,1,1,-1,0)) --Ответ: 2 точки пересечении, (1.70711, 1.70711) (0.29289, 0.29289)

Точки касания окружности с указанной точкой

Линии могут пересекать окружность в двух точках, они называются секущими, а некоторые линии могут вообще не пересекать окружность. Линии, которые пересекают окружность в одной точке называются касательными линиями или просто касательными к окружности из заданной точки. Из одной точки можно провести только две касательные:

Рисунок выше показывает окружность с центром в точке O и точкой A вне окружности. Линии k,l,m и n выходят из точки A и пересекают окружность.

Линии k и l пересекают окружность в двух точках, и, следовательно, эти линии не являются секущими к окружности.
Линии m и n касаются окружности только в одной точке, и поэтому каждая из этих линий называется касательной к окружности из точки A.
Любая линия, проведенная над касательной m или под касательной n не будет пересекать окружность.

Может существовать бесконечное количество секущих к окружности из одной точки, но может существовать только две касательные к окружности из одной и той же точки.

Даны пять чисел: координаты центра окружности, ее радиус (в первой строке), координаты точки (во второй строке).

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

Ввод
1 1 1
2 2
Ответ:
2
1.0 2.0
2.0 1.0

еще можно было бы повернуть отрезок не от центра, а от внешней точки в 30 или 60 градусов. Откуда 30 и 60 градусов? это углы прямоугольного тр-ка. В зависимости от размеров могут меняться. Вспомним, что такое синус/косинус тр-ка.

касательная (решение через поворот)

источник

EPS = 1E-9
-- параллельны ли прямые?
function is_parallel_line(a1,b1,a2,b2)
    return math.abs(a1 * b2 - a2 * b1) <= EPS;
end
-- совпадают ли прямые?
function is_equal_line (a1,b1,c1,a2,b2,c2)
    return math.abs(a1*b2 - a2*b1) <= EPS and math.abs(a1*c2 - a2*c1) <= EPS and math.abs(b1*c2 - b2*c1) <= EPS;
end

-- пересечение двух прямых
function cross_line (a1,b1,c1,a2,b2,c2)
    if is_equal_line (a1,b1,c1,a2,b2,c2) then  return 2; end
    if is_parallel_line (a1,b1,a2,b2) then return 0; end

    local x = (b2*c1 - b1 * c2) / (a2 * b1 - a1 * b2);
    local y 
	if b1 ~= 0 then
		y=(-c1 - a1*x) / b1
	else
		y=(-c2 - a2*x) / b2
	end
    return x,y; 
end
function TouchPoints(x,y,cx,cy,radius)   --(point p,circle c)
	local d=((x-cx)^2+(y-cy)^2)^0.5
	local s=(d^2-radius^2)^0.5
	local alpha=math.atan(radius/s)
	local betta=(math.pi/2.)-alpha
	--np1 np1=turnof(p,betta,c.c)
	local x1=cx + ((x-cx)*math.cos(betta)-(y-cy)*math.sin(betta))
	local y1=cy + ((x-cx)*math.cos(betta)+(y-cy)*math.sin(betta))
	
	--nc1=turnof(c.c,2*pi-alpha,p)
	local x2=cx + ((cx-x)*math.cos(2*math.pi-alpha)-(cy-y)*math.sin(2*math.pi-alpha))
	local y2=cy + ((cx-x)*math.cos(2*math.pi-alpha)+(cy-y)*math.sin(2*math.pi-alpha))
	
	--np2=turnof(p,2*pi-betta,c.c)
	local x3=cx + ((x-cx)*math.cos(2*math.pi-betta)-(y-cy)*math.sin(2*math.pi-betta))
	local y3=cy + ((x-cx)*math.cos(2*math.pi-betta)+(y-cy)*math.sin(2*math.pi-betta))
	
	--nc2=turnof(c.c,alpha,p)
	local x4=cx + ((cx-x)*math.cos(alpha)-(cy-y)*math.sin(alpha))
	local y4=cy + ((cx-x)*math.cos(alpha)+(cy-y)*math.sin(alpha))

	local a1,b1=y1-cy,x1-cx
	local c1= -a1*cx - b1*cy
	
	local a2,b2=y2-y,x2-x
	local c2= -a2*x - b2*y
	
	local a3,b3=y3-cy,x3-cx
	local c3= -a3*cx - b3*cy
	
	local a4,b4=y4-y,x4-x
	local c4= -a4*x - b4*y
	
	local px1,py1 = cross_line(a1,b1,c1,a2,b2,c2)
	local px2,py2 = cross_line(a3,b3,c3,a4,b4,c2)
	return px1,py1, px2,py2
end

print(TouchPoints(2,2,1,1,1)) --Ответ: 1.0	2.0	2.4142135623731	1.0

мой собственный

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

--найти касательную точку
function FindTangents(Xc,Yc,Xo,Yo,R)
    local d = ((Xo-Xc)^2+(Yo-Yc)^2)^0.5
    if d>R then
        --local l = math.abs(d-R)
        --print(R,d,l)
        
		--угол наклона вектора-прямой
        local angle = math.atan2(Yo-Yc,Xo-Xc)
		--откладываем точку B на прямой
        local Bx = Xc + R*math.cos(angle)
        local By = Yc + R*math.sin(angle)
        --точки поворачиваем перпендикулярно от линии
        local Px1 = Bx + R*math.cos(angle+math.pi/2)
        local Py1 = By + R*math.sin(angle+math.pi/2)
        local Px2 = Bx + R*math.cos(angle-math.pi/2)
        local Py2 = By + R*math.sin(angle-math.pi/2)
        return Px1,Py1,Px2,Py2
    end
    
end
print(FindTangents(1,1,2,2,1)) --Ответ: 1.0	2.0	2.4142135623731	1.0

пересечение окружностей

ссылка
источник

EPS = 1E-9
-- пересечение прямой с окружностью
function cross_line_circle (a,b,c,x1,y1,r1)
	-- проекция центра окружности на прямую
	local k = (a*x1 + b*y1 + c) / (a*a + b*b);
	local x,y=x1 - a*k, y1 - b*k

    -- сколько всего решений?
    local flag = 0;
    local d = ((x1-x)^2 + (y1-y)^2)^0.5
	
    if (math.abs (d-r1) <= EPS)then flag = 1; 
    elseif (r1 > d)then flag = 2;
    else return 0;
	end
    -- находим расстояние от проекции до точек пересечения
    k = math.sqrt(r1 * r1 - d*d);
    local t = (b^2 +(-a)^2)^0.5
    -- добавляем к проекции векторы направленные к точкам пеерсечения

	local x1,y1= x - (-b) * k/t , y - a * k/t
	local x2,y2= x - b * k/t , y - (-a) * k/t
    return x1,y1,x2,y2,flag;
end
-- пересечение окружностей
function cross_circle(x1,y1,r1,x2,y2,r2)
    if (math.abs(x1-x2) <= EPS and math.abs(y1-y2) <= EPS and math.abs (r1-r2) <= EPS) then
        return 3;
    end
    local a = 2 * (x2 - x1);
    local b = 2 * (y2 - y1);
    local c = x1 * x1 + y1 * y1 - r1 * r1 - (x2 * x2 + y2 * y2 - r2 * r2);
    return cross_line_circle (a,b,c,x1,y1,r1);
end

-- положение точки относительно окружности
function point_in_circle (x,y, cx,cy,r)
    local d = ((x-cx)^2+(y-cy)^2)^0.5
    if math.abs(r-d) <= EPS then return 1; end
    if (r > d) then return 0; end
    return 2;
end

-- точки касания касательной с окружностью
function contact_points(x,y,cx,cy,r)
--(point p, circle c, point &p1, point &p2)
    local flag = point_in_circle (x,y, cx,cy,r);
    if (flag == 0)then return 0; end
    if (flag == 1)then
        return x,y,1;
    end  
    -- находим расстояние до точек касания
    local d = ((x-cx)^2+(y-cy)^2)^0.5
    local k = (d^2 - r^2)^0.5
    return cross_circle (x,y, k,cx,cy,r);
end

print(contact_points(2,2,1,1,1)) --Ответ: 1.0	2.0	2.4142135623731	1.0

РАССТОЯНИЕ ОТ ТОЧКИ ДО ПРЯМОЙ,ЛУЧА,ОТРЕЗКА

расстояние от точки до прямой линии (короче длина перпендикуляра)

длина перпендикуляра (взят из хгм)

источник

Возможна не точность работы пример.

--Находит длину перпендикуляра от отрезка, заданного Xa, Ya, Xb, Yb к точке, заданной x,y. Полезно при реализации заклинаний типа "Огненная стена", во избежание последовательных пиков юнитов по прямой.
function Perpendicular(x,y, Xa,Ya,Xb,Yb)
    return math.sqrt((Xa-x)^2 + (Ya-y)^2) * math.sin(math.atan2(y-Ya,x-Xa) - math.atan2(Yb-Ya,Xb-Xa))
end
print(Perpendicular(0,4,2,3,2,5))
print(Perpendicular(-200,10,-100,4,100,4))

второй способ - через площади

источник

--дистанция между точкой P(x,y) и линией, заданной через точки P1(x1,y1) и P2(x2,y2)
function dist_between_point_and_line(x,y,x1,y1,x2,y2)
	local len = ((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1))^0.5
	if len ~= 0 then
		 return math.abs((y2 - y1) * x - (x2 - x1) * y + x2 * y1 - x1 * y2)/len;
	else
		return 0
	end
end
print(dist_between_point_and_line(0,4,2,3,2,5))
print(dist_between_point_and_line(-200,10,-100,4,100,4))

третий способ

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

Программа должна вывести одно число: расстояние от данной точки до данной прямой.
Ввод
1 1
1 1 -1
Ответ: 0.70711

Если задано уравнение прямой Ax + By + C = 0, то расстояние от точки M(Mx, My) до прямой можно найти, используя следующую формулу
d = |A·Mx + B·My + C|/√(A^2 + B^2)

function distBetweenPointAndLine(x,y,a,b,c)
	return math.abs(a*x + b*y + c)/ math.sqrt(a^2 + b^2)
end
print(distBetweenPointAndLine(1,1,1,1,-1))

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

Дано шесть чисел: координаты точки (2,1), координаты начала (1,1) и конца вектора (0,2).
Программа должна вывести единственное число: расстояние от точки до луча, заданного вектором.
Ответ: 1.0

собственный способ

--дистанция между точкой P(x,y) и линией, заданной через точки P1(x1,y1) и P2(x2,y2)
function dist_between_point_and_line(x,y,x1,y1,x2,y2)
	local len = ((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1))^0.5
	if len ~= 0 then
		 return math.abs((y2 - y1) * x - (x2 - x1) * y + x2 * y1 - x1 * y2)/len;
	else
		return 0
	end
end
--направление вектора (a*b=0 - перпендикулярна (ортогональны),a*b>0 - в одном напра-нии, a*b<0 - в противоположных)
function scalar_product(x1,y1,x2,y2)
	return x1*x2 + y1*y2 --скалярное произведение векторов |a|*|b|*cos alpha. cos 0 = 1. 3 опер
end

function dist_between_point_and_ray(x,y,x1,y1,x2,y2)
	--если угол тупой <0, перпендикуляр не попадает на луч, значит, ищем расстояние
	if scalar_product(x-x1,y-y1,x2-x1,y2-y1)<0 then
		return ((x-x1)^2 + (y-y1)^2)^0.5 --расстояние
	else
		--иначе возвращаем длину перпендикуляра
		return dist_between_point_and_line(x,y,x1,y1,x2,y2)
	end
end

print(dist_between_point_and_ray(0,4,2,3,2,5))

другой код

function dist_point_point(x1,y1,x2,y2)
    return math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
end
 
function dist_point_line(x,y,x1,y1,x2,y2)
    local det = math.abs((y1-y2)*(x1-x) - (x1-x2)*(y1-y));
    x1=x1-x2; y1=y1-y2;
    det = det/math.sqrt(x1*x1 + y1*y1);
    return det;
end
 
function comp(x,y)
    return (math.abs(x-y) <= 1e-9);
end
 
function inRay(x,y,x1,y1,x2,y2)
    -- x, y must be in line with ray
    local kx1 = x2 - x1;
    local ky1 = y2 - y1;
    local d = dist_point_point(x1, y1, x2, y2);
    kx1 = kx1/d;
    ky1 = ky1/d;
    local kx2 = x - x1;
    local ky2 = y - y1;
    local d2 = dist_point_point(x1, y1, x, y);
    kx2 = kx2/d2;
    ky2 = ky2/d2;
    return (comp(kx1, kx2) and comp(ky1, ky2));
end
 
function dist_point_ray(x,y,x1,y1,x2,y2)
    local dpl = dist_point_line(x,y,x1,y1,x2,y2);
    local A = y2 - y1;
    local B = x1 - x2;
    local cf = math.sqrt(A*A + B*B);
    A = A/cf; --Normalize
    B = B/cf; --Normalize
    local xp1 = x + A * dpl;
    local yp1 = y + B * dpl;
    local xp2 = x - A * dpl;
    local yp2 = y - B * dpl;
    local dpl1 = dist_point_line(xp1, yp1, x1, y1, x2, y2);
    local dpl2 = dist_point_line(xp2, yp2, x1, y1, x2, y2);
    if (dpl2 < dpl1) then
        xp1,xp2=xp2,xp1
		yp1,yp2=yp2,yp1
    end
    if (inRay(xp1, yp1, x1, y1, x2, y2)) then
        return dpl;
    else
        return math.min(dist_point_point(x,y,x1,y1), dist_point_point(x,y,x2,y2));
	end
end

print(dist_point_ray(2,1,1,1,0,2))
print(dist_point_ray(-5,0,0,0,100,0))
print(dist_point_ray(0,10,0,0,100,0))

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

Находит ближайщее расстояние от точки до отрезка

Дано шесть чисел: координаты точки и координаты двух концов отрезка.
0,4
2,3
2,5
вывод: 2.0

первый способ

источник

--скалярное произведение
function scalar_product(x1,y1,x2,y2)
	return x1*x2 + y1*y2 --скалярное произведение векторов |a|*|b|*cos alpha. cos 0 = 1. 3 опер
end
function norm(x,y) -- norm = length of vector
	return math.sqrt(scalar_product(x,y,x,y))
end
function d(x1,y1,x2,y2)
	return norm(x1-x2,y1-y2)
end

--кратчвйшее расстояние от точки до отрезка
function distance_Point_to_Segment(x,y,x1,y1,x2,y2)
    local c1 = scalar_product(x-x1,y-y1,x2-x1,y2-y1);
    if ( c1 <= 0 ) then
        return d(x,y,x1,y1);
	end
    local c2 = scalar_product(x2-x1,y2-y1,x2-x1,y2-y1);
    if ( c2 <= c1 ) then
        return d(x,y,x2,y2);
	end
    local b = c1 / c2;
	
	local x0 = x1 + b*(x2-x1)
	local y0 = y1 + b*(y2-y1)
	
	return d(x,y,x0,y0);
end
print(distance_Point_to_Segment(0,4,2,3,2,5))
print(distance_Point_to_Segment(-200,10,-100,4,100,4))

второй способ

--кратчвйшее расстояние от точки до отрезка
function shortestDistance(x,y,x1,y1,x2,y2)
    local px,py=x2-x1,y2-y1;
    local temp=(px*px)+(py*py);
    local u=((x-x1)*px + (y-y1)*py) / (temp);
    if(u>1)then
        u=1;
    elseif(u<0)then
        u=0;
    end
    local x3,y3 = x1+u*px, y1+u*py;

    local dx,dy = x3-x, y3-y;
    local dist = math.sqrt(dx*dx + dy*dy);
    return dist;
end
print(shortestDistance(0,4,2,3,2,5))
print(shortestDistance(-200,10,-100,4,100,4))

третий способ

--кратчвйшее расстояние от точки до отрезка
function pDistance(x,y,x1,y1,x2,y2)
	local A,B,C,D = (x-x1),(y-y1),(x2-x1),(y2-y1);
	local dot = A*C + B*D;
	local len_sq = C*C + D*D;
	local param = -1;
	if (len_sq ~= 0)then --in case of 0 length line
		param = dot / len_sq;
	end
	local xx, yy;
	if (param < 0)then
		xx = x1;
		yy = y1;
	elseif (param > 1)then
		xx = x2;
		yy = y2;
	else
		xx = x1 + param * C;
		yy = y1 + param * D;
	end
	local dx = x - xx;
	local dy = y - yy;
	return math.sqrt(dx * dx + dy * dy);
end
print(pDistance(0,4,2,3,2,5))
print(pDistance(-200,10,-100,4,100,4))

расстояние между прямыми

вики

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

Расстояние между двумя прямыми линиями на плоскости — это наименьшее расстояние между любыми двумя точками, лежащими на линии. Или между точкой лежащей на прямой с другой параллельной прямой. В случае пересекающихся линий, расстояние между ними равно нулю, потому что минимальное расстояние между ними равно нулю (в точке пересечения); в то время как в случае двух параллельных линий, это перпендикуляр -расстояние от точки на одной прямой к другой прямой.

y = k*x + b1
y = k*x + b2

расстояние между двумя параллельными прямыми — это расстояние между двумя точками пересечения этих линий с перпендикуляром

y=kx*b - стандартное уравнение прямой с угловым коэффициентом

k = (y2-y1)/(x2-x1) -> уравнение составлено 2 точками

мини-преобразования

a = (y2-y1), b = (x1-x2), c = -a*x1 - b*y1 -> уравнение ax+by+c=0
k0 = a/b -> наклон прямой
k1 = -b/a -> наклон перпендикулярной прямой, для нормирования множителя еще прописывают так k0=-1/k1.

y = -x/k - ураневние перпендикулярной прямой

Это расстояние может быть найдено при решении системы линейных уравнений
y = k*x + b1
y = - x/k
и
y = k*x + b2
y = - x/k
чтобы получить координаты точек пересечения. Определяем координаты точки пересечения
x1 = (-b1*k)/(k^2+1)
y1 = b1/(k^2+1)
и
x2 = (-b2*k)/(k^2+1)
y2 = b2/(k^2+1)

Расстояние между точками
d = math.sqrt( (b1*k - b2*k)/(k^2+1) + (b2-b1)/(k^2+1) )

которое можно сократить, как
d = |b2-b1| / math.sqrt((k^2+1))

Если известны уравнения прямых в декартовой системе координат, то можно их записать:
ax1+by1+c1=0
ax2+by2+c2=0

где расстояние между прямыми можно записать так
d = |c2-c1| / math.sqrt((a^2+b^2)) -> тк линии параллельны, то множители-коэффициенты a1,b1 индентичны a2,b2

источник
пример-решебник с ответом

function distBetweenTwoLine(a1,b1,c1, a2,b2,c2)
	--если параллелльные линии
	if (a1*b2 - a2*b1) == 0 then
		local d = math.abs(c2-c1)/math.sqrt(a1^2+b1^2)
		return d
	end
	return 0
end
print(distBetweenTwoLine(1,-1,-2, 1,-1,3)) --ответ: 3.5355339059327

Расстояние от прямой до окружности

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

Выведите единственное число: расстояние от данной окружности до данной прямой.
Ввод
0 0 1
1 0 -2
Ответ: 1.0

function distBetweenPointAndCircle(x,y,radius,a,b,c)
	--находим длину перпендикуляра от точки до прямой
	local d = math.abs(a*x + b*y + c)/ math.sqrt(a^2 + b^2)

	--проверяем не пересекает ли окружность, то ищем расстояние от прямой до линии окружности
	if d>radius then
		d=d-radius
	end
	
	--если прямая пересекает окружность или касается ее, то будет длина перпендикуляра - расстоянике от линии до центра. Если нужно будет исключить такой расчет, просто обнулить d=d-radius

	return d
end
print(distBetweenPointAndCircle(0,0,1,1,0,-2))

прочее

Длина бисектриссы

Найти длины биссектрис a1, b1, c1 треугольника, если известны длины противоположных сторон a, b, c.

тесты

6, 7, 9 Ответ: 7.35803, 6.49923, 4.67652
3.5, 4.5, 5.5 Ответ: 4.66027, 3.79967, 2.88195
100000, 100000, 100000 Ответ: 86602.5, 86602.5, 86602.5
1, 1.118034, 1.118034 Ответ: 1, 0.898056, 0.898056

источник

--Возвращает длину биссектрисы к стороне A при сторонах A, B, C
function getL(c,a,b)
    local s = a + b;
    return math.sqrt(a * b * (s + c) * (s - c))/s;  --Формула длины биссектрисы через три стороны
end

тип треугольника (прямой, острый, тупой)

Определить, существует ли треугольник с заданными целочисленными длинами сторон a,b,c. Если да, то определить тип треугольника - остроугольный, тупоугольный или прямоугольный.

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

Для того, чтобы можно было построить треугольник, необходимо и достаточно выполнения трех неравенств треугольника, т.е.
(a+b>c)&(a+c>b)&(b+c>a).

Между прочим, из истинности этого условия следует также (a>0)&(b>0)&(c>0)

Далее, если h - максимальная из длин сторон a,b,c, a k,l -- длины двух других сторон, то треугольник будет:

прямоугольным при h^2 = k^2 + l^2,
остроугольным при h^2 < k^2 + l^2,
и тупоугольным при h^2 > k^2 + l^2.

источник

function TypeTriangleWithLenghts(a,b,c)
	
	if (a+b>c)and(a+c>b)and(b+c>a) then
		local h = math.max(a,b,c)
		local l = math.min(a,b,c)
		local k
		if h>a and a<l then k=a 
		elseif h>b and b<l then k=b
		else k=c end
		
		local t1,t2=(h^2),(k^2 + l^2)
		if t1==t2 then
			return 1 --прямоугольник тр-к 
		elseif t1>t2 then
			return 2 --остроуголльный тр-к
		else
			return 3 --тупоугольный тр-к
		end	
	end
	return false
end
function TypeTriangleWithVertex(x1,y1,x2,y2,x3,y3)
	local a = ((x2-x1)^2 + (y2-y1))^0.5 --1 и 2
	local b = ((x3-x2)^2 + (y3-y2))^0.5 --2 и 3
	local с = ((x1-x3)^2 + (y1-y3))^0.5 --3 и 1
	return TypeTriangleWithLenghts(a,b,c)
end

угол между прямыми

источник
В геометрии за угол между двумя прямыми принимается МЕНЬШИЙ угол, из чего автоматически следует, что он не может быть тупым.

Если прямые перпендикулярны, то за угол между ними можно принять любой из 4 углов.

Как найти угол между двумя прямыми? Существуют три основные формулы.

общих уравнении ax1+by1+c1=0, ax2+by2+c2=0

ax1 + by1 + c1 = 0
ax2 + by2 + c2 = 0

Из-за тригонометрических функции cos,tg нужно исключить 90 град, тк бесконечность.

Если a1*a2 + b1*b2 = 0 - прямые перпендикулярны

a1*a2 + b1*b2 ≠ 0 - то прямые не перпендикулярны и ориентированный угол Ф между ними можно вычислить с помощью формулы:
tg Ф = (|a1*b1|+|a2*b2|)/(a1*a2 + b1*b2)
И с помощью обратной функции легко найти сам угол, при этом используем нечётность арктангенса:
Ф = arctan(Ф)

function AngleBetweenTwoLines(a1,b1,c1, a2,b2,c2)
	--прямые не перпендикулярны
	if a1*a2 + b1*b2 ~= 0 then
		local angle = (math.abs(a1*b1)+math.abs(a2*b2))/(a1*a2 + b1*b2)
		angle=math.deg(math.atan(angle))
		return angle
	end
	return 90.
end
print(AngleBetweenTwoLines(2,-3,0, 1,3,-7)) ---52.12

из уравнении угловых к-тов y=k1x+b1,y=k2x+b2

Способ второй, он удобен, когда прямые заданы уравнениями с угловым коэффициентом:
y = k1x + b1
y = k2x + b2
Если 1+k1*k2=0, то прямые перпендикулярны
Если 1+k1*k2≠0, то ориентированный угол Ф между ними можно найти с помощью формулы:
tg Ф = k2-k1/1+k1*k2

К слову, из равенства 1+k1*k2=0 следует полезная взаимосвязь угловых коэффициентов перпендикулярных прямых: k1=-1/k

function AngleBetweenTwoLines(k1,k2)
	--прямые не перпендикулярны
	if 1+k1*k2~=0 then
		local angle = (k2-k1)/(1+k1*k2)
		angle=math.deg(math.atan(angle))
		return angle
	end
	return 90.
end
print(AngleBetweenTwoLines(2/3,-1/3)) ---52.12

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

cos a = p1*p2 / |p1|*|p2|
но здесь не принимается во внимание ориентация угла (по любому получится >= 0). Кроме того, он может оказаться тупым, и тогда придётся делать оговорку, что угол между прямыми – это меньший угол, и из Pi радиан (не из !) вычитать получившийся арккосинус

--возвращает направляющий вектор
function ParallelVectorLine(a,b,c)
	return -b,a
end
function AngleVectors(x1,y1,x2,y2)
    return math.acos((x1*x2+y1*y2)/((x1^2+y1^2)^0.5  * (x2^2+y2^2)^0.5))
end
function AngleBetweenTwoLines(a1,b1,c1, a2,b2,c2)
	
	--два направляющих вектора двух прямых
	local px1,py1 = ParallelVectorLine(a1,b1,c1)
	local px2,py2 = ParallelVectorLine(a2,b2,c2)
	
	local angle = math.deg(math.pi-AngleVectors(px1,py1,px2,py2))
	return angle
end
print(AngleBetweenTwoLines(2,-3,0, 1,3,-7)) ---52.12

Вписанная окружность

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

0 0
1 0
0 1
0.2928932188134525

function RadiusInscribedCircle(x1,y1,x2,y2,x3,y3)
	--длины сторон треугольника
	local a = ((x2-x1)^2 + (y2-y1)^2)^0.5
	local b = ((x3-x2)^2 + (y3-y2)^2)^0.5
	local c = ((x1-x3)^2 + (y1-y3)^2)^0.5 --если c неизвестна, можно найти c=(a^2 + b^2)^0.5
	--полупериметр
	local p = (a+b+c)/2
	
	local r = math.sqrt( (p-a)*(p-b)*(p-c)/p)
	return r
end
print(RadiusInscribedCircle(0,0,1,0,0,1))

Если упростить данную формулу для прямоугольного треугольника, воспользовавшись теоремой Пифагора, то мы получим следующее выражение:
r = (a+b-c)/2

Так как в равнобедренном треугольнике боковые стороны равны, то в формуле остаются только обозначения a и b, и ее вид упрощается из все того же первого радикала до следующей формы:
r = b/2 * math.sqrt((2*a -b)/(2*a +b))

В случае с равносторонним треугольником все еще гораздо проще, и его формула может быть выведена не только из формулы для произвольного треугольника, но также и из свойств высоты-медианы-биссектрисы, которые совпадают и делят любую из сторон на две равные части
r = a/2 * math.sqrt(3)

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

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

0 0
1 0
0 1
0.707106781186547

источник <= разные формулы описанных окружностей не только тр-ка, но и других геометрических фигур.

function RadiusCircumcircleToTriangle(x1,y1,x2,y2,x3,y3)
	--длины сторон треугольника
	local a = ((x2-x1)^2 + (y2-y1)^2)^0.5
	local b = ((x3-x2)^2 + (y3-y2)^2)^0.5
	local c = ((x1-x3)^2 + (y1-y3)^2)^0.5 --если c неизвестна, можно найти c=(a^2 + b^2)^0.5
	--полупериметр
	local p = (a+b+c)/2
	
	local r = a*b*c/(4*math.sqrt(p*(p-a)*(p-b)*(p-c)))
	return r
end
print(RadiusCircumcircleToTriangle(0,0,1,0,0,1))

Серединный перпендикуляр треугольника

источник

--найти середину между 3 числами
function math.mid(a,b,c,onlyMiddle)
	local Max = math.max(a,b,c)
	local Min = math.min(a,b,c)
	local Middle
	if Max > a and Min < a then
		Middle = a
	elseif Max > b and Min < b then
		Middle = b
	else
		Middle = c
	end
	if onlyMiddle then
		return Middle
	end
	return Max,Middle,Min
end

function TriangleMidPerpendicular(x1,y1,x2,y2,x3,y3)
	local a = ((x2-x1)^2 + (y2-y1)^2)^0.5
	local b = ((x3-x2)^2 + (y3-y2)^2)^0.5
	local c = ((x1-x3)^2 + (y1-y3)^2)^0.5
	local S = math.abs(x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2))/2
	
	--стороны связаны неравенствами a >= b >= c 
	a,b,c=math.mid(a,b,c)
	print(a,b,c)
	
	--длина перпендикуляра, опущенного из точки середины к точке пересечения всех перпендикуляров
	local pa = (2*a*S)/(a^2+b^2-c^2)
	local pb = (2*b*S)/(a^2+b^2-c^2)
	local pc = (2*c*S)/(a^2+b^2-c^2)
	return pa,pb,pc
end

Минимальная окружность, содержащую внутри себя треугольник. (короче это описанная окружность треугла с радиусом)

Дан треугольник. Найдите минимальную окружность, содержащую внутри себя треугольник.

Выведите три числа: координаты центра и радиус данной окружности.
Ввод

0 0
1 0
0 1
0.5 0.5 0.7071067811865476

По прошлым урокам "определить circumcenter" и "радиус описанной окружности" можно вычислить

function CircumcenterWithRadius(Ax,Ay,Bx,By,Cx,Cy)
local d = 2*(Bx*Cy -By*Cx)
local ux=(Cy*(Bx^2+By^2)-By*(Cx^2+Cy^2))/d
local uy=(Bx*(Cx^2+Cy^2)-Cx*(Bx^2+By^2))/d

--длины сторон треугольника
local a = ((Bx-Ax)^2 + (By-Ay)^2)^0.5
local b = ((Cx-Bx)^2 + (Cy-By)^2)^0.5
local c = ((Ax-Cx)^2 + (Ay-Cy)^2)^0.5 --если c неизвестна, можно найти c=(a^2 + b^2)^0.5
--полупериметр
local p = (a+b+c)/2
	
local r = a*b*c/(4*math.sqrt(p*(p-a)*(p-b)*(p-c)))

return ux,uy,r
end

print(CircumcenterWithRadius(0,0,1,0,0,1)) --Ответ: 0.5 0.5 0.7071067811865476

пересекает ли прямая окружность

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

--идея quq_CCCP
function IsLineCrossCircle(radius,cx,cy,px1,py1,px2,py2)

    px1,py1 = px1 - cx, py1 - cy
    px2,py2 = px2 - cx, py2 - cy

    local dx = px2 - px1 
    local dy = py2 - py1
    local a =  dx * dx + dy * dy 
    local b = 2.00 * ( px1 * dx + py1 * dy )
    local c = px1 * px1 + py1 * py1 - radius * radius 
        
    if ( -b < 0.00 ) then
        return ( c < 0.00 )
    elseif ( -b < ( 2.00 * a ) ) then
        return ( ( 4.0 * a * c - b * b ) < 0 )
    end
    return ( a + b + c < 0 )
end

Угол обзора

Даны пять чисел: координаты центра окружности, ее радиус (в первой строке), координаты точки, лежащей вне окружности (во второй строке).

Выведите единственное число: угол (в радианах), под которым видна данная окружность из данной точки.
Ввод
1 1 1
2 2
Ответ: 1.5707963267948966

Мне кажется нужно опеределить касательные точки, при таких данных когда известны цетр и радиус, и внешняя точка. Нам только и остается определить касательные. Возможно есть какие то способы

function AngleBetweenTwoVectors(dx1,dy1,dx2,dy2) --в радианах (для превращения в градусы заверните в Acos)
    return math.acos((dx1*dx2+dy1*dy2)/((dx1^2+dy1^2)^0.5  * (dx2^2+dy2^2)^0.5))
end

--найти угол обзора
function ViewingAngle(Xc,Yc,Xo,Yo,R)
    local d = ((Xo-Xc)^2+(Yo-Yc)^2)^0.5
    if d>R then
        --длина
        --local l = math.abs(d-R)
        --print(R,d,l)
        
        --угол наклона вектора
        local angle = math.atan2(Yo-Yc,Xo-Xc)
        --сдвигаем точку B впритык к окружности
        local Bx = Xc + R*math.cos(angle)
        local By = Yc + R*math.sin(angle)
        --
        local Px1 = Bx + R*math.cos(angle+math.pi/2)
        local Py1 = By + R*math.sin(angle+math.pi/2)
        local Px2 = Bx + R*math.cos(angle-math.pi/2)
        local Py2 = By + R*math.sin(angle-math.pi/2)
        
        return AngleBetweenTwoVectors(Px1-Xc,Py1-Yc,Px2-Xc,Py2-Yc)
    end
    
end
print(ViewingAngle(1,1,2,2,1)) --Ответ: 1.5707963267949

угол наклона прямой. угловой коэффициент прямой

ссылка
нормальное ур-е прямой имеет вид
Ax +By + C = 0
Представим x = 0, мы узнаем, что y = -C/B. То есть прямая пересекает ось ординат в этой точке.
А если подставить y = 0, то узнаем, что x = -C/A. То есть прямая пересекает ось абцисс в этой точке.

А зная, что угловой коэффициент это отношение y/x => -C/B : -C/A => -C*A/-C*B => A/B
k = A/B

как повернуть/наклонить прямую

ссылка
Даны коэ-ты прямой ax+by+c=0 => a,b,c и угол angle. Необходимо, получить новые коэффициенты прямой при повороте прямой

ax+by+c=0

x*a+y*b+c=0
может быть представлено в нормальной форме записи уравнения:
x*cos(Theta)+y*sin(Theta)-p=0
где
Theta = ArcTan(B/A) - угол между осью OX и началом координат нормальной формы записи уравнения к прямой
p = -C/Sqrt(A^2 + B^2) - расстояние от начала координат до линии (нормальная длина)

Если вы хотите повернуть прямую относительно начала координат (0б0) на угол alpha, просто создайте новое уравнение (обратите вниание на то же значение p):
beta = Theta + alpha
где theta - текущий угол наклона прямой ax+by+c=0, alpha - угол поворота относительно угла theta, beta - новый угол
x*cos(beta)+y*sin(beta)-p=0

Если вы хотите повернуть прямую вокруг произвольной точки (x0,y0):

нормальное расстояние от этой точки до прямой равно
d=x0*cos(theta)+y0*sin(theta)-p
новое уравнение будет
x*cos(beta)+y*sin(beta)-pnew=0
и сохранить нормальное расстояние:
d=x0*cos(theta)+y0*sin(theta)-pnew
так:
pnew=p+x0*(cos(beta)-cos(theta))+y0*(Sin(beta)-Sin(theta))

Поворот прямой

Даны четыре числа: коээфициенты нормального уравнения прямой и угол (в радианах, задан в виде действительного числа).

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

1 1 -1
1.5707963267948966
Ответ: 1.0 -1.0 1.0

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

function LineTurn(a,b,c,angle)
	local k
	if b~= 0 then
		k=-(-a-c)/b --из y=kx+b
	else
		k=0
	end

	local Cos,Sin=math.cos(k+angle),math.sin(k+angle)
	local x1= Cos-Sin
	local y1= Sin+Cos
	--a=y2-y1, 
	--b=x1-x2, 
	--c=x1(y1-y2)+y1(x2-x1)
	
	local a1 = -a*x1
	local b1 = -b*y1
	local c1 = (a1*y1 - b1*x1)-c
	
	return a1,b1,c1
end
print( LineTurn(1,1,-1,1.5707963267948966)) --(1.0 -1.0 1.0)