Help with intersecting line segments
BlitzMax Forums/BlitzMax Programming/Help with intersecting line segments
| ||
I'm using this code (which is mine): http://www.blitzbasic.com/codearcs/codearcs.php?code=2597 I wrote it a while ago but only just got around to needing it. My original code was for intersecting infinite lines - not segments. Some chap has kindly added code for detecting segments and I've modified this slightly as below: Function Between:Byte(X:Double, B:Double, T:Double) If T >= B If X >= B And X <= T Return 1 EndIf Else If X >= T And X <= B Return 1 EndIf EndIf Return 0 End Function The implementation of this is given on the code archive page but I'm not convinced that this is correct. It often works - but not always. My line intersection code seems to work fine, but its when I started wanting to check line segments (which have a defined start and end point) that I started having problems. For instance, its telling me occasionally that two line segments don't intersect when they clearly do, yet if I move them a few pixels closer together, it works. Ideas? |
| ||
So far I haven't needed a function that would determine intersect point for line segments, since I have next two functions.Function Intersect:Int(x1:Float, y1:Float, x2:Float, y2:Float, x3:Float, y3:Float, x4:Float, y4:Float) Return (Sgn((x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1)) <> Sgn((x2 - x1) * (y4 - y1) - (x4 - x1) * (y2 - y1))) And (Sgn((x4 - x3) * (y1 - y3) - (x1 - x3) * (y4 - y3)) <> Sgn((x4 - x3) * (y2 - y3) - (x2 - x3) * (y4 - y3))) End Function The above returns True if line segments intersect at some point. It's very fast. If the line segments intersect, then I use intersect calculation for infinite lines. Infinity doesn't matter since I know the segments intersect. Function IntersectPoint (x1:Float, y1:Float, x2:Float, y2:Float, x3:Float, y3:Float, x4:Float, y4:Float, RX:Float Var, RY:Float Var) 'Function returns the X,Y position of the two intersecting lines. 'The lines are infinite, is line1 goes through x1,y1,x2,y2 and line2 goes through x3,y3,x4,y4. 'For finite lines you must check if the lines truly intersect with the function Intersect% before you use this. Local dx1:Float = x2 - x1 Local dx2:Float = x4 - x3 'Local dx3:Float = x1 - x3 Local dy1:Float = y2 - y1 'Local dy2:Float = y1 - y3 Local dy3:Float = y4 - y3 Local R:Float = dx1 * dy3 - dy1 * dx2 If R <> 0 Then R = ((y1 - y3) * dx2 - (x1 - x3) * dy3) / R rx = x1 + R * dx1 ry = y1 + R * dy1 Else If ((dx1 * (y3 - y1) - (x3 - x1) * dy1) = 0) Then rx = x3 ry = y3 Else rx = x4 ry = y4 EndIf EndIf End Function They should work with double precision too, I think. I haven't had any problems with these. I know this isn't exactly what you wanted (you want to reinvent the wheel, which is pretty much what I like to do too), but maybe these will give you ideas. |
| ||
Thanks, that seems to work perfectly. I have lots of testing to do that's going to keep me here for a few hours yet, but thanks for your help (and put that in the code archives!) |
| ||
Hera an more OO-stylish solution :)SuperStrict Local point1:TPoint2D = TPoint2D.Create(1, 1) Local point2:TPoint2D = TPoint2D.Create(10, 10) Local point3:TPoint2D = TPoint2D.Create(10, 1) Local point4:TPoint2D = TPoint2D.Create(1, 10) Local line1:TLine2D = TLine2D.Create(point1, point2) Local line2:TLine2D = TLine2D.Create(point3, point4) Local line3:TLine2D = TLine2D.Create(point1, point3) Local line4:TLine2D = TLine2D.Create(point2, point4) If line1.intersects(line2) Then Print "Yes, intersects" If line2.intersects(line1) Then Print "Yes, intersects" If Not line3.intersects(line4) Then Print "No, does not intersect" If Not line4.intersects(line3) Then Print "No, does not intersect" Local point10:TPoint2D = TPoint2D.Create(4,4) Local point11:TPoint2D = TPoint2D.Create(6,6) Local line100:TLine2D = TLine2D.Create(point10, point11) Local point20:TPoint2D = TPoint2D.Create(4,6) Local point21:TPoint2D = TPoint2D.Create(6,4) Local line200:TLine2D = TLine2D.Create(point20, point21) Print "Intersects X:"+line100.getIntersectionPoint2D(line200).GetX() Print "Intersects Y:"+line100.getIntersectionPoint2D(line200).GetY() Type TPoint2D Field _x:Double Field _y:Double Function Create:TPoint2d(x:Double, y:Double) Local point:TPoint2D = New TPoint2D point._x = x point._y = y Return point EndFunction Method getX:Double() Return _x EndMethod Method getY:Double() Return _y EndMethod EndType Type TLine2D Field _p1:TPoint2D Field _p2:TPoint2D Function Create:TLine2D(p1:TPoint2D, p2:TPoint2D) Local line:TLine2D = New TLine2D line._p1 = p1 line._p2 = p2 Return line EndFunction Method getP1:TPoint2D() Return _p1 EndMethod Method getP2:TPoint2D() Return _p2 EndMethod Method intersects:Int(other:TLine2D) Return (Sgn((Self.getP2().getX() - Self.getP1().getX()) * (other.getP1().getY() - Self.getP1().getY()) - (other.getP1().getX() - Self.getP1().getX()) * (Self.getP2().getY() - Self.getP1().getY())) <> Sgn((Self.getP2().getX() - Self.getP1().getX()) * (other.getP2().getY() - Self.getP1().getY()) - (other.getP2().getX() - Self.getP1().getX()) * (Self.getP2().getY() - Self.getP1().getY()))) And (Sgn((other.getP2().getX() - other.getP1().getX()) * (Self.getP1().getY() - other.getP1().getY()) - (Self.getP1().getX() - other.getP1().getX()) * (other.getP2().getY() - other.getP1().getY())) <> Sgn((other.getP2().getX() - other.getP1().getX()) * (Self.getP2().getY() - other.getP1().getY()) - (Self.getP2().getX() - other.getP1().getX()) * (other.getP2().getY() - other.getP1().getY()))) EndMethod Method getIntersectionPoint2D:TPoint2D(other:TLine2D) Local result:TPoint2D = Null If Self.intersects(other) Local dx1:Double = Self.getP2().getX() - Self.getP1().getX() Local dx2:Double = Other.getP2().getX() - Other.getP1().getX() Local dy1:Double = Self.getP2().getY() - Self.getP1().getY() Local dy2:Double = Other.getP2().getY() - Other.getP1().getY() Local R:Double = dx1 * dy2 - dy1 * dx2 If R <> 0 Then R = ((Self.getP1().getY() - Other.getP1().getY()) * dx2 - (Self.getP1().getX() - Other.getP1().getX()) * dy2) / R result = TPoint2D.Create(Self.getP1().getX() + R * dx1, Self.getP1().getY() + R * dy1) Else If ((dx1 * (Other.getP1().getY() - Self.getP1().getY()) - (Other.getP1().getX() - Self.getP1().getX()) * dy1) = 0) Then result = TPoint2D.Create(Other.getP1().getX(), Other.getP1().getY()) Else result = TPoint2D.Create(Other.getP2().getX(), Other.getP2().getY()) EndIf EndIf EndIf Return result EndMethod EndType |
| ||
Hera an more OO-stylish solution :) All of those method calls. yak! I don't think I would sacrifice performance over that. Overkill, me thinks :) |
| ||
The OO version is like going to an expensive restaurant and asking for ketchup for your meal. Ketchup may be great, but demolishes the original idea. These kind of math functions are supposed to work lightning fast, so you can call them millions of times per second without having to worry about performance. I hate it when schools teach us OOP is some sort of a god. As far as I see it, it's a good aid, but bad host. Thinking about all the s**t we put CPU to do with all this excess OOP crap. It makes me so mad. Enough ranting, nothing personal, sorry... |
| ||
Rant.Stop() |
| ||
:D Better just set it as null and wait for garbage collector to lock this thread. |
| ||
Sorry for the bump, this just made me laugh out loud.. Thinking about all the s**t we put CPU to do with all this excess OOP crap. It makes me so mad. Rant.Stop() If that was intentional Czar, you're a genius :D |
| ||
@Jasu>>thanks for sharing ! |