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

Thu Aug 11 15:16:49 CEST 2016

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 <andre at familiesomers.nl
> <mailto:andre at familiesomers.nl>> het volgende geschreven:
>
>>
>>
>> Verstuurd vanaf mijn iPhone
>>
>> Op 9 aug. 2016 om 20:43 heeft maitai <maitai at virtual-winds.org
>> <mailto:maitai at 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 <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>
>>>>
>>>>
>>>> _______________________________________________
>>>> Interest mailing list
>>>> Interest at qt-project.org <mailto:Interest at qt-project.org>
>>>> http://lists.qt-project.org/mailman/listinfo/interest
>>> _______________________________________________
>>> Interest mailing list
>>> Interest at qt-project.org <mailto: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/20160811/476efba1/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/20160811/476efba1/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/20160811/476efba1/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/20160811/476efba1/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/20160811/476efba1/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/20160811/476efba1/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/20160811/476efba1/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/20160811/476efba1/attachment.vcf>