Как получить ближайшую точку вне многоугольника из точки внутри многоугольника?
У меня есть карта с большим количеством полигонов и точкой внутри одного из них, например:
Координаты 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 красной точки и координаты xy ребер. Мне нужны координаты х и у зеленой точки.(Ближайшее местоположение за пределами многоугольника)
Мне нужно это в луа, но не стесняйтесь отвечать на любом языке, я могу перевести это.
3 ответа
Решение
Чтобы узнать, в каком полигоне находится точка, вы можете использовать алгоритм Ray Casting.
Для нахождения ближайшего ребра вы можете использовать наивный подход, вычисляя расстояние до каждого ребра, а затем взять минимум. Просто не забудьте проверить, находится ли пересечение с краем за пределами края (отметьте это). Если это снаружи, возьмите расстояние до ближайшего крайнего края.
Хорошо, лучше объясним интуицию с помощью некоторого псевдокода:
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];
}
Я думаю, что этот псевдокод должен помочь вам, разумеется, если у вас есть многоугольник, в котором вы заинтересованы!
Мой 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://stackru.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://stackru.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 многоугольника
- Это не ближайшая ТОЧКА, так как точка может быть между вершинами
- Возьмите двух соседей вершины, удерживая одного с меньшим углом.
- Нижний угол имеет меньшее расстояние, чем верхний угол, потому что больший угол "уходит" быстрее
- Получите ближайшую точку отрезка линии, используя ответ на этот вопрос в Stackru.
Congrats! Вы пережили плохой урок! Надеюсь, это помогло:) + Спасибо всем закомментированные ссылки на ответы, которые помогли мне помочь вам!
Вот C# версия ответа @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));
}
}