Apache OpenOffice (AOO) Bugzilla – Issue 72216
in XY chart do not sort x-values for B-splines
Last modified: 2013-02-24 21:20:45 UTC
If you use the variant B-Spline in an XY chart, then the points are sorted. Therefor you cannot draw curves, which turn back. But I think, that it is not necessary to sort the points. Please have a look at http://www.apm.tuwien.ac.at/docs/lva/mmgdv/k1___014.htm (German). There you find a description, how to calculate B-Spline curves without sorting the control points. Based on that text I try to describe, how I think it might work. I cannot write C++ and do not know about all the stuff in the source, so I will use pseudo code. I refer to graphics/chart2/source/view/charttypes/Splines.cxx /*I use the names as in the function CalculateBSplines. I comment them, so that you can control, whether I understand them correct: nDegree is the order of the B-splines in mathematical sense. It is 1 higher than the value from the input field “Data points orderâ€. */ nDegree = nDegree + 1; /*The control points are in rInput. They come from the data points which the user specifies. I write it so as if they are indexed from 0 to n in the order they are written in the data series. It should be sure, that each control point is a point and no x-value and no y-value is missing. */ // calculate n n = rInput.SequenceX[0].getLength()-1;//maximum index of control points /* nNewSectorCount gives the number of lines, which will build the polyline which interpolates the B-spline curve. nGranularity is the value from the input field “Resolutionâ€. */ nNewSectorCount = nGranularity * n; // t is the node vector const double* t = createTVector(n, nDegree); /* b will contain function values of the blending functions for a specific argument x. b will have indexes from 0 to n+nDegree. Most of the values in b are zero. You need only values from index i0-nDegree+1 to i0, where i0 is that index for with x is in the interval [t[i0];t[i0+1][. */ double *b = new double [n + nDegree + 1]; /* The arguments x must be in [0; n-nDegree+2]. The number of arguments must be nNewSectorCount+1. I will use ib to count the arguments. For each argument x you get a point. Later on you will draw connection lines between this points. Therefor you need a vector or an array (or how you call it) with index ib from 0 to nNewSectorCount to store the points. I will name it BSplinePoint here. */ xStep = (n - nDegree + 2.0) / nNewSectorCount; x = 0.0; //later on it will be increased by xStep for (ib = 0; ib <= nNewSectorCount; ib ++) { // Calculate the values of the blending functions for this special x value BVector(x, n, nDegree, b, t); /* Calculate the B-spline point with index ib. It is a sum. For the boundaries of the sum you need the value i0 like that in function BVector. */ i0 = floor(x) + nDegree – 1; /* Can you multiply a point as a whole with a number? I write it here for each coordinate.*/ // initialize sum with zero BSplinePoint[ib].xcoordinate = 0.0 BSplinePoint[ib].ycoordinate = 0.0 //summarize for (i = i0-nDegree+1; i <= i0; i ++) { BSplinePoint[ib].xcoordinate = BSplinePoint[ib].xcoordinate+ rInput[i].xcoordinate *b[i] BSplinePoint[ib].ycoordinate = BSplinePoint[ib].ycoordinate+ rInput[i].ycoordinate *b[i] } //next value for x x = x+xStep //next value for ib is automatically generated by the loop } /*Now you have got a vector of points, which are points of the B-spline curve. With this points you can draw a polyline, like you would do, if an user chooses the not smoothed variant line in the XY chart. */ ================ In addition: If the text, which I mentioned, is right, then I think you can improve this: In function BVector goto the loops for( sal_Int32 j=2; j<=k; j++ ) for( i=0; i<=i0; i++ ) b[i] = TLeft(x, i, j, t) * b[i] + TRight(x, i, j, t) * b [i + 1]; } I think, that in the inner loop you need not to start with i=0, but you can start with i=i0-j+1, because the other values of b[] are zero.
@IHA: Pls have a look.
I have rewritten the way how BSplines are calculated, so that it is no longer needed to order the points. Now you can use BSplines for spirals and ovals for example. The main idea is, that you do not traverse the points along their x-coordinates, but use the index of the points. You have to calculate the x-coordinate of a BSpline point in the same way as the y-coordinate. I do not use the tricks in the mentioned text to "optimize" the algorithmn, but follow close the old way of calculating. The text contains some if-clauses where I test, ob the given values are valid. If you can ensure, that the place which calls the method guarantees that the values are valid, you can erase those parts. It can happpen, that a user sets a "Data points order" to high, so that there are not enough points to calculate the polynoms. In this case my solution draws nothing. It would be nice, if the user can be told what is wrong, but I don't know how to do. The patch is based on a SCR680_m218. I use Microsoft Visual C++ 2005 Express on WinXp.
Created attachment 46656 [details] new way to calculate BSplines
Created attachment 46657 [details] example charts
Oh, I just see that I have forgotten to erase the function "BSPoint" which is no longer needed. Shall I sent new patch?
Thanks for the patch Regina! I checked it in for CWS chart07. I made the following two changes to the patch: 1) removed unused BSPoint as you indicated 2) changed condition if (fMaxCurveparam <= 0.0) to if (fMaxCurveparam < 0.0) I think having fMaxCurveparam = 0.0 is still valid, or?
I think mathematically it is not valid. If you have n=2 and k=4 for example (2+n-k=2+2-4=0) then you have 3 points and try to approximate with polynoms of degree 3. But that is not possible, because a polynom of degree 3 has 4 coefficients and therefore you need 4 points to calculate them. Even with fMaxCurveParam = 0, we will not enter the outer loop, because the stop-condition is false immediately. Therefore it will not raise an error as far as I see, but you get the last input point into the output. So the question seems to be, whether you want an empty output as in my version or 1 output point as in your version.
hm, I enter the loop and get more than one output point, but when this all is wrong anyhow then we shouldn't do it. I was confused by my example which had two equal points that was counted as one point only after sorting. So the number of points reduced silently, hmhm. For 2.3 we cannot display a warning to the user in this case anymore as feature freeze is passed already. What do you think a bout a silent fallback to a fitting degree? Or better display nothing thus the user stumbles more quickly about the problem?
I looked again and found, that allowing fMaxCurveparam=0 leads to fCurveStep=0. The test must be fMaxCurveparam<=0.0 My current version displays nothing in case fMaxCurveparam, which I think is mathematically correct. Perhaps we can add it to the help.
Thanks a lot. I changed the code back to the mathematically correct behavior.
->Thomas, please verify in CWS chart07. Load the attached example doc and make sure that the line on the spiral page forms a spiral and the line on the oval page forms an oval.
verified
Seen ok in current master -> closed