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

Tue Aug 9 15:37:53 CEST 2016

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
<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>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.qt-project.org/pipermail/interest/attachments/20160809/287c673a/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: qt_logo_with_text_green_rgb_400x141.png
Type: image/png
Size: 16849 bytes
Desc: not available
URL: <http://lists.qt-project.org/pipermail/interest/attachments/20160809/287c673a/attachment.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: qt_facebook.png
Type: image/png
Size: 1407 bytes
Desc: not available
URL: <http://lists.qt-project.org/pipermail/interest/attachments/20160809/287c673a/attachment-0001.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: qt_twitter.png
Type: image/png
Size: 1778 bytes
Desc: not available
URL: <http://lists.qt-project.org/pipermail/interest/attachments/20160809/287c673a/attachment-0002.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: qt_linkedin.png
Type: image/png
Size: 1532 bytes
Desc: not available
URL: <http://lists.qt-project.org/pipermail/interest/attachments/20160809/287c673a/attachment-0003.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: qt_googleplus.png
Type: image/png
Size: 1957 bytes
Desc: not available
URL: <http://lists.qt-project.org/pipermail/interest/attachments/20160809/287c673a/attachment-0004.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: qt_youtube.png
Type: image/png
Size: 1610 bytes
Desc: not available
URL: <http://lists.qt-project.org/pipermail/interest/attachments/20160809/287c673a/attachment-0005.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: viktor_engelmann.vcf
Type: text/x-vcard
Size: 271 bytes
Desc: not available
URL: <http://lists.qt-project.org/pipermail/interest/attachments/20160809/287c673a/attachment.vcf>