[Interest] best qt class to use to detect line/polygon/region collision

[Henry Skoglund]

On 2016-08-08 18:05, maitai wrote:
> Hello all,
>
> I have a list of lines (QLineF) in 2D space. Some might represent a
> closed polygon, some others are just a line or represent a non closed
> polygon. Classical problem: I need to detect if another given line is
> crossing one of the lines in the list. I don't need the crossing point,
> just to know if it crosses or not.
>
> For the time being, I just iterate on the list and use
> QLineF::intersects(). This is of course badly slow.
>
> I read that post (and many others):
> http://stackoverflow.com/questions/9393672/intersection-point-of-qpainterpath-and-line-find-qpainterpath-y-by-x
>
>
> Using a QPainterPath seems the right idea, but as it seems it does not
> work with a single line, so maybe I should convert the line in a tiny
> rectangle to be able to use QPainterPath::intersects(). Will that be
> faster?
>
> Before I try that, I was wondering if someone has a better idea as of
> what class to use in qt to solve this? Calculation speed is the most
> important thing in my case.
>
> Thanks for pointing me in the right direction
> Philippe Lelong

Isn't this some kind of sorting problem in disguise? You could try 
sorting the coords of the lines in your list to speed up the processing. 
I made a simple example using a QMap:
---------------------------------------------------------------------
// make list of QLineFs
     QList<QLineF> lLines;
     for (int i = 0; (i < 1000000); ++i)
     {
         QLineF l(rand() / 100.0,rand() / 100.0,rand() / 100.0,rand() / 
100.0);

     // make sure dx is positive (x1 <= x2)
         if (l.x1() > l.x2())
         // if not swap the points
             l = QLineF(l.p2(),l.p1());

         lLines.append(l);
     }

// insert all x1 coords (and their position in the list) in a map
     QMap<qreal,int> mx1;
     for (int i = 0; (i < lLines.count()); ++i)
         mx1.insertMulti(lLines[i].x1(),i);

// make another list of QLineFs to test with
     QList<QLineF> lTest;
     for (int i = 0; (i < 20); ++i)
     {
         QLineF l(rand() / 100.0,rand() / 100.0,rand() / 100.0,rand() / 
100.0);

     // make sure dx is positive (x1 <= x2)
         if (l.x1() > l.x2())
         // if not swap the points
             l = QLineF(l.p2(),l.p1());

         lTest.append(l);
     }

// test simple way
     int crossings1 = 0;
     for (auto t : lTest)
         for (auto l : lLines)
             if (QLineF::BoundedIntersection == l.intersect(t,nullptr))
                 ++crossings1;

// test with map
     int crossings2 = 0;
     for (auto t : lTest)
     {
         auto iUpper = mx1.upperBound(t.x2());
         auto i = mx1.begin();
         while (i != iUpper)
         {
             auto l = lLines[i.value()];
             if (QLineF::BoundedIntersection == l.intersect(t,nullptr))
                 ++crossings2;

             ++i;
         }
     }

// crossings1 == crossings2
---------------------------------------------------------------------

Random access in the list from the values in QMap well not yield so good 
performance, the QlineFs should be stored in a vector instead.

Perhaps a next step could be to do a similar QMap sorting of the .x2() 
coords and do a .lowerbound(t.x1()) stepping down and then also sort the 
y coords. But I need more coffee to understand that right now..

Rgrds Henry