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

[André Somers]

Verstuurd vanaf mijn iPhone

> Op 9 aug. 2016 om 22:16 heeft André Somers  het 
> volgende geschreven:
> 
> 
> 
> Verstuurd vanaf mijn iPhone
> 
>> Op 9 aug. 2016 om 20:43 heeft maitai  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  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 

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

[André Somers]

Verstuurd vanaf mijn iPhone

> Op 9 aug. 2016 om 20:43 heeft maitai  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é
> 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  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 

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

[maitai]

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

Re: [Interest] QNetworkAccessManager networkAccessible - Android vs iOS

[ekke]

Am 09.08.16 um 15:43 schrieb Jason H:
> This is a well known bug that has bounced around varuous statuses in
> various other issue numbers and is still not fixed it seems.
>  
> https://bugreports.qt.io/browse/QTBUG-49751
Thanks mentioning this. Added my workaround (always instantiate
QNetworkAccessManager) there and hope it'll get fixed.

Just developing the QtCon Conference APP where I only have two requests
(schedule and speakers) - so it's ok.
But other apps are full of requests and I really don't want to live with
the workaround ;-)

ekke
>  
> *Sent:* Tuesday, August 09, 2016 at 5:32 AM
> *From:* ekke 
> *To:* "interest@qt-project.org" 
> *Subject:* [Interest] QNetworkAccessManager networkAccessible -
> Android vs iOS
>
> Hi,
>
> just noticed a difference between Android and iOS
>
> Before doing a request I'm checking the Network
>
> if(mNetworkAccessManager->networkAccessible()!=QNetworkAccessManager::Accessible){
>
>  
>
> on Android all works well.
>
> Switching off wifi and mobile data --> Not Accessible
>
> Switching on again --> Accessible
>
> on iOS it's different:
>
> Switching off wifi and mobile data --> Not Accessible
>
> Switching on again --> state not changed back to accessible
>
> --
>
> QNetworkAccessManager is initialized at first use and then re-used.
> If I always create  a new QNetworkAccessManager before executing the
> request, all is detected well also on iOS
>
> Can I 'reset' the accessibility or should I always create a new
> QNetworkAccessManager and report a bugreport ?
>
> thx
>
> ekke ___ Interest mailing
> list Interest@qt-project.org
> http://lists.qt-project.org/mailman/listinfo/interest


-- 

ekke (ekkehard gentz)

independent software architect
international development native mobile business apps
BlackBerry 10 | Qt Mobile (Android, iOS)
workshops - trainings - bootcamps

*BlackBerry Elite Developer
BlackBerry Platinum Enterprise Partner*

max-josefs-platz 30, D-83022 rosenheim, germany
mailto:e...@ekkes-corner.org
blog: http://ekkes-corner.org
apps and more: http://appbus.org

twitter: @ekkescorner
skype: ekkes-corner
LinkedIn: http://linkedin.com/in/ekkehard/
Steuer-Nr: 156/220/30931 FA Rosenheim, UST-ID: DE189929490

___
Interest mailing list
Interest@qt-project.org
http://lists.qt-project.org/mailman/listinfo/interest

Re: [Interest] QNetworkAccessManager networkAccessible - Android vs iOS

[Jason H]

This is a well known bug that has bounced around varuous statuses in various other issue numbers and is still not fixed it seems.

 

https://bugreports.qt.io/browse/QTBUG-49751

 

Sent: Tuesday, August 09, 2016 at 5:32 AM
From: ekke 
To: "interest@qt-project.org" 
Subject: [Interest] QNetworkAccessManager networkAccessible - Android vs iOS



Hi,

just noticed a difference between Android and iOS

Before doing a request I'm checking the Network





if(mNetworkAccessManager->networkAccessible() != QNetworkAccessManager::Accessible) {

 

on Android all works well.

Switching off wifi and mobile data --> Not Accessible

Switching on again --> Accessible

on iOS it's different:

Switching off wifi and mobile data --> Not Accessible

Switching on again --> state not changed back to accessible

--
QNetworkAccessManager is initialized at first use and then re-used.
If I always create  a new QNetworkAccessManager before executing the request, all is detected well also on iOS

Can I 'reset' the accessibility or should I always create a new QNetworkAccessManager and report a bugreport ?

thx

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

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

[Viktor Engelmann]

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

[Interest] QNetworkAccessManager networkAccessible - Android vs iOS

[ekke]

Hi,

just noticed a difference between Android and iOS

Before doing a request I'm checking the Network

if(mNetworkAccessManager->networkAccessible()!=QNetworkAccessManager::Accessible){

on Android all works well.

Switching off wifi and mobile data --> Not Accessible

Switching on again --> Accessible

on iOS it's different:

Switching off wifi and mobile data --> Not Accessible

Switching on again --> state not changed back to accessible

--

QNetworkAccessManager is initialized at first use and then re-used.
If I always create  a new QNetworkAccessManager before executing the
request, all is detected well also on iOS

Can I 'reset' the accessibility or should I always create a new
QNetworkAccessManager and report a bugreport ?

thx

ekke
___
Interest mailing list
Interest@qt-project.org
http://lists.qt-project.org/mailman/listinfo/interest

Re: [Interest] item edit on mouse over - was: dynamic widget creation in QScrollArea

[Frank Rueter | OHUfx]

Hi Volker,

that doesn't sound like a bad idea at all I think, though I'm no QT 
expert myself.

I will try that tomorrow, thanks.



On 9/08/16 5:57 pm, Volker Siepmann wrote:

I'm quite new to qt, so please set me straight if this is nonsense:
Can you use the blockSignals(True) method once the event was called, 
so it doesn't try to open it multiple times as you continue hovering?
Then you need to catch the event of editor closing, so you can enable 
the signals again by blockSignals(False).

​


--
ohufxLogo 50x50 

*vfx for storytellers *

*vfx compositing  | 
*workflow customisation & consulting 
**


*W E L L I N G T O N|N E W   Z E A L A N D *

___
Interest mailing list
Interest@qt-project.org
http://lists.qt-project.org/mailman/listinfo/interest