View Full Version : QGraphicsItem; Finding path

23rd March 2011, 22:46
I've created a simple image to demonstrate my problem and hopefully someone can give me some hints or tips on how to solve this.

As you can see in the image there is three lines. The blue line is a polyline that intersects with the black line. The red one is exactly the same as the blue except for that it intersects with two lines(The blue and the black line). I'm having serious problem figuring out how I can find the intersected path for the red line. I hope someone can help me figuring this out.

23rd March 2011, 23:21
You could look up 'polygon intersection'; there are several algorithms. The most efficient approach would likely be a variant of a scan-line algorithm. If there are never more than a few segments per line, though, a more brute-force approach of checking every pair of segments between two lines for intersection would probably work just fine and be simpler to implement than scan-line. As the number of segments grows, however, the number of comparisons grows as n^2, so such an approach quickly becomes too slow to be practical. For a dozen or so segments, though, speed ought to be fine.

24th March 2011, 20:13
Thank you for the hints SixDegrees! I have found a library that is called generic polygon clipper but I'm not sure this is what I need. But I will try it out :)