I'm developing a game in which the player can draw a line. I want to detect if that line intersects with itself. How would I do this?
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It only takes a minute to sign up.Sign up to join this community
Anyway, any representation should be possible to convert into a list of points that represent the curve to some precision. It might look something like this:
Go through adjacent point pairs and check if they intersect with another point pair that isn't the same.
function intersectsWithSelf(curvePoints) local points = curvePoints for i = 0, len(points) - 1 do -- Point pair 1 local p1 = points[i] local p2 = points[i+1] for j = 0, len(points) - 1 do -- Point pair 2 local p3 = points[j] local p4 = points[j+1] if p3 is not p1 then if intersects(p1,p2, p3,p4) then return true end end end return false end
In the innermost loop, the function
intersects checks whether two line segments intersect. This has been solved in many interesting ways. It's been covered well before.
Your pictorial example would suggest the curves are quite simple. However, if you find that curves have to be long or their precision quite high, the polynomial time naive algorithm may be too slow. More advanced algorithms exist and some of them can solve the problem in logarithmic time by performing a sweep test. These are, of course, much more complex to implement.