# Thread: How to detect an intersection between two lines?

1. ## How to detect an intersection between two lines?

Hello.
As in the subject, how to do this? I've got this code (I'll do minor fixes later):
http://pastebin.com/f4d5572a7

TShapeVec is just a class that stores X and Y coords. FPoints is a TList object.

This solution seems working, but when I define points like these:
Code:
```    &#40;0; 0&#41;
&#40;1; 3&#41;
&#40;0; 5&#41;
&#40;10; 4&#41;```
Validate returns that those points intersect. :shock:

Do they really intersect or maybe the code is wrong? :?

2. ## How to detect an intersection between two lines?

I've found some source code on a dutch delphi forum,that shows how to determine line intersection.
I looked at the sourcecode and it's all english (AFAIK) :razz:

Here it is: http://www.nldelphi.com/Forum/attach...6&d=1144865795

It contains 2 line intersection algorithms (i guess both work the same), but one is a little more compact, and returns more info about the intersection.

You should try your coordinates with this code. You may find the problem with your source. :razz:

Hope this helps

3. ## How to detect an intersection between two lines?

chronozphere, this doesn't work either. But I think the problem is with these loops:
[pascal]
var
I, J: Integer;
begin
Result := True;

for I := 0 to FPoints.Count -4 do
for J := I + 1 to FPoints.Count -2 do
begin
if LinesCross(TShapeVec(FPoints.Items[I]).X,
TShapeVec(FPoints.Items[I]).Y,
TShapeVec(FPoints.Items[I + 1]).X,
TShapeVec(FPoints.Items[I + 1]).Y,
TShapeVec(FPoints.Items[J]).X,
TShapeVec(FPoints.Items[J]).Y,
TShapeVec(FPoints.Items[J + 1]).X,
TShapeVec(FPoints.Items[J + 1]).Y) then
begin
Result := False;
exit;
end;
end;
[/pascal]

Can anyone tell me what's wrong there? :?

4. ## How to detect an intersection between two lines?

Could you give us a little word what the code is supposed to do?

What information does FPoints hold?

5. ## How to detect an intersection between two lines?

Could you give us a little word what the code is supposed to do?
What information does FPoints hold?
Sure thing!

FPoints is a TList object and it stores TShapeVec objects:
[pascal]
{ .: TShapeVec :. }
TShapeVec = class(TObject)
public
{ Public declarations }
X, Y: Integer;
constructor Create(const AX, AY: Integer);
end;
[/pascal]

TShape stores points that describe a shape. It has a few other methods. Here's the snippet:
[pascal]
{ .: TShape :. }
TShape = class(TObject)
private
{ Private declarations }
FPoints: TList;

function GetPoint(const AIndex: Integer): TShapeVec;
procedure SetPoint(const AIndex: Integer; const Value: TShapeVec);
function GetCount(): Integer;
public
{ Public declarations }
destructor Destroy(); override;

procedure Delete(const AIndex: Integer);
procedure Clear();

function Validate(): Boolean;

procedure SaveToXML(const FileName: String);
procedure ImportFromStream(S: TMemoryStream);
procedure ExportToStream(S: TMemoryStream);

property Points[const AIndex: Integer]: TShapeVec read GetPoint
write SetPoint; default;
end;
[/pascal]

I've got a problem with Validate method, which is supposed to check if the lines doesn't intersect. Here is the code (not optimized so far):
http://pastebin.com/f4d5572a7

This procedure sometimes works correctly, sometimes not. :shock: I.e. it doesn't work for these points:
[pascal]
(0; 0)
(1; 3)
(0; 5)
(10; 4)
[/pascal]
It says these points intersect, but they don't!

Why doesn't it work? :cry:

6. ## How to detect an intersection between two lines?

We had chat on msn about this earlier to get this far. On my understanding the validate function should check whether any line intersect with each other and just that. Start and end are not connected so they are not polygons.

This was what i had in mind and they really should be correct numbers:
[pascal] for I := 0 to FPoints.Count -3 do
for J := I + 1 to FPoints.Count -2 do [/pascal]

FPoints-3 is the third last point where 3 points can form 2 lines that if overlapped should result in false. Problem was to find good line intersection function that works with end points.

7. ## How to detect an intersection between two lines?

Hi, this is our code for general purpose line intersection. It is used in our polypoint collision code. Hopefully it can work for you too. You pass the end points of the two lines and it will return the intersection coord and type.

[pascal]type
{ TP2DLineIntersection }
TP2DLineIntersection = (
liNone = 0,
liTrue = 1,
liParallel = 2
);

function P2D_LineIntersection(X1, Y1, X2, Y2, X3, Y3, X4, Y4: Integer; var X, Y: Integer): TP2DLineIntersection;
var
Ax,Bx,Cx,Ay,By,Cy,d,e, f, num: Integer;
offset: Integer;
x1lo,x1hi,y1lo,y1hi: Integer;
begin
Result := liNone;

Ax := x2-x1;
Bx := x3-x4;

if (Ax<0>0) then
begin
if (x1hi < x4) or (x3 < x1lo) then Exit;
end else
begin
if (x1hi < x3) or (x4 < x1lo) then Exit;
end;

Ay := y2-y1;
By := y3-y4;

if (Ay<0>0) then
begin
if (y1hi < y4) or (y3 < y1lo) then Exit;
end else
begin
if (y1hi < y3) or (y4 <y1lo>0) then
begin
if (d<0>f) then Exit;
end else
begin
if (d>0) or (d<f>0) then
begin
if (e<0>f) then Exit;
end else
begin
if (e>0) or (e<f) then Exit;
end;

if(f=0) then
begin
Result := liParallel;
Exit;
end;

num := d*Ax;
if SameSign(num, f) then
offset := f div 2
else
offset := -f div 2;
x := x1 + (num+offset) div f;

num := d*Ay;
if SameSign(num, f) then
offset := f div 2
else
offset := -f div 2;

y := y1 + (num+offset) div f;

Result := liTrue;
end;[/pascal]

8. ## How to detect an intersection between two lines?

Pyrogine~ disable html on your post, code and pascal tags don't correctly show the source on the forum