Пересечение отрезков.

← →
Kobik © (2005-09-24 20:27) [0]

Вот я математик, но наверно плохо геометрию учил :) Короче написал такую функцию:

function concurrence_of_lines(const x1,y1,x2,y2,x3,y3,x4,y4:integer;var rez_x,rez_y:integer):boolean; var a1,a2,a3,a4,a5,b1,b2:real; begin a1:=y4-y3;//переменные для оптимизации a2:=x4-x3; a3:=y2-y1; a4:=x2-x1; //находим точку пересечения ПРЯМЫХ if a3=0 then a5:=0 else if a4=0 then a5:=1000000 else a5:=a3/a4; b1:=(x3*a1+a2*(y1-y3-x1*a5)); b2:=(a1-a2*a5); if(b1=0)then rez_x:=0 else if b2=0 then begin concurrence_of_lines:=false;exit;end else begin b2:=b1/b2; rez_x:=round(b2); end; b1:=((b2-x1)*a3); if(b1=0)then rez_y:=y1 else if a4=0 then begin concurrence_of_lines:=false;exit;end else rez_y:=round(b1/a4)+y1; //далее делаем проверку на нахождение точки пересечения в ОТРЕЗКАХ if(rez_x>=min(x1,x2))and(rez_x<=max(x1,x2))and(rez_y>=min(y1,y2))and(rez_y<=max(y1,y2))and (rez_x>=min(x3,x4))and(rez_x<=max(x3,x4))and(rez_y>=min(y3,y4))and(rez_y<=max(y3,y4))then concurrence_of_lines:=true else concurrence_of_lines:=false; end;
Потестил - вроде все работает. Но потом, в игре иногда создается впечатление, что функция дает осечки. Из-за чего я так и не понял :(
Зашел на algolist.manual.ru. Там есть похожий алгоритм с реализацией на си, но в комментариях написано, что он не работает. Так что я даже не пробовал перевести.

Короче, у кого есть готовая функция, отзовитесь.

← →
grouzd[E]v © (2005-09-24 20:53) [1]

вот, от эмбриона своих несостоявшихся race =), правда без результата

function LinesCollisions(x1, y1, x2, y2, x3, y3, x4, y4 : single) : boolean;
var
t1, t2, a, b, c : single;
begin
result := false;
a := x3 - x1; b := x4 - x3; c := x2 - x1;
t1 := (c * (y1 - y3) + (y2 - y1) * a) / ((y4 - y3) * c - b * (y2 - y1));
if (t1 <= 0) or (t1 >= 1) then exit;
t2 := (a + t1 * b) / c;
result := (t2 > 0) and (t2 < 1);
end;

---
... we are walking on a thin line and you better avoid the risk ...

← →
NE_Parovoz © (2005-09-24 21:14) [2]

grouzd[E]v, так ты что в не участвуеш? :(

← →
grouzd[E]v © (2005-09-24 23:42) [3]

оффтоп
Неа - времени совсем нет ни на физику ни на ии. Школа + универ блнЪ =(

---
... we are walking on a thin line and you better avoid the risk ...

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

{Проверка пересечения двух отрезков}

function CrossLines(X1,Y1,X2,Y2, X3,Y3,X4,Y4: Integer): Boolean;
begin
Result := (((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;

Пересечение отрезков. Найти похожие ветки