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

一尘不染

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

algorithm

我有一张地图，里面有很多多边形，其中一个里面有一个点，像这样：

多边形边缘的x和y坐标保存在这样的数据库中（例如）：

Polygon(Point(11824, 10756), Point(11822, 10618), Point(11912, 10517), Point(12060, 10529), Point(12158, 10604), Point(12133, 10713), Point(12027, 10812), Point(11902, 10902)),
Polygon(Point(11077, 13610), Point(10949, 13642), Point(10828, 13584), Point(10772, 13480), Point(10756, 13353), Point(10849, 13256), Point(10976, 13224), Point(11103, 13294), Point(11171, 13414), Point(11135, 13558)),
Polygon(Point(11051.801757813, 11373.985351563), Point(11165.717773438, 11275.469726563), Point(11281.733398438, 11255.646484375), Point(11381.07421875, 11333.15625), Point(11440.202148438, 11467.706054688), Point(11404.73046875, 11584.534179688), Point(11301.662109375, 11643.852539063), Point(11169.486328125, 11644.079101563), Point(11067.555664063, 11579.676757813), Point(11018.21484375, 11454.750976563)),
Polygon(Point(12145, 13013), Point(12069.065429688, 13014.67578125), Point(12012.672851563, 12953.833984375), Point(11973.942382813, 12910.14453125), Point(11958.610351563, 12853.736328125), Point(11988.58203125, 12780.668945313), Point(12046.806640625, 12735.046875), Point(12117.080078125, 12729.838867188), Point(12185.567382813, 12743.389648438), Point(12225.575195313, 12803.530273438), Point(12255.934570313, 12859.2109375), Point(12263.861328125, 12914.166992188), Point(12221.2578125, 12978.983398438)),

它们是在以后绘制的，我无法访问，只能访问此坐标。所以我有多边形边缘的x / y和红点的x / y。现在我必须知道红点在哪个多边形中。

然后，我最需要的是：多边形

我有红点的x和y坐标以及边缘的xy坐标。我需要绿点的x和y坐标。（多边形外最近的位置）

我需要lua，但可以用任何语言随意回答，我可以翻译。

阅读 256

2020-07-28

共1个答案

一尘不染

要知道该点在哪个多边形中，可以使用“ 射线投射”算法。

为了找到最接近的边缘，您可以使用幼稚的方法来计算到每个边缘的距离，然后取最小值。只要记住检查与边的交点是否在边之外（请检查此）。如果在外面，则将其距离边缘的最近端点。

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

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

我认为这个伪代码应该可以帮助您，当然，一旦有了要插入的多边形！

2020-07-28