[RESOLVED] Intersecting Lines

I have to admit that I haven't even thought about this problem, so it may be SERIOUSLY easy, but I'm designing something different, and know this place is a source for good suggestions, so here it is:

I have two objects in a database. These objects could be defined down to two points, and I almost certainly will do it that way, though the objects are 3D. Therefore, there is a line segment defined by the points (X1,Y1) - (X2,Y2).

I will also have another table of line segments. Without any thought, I can query the database to find that set of line segments that are near the target line segment, but I'm looking for a way to determine whether one of the line segments in the table intersect the target line segment.

Here's the reason: One piece of a robot brain will be examining gaps in the map it is creating of the world. A gap is an unexplored area between two objects (which have been identified by other modules based on touch and ultrasonic echo location). One thing about echo location is that I only get single points from an object, so I can't tell without some kind of investigation whether two echoes are separate objects, or the same (there's MUCH more going into it than that, but I don't want to write a book here). Therefore, this module will figure out which gaps should be investigated to see whether or not they are real, or just blind spots. To do this, the robot will have to figure out whether or not it has traveled through the gaps that have been found. Thus, the points mentioned are the objects, and the line segment table will hold the past travels of the bot. Of course, gap detection is something the bot will be doing only when it doesn't have something more important to do, but it will go into building a more accurate world map.

Re: Intersecting Lines

Hi Shaggy, I'm using the following Function to calculate intersections.
Note that it will Return a Intersection of X=0 and Y=0 if no intersection is found! Furthermore the found Intersection be outside of the Start/End of a line! I'm using another routine to check for that.

Code:

Public Function Intersection(ByVal Line1Start As PointF, ByVal Line1End As PointF, ByVal Line2Start As PointF, ByVal Line2End As PointF) As PointF 'Input Start and EnpPoint of Lines 'Output the Intersection Dim DX1 As Single Dim DX2 As Single Dim DY1 As Single Dim DY2 As Single Dim M1 As Single Dim M2 As Single Dim B1 As Single Dim B2 As Single Dim SymPoint As PointF DX1 = Line1End.X - Line1Start.X DX2 = Line2End.X - Line2Start.X DY1 = Line1End.Y - Line1Start.Y DY2 = Line2End.Y - Line2Start.Y If Not Math.Abs(DX1) <= 0.001 Then M1 = DY1 / DX1 End If If Not Math.Abs(DX2) <= 0.001 Then M2 = DY2 / DX2 End If B1 = Line1Start.Y - M1 * Line1Start.X B2 = Line2Start.Y - M2 * Line2Start.X If Math.Abs(DX1) <= 0.001 Or Math.Abs(DX2) <= 0.001 Then 'Special cases for North/South Lines If Math.Abs(DX1) <= 0.001 And DX2 <> 0 Then 'The Intersection has to be at Line1Start.X 'only the Y coordinate has to be calculated Intersection.X = Line1Start.X Intersection.Y = Line2Start.Y + M2 * (Line1Start.X - Line2Start.X) End If If Math.Abs(DX2) <= 0.001 And DX1 <> 0 Then 'The Intersection has to be at Line2Start.X 'only the Y coordinate has to be calculated Intersection.X = Line2Start.X Intersection.Y = Line1Start.Y + M2 * (Line2Start.X - Line1Start.X) End If If Math.Abs(DX1) <= 0.001 And Math.Abs(DX2) <= 0.001 Then 'both Lines run North/South 'An Intersection exists only if one of the Endpoints of one Line in within the Endpoints of the other Line! If Line1Start.Y < Line1End.Y Then If (Line2Start.Y >= Line1Start.Y And Line2Start.Y <= Line1End.Y) Then Intersection.Y = Line2Start.Y End If If (Line2End.Y >= Line1Start.Y And Line2End.Y <= Line1End.Y) Then Intersection.Y = Line2End.Y End If Else If (Line2Start.Y <= Line1Start.Y And Line2Start.Y >= Line1End.Y) Then Intersection.Y = Line2Start.Y End If If (Line2End.Y <= Line1Start.Y And Line2End.Y <= Line1End.Y) Then Intersection.Y = Line2End.Y End If End If Intersection.X = Line1Start.X End If Else If Not -1 * M1 = M2 Then 'Normal Case Intersection.X = (B2 - B1) / (M1 - M2) Intersection.Y = Line1Start.Y + M1 * (Intersection.X - Line1Start.X) Else 'the Lines are perpendicular (90°) 'symetrical solution SymPoint.Y = Line1Start.X * M2 + B2 Intersection.Y = Line1Start.Y + (SymPoint.Y - Line1Start.Y) / 2 Intersection.X = Intersection.Y * M1 + B1 End If End If Return Intersection End Function

