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

[Ch'Gans]

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