Line intersection detection algorithm

I'm trying to detect if a line drawn by the user intersects itself. I'm using a line intersection detection algorithm that goes through each waypoint of the line and checks if intersects with any other point in the line.

This is a costly method and has started to produce performance problems. What would be the recommended algorithm for this problem? Is there a code example of it?

The line is represented with wayPoints which are coordinates that have been gathered by users movement on screen.

Thanks a lot for just reading this far! All help Appreciated!

for i in 1 ..<(wayPoints.count-1) {
for j in 0 ..< i-1 {
if let intersection = intersectionBetweenSegments(wayPoints[i], wayPoints[i+1], wayPoints[j], wayPoints[j+1]){
...}
}
}

func intersectionBetweenSegments(p0: CGPoint, _ p1: CGPoint, _ p2: CGPoint, _ p3: CGPoint) -> CGPoint? {
var denominator = (p3.y - p2.y) * (p1.x - p0.x) - (p3.x - p2.x) * (p1.y - p0.y)
var ua = (p3.x - p2.x) * (p0.y - p2.y) - (p3.y - p2.y) * (p0.x - p2.x)
var ub = (p1.x - p0.x) * (p0.y - p2.y) - (p1.y - p0.y) * (p0.x - p2.x)
if (denominator < 0) {
ua = -ua; ub = -ub; denominator = -denominator
}

if ua >= 0.0 && ua <= denominator && ub >= 0.0 && ub <= denominator && denominator != 0 {
return CGPoint(x: p0.x + ua / denominator * (p1.x - p0.x), y: p0.y + ua / denominator * (p1.y - p0.y))
}

return nil
}
• Post an outline of what you are doing now Mar 6, 2015 at 5:09

This is a costly method and has started to produce performance problems. What would be the recommended algorithm for this problem? Is there a code example of it?

It depends very much on how you represent the line itself. It seems that you use a broken line, that is a juxtaposition of straight lines.

The first idea that jumps to my mind is to do a simple region check. You can pack each line in a small rectangle (its bounding box) and it is very easy to check if two bounding boxes overlap or not – you can do this by doing a few subtractions, which is much cheaper than computing a determinant! If the region check fails, then the lines certainly do not intersect so you do not need to compute the determinant.

With this you should jump from complexity (nˆ4) to (nˆ2) where n is the number of tiny straight lines in your line.

If this is not enough, a second common technique is to divide the canvas in regions and represent this region as a binary tree. You start with the full canvas, then cut in halves, and then subdivide each half in two, again and again, until you reach a number of splitting you choose in advance. (You can do empirical tests to determine a value suitable for your data.) Then you can attach each line segment to a region where its bounding box fits – Typically a leaf, but it can be a higher level node if a line segment cuts a region border. Once you packed each line segment in the region tree, it is easy to retrieve neighbours of a segment line, where the intersection can take place.

• The line is represented with wayPoints which are coordinates that have been gathered by users movement on screen. I only have one line and I'm trying to figure out whether it intersects itself so I suppose boxing approach could turn out to be difficult. Mar 6, 2015 at 8:06
• Simple region test may eliminate the number of values to check, though that simple region test you still must perform on every combination of two lines. And, if they pass the test, you will have to perform the more complicated calculation anyway. It may surprise you to know that this is not optimal
– Neil
Mar 6, 2015 at 11:40
• @user594883 Boxing is intended to be applied to the small straight lines constituting your line. Mar 6, 2015 at 21:33
• @Neil I am not very surprised to know that it is not optimal. Actually, I hid in the third paragraph an improvement of the simple region test I describe in the first paragraph. Mar 6, 2015 at 21:47

This is originally a comment seeking clarifications, but is too long to fit. So I posted each question here, along with my "what-if" answers for each question based on possible responses.

Before seeking clarifications, everyone should see that the current implementation has time complexity that is quadratic in the number of waypoints. The notation is O(N^2).

To put it simply, if the number of waypoints are doubled (increased to twice), the execution time will approximately be quadrupled (increased to fourfold).

(1) What is the typical number of waypoints you need to handle? If there is no typical number, state the maximum possible number of waypoints that your code needs to support.

For example, if you find that the performance issue do not occur when N (number of waypoints) is below several hundreds, you may impose a software restriction that the mouse movement cannot be longer than that number of pixels. Whether this is acceptable or not depends on your software's purpose.

(2) Are you allowed to use line simplification techniques to reduce the number of waypoints before checking for intersections?

Line simplification technique can cut down the number of waypoints by tenfold (one-tenth) or more (less), when mouse movement is used as input. The user will have to move the mouse very frantically to cause this reduction to fail.

(3) Do you know how to implement and use QuadTree by yourself?

A quadtree allows average case O(log N) query into a collection (tree) of bounding boxes that overlap with the query bounding box. To find all pairwise overlapping bounding boxes, one would first add all bounding boxes to it, and then make query on each bounding box. This gives a total that is average case O(N log N), which is better than the original implementation that is O(N^2).

(4) What is the width and height of the movement area, measured in pixels, that you need to support?

If total movement area (in squared pixels, that is, the product of width and height) is less than a few million, and if one is allowed to allocate an array that can hold a few million bytes (or bits - we only need each element to be true or false), then one can allocate such an array to act as a bitmap (literally a map of bits).

The bitmap will be initialized with false. Then, as the user "paints" with mouse movement, the corresponding pixels in the bitmap will be set to true.

Caveat. Note that if the user's pixel trail is only a single pixel (1 by 1) wide, the following edge case will happen:

Suppose the trace goes from (10, 10) to (11, 11). Later in the trace, it crosses that segment by going (10, 11) to (11, 10). Since the pixels themselves do not overlap, this bitmap-based scheme will fail to detect an intersection of this kind.

The solution to the caveat is that one has to check a 3-by-3 neighborhood for pixels that had been painted before. While doing this, one also has to remember to ignore pixels that have just been painted freshly. It is possible that one may have to use one byte per pixel (as opposed to one bit per pixel) in order to store additional information to help workaround this caveat.