Re: Intersecting Lines

I'll look it over this weekend when I get working on that module, but thanks for posting it, it'll save me a fair amount of time.

Re: Intersecting Lines

I thought of a rather novel way to do this, though I think that opus's code is basically what you were looking for.

My weird way involves translating and rotating the line segments with a dash of linear algebra, and then computing the possible intersection with only one or two "ifs". Logically it seems significantly more elegant than the slope-intercept method, but algorithmically they're probably nearly identical.

If anyone's interested in the specifics I could try to flesh it out more :)

Re: Intersecting Lines

I think you should flesh it out more and post it on here just on the principle, but if you'd like encouragement, I'd be interested in seeing what you produce.

As it turned out, I never even got close to dealing with this issue last weekend, despite spending two days working on the programs. Instead, I am totally bunged up over some networking issues, and may not get back to this piece for two more weeks. Very frustrating.

Re: Intersecting Lines

Quote:

Originally Posted by jemidiah

My weird way involves translating and rotating the line segments with a dash of linear algebra, and then computing the possible intersection with only one or two "ifs".

I have no idea what it will take (CPU-cycle wise) to do the translation/rotation of all line segments, however IMHO it will take more then one or two Ifs to do the rest.

Assume you have translated/rotated all lines, your line against all the others are checked does have y-values of 0 on both sides, x1 will be 0 as well, X2 will be the only one with a non zero value (or better a value of >0).
You have to check for each line:
Does the line have one Y-value at or above 0 and the other at or below 0?
If that's true:
If both X Values are between X1 and X2, there is an intersection.
If one X-Value is outside and the other is inside (or better in between X1 and X2) the obvious would be to believe that there is an intersection. But that's not correct, since the intersection of the y=0 -line could be outside of X1 and X2 (use a line which is nearly paralell!).
At this point I'll stop, because I don't think that all the needed Ifs will justify this other "weird" approach.

Re: Intersecting Lines

I'm not sure this may be of any help to you. The function below calculates the intersection not of 2 straight lines but of 2 segments defined by 2 straight lines. Sorry I haven't used point structures -like opus did- which might have clarified the code quite a bit, still you can fix it yourself quite easily.

Notice in the following code you can use either the parameter Alpha or Beta (though both are included) so you can modify the function removing either one. These parameters are optional as the function may be used just to check whether there is an intersection or not when the coordinates of the intersection are not needed.

VB Code:

Private Function SegmentIntersection(x1, y1, x2, y2, x3, y3, x4, y4, xint, yint, Optional Alpha, Optional Beta) As Boolean
 
    'Calculates the intersection (xint,yint) of the carrier straight lines
    'of segments P1(x1,y1)-P2(x2,y2) and P3(x3,y3)-P4(x4,y4)
    
    'If the straight lines are parallel, there is
    'no intersection and the function returns FALSE
    
    'If the intersection point belongs to both segments
    'the function returns True, else it returns False
    
    Dim a As Single, b As Single, c As Single, p As Single, q As Single
    Dim Gamma As Single
 
    SegmentIntersection = False
    
    a = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1)
    b = (x4 - x3) * (x4 - x3) + (y4 - y3) * (y4 - y3)
    c = (x4 - x3) * (x2 - x1) + (y4 - y3) * (y2 - y1)
    Gamma = a * b - c * c
    
    'If segments are parallel there is no intersection
    If Gamma = 0 Then Exit Function
        
    p = (x3 - x1) * (x2 - x1) + (y3 - y1) * (y2 - y1)
    q = (x3 - x1) * (x4 - x3) + (y3 - y1) * (y4 - y3)
    
    'In order to get to the intersection point, a vector
    'must be added to the vector (x1,y1) with modulus
    'equal to that of (x2-x1,y2-y1) times Alpha
    Alpha = (b * p - c * q) / Gamma
    'Same for Beta with respect to the other segment
    Beta = (c * p - a * q) / Gamma
    
    'If the fractions belong to [0,1] then the intersections occur on the segments
    'Else the segments do not intersect so return False
    If Alpha >= 0 And Alpha <= 1 And Beta >= 0 And Beta <= 1 Then
        xint = x1 + Alpha * (x2 - x1)
        yint = y1 + Alpha * (y2 - y1)
        'The following is ok as well (produces the same result):
        'xint = x3 + Beta * (x4 - x3)
        'yint = y3 + Beta * (y4 - y3)
        SegmentIntersection = True
    End If
        
End Function

Re: Intersecting Lines

@krtxmrtz:
your math is better than mine, since you need less Ifs to get a solution!

However what is your reasoning for Alpha and Beta? You have them asan optional input to your function, but you use them as a local variable?
Furthermore your function doesn't return the Intersection (you are not using Xint and Yint ByRef)?

Re: Intersecting Lines

The rotation is supposed to be accomplished by using the standard 2D rotation matrix, whose entries are all sines and cosines of the angle to be rotated. I was going to find the angle by taking the dot product of the segment and the positive x axis, which (when normalized) would yield the cosine of the angle of rotation, all without any trig. You can get the sine from the Pythagorean Theorem for an additional square root.

I was also going to cut down on the if checks needed by just checking if the product of Y1 and Y2 was nonpositive--you would pass the "if" when either Y1 or Y2 is on the x axis, or when the sign flips. It rolls most of the conditions into one fairly elegant check; if the check fails, there is clearly no intersection.

There are still two conceptual problems I haven't solved: first, if the first segment happens to be greater than 180 degrees from the x unit vector, my rotations won't work right (probably; it depends on the next issue). This can be solved easily by reversing the order of the points of the segment, but would require an additional if check if I can't come up with some nifty solution.

Second, the more difficult problem: checking for a true intersection (as Opus had asked about). I have what might be a nifty idea around this, but I don't know if it can be optimized enough to require just one (simple) if check.

...I haven't really had time to work on this, but I really like the first part's simplicity. If I can find a nice algorithm at the end and the beginning this would be a much cleaner approach than the standard brute force algebra, but that's a big "if" :)

Re: Intersecting Lines

@jemidiah: I'm looking foreward to see your solution, however I think the math of krtxmrtz solution is clean and easy enough. I have to admit that I don't understand all the claculations, but I'm going to use it instead of my posted function.
But I didin't start this thread!

Re: Intersecting Lines

Quote:

Originally Posted by opus

@krtxmrtz:
your math is better than mine, since you need less Ifs to get a solution!

However what is your reasoning for Alpha and Beta? You have them asan optional input to your function, but you use them as a local variable?
Furthermore your function doesn't return the Intersection (you are not using Xint and Yint ByRef)?

