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!.

Answer 2

My PolyCollisions class:

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

}

Here's a small explanation (Fun Fact: This is the first image I posted to stack overflow!)

Sorry that it's so messy...

---

Step-by-Step of the class:

• Check if the given point is within a polygon
  • If it isn't, return the current point as no changes are needed.
• Find the closest VERTEX of the polygon
  • This is not the closest POINT, as a point can be between vertexes
• Grab the two neighbors of the vertex, keeping the one with a lower angle.
  • The lower angle has lower distance than the higher angle because the higher angle "goes away" faster
• Get the closest point of the line segment, using the answer to this question on StackOverflow.

---

Congrats! You survived the bad tutorial! Hopefully it helped :) + Thanks to all of the commented links to answers that helped me help you!

Snap Point to Line

How to calculate an angle from 3 points

Answer 3

Here is C# version of the answer @nathanfranke

using System;
using Windows.Foundation;
using Windows.UI.Xaml.Shapes;
using System.Numerics;

    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 bool PointIsInPoly(Vector2[] verts, Vector2 p)
            {
                int nvert = verts.Length;
                double[] vertx = new double[nvert];
                double[] verty = new double[nvert];
                for (int d = 0; d < nvert; d++)
                {
                    Vector2 vert = verts[d];
                    vertx[d] = vert.X;
                    verty[d] = vert.Y;
                }
                
                double testx = p.X;
                double testy = p.Y;
                int i, j;
                bool 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((float)(ax + (abx * t)), (float)(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].X - 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.MaxValue;
    
                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));
            }
    
        }