3

Objective:

Given a set of data, how can I determine if a new data point is above or below the line connecting the points.

For example, how can I determine if the red point shown is above or below the line (without visual inspection)?

![enter image description here

I'd like to fit an exact line to the points. Essentially joining the points, and need a fit to be able to use any point on the line for a comparator.

Current attempts:

So far I've tried fitting various splines to the data, but it is still a bit too smooth. I'm really looking for an exact fit to the data, sharp corners and all.

I've tried a natural spline (as well as smooth.splines), but can't quite get the fit exact/sharp enough:

plot(df$lowerx, df$lowery, type='b', xlab='x', ylab='y', pch=21, bg='steel blue')
myspline <- splinefun(df$lowerx, df$lowery, method='natural')
curve(myspline, add=T, from = 0, to=140, n = 100, col='green')

enter image description here

I think once I get the fit right it will be straightforward use it to figure out if points are above or below the line (e.g. using predict or the function), but I need help with the fit.

Also would welcome another approach entirely.

Data:

df <- structure(list(lowerx = c(11.791, 18.073, 23.833, 35.875, 39.638, 44.153, 59.206, 71.498, 83.289, 95.091, 119.676, 131.467, 143.76), lowery = c(5.205, 5.89, 6.233, 9.041, 10, 10.342, 12.603, 13.493, 14.658, 15.274, 15.89, 15.616, 15.342)), .Names = c("lowerx", "lowery"), class = "data.frame", row.names = c(NA, -13L))
IRTFM
  • 258,963
  • 21
  • 364
  • 487
Minnow
  • 1,733
  • 2
  • 26
  • 52
  • What do you mean by an exact fit? The splines are going through all of the points and the same is true for the linear interpolation in your first figure. In what sense is one of them more exact than the other? – Stibu Dec 18 '15 at 20:39
  • The fit and the line connecting the points should overlap. If you look at the second figure, the green line bows out in places, such that it is not exactly the same as the connecting line. Does that makes sense? – Minnow Dec 18 '15 at 20:52
  • Splines are not supposed to match the linear interpolation. The two are simply different methods that can be used in order to find a line that connects some points. Which one of the two is better depends on the situation. If, for some reason, you should now that the linear interpolation corresponds to the true solution, this "fit" would be the exact one. And vice versa... However, since you usually don't know the true answer, there is no point in calling your interpolant exact. – Stibu Dec 18 '15 at 21:01
  • In this case, the linear interpolation is the true solution. Thanks for the explanation about splines. They were clearly the wrong choice. Didn't know about the approxfun provided by @42, thus the question. – Minnow Dec 18 '15 at 21:10

2 Answers2

10

The R function approxfun will create a function that does a linear interpolation.

> F <- approxfun(x=df$lowerx, y=df$lowery)
> F(80) > 13
[1] TRUE

I used the data you offered and tested my best guess at the coordinates of the "red point" as (80, 13), so it says that 13 is less than the interpolation and (80,15) is above:

> F(80) > 15
[1] FALSE
IRTFM
  • 258,963
  • 21
  • 364
  • 487
0

this post shows how to do the trick: How to tell whether a point is to the right or left side of a line

if position is +1 the point is above, if it's -1 the point is below, if 0 it is directly on the line, no fitting required, you just need to know which two points to refer to span the line...

applied to your example:

df <- structure(list(lowerx = c(11.791, 18.073, 23.833, 35.875, 39.638, 44.153, 59.206, 71.498, 83.289, 95.091, 119.676, 131.467, 143.76), lowery = c(5.205, 5.89, 6.233, 9.041, 10, 10.342, 12.603, 13.493, 14.658, 15.274, 15.89, 15.616, 15.342)), .Names = c("lowerx", "lowery"), class = "data.frame", row.names = c(NA, -15L))

X <- 79
Y <- 13
xIndex2 <- which(df$lowerx > X)[1]
xIndex1 <- xIndex2 - 1
Ax <- df$lowerx[xIndex1]
Ay <- df$lowery[xIndex1]
Bx <- df$lowerx[xIndex2]
By <- df$lowery[xIndex2]
position = sign((Bx - Ax) * (Y - Ay) - (By - Ay) * (X - Ax))
Community
  • 1
  • 1
b00tsy
  • 635
  • 8
  • 25