PDA

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! ;)