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
}
1
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.
4
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.