Yes, surprisingly enough they work as local variables, I don't know if they were supposed to, but the thing is it works. About the intersection, I'm passing the variables by reference, indeed, I really don't see your point. Convince yourself that the function does work.
I don't know where I placed my math notes that I keep in a notebook, as soon as I can lay my paws on them I'll transcribe an explanation about the method I've used.
By the way, if you implement the function using point structures it will become more readable (I'll do it myself one of these days)...

Re: Intersecting Lines

Wow, I'm glad I started this thread. I'm even (a little) glad that I got side tracked into solving some UDP networking issues. Got that problem solved, and it's posted in the networking section, so now I'm going to be back to working on this piece, and will be working on this part....maybe in a few hours, some non-programming stuff is getting in the way.

Re: Intersecting Lines

Non programming stuff, what could be trhat? Are we talking real-world, does it still exist, I got ot believe that we're in the matrix ;-)

@krtxmrtz:
On the ByRef topic, it looks I'm getting more and more used to VB2005, what was/is the default in VB6 (I have forgotten!)

I already made a function for VB2005, my Output is the Intersection itself, but I'm using two Boolean to tell wether the found intersection is Valid for the line-segment.
The only check left to do is the case for parallel lines that are on top of each other, in my application I want to get a point result for that case.

Code:

Public Function Intersection(ByVal Line1Start As PointF, ByVal Line1End As PointF, ByVal Line2Start As PointF, ByVal Line2End As PointF, ByRef Check1 As Boolean, ByRef Check2 As Boolean) As PointF 'Input Start and Endpoint of Lines 'Output the Intersection and Check1/ Check2 'Intersection only valid if at least one Check is true! 'Math copyright by krtxmrtz!! 'Calculates the intersection of the carrier straight lines 'of segments Line1Start-Line1End and Line2Start-Line2End 'If the straight lines are parallel, there is 'no intersection and the function returns for both Check FALSE 'If the intersection point belongs to both segments 'the function returns True for both. Dim a As Single, b As Single, c As Single, p As Single, q As Single Dim Gamma As Single a = (Line1End.X - Line1Start.X) * (Line1End.X - Line1Start.X) + (Line1End.Y - Line1Start.Y) * (Line1End.Y - Line1Start.Y) b = (Line2End.X - Line2Start.X) * (Line2End.X - Line2Start.X) + (Line2End.Y - Line2Start.Y) * (Line2End.Y - Line2Start.Y) c = (Line2End.X - Line2Start.X) * (Line1End.X - Line1Start.X) + (Line2End.Y - Line2Start.Y) * (Line1End.Y - Line1Start.Y) Gamma = a * b - c * c 'If segments are parallel there is no intersection If Gamma = 0 Then Check1 = False Check2 = False Exit Function End If p = (Line2Start.X - Line1Start.X) * (Line1End.X - Line1Start.X) + (Line2Start.Y - Line1Start.Y) * (Line1End.Y - Line1Start.Y) q = (Line2Start.X - Line1Start.X) * (Line2End.X - Line2Start.X) + (Line2Start.Y - Line1Start.Y) * (Line2End.Y - Line2Start.Y) 'In order to get to the intersection point, a vector 'must be added to the vector (line1Start) with modulus 'equal to that of (line1end.x-line1start.x,line1send.y-line1stasrt.y) times Alpha Dim Alpha As Single = (b * p - c * q) / Gamma 'Same for Beta with respect to the other segment Dim Beta As Single = (c * p - a * q) / Gamma Schnittpunkt.X = Line1Start.X + Alpha * (Line1End.X - Line1Start.X) Schnittpunkt.Y = Line1Start.Y + Alpha * (Line1End.Y - Line1Start.Y) 'If the fractions belong to [0,1] then the intersections occur on the segments 'Else the segments do not intersect If Alpha >= 0 And Alpha <= 1 And Beta >= 0 And Beta <= 1 Then Check1 = True Check2 = True ElseIf (Alpha < 0 Or Alpha > 1) And Beta >= 0 And Beta <= 1 Then Check1 = False Check2 = True ElseIf Alpha >= 0 And Alpha <= 1 And (Beta < 0 Or Beta > 1) Then Check1 = True Check2 = False ElseIf (Alpha < 0 Or Alpha > 1) And (Beta < 0 Or Beta > 1) Then Check1 = False Check2 = False End If End Function

Re: Intersecting Lines

Well, I never got around to it, but ended up working on something else, instead. Covered lots of ground, just not this particular ground.

The default in .NET is ByVal, but in VB6 it was ByRef. It got swapped.

Re: Intersecting Lines

Quote:

Originally Posted by Shaggy Hiker

The default in .NET is ByVal, but in VB6 it was ByRef. It got swapped.

Thanks Shaggy.

BTW, although I'm not 100%-sure, I believe that the Math approach from krtxmrtz is working in the way you where thinking. Look at the final check, where Alpha and Beta are checked wether they are within [0,1].
I hope he [krtxmrtz] finds his math notes.

Re: Intersecting Lines

Quote:

Originally Posted by opus

...@krtxmrtz:
On the ByRef topic, it looks I'm getting more and more used to VB2005, what was/is the default in VB6 (I have forgotten!)

I think the default is ByRef.

Quote:

Originally Posted by opus

...
The only check left to do is the case for parallel lines that are on top of each other, in my application I want to get a point result for that case.

OK, hang on...
I seem to have mislaid my notes, however I decided to derive the whole thing again. It turns out to be much easier than the code I posted but I found a flaw: you actually need to calculate both alpha and beta (yet the code seems to work for me in the present shape that I posted above), therefore just wait a little longer and I'll post my derivation, then you can check it up thoroughly.
Btw, the case where both segments are on the same carrier line is easy to pick up.

1 Attachment(s)

Re: Intersecting Lines

Here's a word document with my derivation. I wrote it a little hurriedly so please let me know if there's some typo, mistake or inconsistency of any kind.

I don't know where the heck the code in post #7 came from, probably it's correct but I have yet to study it in depth.

Re: Intersecting Lines

Quote:

Originally Posted by krtxmrtz

I don't know where the heck the code in post #7 came from, probably it's correct but I have yet to study it in depth.

I feel better now, it doesn't happen to me only!

Re: Intersecting Lines

Hey krtxmrtz,
I used your document to rework the Function (only in VB2005, if you need it in VB6 let me know).
I haven't completed the checks in case of LineSegments on a Line, maybe soemone else could step in :-)

Code:

Private Function Intersection(ByVal Line1Start As PointF, ByVal Line1End As PointF, ByVal Line2Start As PointF, ByVal Line2End As PointF, ByRef Check1 As Boolean, ByRef Check2 As Boolean) As PointF 'Input Line1Start , Line1End, Line2Start, Line2End 'Output Booleans Check1/Check2 are True if Intersection exists on both LineSegments! 'If an intersection is found outside a segment, the respective Check will be False! Dim Determinante As Single Dim DeterminanteS As Single Dim DeterminanteT As Single Dim S As Single Dim T As Single Determinante = (Line1End.Y - Line1Start.Y) * (Line2End.X - Line2Start.X) - (Line1End.X - Line1Start.X) * (Line2End.Y - Line2Start.Y) DeterminanteS = (Line2Start.Y - Line1Start.Y) * (Line2End.X - Line2Start.X) - (Line2Start.X - Line1Start.X) * (Line2End.Y - Line2Start.Y) DeterminanteT = (Line2Start.Y - Line1Start.Y) * (Line1End.X - Line1Start.X) - (Line2Start.X - Line1Start.X) * (Line1End.Y - Line1Start.Y) If Determinante = 0 Then 'The LineSegments are either parallel or identical If DeterminanteS <> 0 Or DeterminanteT <> 0 Then 'the LineSegments only parallel, but not on the same Line, no Intersection! Check1 = False Check2 = False Exit Function Else 'both LineSegments are on the same Line, however they could be seperated! 'TOBE COMPLETED!!! End If Else S = DeterminanteS / Determinante If S < 0 Or S > 1 Then 'Intersection is outside of Line1Segment! Check1 = False Else Check1 = True End If T = DeterminanteT / Determinante If T < 0 Or T > 1 Then 'Intersection is outside of Line2Segment! Check2 = False Else Check2 = True End If Intersection.X = Line1Start.X + S * (Line1End.X - Line1Start.X) Intersection.Y = Line1Start.Y + S * (Line1End.Y - Line1Start.Y) End If End Function

Re: Intersecting Lines

Quote:

Originally Posted by opus

Hey krtxmrtz,
I used your document to rework the Function (only in VB2005, if you need it in VB6 let me know)...

It certainly looks more readable now... and I hope it works!

No problem about converting to VB6, I wrote this function long ago before I even knew that such a thing as UDT existed... Next time I need to use the function I will do the conversion myself. Thanks anyway.

Re: Intersecting Lines

Looks good.

Last night I realized that my original question had fallen out of date. I realized that I have a totally different way to solve the original question that has nothing to do with line segments, but with logic. However, I now believe that the issue of line segments will be an issue in possibly two other modules in the code.

Re: Intersecting Lines

I'm think I have a way to check for the case when the LineSegments are parallel and are on the same Line.
PseudoCode:
For Each EndPoint of LineSegment A check wether the distance to each EndPoint of LineSegment B is equal or less then the Segment distance of LineSegment B. If this is True (for both EndPoints of LineSegment B) the Point is on LineSegment B.

Actually we don't have to calculate the correct distance-value, we can ommit the SquareRooting because we only check the relation between those values.

That way we need to calculate 6 Distances (without the SquareRoot) and do 4 If-Thens Checks.

You'll have to wait until Friday or Saturday to have that incooperated into the Function posted above. (Some real-live problems have to be solved!)

Re: Intersecting Lines

See? Real life gets in the way.

I won't be getting to this part for a couple of months at this rate. I realized last night that before the robot creates a track that crosses the line segment, the question of whether or not it CAN cross the line segment will have been answered. Though as I write this, it occured to me that I might be able to use the code MUCH sooner, because it would allow me to determine whether or not the bounding box around an object crosses a line segment. Four line segments, and if any one of them touches or crosses, then that's all I need to know.

By the way, after looking at that code, I decided to test whether (X-x)*(X-x) (as you have) is faster than (X-x)^2. I put both into my test app, and the way you have it was VASTLY faster. Therefore, don't use ^ unless you really need to. This may not be true if you are doing anything other than simply squaring the argument.

Re: Intersecting Lines

Quote:

Originally Posted by opus

I'm think I have a way to check for the case when the LineSegments are parallel and are on the same Line...

Wait a minute, this case was already dealt with in the document I attached to post #17, wasn't it? First you test whether the segments are parallel. If they are then you additionally test if they are on the same carrier line.

Re: Intersecting Lines

Quote:

Originally Posted by Shaggy Hiker

...By the way, after looking at that code, I decided to test whether (X-x)*(X-x) (as you have) is faster than (X-x)^2. I put both into my test app, and the way you have it was VASTLY faster. Therefore, don't use ^ unless you really need to. This may not be true if you are doing anything other than simply squaring the argument.

I think this is always true no matter what the variable type is. The more sophisticated the operation, the longer it takes. So * is faster than ^ but I haven't checked if, say, x + x + x is faster than 3*x, not very useful though, even if it is.

Re: Intersecting Lines

Quote:

Originally Posted by Shaggy Hiker

By the way, after looking at that code, I decided to test whether (X-x)*(X-x) (as you have) is faster than (X-x)^2. I put both into my test app, and the way you have it was VASTLY faster. Therefore, don't use ^ unless you really need to. This may not be true if you are doing anything other than simply squaring the argument.

Exactly this topic has been discussed AND benchmarked in depth somewhere in VBForums (I'd guess 3 or 4 years ago), and with the same result you found!

Re: Intersecting Lines

Quote:

Originally Posted by krtxmrtz

First you test whether the segments are parallel. If they are then you additionally test if they are on the same carrier line.

I see/understand the test for parallel, but I don't see/understand any checking for the same carrier line (maybe it's my stupidity!)

Re: Intersecting Lines

Quote:

Originally Posted by opus

I see/understand the test for parallel, but I don't see/understand any checking for the same carrier line (maybe it's my stupidity!)

