how to detect collision in qpainterpath

[wagmare]

hi friends/experts,
I have created a free draw on qgraphicsscene using a qgraphicsitem with QPainterpath. i can able to draw or mark anything on the scene using mousepress and mouseMove.
but how i can detect if the painterpath the user drawn crossed with the starting or any part of the path the user started..?
because if the painterpath is not completed by joining the starting point to the end point i have to draw a line to complete .i did it . but if user already crossed or joined the path at some point in the path , i have to clear the extra path lines.
so i want to detect how i can come to know if the path already collided with the path drawn .9829

i have marked the collision area in red circle .. please help me ..

[stampede]

First thing I can think of is to keep track of bounding rectangles of the path's segments, like on this poor reference image I made :)
9835
Ok so my idea is that rectangle intersection tests are very fast, and it will be more efficient to first test if a part of the path is a good candidate for intersection with another part of the path by testing the bounding rectangles. If bounding rect test fails, you can move on to next part of the path.
The fact that old parts of your path does not change allows you to optimize the search by testing only the new parts added by user (if two parts of the curve never intersected, they never will, so you can skip the tests).
Now what to do if you find a good candidate for intersection ?
9836
You can apply a brute force algorithm that will test each line from green rect vs. each line from blue rect. If they in fact intersects you will find the intersection point this way, eventually.
Another approach would be to apply further subdivision of the green and blue bounding rects, and first test the sub-rects before doing actual test on the line segments.
How many line segments should be included in one bounding rectangle ? I don't know :) Remember that if you include many line segments in one bounding rect, you'll have to test for interseciton inside the bounding rect as well (but again, this is calculated only once).
Testing the intersection of two line segments is an easy mathematical excercise ;)
Unfortunately I don't think there is a ready-made solution - maybe you can somehow use the QGraphicsScene::collidingItems method, but it depends on how you store the path data (it can test item vs. item collision). You could also use some existing 2d collision detection library.