The sweepline algorithm finds all intersection points in a set of lines and (IIRC) it has running time O(n*log(n)). I doubt that it is possible to do faster than that... Note: there are several different algorithms referred to as "sweepline algorithm". The sweepline is more of a general approach than a concrete algorithm.
Viktor On 09.08.2016 22:38, André Somers wrote: > > > Verstuurd vanaf mijn iPhone > > Op 9 aug. 2016 om 22:16 heeft André Somers <an...@familiesomers.nl > <mailto:an...@familiesomers.nl>> het volgende geschreven: > >> >> >> Verstuurd vanaf mijn iPhone >> >> Op 9 aug. 2016 om 20:43 heeft maitai <mai...@virtual-winds.org >> <mailto:mai...@virtual-winds.org>> het volgende geschreven: >> >>> 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. >>> >> >> Then look into spacial data structures to organize your data. In this >> case, a quad tree structure comes to mind, where you put a pointer to >> the element (line, polygon) into every bucket it crosses. That uses >> memory and takes time to set up, but you get very fast lookups in >> return. QGraphicsView already organizes its contents into a spacial >> structure btw. >> >> André > > Ps. Note that your choice of data structure depends heavily on your > use case. Is your set of data stable or does it change a lot? What is > the distribution over the space? Is the space bounded or not? What is > the distribution of sizes of objects in relation with the size of your > space? Is memory use an issue? Etc. A quad tree may work, but would > not be the optimal solution for every scenario. > > André >>> >>> 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 <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> >>>> >>>> >>>> _______________________________________________ >>>> Interest mailing list >>>> Interest@qt-project.org <mailto:Interest@qt-project.org> >>>> http://lists.qt-project.org/mailman/listinfo/interest >>> _______________________________________________ >>> Interest mailing list >>> Interest@qt-project.org <mailto: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
