How to get the nearest point outside a polygon from a point inside a polygon?

Question

I have a map with a lot of polygons and a point inside in one of them, like this:

The x and y coordinates of the edges of the polygons are save in a database like this(for example):

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)),

They are drawn later, I don't have access to that, only to this coordinates. So I have the x/y of the edges of the polygons and the x/y of the red dot. Now i have to know in which polygon the red dot is.

Then the most important I need is this:

I have the x and y coordinates of the red point and the x y coordinates of the edges. I need the x and y coordinates of the green dot.(The nearest location outside the polygon)

I need it in lua, but feel free to answer in any language, I can translate it.

Answer 1

To know in which polygon the point is in you can use the Ray Casting algorithm.

For finding the closest edge you could use a naive approach computing the distance to each edge and then take the minimum. Just remember to check if the intersection with edge is outside the edge (check this). If it is outside take the distance to the closest extreme of the edge.

Ok better explaining the intuition with some pseudo-code:

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

I think this pseudo-code should get you going, of course once you have the polygon your point is in!.