Skip to content

Commit eaa4fc9

Browse files
eskrocheskroch
committed
Automatically draw a monotonic curve when using Hermite cubic spline interpolation on a scatter plot with monotonic plot data. Fixed issue core-plot#193.
1 parent 0ebfd13 commit eaa4fc9

1 file changed

Lines changed: 127 additions & 26 deletions

File tree

‎framework/Source/CPTScatterPlot.m‎

Lines changed: 127 additions & 26 deletions
Original file line numberDiff line numberDiff line change
@@ -52,6 +52,7 @@ -(nonnull CGPathRef)newCurvedDataLinePathForViewPoints:(nonnull CGPoint *)viewPo
5252
-(void)computeBezierControlPoints:(nonnull CGPoint *)cp1 points2:(nonnull CGPoint *)cp2 forViewPoints:(nonnull CGPoint *)viewPoints indexRange:(NSRange)indexRange;
5353
-(void)computeCatmullRomControlPoints:(nonnull CGPoint *)points points2:(nonnull CGPoint *)points2 withAlpha:(CGFloat)alpha forViewPoints:(nonnull CGPoint *)viewPoints indexRange:(NSRange)indexRange;
5454
-(void)computeHermiteControlPoints:(nonnull CGPoint *)points points2:(nonnull CGPoint *)points2 forViewPoints:(nonnull CGPoint *)viewPoints indexRange:(NSRange)indexRange;
55+
-(BOOL)monotonicViewPoints:(nonnull CGPoint *)viewPoints indexRange:(NSRange)indexRange;
5556

5657
@end
5758

@@ -1246,7 +1247,7 @@ -(nonnull CGPathRef)newCurvedDataLinePathForViewPoints:(nonnull CGPoint *)viewPo
12461247
* @param alpha The alpha value used for the catmull-rom interpolation.
12471248
* @param viewPoints A pointer to the array which holds all view points for which the interpolation should be calculated.
12481249
* @param indexRange The range in which the interpolation should occur.
1249-
* @warning The indexRange must be valid for all passed arrays otherwise this method crashes.
1250+
* @warning The @par{indexRange} must be valid for all passed arrays otherwise this method crashes.
12501251
**/
12511252
-(void)computeCatmullRomControlPoints:(nonnull CGPoint *)points points2:(nonnull CGPoint *)points2 withAlpha:(CGFloat)alpha forViewPoints:(nonnull CGPoint *)viewPoints indexRange:(NSRange)indexRange
12521253
{
@@ -1318,57 +1319,157 @@ -(void)computeCatmullRomControlPoints:(nonnull CGPoint *)points points2:(nonnull
13181319
}
13191320
}
13201321

