What is the best way to find which pair of adjacent points in an arraylist a single point X is closest to in Java?

Question

I have 2D Points in an arraylist (i.e. A, B, C, D), there can contain an arbitrary number of points that represent a line string strung together.

Assume I had a point X that fell between points B and C, how can I ensure that the output of the function is an arraylist with points "B" and "C" are returned (or simply pointA or pointB are assigned to points "B" and "C") given the following two cases:

1- Point X is closer to B than C, but still falls between B and C
2- Point X is closer to C than B, but still falls between C and B
3- Point X is closer to C than G (maybe because the line segments from the array list is oddly shaped like a U or something), but the function should return either the points C and D or C and B, depending on whichever is the closest to pointX.

My current code is as follows, assume pointX is passed into a function that does the following:

Point pointA = null;
Point pointB = null;

int minDistance = Integer.MAX_VALUE;
for(int i = 0; i < pointlist.size(); i++) {
   int distance = pointlist.get(i).getDistanceToPoint(xPoint);
   if(distance < minDistance) {

      if(pointB != null) {
           pointB = pointA;
      }
      minDistance = distance;
      pointA = pointlist.get(i); 
   } else {
     pointB = pointA;
     pointA = pointlist.get(i);
   }
}

The above meets case #1, but not case #2. What is the best way to do this such that pointA is equal to "B", and pointB is equal to "C"? If there is a better way to do this, I am open to it.

Its just the two points that are closest to pointX right? It is not just a 1st and second closest point, if the arraylist of points happened to form a U shape, or some shape that made it so that two points were closest, but not necessarily adjacent to each other, if the function returned those two points, that is incorrect. It should instead return the first point closest to it, then the 2nd point that is adjacent to that point. UNLESS the user may have specified to start from point "4" or a specific index such that if the 6th point was the 2nd closest point to it, then the result would return that 6th point along with the 5th or the 7th, depending on which line segment it falls within.

Unless I'm missing something here, it's no different then finding minimum and second lowest elements in an array. — PM 77-1, Nov 04 '14 at 19:53
I don't get what you are trying to do. If `pointA` is `B` and `pointB` is `C`, then why are you iterating over all the points? Just compare the distance from `pointA` to `pointX` and the distance from `pointB` to `pointX`. — RockOnRockOut, Nov 04 '14 at 19:53
What are the "points"? 2D coordinates? 3D coordinates? single values? (in which case they're not points at all and your naming convension's muddling the problem statement). — Mike 'Pomax' Kamermans, Nov 04 '14 at 19:54
pointA and pointB both start as null. It is up to the code to determine where pointA and pointB equals based on the pointX passed in. 2D coordinates. If pointX happened to lie somewhere betwwn pointC and pointD, the resultwould make pointA=C and pointB=D. Note the points must be adjacent to each other. — Rolando, Nov 04 '14 at 19:55
int minDistance = 10000000; what makes you think an int can hold this large a value ? — StackFlowed, Nov 04 '14 at 19:56
So you have an arbitrary set of 2D points, and you want the subset of size two of the points nearest some given point X? — Mike 'Pomax' Kamermans, Nov 04 '14 at 19:58
@Mike 'Pomax' Kamermans Yes! But the points represent the sequence of multiple line segments strung together. — Rolando, Nov 04 '14 at 19:58
@Rolando that's worth rewriting your question over, because talking about having "A, B, C and D" creates the impression you have four points only. I'll write up an answer. — Mike 'Pomax' Kamermans, Nov 04 '14 at 19:59
You can use `Integer.MAX_VALUE` as your *very large* number. — PM 77-1, Nov 04 '14 at 20:03
My idea was you go through each point the list and use the "distance to pointX" as the way to find out point is closest (that would be something like pointB)... assuming pointB was equal to "D", then you know the other end of the segment must be point "C" or point "E". — Rolando, Nov 04 '14 at 20:08
@PM 77-1 It is not just a 1st and second closest point, if the arraylist of points happened to form a U shape, or some shape that made it so that two points were closest, but not necessarily adjacent to each other, if the function returned those two points, that is incorrect. — Rolando, Nov 04 '14 at 20:10
Yes or a[n], a[n-1]. Point A->B or B->C, or D->E,... or G->H. — Rolando, Nov 04 '14 at 20:16
Again, how do you define "*closest*"? What **metrics** should be used? — PM 77-1, Nov 04 '14 at 20:23
@Rolando you really need to learn to write a good question =) You're making it clear you **don't** have a set of points, you have a set of lines, and you want the line segment that is closest to point X, with the coordinates at the end really being completely irrelevant in terms of "points". — Mike 'Pomax' Kamermans, Nov 04 '14 at 20:25
Edits are welcome. The array list contains a set of "points" ordered by the sequence that make up multiple line segments. (Two points make up a line, 3 points in the list make up up 2 lines). The two points that are "output" or are stored in "pointA" and "pointB" are the points that make up the opposite ends of the line segment closest to the lone pointX that is passed into the function. — Rolando, Nov 04 '14 at 20:29

score 0 · Accepted Answer · edited May 23 '17 at 12:05

So after 14 commends in the comment thread it turns out the problem is actually one of finding the line segment closest to some point X from a set of connected line segments. The set happens to be stored as vertex coordinates only, but this is essentially irrelevant.

I'm going to use Segment because: Java, and also because if you want to solve a problem use the datastructures to match your problem. Want to find a line? Use a line class. So: let's use a dedicated class to represent a line segment instead of an ArrayList with 2 points in it:

class Segment {
  Point p1, p2;
  public Segment(Point a, Point b) { p1=a; p2=b; }
}

ArrayList<Segment> segments = new ArrayList<Segment>();
for(int i=0, last=points.size()-1; i<last; i++) {
  segments.add(new Segment(points.get(i), points.get(i+1));
}

Done. So, closest segment:

Segment findClosestSegment(ArrayList<Segment> segments, Point target) {
  double dist, minDist = Double.MAX_VALUE;
  Segment minDistSegment;
  for(Segment s: segments) {
    dist = s.distanceTo(target);
    if(dist < minDist) {
      minDist = dist;
      minDistSegment = s;
    }
  }
  return minDistSegment;
}

Now we just need to implement Segment.distanceTo(Point), which requires implementing a bit of linear algebra for (a) getting the projection distance for the point to the line segment, and then (b) making sure the projection lies within the segment's start/end point.

There's actually tons of sites that have that code for you so I'm not including it here (pretty sure there are SO questions for that code in every conceivable language by now), but is literally the only correct metric for determining closeness of a point to a specific line segment.

What is the best way to find which pair of adjacent points in an arraylist a single point X is closest to in Java?

1 Answers1