How to detect an intersection between two lines?

[Brainer]

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:

    (0; 0)
    (1; 3)
    (0; 5)
    (10; 4)

Validate returns that those points intersect. :shock:

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

[chronozphere]

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

[Brainer]

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? :?

[JSoftware]

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

What information does FPoints hold?

[Brainer]

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 }
constructor Create(); overload;
constructor Create(AShape: TShape); overload;
constructor Create(APoints: TArrOfPoints); overload;
destructor Destroy(); override;

procedure Add(const AX, AY: Integer);
procedure Delete(const AIndex: Integer);
procedure Clear();

function Validate(): Boolean;

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

property Points[const AIndex: Integer]: TShapeVec read GetPoint
write SetPoint; default;
property Count: Integer read GetCount;
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:

[User137]

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.

[Pyrogine]

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]

[arthurprs]

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

[Brainer]

Please do, Pyrogine. Edit your post, please.

[Pyrogine]

Oh, sorry. Not sure what happened. It looked ok when I view it so I assumed all was ok. I Disabled HTML, is it ok now?