View Full Version : How to detect an intersection between two lines?

Brainer

28-10-2007, 03:54 AM

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

28-10-2007, 07:43 AM

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/attachment.php?attachmentid=3126&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

29-10-2007, 04:27 AM

chronozphere, this doesn't work either. :( But I think the problem is with these loops:

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;

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

JSoftware

29-10-2007, 05:23 AM

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

What information does FPoints hold?

Brainer

29-10-2007, 06:08 AM

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

What information does FPoints hold?

Sure thing! :D

FPoints is a TList object and it stores TShapeVec objects:

{ .: TShapeVec :. }

TShapeVec = class(TObject)

public

{ Public declarations }

X, Y: Integer;

constructor Create(const AX, AY: Integer);

end;

TShape stores points that describe a shape. It has a few other methods. Here's the snippet:

{ .: 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;

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:

(0; 0)

(1; 3)

(0; 5)

(10; 4)

It says these points intersect, but they don't!

Why doesn't it work? :cry:

User137

29-10-2007, 08:11 AM

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:

for I := 0 to FPoints.Count -3 do

for J := I + 1 to FPoints.Count -2 do

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

29-10-2007, 02:44 PM

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.

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;

arthurprs

29-10-2007, 02:58 PM

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

Brainer

29-10-2007, 03:58 PM

Please do, Pyrogine. Edit your post, please.

Pyrogine

29-10-2007, 05:27 PM

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?

Robert Kosek

29-10-2007, 05:32 PM

You will have to repaste your code. The posting process with Disable HTML unchecked mangles the code, so just unchecking the box does nothing by itself.

Pyrogine

29-10-2007, 05:48 PM

I see. Ok, what about now?

Brainer

29-10-2007, 07:03 PM

Okay, I've solved the problem. :) I checked out my math book and read that two segments with the same point intersect (i.e. 1;2 and 2;3). :shock:

That was my bad from the very beginning. :oops:

paul_nicholls

30-10-2007, 01:28 AM

Hi Brainer :-)

I'd just thought I'd let you know that the code you posted (http://pastebin.com/f4d5572a7) appears to be incorrect...

I believe the code should be this (ignoring optimizations):

function LinesCross(x0, y0, x1, y1, x2, y2, x3, y3 : Integer): Boolean;

var

D, AB, CD: Single;

begin

D := (x1 - x0) * (y3 - y2) - (y1 - y0) * (x3 - x2);

if (Abs(D) < 0.001) then

begin

Result := False;

exit;

end;

AB := ((y0 - y2) * (x3 - x2) -(x0 - x2) * (y3 - y2)) / D;

if (AB > 0.0) and (AB < 1.0) then

begin

CD := ((y0 - y2) * (x1 - x0) - (x0 - x2) * (y1 - y0)) / D;

if (CD > 0.0) and (CD < 1.0) then

begin

Result := True;

exit;

end;

end;

Result := False;

end;

It should only get to the innermost Begin-End block and make the result true if the lines do cross...

This page may help (http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/)

cheers,

Paul

Brainer

30-10-2007, 11:40 AM

Hello, Paul. :)

You know, right now I'm using a totally different code and everything seems working OK. Anyway, thanks for your post! ;)

Powered by vBulletin® Version 4.2.5 Copyright © 2020 vBulletin Solutions Inc. All rights reserved.