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

Tue Aug 9 20:43:01 CEST 2016

Thanks Viktor but my problem is not to detect whether 2 lines are
crossing, it is to avoid looping on 50k lines for nothing ;) My worst
case is when no cross is found and I looked at each and every line for
just nothing. Checking a line is crossing another is really fast and I
am not using QLineF::intersects() for that, because I don't need the
crossing point and I save some cycles not computing it. 

I think Henry's idea is a good one, and it actually save some ms, but
not much because I have already a mechanism with cells and
boundingRects. It all depends if the lines are more on the left (or
right, or up, or down) depending on what criteria is chosen to build the
QMap (x1, x2, y1 ou y2). A double QMap (or more) seems more expensive
than checking a cross on the remaining set, but I will give it a try. I
can spend some cpu time organizing the set of lines, provided it saves
something later when checking a million random lines for a cross against
the set of fixed lines.  

Still working on that. 

Philippe Lelong 

Le 09-08-2016 15:37, Viktor Engelmann a écrit :

> Sweepline algorithms are what you are looking for. 
> 
> For 2 single lines, check this
> http://algorithman.de/Mathe/GeomSchnitt.pdf
> It contains an explicit formula :-) for detecting whether 2 lines intersect.
> It is in german, but contains mostly formulas - so it might be understandable. 
> 
> Kind regards 
> 
> Viktor 
> 
> On 09.08.2016 07:22, maitai wrote: 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
 _______________________________________________ 
Interest mailing list 
Interest at qt-project.org 
http://lists.qt-project.org/mailman/listinfo/interest 
-- 

 Viktor Engelmann
Software Engineer

The Qt Company GmbH
Rudower Chaussee 13
D-12489 Berlin
Viktor.Engelmann at qt.io
+49 151 26784521
http://qt.io

Geschäftsführer: Mika Pälsi, Juha Varelius, Mika Harjuaho
Sitz der Gesellschaft: Berlin, Registergericht: Amtsgericht
Charlottenburg, HRB 144331 B 

 		 [1]

 		 [2]
 		 [3]
 		 [4]
 		 [5]
 		 [6]

_______________________________________________
Interest mailing list
Interest at qt-project.org
http://lists.qt-project.org/mailman/listinfo/interest 

Links:
------
[1] http://qt.io
[2] http://www.facebook.com/Qt
[3] http://www.twitter.com/qtproject
[4] https://www.linkedin.com/company/the-qt-company/
[5] https://plus.google.com/104580575722059274792
[6] https://www.youtube.com/QtStudios
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.qt-project.org/pipermail/interest/attachments/20160809/bdab858e/attachment.html>