如何从多边形内的点获取多边形外的最近点？

2 回答

• 1

  要知道该点在哪个多边形中，可以使用Ray Casting algorithm .

  为了找到最近的边缘，你可以使用一个简单的方法计算distance to each edge然后采取最小值 . 只需记住检查边缘的交点是否在边缘之外（检查this） . 如果它在外面，则距离边缘最近的极端 .

  好吧用一些伪代码更好地解释直觉：

  dot(u,v) --> ((u).x * (v).x + (u).y * (v).y)
  norm(v)  --> sqrt(dot(v,v))     // norm = length of vector
  dist(u,v)--> norm(u-v)          // distance = norm of difference
  
  // Vector contains x and y
  // Point contains x and y
  // Segment contains P0 and P1 of type Point
  // Point  = Point ± Vector
  // Vector = Point - Point
  // Vector = Scalar * Vector
  Point closest_Point_in_Segment_to(Point P, Segment S)
  {
       Vector v = S.P1 - S.P0;
       Vector w = P - S.P0;
  
       double c1 = dot(w,v);
       if ( c1 <= 0 )   // the closest point is outside the segment and nearer to P0
            return S.P0;
  
       double c2 = dot(v,v);
       if ( c2 <= c1 )  // the closest point is outside the segment and nearer to P1
            return S.P1;
  
       double b = c1 / c2;
       Point Pb = S.P0 + b * v;
       return Pb;
  }
  
  [Point, Segment] get_closest_border_point_to(Point point, Polygon poly) {
  
      double bestDistance = MAX_DOUBLE;
      Segment bestSegment;
      Point bestPoint;
  
      foreach s in poly.segments {
          Point closestInS = closest_Point_in_Segment_to(point, s);
          double d = dist(point, closestInS);
          if (d < bestDistance) {
              bestDistance = d;
              bestSegment = s;
              bestPoint = closestInS; 
          }
      }
  
      return [bestPoint, bestSegment];
  }
  

  我认为这个伪代码应该让你去，当然，一旦你有了多边形你的观点！

  回复于 2024-05-02T09:02:06+08:00
• 4

  我的 PolyCollisions 课程：

  public class PolyCollisions {
  
      // Call this function...
      public static Vector2 doCollisions (Vector2[] polygon, Vector2 point) {
  
          if(!pointIsInPoly(polygon, point)) {
              // The point is not colliding with the polygon, so it does not need to change location
              return point;
          }
  
          // Get the closest point of the polygon
          return closestPointOutsidePolygon(polygon, point);
  
      }
  
      // Check if the given point is within the given polygon (Vertexes)
      // 
      // If so, call on collision if required, and move the point to the
      // closest point outside of the polygon
      public static boolean pointIsInPoly(Vector2[] verts, Vector2 p) {
          int nvert = verts.length;
          double[] vertx = new double[nvert];
          double[] verty = new double[nvert];
          for(int i = 0; i < nvert; i++) {
              Vector2 vert = verts[i];
              vertx[i] = vert.x;
              verty[i] = vert.y;
          }
          double testx = p.x;
          double testy = p.y;
          int i, j;
          boolean c = false;
          for (i = 0, j = nvert-1; i < nvert; j = i++) {
              if ( ((verty[i]>testy) != (verty[j]>testy)) &&
                      (testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) )
                  c = !c;
          }
          return c;
      }
  
      // Gets the closed point that isn't inside the polygon...
      public static Vector2 closestPointOutsidePolygon (Vector2[] poly, Vector2 point) {
  
          return getClosestPointInSegment(closestSegment(poly, point), point);
  
      }
  
      public static Vector2 getClosestPointInSegment (Vector2[] segment, Vector2 point) {
  
          return newPointFromCollision(segment[0], segment[1], point);
  
      }
  
      public static Vector2 newPointFromCollision (Vector2 aLine, Vector2 bLine, Vector2 p) {
  
          return nearestPointOnLine(aLine.x, aLine.y, bLine.x, bLine.y, p.x, p.y);
  
      }
  
      public static Vector2 nearestPointOnLine(double ax, double ay, double bx, double by, double px, double py) {
  
          // https://stackoverflow.com/questions/1459368/snap-point-to-a-line-java
  
          double apx = px - ax;
          double apy = py - ay;
          double abx = bx - ax;
          double aby = by - ay;
  
          double ab2 = abx * abx + aby * aby;
          double ap_ab = apx * abx + apy * aby;
          double t = ap_ab / ab2;
          if (t < 0) {
              t = 0;
          } else if (t > 1) {
              t = 1;
          }
          return new Vector2(ax + abx * t, ay + aby * t);
      }
  
      public static Vector2[] closestSegment (Vector2[] points, Vector2 point) {
  
          Vector2[] returns = new Vector2[2];
  
          int index = closestPointIndex(points, point);
  
          returns[0] = points[index];
  
          Vector2[] neighbors = new Vector2[] {
                  points[(index+1+points.length)%points.length],
                  points[(index-1+points.length)%points.length]
          };
  
          double[] neighborAngles = new double[] {
                  getAngle(new Vector2[] {point, returns[0], neighbors[0]}),
                  getAngle(new Vector2[] {point, returns[0], neighbors[1]})
          };
          // The neighbor with the lower angle is the one to use
          if(neighborAngles[0] < neighborAngles[1]) {
              returns[1] = neighbors[0];
          } else {
              returns[1] = neighbors[1];
          }
  
          return returns;
  
      }
  
      public static double getAngle (Vector2[] abc) {
  
          // https://stackoverflow.com/questions/1211212/how-to-calculate-an-angle-from-three-points
          // atan2(P2.y - P1.y, P2.x - P1.x) - atan2(P3.y - P1.y, P3.x - P1.x)
          return Math.atan2(abc[2].y - abc[0].y, abc[2].x - abc[0].x) - Math.atan2(abc[1].y - abc[0].y, abc[1].x - abc[0].x);
  
      }
  
      public static int closestPointIndex (Vector2[] points, Vector2 point) {
  
          int leastDistanceIndex = 0;
          double leastDistance = Double.MAX_VALUE;
  
          for(int i = 0; i < points.length; i++) {
              double dist = distance(points[i], point);
              if(dist < leastDistance) {
                  leastDistanceIndex = i;
                  leastDistance = dist;
              }
          }
  
          return leastDistanceIndex;
  
      }
  
      public static double distance (Vector2 a, Vector2 b) {
          return Math.sqrt(Math.pow(Math.abs(a.x-b.x), 2)+Math.pow(Math.abs(a.y-b.y), 2));
      }
  
  }
  

  这是一个小的解释（有趣的事实：这是我发布到堆栈溢出的第一个图像！）

  

  对不起，它太乱了......

  ---

  课程循序渐进：

  • 检查给定点是否在多边形内

  • 如果不是，则返回当前点，因为不需要进行任何更改 .

  • 找到多边形最近的VERTEX

  • 这不是最接近的POINT，因为点可以在顶点之间

  • grab 顶点的两个邻居，保持一个角度较小的邻居 .

  • 较低的角度比较高的角度具有较低的距离，因为较高的角度"goes away"更快

  • 使用StackOverflow上this问题的答案获取线段的最近点 .

  ---

  恭喜！你幸免于糟糕的教程！希望它有所帮助:)感谢所有评论链接的答案，帮助我帮助你！

  Snap Point to Line

  How to calculate an angle from 3 points

  回复于 2024-05-02T09:02:06+08:00