CODEWITHSUNDEEP
pythonalgorithmfunction
user5251577
user5251577

Reputation:

Finding the points nearest to a given x?

I need to interpolate a linear function and I can't use numpy or scipy.

I'm given this data points ((0,10), (1,4), (2,3), (3,5), (4,12)) and a point on `x = 2.8. the data points is polyline (linear between 2 coordinates)

of course I need to use the closest x-points from the data for 2.8. which is from (2,3) and (3,5) because 2.8 lies between the 2 and 3.

How do I make a function to find this closest points?

Upvotes: 2

Views: 3550

Answers (4)

Delgan
Delgan

Reputation: 19677

def closest(points, x):
    return sorted(points, key=lambda p: abs(p[0] - x))[:2]

>>> points = ((0,10), (1,4), (2,3), (3,5), (4,12))
>>> x = 2.8
>>> closest(points, x)
[(3, 5), (2, 3)]


This can also be written without using lambda function (but x have to be global then): 

def mySortKey(p):
    return abs(p[0] - x) 

def closest(points):
    return sorted(points, key = mySortKey)[:2]

Upvotes: 4

redevined
redevined

Reputation: 832

Just to be sure, the only things that matter are the first values of your 2-tuples?

This is a very simple approach:

def getNearest(x, points) :
    smaller = [point for point in points if point[0] <= x]
    greater = [point for point in points if point[0] >= x]
    smallest = max(sorted(smaller))
    greatest = min(sorted(greater))
    return smallest, greatest

points = ((0,10), (1,4), (2,3), (3,5), (4,12))
x = 2.8

pointA, pointB = getNearest(x, points)

pointA and pointB are the nearest lower and upper points to your x.

Upvotes: 0

Yves Lange
Yves Lange

Reputation: 3994

You can compute the distance of chosen points.

1) Search for the minimun distance X value (left and right).

2) Search each points corresponding with X_MIN_LEFT and X_MIN_RIGHT. At the same time you can check the distance with Y and find the minimum Y distance.

That's it.

Upvotes: 0

ilent2
ilent2

Reputation: 5241

You could start by eliminating the pairs which do not bound the target point.

x = 2.8
given = [(0,10), (1,4), (2,3), (3,5), (4,12)]
fewer = [(a,b) for a,b in given if a <= x and b >= x]

Then you might want to choose the smallest range which bounds the points.

result = min(fewer, key = lambda l: l[1]-l[0])

You can improve on this method by possibly combining the steps, but this solution breaks the problem down into smaller components.

I'll leave it to you to make this into a function.

Upvotes: 0

Related Questions