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