在Java中，找到单个点X最接近arraylist中哪对相邻点的最佳方法是什么？

Question

我在arraylist中有2D点（即A、B、C、D），可以包含任意数量的点，这些点代表串在一起的线串

假设我有一个位于点B和C之间的点X，在以下两种情况下，如何确保函数的输出是一个返回点“B”和“C”的arraylist（或者简单地将点a或点B分配给点“B”和“C”）：

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.

我当前的代码如下，假设pointX被传递到一个函数中，该函数执行以下操作：

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);
   }
}

上述情况符合案例1，但不符合案例2。这样做的最佳方式是什么，使得点A等于“B”，点B等于“C”？如果有更好的方法，我愿意接受

这只是最接近pointX的两个点，对吗 如果点的数组列表恰好形成了一个U形，那么它不仅是第一个和第二个最近的点，或者是某个形状使得两个点最近，但不一定彼此相邻，如果函数返回了这两个点，那么这是不正确的。它应该返回最接近它的第一个点，然后返回与该点相邻的第二个点除非用户可能指定从点“4”或特定索引开始，如果第6个点是距离它最近的第2个点，则结果将返回该第6个点以及第5个或第7个点，具体取决于它属于哪个线段

Answer 1

因此，在注释线程中输入14次后，问题实际上是从一组连接的线段中找到离某个点X最近的线段。该集合碰巧只存储为顶点坐标，但这基本上是无关的

我将使用Segment因为：Java，而且如果你想解决一个问题，使用数据结构来匹配你的问题。想排队吗？使用line类。所以：让我们使用一个专用类来表示线段，而不是一个包含两个点的ArrayList：

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));
}

完成了。所以，最近的部分：

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;
}

现在我们只需要实现Segment.distanceTo(Point)，这需要为（a）getting the projection distance for the point to the line segment实现一点线性代数，然后（b）确保投影位于段的起点/终点内

事实上，有很多网站都有这样的代码，所以我不在这里（非常确定there are SO questions for that code在所有可能的语言中都有），但它确实是确定一个点到特定线段的接近程度的唯一正确指标