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
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
(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.