| Новости | Поиск | FAQ | Статьи | Книги | Новости VCL | | Форумы ЧАТ | Орешник | KOL и MCK |
Форумы -» Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

	« предыдущая ветвь | форум | следующая ветвь »

Пересечение отрезков. [Delphi, Алгоритмы]

Kobik ©   (2005-09-24 20:27:00) 

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


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. Там есть похожий алгоритм с реализацией на си, но в комментариях написано, что он не работает. Так что я даже не пробовал перевести.

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

---

Fenik   (2005-09-25 10:51:00) [1]

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

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;

---

MBo   (2005-09-25 07:25:00) [2]

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

---

grouzd[E]v   (2005-09-24 23:42:00) [3]

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

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

---

NE_Parovoz   (2005-09-24 21:14:00) [4]

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

---

grouzd[E]v   (2005-09-24 20:53:00) [5]

вот, от эмбриона своих несостоявшихся 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 ...

---

Наверх