Well, if they are parallel, check if the coordinates of, say, P₂ produce an identity when substituted in the equation of the carrier line of segment P₃-P₄, then P₂ (and of course P₁) will be on that line.

Re: Intersecting Lines

I guess you are refering to this line:
(y3 – y1)(x2 – x1) = (x3 – x1)(y2 – y1)

This will be true if Point x3;y3 is on the line that goes through the points x1;y2 and x2;y2, however we are looking for a check that tells wether x3;y3 is between those points!

For example:
Line 1
x1;y1 [0;0]
x2;y2 [0;2]
Line 2
x3;y4 [0;3]
x4;y4 [0;4]
Both lines are parallel, but they are NOT overlapping.
Check for parallel:
(y4 – y3)(x2 – x1) = (x4 – x3)(y2 – y1)
(4-3)(0-0)=(0-0)(2-0)
0=0 hence parallel

Check if x3;y3 is on Line
(y3 – y1)(x2 – x1) = (x3 – x1)(y2 – y1)
(3-0)(0-0)=(0-0)(2-0)
0=0
That would tell they are overlapping, which they don't!!

Re: Intersecting Lines

Quote:

Originally Posted by krtxmrtz

I think this is always true no matter what the variable type is. The more sophisticated the operation, the longer it takes. So * is faster than ^ but I haven't checked if, say, x + x + x is faster than 3*x, not very useful though, even if it is.

