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
