Thanks Ch'Gans for replying.
The lines do not have a width. I thought about QGraphicsScene which I
use already but it does seems to be too much for that (plus memory
consumption is an issue as well).
To give a bit mode details: The list of lines does not change during
calculation, it changes only when the user moves the view, but remain as
it is during calculation. I don't need the crossing point, and I don't
need the number of lines that crosses. If it crosses once I break. No
bezier curves or fancy things, just lines. Most of these lines form a
closed polygon that I can detect and manipulate as such, but some other
are just single lines (or non-closed polygons) not connected to anything
else.
The number of lines in the list can vary from 0 to around 50k, it
depends. I already divide the set of lines in subsets (square cells) and
before I go iterate on the list of lines in a cell, I check that the
line is crossing (or is inside) the cell. I have then improved a bit by
using a QPainterPath to determine the boundingRect of the lines within a
cell which I use instead of the cell borders. A bit better, but not that
much. The size of cells is also difficult to tune (more cells with less
lines, or the opposite?).
Since my first mail I have also tried to give some thickness to the line
and use QPainterPath::intersects(). The result is much slower than
simply iterating on the list of lines, at least 1000 times slower (and
cpu is going crazy). I was also considering using QRegion but I suppose
the result will be similar.
I will have a look at CGAL Minkowski 2D algorithms, and will also try
the elegant solution with a QMap provided by Henry in the other reply.
Thanks to you both,
Philippe
Le 09-08-2016 03:07, Ch'Gans a écrit :
On 9 August 2016 at 04:05, maitai <mai...@virtual-winds.org> 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.
Do your lines have a width? or are they "ideal" lines (0 thickness)?
If you need to deal with outline/shape stroking, then you might
consider using QGraphicsScene.
This might look a bit too much at first, but maybe in the long run
this can save you lot of time depending on you spatial query use
cases.
Just check
http://doc.qt.io/qt-5/qtwidgets-graphicsview-chip-example.html
if you never tried before.
Fore more "advanced" geometry approach, you could have a look at cgal
(eg: 2D arrangements)
http://doc.cgal.org/latest/Manual/packages.html#PkgArrangement2Summary
If you find yourself falling short with QPainterPath and
QPainterPathStroker, maybe CGAL Minkowski sums and polygon offsetting
is what you're after
http://doc.cgal.org/latest/Manual/packages.html#PkgMinkowskiSum2Summary
http://doc.cgal.org/latest/Manual/packages.html#PkgStraightSkeleton2Summary
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?
Yeah, that's where you realise the "Painter" role in "QPainterPath".
QPainterPath is definitely tailored to address Qt painting needs.
Plus beware of instability with QPainterPath if you use bezier curves
and circular arcs (implemented internally as bezier curves). Again it
might be OK when your job is painting, but it is not OK if your job is
"geometry solving with precision"
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.
Maybe gives more details about your application:
How many line-segments are you talking about, hundreds, thousands,
millions?
What is the likeliness of intersection?
Are the line static or are they moving? How often the spatial
configuration changes?
How often you need to query the arrangement?
Do you need to detect *every* intersection at *any* moment, or within
an "area of interest" during a "time span of interest:, ... ?
Chris
Thanks for pointing me in the right direction
Philippe Lelong
_______________________________________________
Interest mailing list
Interest@qt-project.org
http://lists.qt-project.org/mailman/listinfo/interest
_______________________________________________
Interest mailing list
Interest@qt-project.org
http://lists.qt-project.org/mailman/listinfo/interest