1321-
/** @brief Compute the control points using a hermite cubic spline. Taken from https://en.wikipedia.org/wiki/Cubic_Hermite_spline (see representations).
1322+
/** @brief Compute the control points using a hermite cubic spline.
1323+
*
1324+
* If the view points are monotonically increasing or decreasing in both @par{x} and @par{y},
1325+
* the smoothed curve will be also.
1326+
*
13221327
* @param points A pointer to the array which should hold the first control points.
13231328
* @param points2 A pointer to the array which should hold the second control points.
13241329
* @param viewPoints A pointer to the array which holds all view points for which the interpolation should be calculated.
13251330
* @param indexRange The range in which the interpolation should occur.
1326-
* @warning The indexRange must be valid for all passed arrays otherwise this method crashes.
1331+
* @warning The @par{indexRange} must be valid for all passed arrays otherwise this method crashes.
13271332
**/
13281333
-(void)computeHermiteControlPoints:(nonnull CGPoint *)points points2:(nonnull CGPoint *)points2 forViewPoints:(nonnull CGPoint *)viewPoints indexRange:(NSRange)indexRange
13291334
{
1335+
// See https://en.wikipedia.org/wiki/Cubic_Hermite_spline and https://en.m.wikipedia.org/wiki/Monotone_cubic_interpolation for a discussion of algorithms used.
13301336
if ( indexRange.length >= 2 ) {
1331-
NSUInteger startIndex = indexRange.location;
1332-
NSUInteger numberOfPoints = NSMaxRange(indexRange) - 1; // last accessible element in view points
1333-
for ( NSUInteger index = indexRange.location; index <= numberOfPoints; index++ ) {
1334-
CGPoint p0, p1, p2, lhsControlPoint, rhsControlPoint;
1337+
NSUInteger startIndex = indexRange.location;
1338+
NSUInteger lastIndex = NSMaxRange(indexRange) - 1; // last accessible element in view points
13351339

1336-
p1 = viewPoints[index]; // is always valid
1340+
BOOL monotonic = [self monotonicViewPoints:viewPoints indexRange:indexRange];
1341+
1342+
for ( NSUInteger index = startIndex; index <= lastIndex; index++ ) {
1343+
CGVector m;
1344+
CGPoint p1 = viewPoints[index];
13371345

1338-
CGFloat mx, my;
13391346
if ( index == startIndex ) {
1340-
p2 = viewPoints[index + 1];
1341-
mx = (p2.x - p1.x) * CPTFloat(0.5);
1342-
my = (p2.y - p1.y) * CPTFloat(0.5);
1347+
CGPoint p2 = viewPoints[index + 1];
1348+
1349+
m.dx = p2.x - p1.x;
1350+
m.dy = p2.y - p1.y;
13431351
}
1344-
else if ( index == numberOfPoints ) {
1345-
p0 = viewPoints[index - 1];
1346-
mx = (p1.x - p0.x) * CPTFloat(0.5);
1347-
my = (p1.y - p0.y) * CPTFloat(0.5);
1352+
else if ( index == lastIndex ) {
1353+
CGPoint p0 = viewPoints[index - 1];
1354+
1355+
m.dx = p1.x - p0.x;
1356+
m.dy = p1.y - p0.y;
13481357
}
13491358
else { // index > startIndex && index < numberOfPoints
1350-
p2 = viewPoints[index + 1];
1351-
p0 = viewPoints[index - 1];
1359+
CGPoint p0 = viewPoints[index - 1];
1360+
CGPoint p2 = viewPoints[index + 1];
13521361

1353-
mx = (p2.x - p1.x) * CPTFloat(0.5) + (p1.x - p0.x) * CPTFloat(0.5);
1354-
my = (p2.y - p1.y) * CPTFloat(0.5) + (p1.y - p0.y) * CPTFloat(0.5);
1362+
m.dx = p2.x - p0.x;
1363+
m.dy = p2.y - p0.y;
1364+
1365+
if ( monotonic ) {
1366+
if ( m.dx > CPTFloat(0.0) ) {
1367+
m.dx = MIN(p2.x - p1.x, p1.x - p0.x);
1368+
}
1369+
else if ( m.dx < CPTFloat(0.0) ) {
1370+
m.dx = MAX(p2.x - p1.x, p1.x - p0.x);
1371+
}
1372+
1373+
if ( m.dy > CPTFloat(0.0) ) {
1374+
m.dy = MIN(p2.y - p1.y, p1.y - p0.y);
1375+
}
1376+
else if ( m.dy < CPTFloat(0.0) ) {
1377+
m.dy = MAX(p2.y - p1.y, p1.y - p0.y);
1378+
}
1379+
}
13551380
}
1381+
13561382
// get control points
1357-
mx /= CPTFloat(3.0);
1358-
my /= CPTFloat(3.0);
1359-
rhsControlPoint = CPTPointMake(p1.x + mx, p1.y + my);
1360-
lhsControlPoint = CPTPointMake(p1.x - mx, p1.y - my);
1383+
m.dx /= CPTFloat(6.0);
1384+
m.dy /= CPTFloat(6.0);
13611385

1362-
// We calculated the lhs & rhs control point. the rhs control point is the first control point for the curve to the next point. the lhs control point is the second control point for the curve to the current point.
1386+
CGPoint rhsControlPoint = CPTPointMake(p1.x + m.dx, p1.y + m.dy);
1387+
CGPoint lhsControlPoint = CPTPointMake(p1.x - m.dx, p1.y - m.dy);
1388+
1389+
// We calculated the lhs & rhs control point. The rhs control point is the first control point for the curve to the next point. The lhs control point is the second control point for the curve to the current point.
13631390

13641391
points2[index] = lhsControlPoint;
1365-
if ( index + 1 <= numberOfPoints ) {
1392+
if ( index + 1 <= lastIndex ) {
13661393
points[index + 1] = rhsControlPoint;
13671394
}
13681395
}
13691396
}
13701397
}
13711398

1399+
/** @brief Determine whether the plot points form a monotonic series.
1400+
* @param viewPoints A pointer to the array which holds all view points for which the interpolation should be calculated.
1401+
* @param indexRange The range in which the interpolation should occur.
1402+
* @return Returns @YES if the viewpoints are monotonically increasing or decreasing in both @par{x} and @par{y}.
1403+
* @warning The @par{indexRange} must be valid for all passed arrays otherwise this method crashes.
1404+
**/
1405+
-(BOOL)monotonicViewPoints:(nonnull CGPoint *)viewPoints indexRange:(NSRange)indexRange
1406+
{
1407+
if ( indexRange.length < 2 ) {
1408+
return YES;
1409+
}
1410+
1411+
NSUInteger startIndex = indexRange.location;
1412+
NSUInteger lastIndex = NSMaxRange(indexRange) - 2;
1413+
1414+
BOOL foundTrendX = NO;
1415+
BOOL foundTrendY = NO;
1416+
BOOL isIncreasingX = NO;
1417+
BOOL isIncreasingY = NO;
1418+
1419+
for ( NSUInteger index = startIndex; index <= lastIndex; index++ ) {
1420+
CGPoint p1 = viewPoints[index];
1421+
CGPoint p2 = viewPoints[index + 1];
1422+
1423+
if ( !foundTrendX ) {
1424+
if ( p2.x > p1.x ) {
1425+
isIncreasingX = YES;
1426+
foundTrendX = YES;
1427+
}
1428+
else if ( p2.x < p1.x ) {
1429+
foundTrendX = YES;
1430+
}
1431+
}
1432+
1433+
if ( foundTrendX ) {
1434+
if ( isIncreasingX ) {
1435+
if ( p2.x < p1.x ) {
1436+
return NO;
1437+
}
1438+
}
1439+
else {
1440+
if ( p2.x > p1.x ) {
1441+
return NO;
1442+
}
1443+
}
1444+
}
1445+
1446+
if ( !foundTrendY ) {
1447+
if ( p2.y > p1.y ) {
1448+
isIncreasingY = YES;
1449+
foundTrendY = YES;
1450+
}
1451+
else if ( p2.y < p1.y ) {
1452+
foundTrendY = YES;
1453+
}
1454+
}
1455+
1456+
if ( foundTrendY ) {
1457+
if ( isIncreasingY ) {
1458+
if ( p2.y < p1.y ) {
1459+
return NO;
1460+
}
1461+
}
1462+
else {
1463+
if ( p2.y > p1.y ) {
1464+
return NO;
1465+
}
1466+
}
1467+
}
1468+
}
1469+
1470+
return YES;
1471+
}
1472+
13721473
// Compute the control points using the algorithm described at http://www.particleincell.com/blog/2012/bezier-splines/
13731474
// cp1, cp2, and viewPoints should point to arrays of points with at least NSMaxRange(indexRange) elements each.
13741475
-(void)computeBezierControlPoints:(nonnull CGPoint *)cp1 points2:(nonnull CGPoint *)cp2 forViewPoints:(nonnull CGPoint *)viewPoints indexRange:(NSRange)indexRange

0 commit comments

Comments
 (0)