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

[maitai]

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 <maitai at 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 at qt-project.org
>> http://lists.qt-project.org/mailman/listinfo/interest