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

 
 

bug #44617: polyline insertPointsAt and splitAt failing

Submitted by:  gianluca de santis <gianlucadesi>
Submitted on:  Tue 24 Mar 2015 10:50:21 AM UTC  
 
Category: PluginsSeverity: 4 - Important
Item Group: Functionality errorStatus: Fixed
Privacy: PublicAssigned to: Benedict Verhegghe <bverheg>
Open/Closed: Closed

Add a New Comment(Rich Markup)
   

You are not logged in

Please log in, so followups can be emailed to you.

 

(Jump to the original submission 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>
Project AdministratorIn charge of this item.
Tue 24 Mar 2015 01:56:17 PM UTC, comment #7:

Fixed in 1568e60.

Benedict Verhegghe <bverheg>
Project AdministratorIn charge of this item.
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>
Project 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>
Project 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:

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

Benedict Verhegghe <bverheg>
Project AdministratorIn charge of this item.
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>
Project AdministratorIn charge of this item.
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>
Project 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>
Project AdministratorIn charge of this item.
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>
Project Member

 

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

Attach File(s):
   
   
Comment:
   

No files currently attached

 

Depends on the following items: None found

Items that depend on this one: None found

 

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

    Do you think this task is very important?
    If so, you can click here to add your encouragement to it.
    This task has 0 encouragements so far.

    Only logged-in users can vote.

     

    Please enter the title of George Orwell's famous dystopian book (it's a date):

     

     

    Follow 5 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Wed 27 May 2015 11:30:03 AM UTCbverhegStatusReady For Test=>Fixed
      Open/ClosedOpen=>Closed
    Tue 24 Mar 2015 01:56:17 PM UTCbverhegStatusNone=>Ready For Test
      Assigned toNone=>bverheg
      Summarypolyline splitAt failing=>polyline insertPointsAt and splitAt failing

    Back to the top


    Powered by Savane 3.1-cleanup1