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 <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 -- Viktor Engelmann Software Engineer The Qt Company GmbH Rudower Chaussee 13 D-12489 Berlin viktor.engelm...@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 <http://qt.io> <http://www.facebook.com/Qt> <http://www.twitter.com/qtproject> <https://www.linkedin.com/company/the-qt-company/> <https://plus.google.com/104580575722059274792> <https://www.youtube.com/QtStudios>
<<attachment: viktor_engelmann.vcf>>
_______________________________________________ Interest mailing list Interest@qt-project.org http://lists.qt-project.org/mailman/listinfo/interest
