# PureBasic Forum

 It is currently Mon May 25, 2020 8:49 am

 All times are UTC + 1 hour

 Page 1 of 1 [ 12 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: Intersection of two line segmentsPosted: Thu Jan 24, 2013 3:42 pm

Joined: Thu Jun 07, 2007 3:25 pm
Posts: 3845
Location: Berlin, Germany
Hi,

calculating the intersection of two (infinite) lines or (finite) line segments is a problem which is pretty easy to understand, and so seems simple at the first glance. However, some special cases have to be taken into account, and "out there on the internet" I saw code that did not do so properly. In order to realize some typical cases, firstly I show several figures. These figures give the expected results, so that we can check whether the results of our code are correct.

If you are only interested in the code, go directly to the second post.

//Edit 2016-05-21:
• Extended the above text.
• Extended figure b.
• Changed the captions of the figures.

Fig. a                                                                                                     Fig. b
The lines and the segments intersect.                                                     The lines intersect;
the segments do not intersect.

Fig. c                                                                                                    Fig. d
The lines intersect;                                                                                The lines intersect;
an end point of one segment is on the other segment.                             an end point of one segment is on the other line,
but not on the other segment.

Fig. e                                                                                                    Fig. f
The lines are parallel.                                                                            The lines are coincident,
the segments are not in contact.

Fig. g                                                                                                     Fig. h
The lines are coincident;                                                                        The lines are coincident;
the segments share one end point.                                                          the segments share multiple points.

Fig. i                                                                                                     Fig. j
The lines are coincident;                                                                        The lines and the segments are coincident.
one segment contains the other segment.

The figures were created with the excellent open source program GeoGebra.

_________________
Please excuse my flawed English. My native language is PureBasic.
Search
RSBasic's backups

Last edited by Little John on Fri May 20, 2016 11:07 pm, edited 1 time in total.

Top

 Post subject: Re: Intersection of two line segmentsPosted: Thu Jan 24, 2013 3:43 pm

Joined: Thu Jun 07, 2007 3:25 pm
Posts: 3845
Location: Berlin, Germany
Works also with PB 5.20

The following procedure is based on C code from http://paulbourke.net/geometry/pointlineplane/. Thanks to Paul Bourke for the code, and thanks to IdeasVacuum for pointing to that website here on the forum.
My code is a corrected and extended version. The original code returns wrong results for examples f and g above. And it always returns only 1 point as result, whereas I decided to return 2 points as result if applicable, in order not to lose any information.

//Edit 2016-05-21:
• Changed the parameters that take the output (no linked list needed anymore).
• By means of the new optional parameter 'checkLines', now it's not only possible to check the intersection of two (finite) line segments, but also of two (infinite) lines.

Code:
EnableExplicit

#Epsilon = 0.000001

Structure PointD
x.d
y.d
EndStructure

Macro IsBetween (_x_, _a_, _b_)
; Is _x_ between _a_ and _b_?
; It doesn't matter whether _a_ is the minimum and _b_ is the maximum, or vice versa.
(((_a_) <= (_x_) And (_x_) <= (_b_)) Or ((_b_) <= (_x_) And (_x_) <= (_a_)))
EndMacro

Procedure.i Intersect_Segments (*p1.PointD, *p2.PointD, *p3.PointD, *p4.PointD,
*ps1.PointD, *ps2.PointD, checkLines.i=#False)
; -- Determine the intersection of two lines or two line segments (in 2 dimensions).
; in : *p1, *p2  : points on line a or segment a
;      *p3, *p4  : points on line b or segment b
;      checkLines: #True  for checking the intersection of two lines,
;                  #False for checking the intersection of two segments.
; out: *ps1        : intersection point (if existing), or
;      *ps1, *ps2  : endpoints of overlapping part of the segments (if existing)
;      return value: 0 if there is no intersection point
;                    1 if there is exactly one intersection point
;                    2 if the segments overlap (more than one point)
;                   -1 if the lines are coincident
;
; [http://www.purebasic.fr/english/viewtopic.php?f=12&t=53070]
Protected.d numera, numerb, denom, mua, mub
Protected.i ret=0

numera = (*p4\x-*p3\x)*(*p1\y-*p3\y) - (*p4\y-*p3\y)*(*p1\x-*p3\x)
numerb = (*p2\x-*p1\x)*(*p1\y-*p3\y) - (*p2\y-*p1\y)*(*p1\x-*p3\x)
denom  = (*p4\y-*p3\y)*(*p2\x-*p1\x) - (*p4\x-*p3\x)*(*p2\y-*p1\y)

If Abs(denom) >= #Epsilon                                        ; if the lines are not parallel
mua = numera / denom
mub = numerb / denom

If checkLines Or
(mua >= 0.0 And mua <= 1.0 And mub >= 0.0 And mub <= 1.0)  ; if the intersection is along the segments
*ps1\x = *p1\x + mua * (*p2\x-*p1\x)
*ps1\y = *p1\y + mua * (*p2\y-*p1\y)
ProcedureReturn 1
Else
ProcedureReturn 0
EndIf

ElseIf Abs(numera) < #Epsilon And Abs(numerb) < #Epsilon         ; if the lines are coincident
If checkLines
ProcedureReturn -1

Else                                                          ; do the segments share one or more points?
If IsBetween(*p1\x, *p3\x, *p4\x) And IsBetween(*p1\y, *p3\y, *p4\y)
*ps1\x = *p1\x
*ps1\y = *p1\y
ret + 1
EndIf
If IsBetween(*p3\x, *p1\x, *p2\x) And IsBetween(*p3\y, *p1\y, *p2\y)
If ret = 0
*ps1\x = *p3\x
*ps1\y = *p3\y
ret + 1
ElseIf *ps1\x <> *p3\x Or *ps1\y <> *p3\y
*ps2\x = *p3\x
*ps2\y = *p3\y
ret + 1
EndIf
EndIf
If IsBetween(*p2\x, *p3\x, *p4\x) And IsBetween(*p2\y, *p3\y, *p4\y)
If ret = 0
*ps1\x = *p2\x
*ps1\y = *p2\y
ret + 1
ElseIf ret = 1 And (*ps1\x <> *p2\x Or *ps1\y <> *p2\y)
*ps2\x = *p2\x
*ps2\y = *p2\y
ret + 1
EndIf
EndIf
If IsBetween(*p4\x, *p1\x, *p2\x) And IsBetween(*p4\y, *p1\y, *p2\y)
If ret = 1 And (*ps1\x <> *p4\x Or *ps1\y <> *p4\y)
*ps2\x = *p4\x
*ps2\y = *p4\y
ret + 1
EndIf
EndIf
ProcedureReturn ret                                        ; 0, 1, or 2
EndIf

Else                                                             ; if the lines are parallel, but not coincident
ProcedureReturn 0
EndIf
EndProcedure

CompilerIf #PB_Compiler_IsMainFile
; -- Demo

Macro ShowResult (_label_, _expected_result_, _checkLines_=#False)
Debug _label_ + ":"
count = Intersect_Segments(p1, p2, p3, p4, ps1, ps2, _checkLines_)
If count <> _expected_result_
Debug "ERROR: count = " + count
EndIf
If count = 0
Debug "no intersection"
ElseIf count = -1
Debug "coincident"
Else
Debug "(" + StrD(ps1\x,2) + ", " + StrD(ps1\y,2) + ")"
If count = 2
Debug "(" + StrD(ps2\x,2) + ", " + StrD(ps2\y,2) + ")"
EndIf
EndIf
EndMacro

Define.PointD p1, p2, p3, p4, ps1, ps2
Define.i count

; Example a: The lines and the segments intersect.
p1\x = 1.0 : p1\y = 3.0
p2\x = 3.0 : p2\y = 2.0
p3\x = 1.5 : p3\y = 1.0
p4\x = 3.0 : p4\y = 4.0
Debug "* Example a *"
ShowResult("Lines", 1, #True)
ShowResult("Segments", 1)
Debug "---------------"

; Example b: The lines intersect;
;            the segments do not intersect.
p1\x = 1.0 : p1\y = 3.0
p2\x = 1.8 : p2\y = 2.5
p3\x = 1.5 : p3\y = 1.0
p4\x = 3.0 : p4\y = 4.0
Debug "* Example b *"
ShowResult("Lines", 1, #True)
ShowResult("Segments", 0)
Debug "---------------"

; Example c: The lines intersect;
;            an end point of one segment is on the other segment.
p1\x = 1.0 : p1\y = 3.0
p2\x = 3.0 : p2\y = 2.0
p3\x = 2.0 : p3\y = 2.5
p4\x = 3.0 : p4\y = 4.0
Debug "* Example c *"
ShowResult("Lines", 1, #True)
ShowResult("Segments", 1)
Debug "---------------"

; Example d: The lines intersect;
;            an end point of one segment is on the other line,
;            but not on the other segment.
p1\x = 1.0 : p1\y = 3.0
p2\x = 3.0 : p2\y = 2.0
p3\x = 4.0 : p3\y = 1.5
p4\x = 3.0 : p4\y = 4.0
Debug "* Example d *"
ShowResult("Lines", 1, #True)
ShowResult("Segments", 0)
Debug "---------------"

; Example e: The lines are parallel.
p1\x = 1.0 : p1\y = 3.0
p2\x = 3.0 : p2\y = 2.0
p3\x = 2.0 : p3\y = 4.0
p4\x = 4.0 : p4\y = 3.0
Debug "* Example e *"
ShowResult("Lines", 0, #True)
ShowResult("Segments", 0)
Debug "---------------"

; Example f: The lines are coincident;
;            the segments are not in contact.
p1\x = 1.0 : p1\y = 3.0
p2\x = 3.0 : p2\y = 2.0
p3\x = 4.0 : p3\y = 1.5
p4\x = 5.0 : p4\y = 1.0
Debug "* Example f *"
ShowResult("Lines", -1, #True)
ShowResult("Segments", 0)
Debug "---------------"

; Example g: The lines are coincident;
;            the segments share one end point.
p1\x = 1.0 : p1\y = 3.0
p2\x = 3.0 : p2\y = 2.0
p3\x = 3.0 : p3\y = 2.0
p4\x = 5.0 : p4\y = 1.0
Debug "* Example g *"
ShowResult("Lines", -1, #True)
ShowResult("Segments", 1)
Debug "---------------"

; Example h: The lines are coincident;
;            the segments share multiple points.
p1\x = 1.0 : p1\y = 3.0
p2\x = 3.0 : p2\y = 2.0
p3\x = 2.0 : p3\y = 2.5
p4\x = 5.0 : p4\y = 1.0
Debug "* Example h *"
ShowResult("Lines", -1, #True)
ShowResult("Segments", 2)
Debug "---------------"

; Example i: The lines are coincident;
;            one segment contains the other segment.
p1\x = 1.0 : p1\y = 3.0
p2\x = 3.0 : p2\y = 2.0
p3\x = 0.5 : p3\y = 3.25
p4\x = 5.0 : p4\y = 1.0
Debug "* Example i *"
ShowResult("Lines", -1, #True)
ShowResult("Segments", 2)
Debug "---------------"

; Example j: The lines and the segments are coincident.
p1\x = 1.0 : p1\y = 3.0
p2\x = 3.0 : p2\y = 2.0
p3\x = 1.0 : p3\y = 3.0
p4\x = 3.0 : p4\y = 2.0
Debug "* Example j *"
ShowResult("Lines", -1, #True)
ShowResult("Segments", 2)
CompilerEndIf

_________________
Please excuse my flawed English. My native language is PureBasic.
Search
RSBasic's backups

Last edited by Little John on Fri May 20, 2016 11:19 pm, edited 2 times in total.

Top

 Post subject: Re: Intersection of two line segmentsPosted: Thu Jan 24, 2013 3:57 pm

Joined: Mon May 26, 2003 3:07 pm
Posts: 1477
Location: Nantes
Hi
Is it fast enough for sprite polygon collision ?

_________________
win8.1 x64 5.31 | IDE | PB plugin | Tools | Sprite | JSON | visual tool

Top

 Post subject: Re: Intersection of two line segmentsPosted: Thu Jan 24, 2013 3:58 pm

Joined: Thu Jun 07, 2007 3:25 pm
Posts: 3845
Location: Berlin, Germany
eddy wrote:
Hi
Is it fast enough for sprite polygon collision ?

Hi,

I don't know. Please test yourself.

Regards, Little John

_________________
Please excuse my flawed English. My native language is PureBasic.
Search
RSBasic's backups

Top

 Post subject: Re: Intersection of two line segmentsPosted: Thu Jan 24, 2013 4:29 pm

Joined: Wed Aug 31, 2005 11:09 pm
Posts: 3698
Location: Italy
Nice, thank you

_________________

Top

 Post subject: Re: Intersection of two line segmentsPosted: Thu Jan 24, 2013 4:30 pm

Joined: Thu Jan 10, 2008 1:30 pm
Posts: 1271
Location: Germany, Glienicke
eddy wrote:
Hi
Is it fast enough for sprite polygon collision ?

Little John code is for line-line-collision, a polygon is a surface, there you check whether a point is in the triangle.
Or you mean a polyline?

@Little John: line-line-collision is ok, but have you a code for check bézier curve collision?

_________________

Top

 Post subject: Re: Intersection of two line segmentsPosted: Thu Jan 24, 2013 5:30 pm

Joined: Thu Jun 07, 2007 3:25 pm
Posts: 3845
Location: Berlin, Germany
STARGÅTE wrote:
@Little John: line-line-collision is ok, but have you a code for check bézier curve collision?

I don't have such code, sorry.

_________________
Please excuse my flawed English. My native language is PureBasic.
Search
RSBasic's backups

Top

 Post subject: Re: Intersection of two line segmentsPosted: Thu Jan 24, 2013 5:35 pm

Joined: Mon May 26, 2003 3:07 pm
Posts: 1477
Location: Nantes
Sorry I meant polyline.

_________________
win8.1 x64 5.31 | IDE | PB plugin | Tools | Sprite | JSON | visual tool

Top

 Post subject: Re: Intersection of two line segmentsPosted: Thu Jan 24, 2013 5:53 pm

Joined: Thu Jun 24, 2004 8:51 am
Posts: 1480
Location: Germany
You should use the Chipmunk4PB wrapper for collision detection.

_________________
Belive!
<Wrapper>4PB, PB<game>, =QONK=, PetriDish, Movie2Image, PictureManager,...

Top

 Post subject: Re: Intersection of two line segmentsPosted: Fri Jan 25, 2013 8:24 pm
 Enthusiast

Joined: Thu Apr 14, 2011 6:07 pm
Posts: 342
Interesting, thanks for sharing and for the link

Top

 Post subject: Re: Intersection of two line segmentsPosted: Sun Dec 21, 2014 11:31 am

Joined: Mon Nov 25, 2013 6:41 am
Posts: 811
Top

 Post subject: Re: Intersection of two line segmentsPosted: Fri May 20, 2016 11:22 pm

Joined: Thu Jun 07, 2007 3:25 pm
Posts: 3845
Location: Berlin, Germany
Code extended and slightly improved.
For details see 1st and 2nd post.

_________________
Please excuse my flawed English. My native language is PureBasic.
Search
RSBasic's backups

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 12 posts ]

 All times are UTC + 1 hour

#### Who is online

Users browsing this forum: No registered users and 11 guests

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forum

Search for:
 Jump to:  Select a forum ------------------ PureBasic    Coding Questions    Game Programming    3D Programming    Assembly Programming    The PureBasic Editor    The PureBasic Form Designer    General Discussion    Feature Requests and Wishlists    Tricks 'n' Tips Bug Reports    Bugs - Windows    Bugs - Linux    Bugs - Mac OSX    Bugs - IDE    Bugs - Documentation OS Specific    AmigaOS    Linux    Windows    Mac OSX Miscellaneous    Announcement    Off Topic Showcase    Applications - Feedback and Discussion    PureFORM & JaPBe    TailBite