bugpyFormex - Bugs: bug #44617, polyline insertPointsAt and...

 
 

bug #44617: polyline insertPointsAt and splitAt failing

Submitter:  gianluca de santis <gianlucadesi>
Submitted:  Tue 24 Mar 2015 10:50:21 AM UTC
   
 
Category:  Plugins Severity:  4 - Important
Item Group:  Functionality error Status:  Fixed
Privacy:  Public Assigned to:  bverheg
Open/Closed:  Closed
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Tue 24 Mar 2015 02:14:14 PM UTC, comment #8: 

Concerning the question of using a stable merge sort everywhere:
I think it is not a good idea, because:

1. quicksort is a lot faster, so if you do not need a stable sort (is often the case), you can better use it.
2. this bug precisely is detected because of using an unstable sort. With a stable one, it might(?) have gone undetected for much longer.

BTW., I have added t=sorted(t) at the start of insertPointsAt,
so now the parameter values are sorted first before using.

Now I also remember how such a bug got into this function. At first, we had the restriction that you could only have at most one new point inserted per segment, so sorting the segment numbers was the same (and slightly faster, because integers) than sorting the parameter values. The restriction was required because when you insert a point in a segment, the decimal part of the parameter value of the points to be inserted further on the same segment, change. 

After I got the briljant ;) insight that the decimal part of points to be inserted BEFORE does not change, I relaxed that restriction, adding the points in a backward order.
But the sorting was never adapted to the now required sorting on the full parameter value instead of on the integer part only.

Benedict Verhegghe <bverheg>
Group administrator
Tue 24 Mar 2015 01:56:17 PM UTC, comment #7: 

Fixed in 1568e60.

Benedict Verhegghe <bverheg>
Group administrator
Tue 24 Mar 2015 01:56:05 PM UTC, comment #6: 

It is not the first time we get troubles because of the unstable deafult sorting algorithm of numpy (i.e. quicksort).

Of the 3 sorting algorithm only the mergesort is stable:

http://www.biochem-caflisch.uzh.ch/zhou/Numpy_Example_List_With_Doc.html#sort

Would it be a good think to change the default algorithm of
sort() and argsort() to mergesort in the full pyformex code (unless differently specified)?


gianluca de santis <gianlucadesi>
Group Member
Tue 24 Mar 2015 01:49:50 PM UTC, comment #5: 

Great expanation!!!

I think this can using the mergesort:

ar.argsort(kind='mergesort')

This was already done in arraytools uniqueOrdered

gianluca de santis <gianlucadesi>
Group Member
Tue 24 Mar 2015 01:43:42 PM UTC, comment #4: 

I can confirm that the problem is in insertPointsAt.

The algorithm sorts the points to be inserted, so the values do not have to be in increasing order, as I said in https://savannah.nongnu.org/bugs/?44617#comment1

But it only sorts on the integer part (the segment number) of the parameter value, instead of on the full value. In the example with a single segment, all values are thus 0.

The sorting is done with argsort. For a list of all 0 values, this function leaves the order unchanged if there are no more than 16 values. When more than 16, the returned order is not the original. This is not faulty, as all values are the same. But it explains why the bug has been undetected so long: we usually use increasing values, and the original order is the correct one. Above 16 values the order is mangled, probably because another sorting algorithm is used for longer lists. Here you can see this happening:


>>> from numpy import *
>>> argsort([0]*16)
array([ 0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15])
>>> argsort([0]*17)
array([ 0, 14, 13, 12, 11, 10,  9, 15,  8,  6,  5,  4,  3,  2,  1,  7, 16])


We need to fix the sorting, probably sorting right from the start in insertPointsAt.

Benedict Verhegghe <bverheg>
Group administrator
Tue 24 Mar 2015 12:32:03 PM UTC, comment #3: 

I have tried other examples and it seems to fail when you have more than 16 points.

Benedict Verhegghe <bverheg>
Group administrator
Tue 24 Mar 2015 12:08:08 PM UTC, comment #2: 

arange(0., 0.85, 0.05) is increasing:

[ 0.  ,  0.05,  0.1 ,  0.15,  0.2 ,  0.25,  0.3 ,  0.35,  0.4 ,
        0.45,  0.5 ,  0.55,  0.6 ,  0.65,  0.7 ,  0.75,  0.8 ]

gianluca de santis <gianlucadesi>
Group Member
Tue 24 Mar 2015 11:33:42 AM UTC, comment #1: 

I am not sure, but I think that the split values should be in increasing order?

Benedict Verhegghe <bverheg>
Group administrator
Tue 24 Mar 2015 10:50:21 AM UTC, original submission:  

I have encountered an error and after digging into it I could find the source of the problem into PolyLine.splitAt. Why the following lines give an error?


PL = PolyLine([[ 0.,0.,0.],[10.,0.,0.]])
t = arange(0., 0.85, 0.05)
x = PL.splitAt(t)

gianluca de santis <gianlucadesi>
Group Member

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

No files currently attached

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by bverheg (Posted a comment)
  • -email is unavailable- added by gianlucadesi (Submitted the item)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only logged-in users can vote.

     

    Follow 5 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2015-05-27 bverheg StatusReady For Test Fixed
        Open/ClosedOpen Closed
    2015-03-24 bverheg StatusNone Ready For Test
        Assigned toNone bverheg
        Summarypolyline splitAt failing polyline insertPointsAt and splitAt failing

    Back to the top

    Powered by Savane 3.13-758e.
    Corresponding source code