2

[Question has been rewritten for clarification]

I'm trying to come up with a sorting function. What is being sorted is a list of points.

The sorting function takes in 3 points. One from the list of points to be sorted, and two others that are used for comparison. The goal is to determine the relative euclidean distance the point to be sorted is from the other two points. The lowest value of the function should be given when the point lies directly between the two points. The function should make use of the euclidean distance between both points.

So far seems like the formula should either be the some of the squares of the distance, or to create a point in between the two given points, and use the euclidean distance to that point. below I've include the two possible function so far.

p is the point to be sorted
p1,p2 are the given points

def f(p,p1,p2): #Midpoint distance
   midPoint = midpoint(p1,p2)
   return distance(p,midPoint)

def f(p,p1,p2): #Sum of squares
   return distance(p,p1) ** 2 + distance(p,p2) ** 2

def distance(pointA,pointB): #Psudocode
   dx = pointA.x - pointB.x
   dy = pointA.y - pointB.y
   return sqrt(dx ** 2 + dy ** 2)

Below is an example:

enter image description here

The two points being considered here are the ones with the line drawn between them. The circled points should be the three lowest points in the sorting algorithm. The close point to the left is penalized for being close to one of the two points, but far from the other.

Nuclearman
  • 5,029
  • 1
  • 19
  • 35
  • 1
    Could give some more context? Because I really do not understand with which logic you want those 3 to be the closest. I'd do exactly the opposite of you. I define a distance `h` and then using it I'd say "oh yes they indeed are the closest" or "no they weren't". Doing the other way round without a lot more information on which characteristic you want to have is really hard. – Bakuriu Nov 20 '12 at 17:33
  • It sounds like you're working with matrices, in which case [this might be what you're looking for](http://stackoverflow.com/questions/1871536/euclidean-distance-between-points-in-two-different-numpy-arrays-not-within). – jathanism Nov 20 '12 at 17:34
  • 1
    Please explain *why* you consider those three points to be the closest. This might help clarify your problem statement, which is a little vague at present. – NPE Nov 20 '12 at 17:36
  • 1
    Also, how can we tell you an "accepted way of doing this" if you do not tell us what you are doing? Different situations would require different distances, so I'd say there is no "accepted" answer to your general question. You have to narrow it down if you want useful answers. – Bakuriu Nov 20 '12 at 17:36
  • I've updated the question to try to clarify what I meant. I'm thinking least squares/minimize the sum of the squares might be what I'm looking for. – Nuclearman Nov 20 '12 at 18:32
  • This question as is cannot be answered, because you don't know (yet) what you want. After you decide which distance function you want to use, then we can help. I suggest consider the minimum distance between point and segment, or between point and segment's middle, or whatever else is DEFINED. – heltonbiker Nov 20 '12 at 18:37
  • Euclidian distance between what? – heltonbiker Nov 20 '12 at 18:40
  • I've rewritten and add the two current possibilities for function. That might answer what your asking. Also added psudocode for the distance function – Nuclearman Nov 20 '12 at 18:58

2 Answers2

2

Well using the average seems like the intuitive way to do it (by the way this will be the same as using the sum). One other thing you could do would be to use the 'weighted' average. For instance, if a is the shorter distance, you could give it a higher priority by using (2*a + b) / 3, for instance (or in general (m*a + b*n) / (m + n) where m > n).

arshajii
  • 127,459
  • 24
  • 238
  • 287
2

Maybe the Least Squares method would help? So you sum the square of the distances. This way the left node would be penalized for being too far from the right node in the line.

Another option is to take the distance to the halfway point on the line made by the two base nodes. This would also prefer the three nodes to the one on the left.

BoppreH
  • 8,014
  • 4
  • 34
  • 71
  • Both are those might be useful, as the "closest" possible would lie in-between the two points given. Hard to say which would be better at this point. Might end up trying both and see what yields better results. – Nuclearman Nov 20 '12 at 18:35