Issue 72216 - in XY chart do not sort x-values for B-splines
Summary: in XY chart do not sort x-values for B-splines
Status: CLOSED FIXED
Alias: None
Product: General
Classification: Code
Component: chart (show other issues)
Version: 3.3.0 or older (OOo)
Hardware: PC Windows XP
: P3 Trivial (vote)
Target Milestone: ---
Assignee: kla
QA Contact: issues@graphics
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2006-12-02 23:13 UTC by Regina Henschel
Modified: 2013-02-24 21:20 UTC (History)
2 users (show)

See Also:
Issue Type: PATCH
Latest Confirmation in: ---
Developer Difficulty: ---


Attachments
new way to calculate BSplines (5.11 KB, text/plain)
2007-07-09 17:45 UTC, Regina Henschel
no flags Details
example charts (59.26 KB, application/vnd.oasis.opendocument.spreadsheet)
2007-07-09 17:46 UTC, Regina Henschel
no flags Details

Note You need to log in before you can comment on or make changes to this issue.
Description Regina Henschel 2006-12-02 23:13:15 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.
Comment 1 kla 2006-12-04 14:21:17 UTC
@IHA: Pls have a look.
Comment 2 Regina Henschel 2007-07-09 17:44:33 UTC
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.
 
Comment 3 Regina Henschel 2007-07-09 17:45:37 UTC
Created attachment 46656 [details]
new way to calculate BSplines
Comment 4 Regina Henschel 2007-07-09 17:46:21 UTC
Created attachment 46657 [details]
example charts
Comment 5 Regina Henschel 2007-07-09 17:52:21 UTC
Oh, I just see that I have forgotten to erase the function "BSPoint" which is no
longer needed. Shall I sent new patch?
Comment 6 IngridvdM 2007-07-10 13:27:30 UTC
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?
Comment 7 Regina Henschel 2007-07-10 13:54:35 UTC
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.
Comment 8 IngridvdM 2007-07-10 14:27:48 UTC
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?
Comment 9 Regina Henschel 2007-07-10 14:55:23 UTC
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.
Comment 10 IngridvdM 2007-07-10 15:08:12 UTC
Thanks a lot. I changed the code back to the mathematically correct behavior.
Comment 11 IngridvdM 2007-07-16 10:50:56 UTC
->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.
Comment 12 kla 2007-07-17 12:27:31 UTC
verified
Comment 13 kla 2007-11-30 10:51:41 UTC
Seen ok in current master -> closed