I don't think I'd benchmark that one. The answer is this:

If x is an integer type then

X+X+X is FAR faster than 3*x

if x is a decimal type then

X+X+X should be slower than 3*x

The reason is that for integer math, the addition is in the RISC subset of the instructions on an x86 processor, so it is among the fastest of all operations, whereas the integer multiplication, while still in the instruction set of the processor, is one of the slower instructions. You can't get actual timing anymore, because there are so many factors going into the actual timing of the instructions that the exact timing for any particular instruction is kind of fluid.

For the floating point, addition is very tough, while multiplication is relatively easy. Both are off on the FPU of the CPU, and the timing for them is a bit vague, as well, but back on the first pentiums, floating point mult and div was supposed to be faster than floating point addition or subtraction (my tests at the time confirmed that, though I have recently found that it may not be true any longer). Integer addition and subtraction should be far faster than any of the others, though.

Re: Intersecting Lines

Quote:

Originally Posted by opus

Exactly this topic has been discussed AND benchmarked in depth somewhere in VBForums (I'd guess 3 or 4 years ago), and with the same result you found!

I vaguely remember the subject, and may have participated, since it's the kind of topic I would tend to try out.

Re: Intersecting Lines

Quote:

Originally Posted by opus

...however we are looking for a check that tells wether x3;y3 is between those points!
...

Oh, is that what you meant!? Sorry I hadn't grasped it.

Well, once you're sure they are parallel and on the same carrier line, all that's left to do is check whether or not the following is true:

x₁ <= x₃ AND x₁ <= x₄ AND x₂ >= x₃ AND x₂ >= x₄

or alternatively you can do the same test using y instead of x. Of course, if it's true for x then it will be for y and vice versa since they are on the same line.

This is the case the segment [P₁,P₂] contains the segment [P₃,P₄]. You can easily test for the opposite case.

Re: Intersecting Lines

Doing the check for that situation would need several IFs, since one line-segment could be only overlapping. You have to make sure that the points are in some order for decrease the needed checks [what if x1 >x2 in your example?].

I would go for this check in the complete function:

Code:

Private Function Intersection(ByVal Line1Start As PointF, ByVal Line1End As PointF, ByVal Line2Start As PointF, ByVal Line2End As PointF, ByRef Check1 As Boolean, ByRef Check2 As Boolean) As PointF 'Input Line1Start , Line1End, Line2Start, Line2End 'Output Booleans Check1/Check2 are True if Intersection exists on both LineSegments! 'If an intersection is found outside a segment, the respective Check will be False! Dim Determinante As Single Dim DeterminanteS As Single Dim DeterminanteT As Single Dim Dist1 As Single Dim Dist2 As Single Dim Dist11 As Single Dim Dist12 As Single Dim Dist21 As Single Dim Dist22 As Single Dim S As Single Dim T As Single Determinante = (Line1End.Y - Line1Start.Y) * (Line2End.X - Line2Start.X) - (Line1End.X - Line1Start.X) * (Line2End.Y - Line2Start.Y) DeterminanteS = (Line2Start.Y - Line1Start.Y) * (Line2End.X - Line2Start.X) - (Line2Start.X - Line1Start.X) * (Line2End.Y - Line2Start.Y) DeterminanteT = (Line2Start.Y - Line1Start.Y) * (Line1End.X - Line1Start.X) - (Line2Start.X - Line1Start.X) * (Line1End.Y - Line1Start.Y) If Determinante = 0 Then 'The LineSegments are either parallel or identical If DeterminanteS <> 0 Or DeterminanteT <> 0 Then 'the LineSegments only parallel, but not on the same Line, no Intersection! Check1 = False Check2 = False Exit Function Else 'both LineSegments are on the same Line, however they could be seperated! 'the NEW Check! 'both LineSegments are on the same Line, however they could be seperated! 'Two LineSegments on a identical Line have an overlapp if the distance of one EndPoint to 'the Start and EndPoint of the other LineSegment is less then the distance of this other LineSegment! 'for all distances, the squareroot is ommited, because only the relation between distances is checked! 'Length of Line1 Dist1 = (Line1End.X - Line1Start.X) * (Line1End.X - Line1Start.X) + (Line1End.Y - Line1Start.Y) * (Line1End.Y - Line1Start.Y) 'Length of Line2 Dist2 = (Line2End.X - Line2Start.X) * (Line2End.X - Line2Start.X) + (Line2End.Y - Line2Start.Y) * (Line2End.Y - Line2Start.Y) 'Distance from Line1Start to Line2Start Dist11 = (Line1Start.X - Line2Start.X) * (Line1Start.X - Line2Start.X) + (Line1Start.Y - Line2Start.Y) * (Line1Start.Y - Line2Start.Y) 'Distance from Line1Start to Line2End Dist12 = (Line1Start.X - Line2End.X) * (Line1Start.X - Line2End.X) + (Line1Start.Y - Line2End.Y) * (Line1Start.Y - Line2End.Y) 'Distance from Line1End to Line2End Dist21 = (Line2End.X - Line1End.X) * (Line2End.X - Line1End.X) + (Line2End.Y - Line1End.Y) * (Line2End.Y - Line1End.Y) 'Distance from Line1End to Line2Start Dist22 = (Line2Start.X - Line1End.X) * (Line2Start.X - Line1End.X) + (Line2Start.Y - Line1End.Y) * (Line2Start.Y - Line1End.Y) 'Check Distance of Line2Start to Line1Start/Line1End against Line1! If Dist11 <= Dist1 And Dist22 <= Dist1 Then Intersection.X = Line2Start.X Intersection.Y = Line2Start.Y Check1 = True Check2 = True Exit Function End If 'Check Distance of Line2End to Line1Start/Line1End against Line1! If Dist12 <= Dist1 And Dist21 <= Dist1 Then Intersection.X = Line2End.X Intersection.Y = Line2End.Y Check1 = True Check2 = True Exit Function End If 'Check Distance of Line1Start to Line2Start/Line2Start against Line2! If Dist11 <= Dist2 And Dist12 <= Dist2 Then Intersection.X = Line1Start.X Intersection.Y = Line1Start.Y Check1 = True Check2 = True Exit Function End If 'Check Distance of Line1End to Line1Start/Line2End against Line2! If Dist21 <= Dist2 And Dist22 <= Dist2 Then Intersection.X = Line1End.X Intersection.Y = Line1End.Y Check1 = True Check2 = True Exit Function End If 'None of the Segments have Intersections! Check1 = False Check2 = False Exit Function End If Else S = DeterminanteS / Determinante If S < 0 Or S > 1 Then 'Intersection is outside of Line1Segment! Check1 = False Else Check1 = True End If T = DeterminanteT / Determinante If T < 0 Or T > 1 Then 'Intersection is outside of Line2Segment! Check2 = False Else Check2 = True End If Intersection.X = Line1Start.X + S * (Line1End.X - Line1Start.X) Intersection.Y = Line1Start.Y + S * (Line1End.Y - Line1Start.Y) End If End Function

Re: Intersecting Lines

Quote:

Originally Posted by opus

Doing the check for that situation would need several IFs, since one line-segment could be only overlapping. You have to make sure that the points are in some order for decrease the needed checks [what if x1 >x2 in your example?]...

I forgot about that in my last post. But the usual way I do it in any situation is this: regardless of whether or not x₁ is greater than x₂ you can do it a few simple statements using the sgn function. For example, to test if x₃ lies in between x₁ and x₂,
VB Code:
s = sgn(x2 - x1)
If x1*s <= x3*s AND x2*s >= x3*s Then
'...

Re: Intersecting Lines

Quote:

Originally Posted by krtxmrtz

I think this is always true no matter what the variable type is. The more sophisticated the operation, the longer it takes. So * is faster than ^ but I haven't checked if, say, x + x + x is faster than 3*x, not very useful though, even if it is.

Just for grins, I ran this test. x+x+x should have been FAR faster than 3*x, but in VB.NET 2005, it took about twice as long, as if there was no difference between multiplication and addition in the underlying code. The IL for the two tests looked just the way I expected it to.

Then I tested whether 3+3+3 was faster than 3*x, and it was. However, it was faster because 3+3+3 generated the code: Move 9 to memory location. Therefore, the compiler was able to optimize away the entire operation.

However, I then tested x+x+x vs 3*x for double, rather than integer, values, and the two equations took exactly the same time, both of which were faster than the integer version. That's a bit disturbing. Floating point math should be slower, but it's faster. Integer addition should be faster than multiplication, but it looks like the cost for an integer operation is constant, so the number of operations is more important than what the operation is. Floating point math appears to be handled more effectively than the integer math, regardless of what kind of operation.

In C++, I had written an approximation of the Pythagorean Theorem that used only a couple additions and a pair of bit shifts, all of which are particularly fast on the x86. After doing these tests, I guess that I might as well stick with the real algorithm as long as I am working in .NET.

1 Attachment(s)

Re: Intersecting Lines

Quote:

Originally Posted by krtxmrtz

...
I don't know where I placed my math notes that I keep in a notebook...

I've finally found them!!!

I have attached a pdf file with my derivation of the distance between 2 segments (starting at page 2) and as you will see I made it damn complicated... The other solution I gave in post #17 is much easier. Still I knew the code in post #7 worked and that I had a derivation for it.

Re: Intersecting Lines

My project was seriously derailed about two weeks back when I discovered that the hardware had nowhere near the accuracy I had understood it to have. It was good to see this discussion, and it may be that I eventually will even use it, but for now, I am off on an AI adventure. With my sensors proving to be wildly innacurate beyond fairly short range, I am working on a fuzzy logic mapping design which is likely to totally remove any work with lines or line segments of any sort. At best, my "eyes" can determine that there is something out there at a certain distance from the eye, with no direction other than the arc of sight. In other words, I can know that something is about 3m away, and it lies on an arc of maybe as little as 30 degrees, but where on that arc it lies I cannot say.

I've come up with a fuzzy mapping routine (not yet implemented) which should eventually figure out where objects are, but my original intent was to look at gaps between objects, which won't be meaningful anymore now that the world will be nothing more than a probability contour.

Makes life more interesting, though.

Re: Colinear Line Segment Overlap

Quote:
Originally Posted by krtxmrtz
For example, to test if x₃ lies in between x₁ and x₂,
VB Code:
s = sgn(x2 - x1)
If x1*s <= x3*s AND x2*s >= x3*s Then
'...
Another way to make the same check:

Code:

If (x3 - x1) * (x3 - x2) <= 0 Then '...

Of course, you still have to make several checks to determine if there is any overlap of two colinear line segments. I have come up with a simpler check by comparing the length of the segments to the distance between their midpoints. If their combined length is at least twice the distance between their midpoints, then an overlap must occur, given that the segments are colinear.

Code:

If Abs(x1 - x2) + Abs(x3 - x4) >= Abs(x1 + x2 - x3 - x4) Then '...

Conversely, if their combined length is less than twice the distance between their midpoints, than an overlap cannot occur. This is certainly true even when the segments are not colinear. As such, the above test of the segments' horizontal projections can be combined with a similar test of their vertical projections to rule out the possibility of an intersection when the rectangular regions defined by the segments do not overlap.

Re: Colinear Line Segment Overlap

Quote:

Originally Posted by Logophobic

Another way to make the same check:
...

This is much easier, indeed!