Page 1 of 2 12 LastLast
Results 1 to 10 of 15

Thread: How to detect an intersection between two lines?

  1. #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:
        (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? :?

  2. #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
    Coders rule nr 1: Face ur bugz.. dont cage them with code, kill'em with ur cursor.

  3. #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. #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?
    Peregrinus, expectavi pedes meos in cymbalis
    Nullus norvegicorum sole urinat

  5. #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 }
    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:

  6. #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. #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]
    Jarrod Davis
    Technical Director @ Piradyne Games

  8. #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
    From brazil (:

    Pascal pownz!

  9. #9

    How to detect an intersection between two lines?

    Please do, Pyrogine. Edit your post, please.

  10. #10

    How to detect an intersection between two lines?

    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?
    Jarrod Davis
    Technical Director @ Piradyne Games

Page 1 of 2 12 LastLast

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
Comodo SSL