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?

self-intersecting curve

  • 5
    \$\begingroup\$ Tell us something about how you represent data and the algorithm you use to draw new lines. Also, please post a picture of the kind of intersection you want to detect, I'm not sure I understand you perfectly. \$\endgroup\$
    – Paul Manta
    Feb 4, 2013 at 7:38
  • 3
    \$\begingroup\$ Paul Manta's question still isn't really answered. Are the lines simple chains of straight line segments, or are you doing something more complicated? If they're simple chains of straight line segments, do you know how to check whether two straight line segments intersect? \$\endgroup\$ Feb 4, 2013 at 13:18
  • 1
    \$\begingroup\$ @PeterTaylor I believe that is the solution, at the end of the day to draw the lines it would need to be broken into segments whether its represented by an equation or simple stored as a list of points. Therefore simple straight line intersection is the solution: stackoverflow.com/questions/563198/… \$\endgroup\$
    – dennmat
    Feb 4, 2013 at 14:19
  • 2
    \$\begingroup\$ @dennmat, it's not the only viable solution. As you observe, a list of points is another; I could add that some curves can be drawn by Bresenham's algorithm or variants, or by marching squares. \$\endgroup\$ Feb 4, 2013 at 18:15
  • 1
    \$\begingroup\$ +1 @PeterTaylor true, I should have stated I believed given the info we have IMO it is the solution. However there's lots of possibilities, calculating an area graph for the set of points in the case of a non closed polygon(aka not a polygon) it would break early telling you the points do not intersect. Or feeding the points to a path finding algorithm if the result is shorter than the sum of the lines they intersect. There's tons I just find the line intersection to be generic enough to answer the generic question. \$\endgroup\$
    – dennmat
    Feb 4, 2013 at 18:24

1 Answer 1


As the comments ask: How are you representing your curve (i.e. "drawn line")?

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:

a curve and some points that represent it

Naive algorithm

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
        return false

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.

Complex algorithms?

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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .