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
_______________________________________________
Interest mailing list
Interest@qt-project.org
http://lists.qt-project.org/mailman/listinfo/interest
