如何确定 GPS 坐标是否位于矩形区域内?

2022-01-22 00:00:00 algorithm coordinates math gps java

我在 Stackoverflow 和其他网站上遇到了许多类似的问题，我的解决方案基于这些答案，但我仍然无法让它发挥作用……

I went through many similar questions on Stackoverflow and other websites and I based my solution on those answers but I still can't get it to work…

我的问题:我想确定某个 GPS 位置 P 是否位于由四个给定 GPS 坐标 A, B, C, D.

My problem: I want to determine whether or not a certain GPS location P lies within a rectangular area bounded by four given GPS coordinates A, B, C, D.

目前我正在计算三角形 ABP、BCP、CDP 和 DAP 的面积.如果这些区域中的任何一个大于零(不要生气，数学家)，则该点位于我的矩形之外，如 这里.

At the moment I am calculating the areas of triangles ABP, BCP, CDP and DAP. If any of those areas is bigger than zero (don't be upset, mathematicians) the point lies outside my rectangle as explained here.

代码:

private static double triangleArea(Location a, Location b, Location c) {
    // (C.x*B.y-B.x*C.y)-(C.x*A.y-A.x*C.y)+(B.x*A.y-A.x*B.y)
    double result = (c.getLongitude()*b.getLatitude()-b.getLongitude()*c.getLatitude())-(c.getLongitude()*a.getLatitude()-a.getLongitude()*c.getLatitude())+(b.getLongitude()*a.getLatitude()-a.getLongitude()*b.getLatitude());
    return result;
}

public static boolean isInsideSquare(Location a, Location b, Location c, Location d, Location p) {
    if (triangleArea(a,b,p)>0 || triangleArea(b,c,p)>0 || triangleArea(c,d,p)>0 || triangleArea(d,a,p)>0) {
        return false;
    }
    return true;
}

但是当我调用这个函数时，它总是返回 false.即使使用以下坐标(纬度、经度):

But when I call this function it's always returning false. Even when using the following coordinates (latitude, longitude):

A: (50.884706, 4.714151)
B: (50.884944, 4.716149)
C: (50.884679, 4.716228)
D: (50.884441, 4.714230)
P: (50.884538, 4.714615)

然而，当我在地图上绘制这些点时(例如 这里)，我可以看到那个点 P位于 ABCD 内……(见下文)

Yet when I plot those points on a map (e.g. here) I can see that point P lies within ABCD… (see below)

我已经阅读了一些简单的解决方案，您只需减去点的 x、y 坐标，但这显然只适用于平行于 x 轴和 y 轴的矩形，而我的矩形可以任意定向角度.

I've read some easy solutions where you just subtract the x, y coordinates of your points, but that would obviously only work for rectangles parallel to the x-axis and y-axis, whereas my rectangle can be oriented in any angle.

谁能告诉我我做错了什么或提出更好的解决方案来解决这个问题?

Can anyone tell me what I am doing wrong or suggest a better solution to solve this problem?

非常感谢！

推荐答案

如果一个点在一个矩形内.在飞机上.对于数学家或大地测量学 (GPS) 坐标

  • 让我们延长矩形的边.所以我们有 4 条直线 lAB、lBC、lCD、lDA，或者，简而言之, l1, l2, l3, l4.

  • 为每个 li 做一个方程.方程排序:

    If a point is inside a rectangle. On a plane. For mathematician or geodesy (GPS) coordinates

    • Lets prolong the sides of the rectangle. So we have 4 straight lines lAB, lBC, lCD, lDA, or, for shortness, l1, l2, l3, l4.

    • Make an equation for every li. The equation sort of:

      fi(P)=0.

      P 是一个点.对于属于 li 的点，等式成立.

      P is a point. For points, belonging to li, the equation is true.

      • 我们需要方程左边的函数.它们是 f1、f2、f3、f4.
      • 注意，对于来自 li 一侧的每个点，函数 fi 大于 0，对于来自另一侧的点 fi 小于 0.
      • 所以，如果我们要检查 P 是否在矩形中，我们只需要让 p 在所有四行的正确边上.因此，我们必须检查四个函数的符号.
      • 但是直线的哪一侧是正确的，矩形属于哪一侧?它是边，矩形的顶点不属于该线.为了检查，我们可以选择两个不属于的顶点中的任何一个.

      • 所以，我们必须检查一下:

      • We need the functions on the left sides of the equations. They are f1, f2, f3, f4.
      • Notice, that for every point from one side of li the function fi is greater than 0, for points from the other side fi is lesser than 0.
      • So, if we are checking for P being in rectangle, we only need for the p to be on correct sides of all four lines. So, we have to check four functions for their signs.
      • But what side of the line is the correct one, to which the rectangle belongs? It is the side, where lie the vertices of rectangle that don't belong to the line. For checking we can choose anyone of two not belonging vertices.

      • So, we have to check this:

      fAB(P) fAB(C) >= 0

      fAB(P) fAB(C) >= 0

      fBC(P) fBC(D) >= 0

      fBC(P) fBC(D) >= 0

      fCD(P) fCD(A) >= 0

      fCD(P) fCD(A) >= 0

      fDA(P) fDA(B) >= 0

      fDA(P) fDA(B) >= 0

      不等式并不严格，因为如果一个点在边界上，它也属于矩形.如果您不需要边界上的点，则可以将不等式更改为严格的不等式.但是当你从事浮点运算时，选择是无关紧要的.

      • 对于矩形中的一个点，所有四个不等式都是正确的.请注意，它也适用于每个凸多边形，只是线/方程的数量会有所不同.

      • 剩下的唯一事情就是得到一条穿过两点的线的方程.这是一个众所周知的线性方程.让我们把它写成线AB和点P:

      • For a point, that is in the rectangle, all four inequations are true. Notice, that it works also for every convex polygon, only the number of lines/equations will differ.

      • The only thing left is to get an equation for a line going through two points. It is a well-known linear equation. Let's write it for a line AB and point P:

      fAB(P)   ≡  (xA-xB) (yP-yB) - (yA-yB) (xP-xB)

      fAB(P)   ≡   (xA-xB) (yP-yB) - (yA-yB) (xP-xB)

      检查可以简化 - 让我们沿着矩形顺时针 - A、B、C、D、A.然后所有正确的边都将位于线条的右侧.因此，我们不需要与另一个顶点所在的边进行比较.我们需要检查一组更短的不等式:

      The check could be simplified - let's go along the rectangle clockwise - A, B, C, D, A. Then all correct sides will be to the right of the lines. So, we needn't compare with the side where another vertice is. And we need check a set of shorter inequations:

      fAB(P) >= 0

      fBC(P) >= 0

      fCD(P) >= 0

      fDA(P) >= 0

      但这对于正常的 数学家 坐标集是正确的，其中 X 位于右侧，Y 位于顶部.对于 GPS 中使用的 大地测量 坐标，其中 X 位于顶部，Y 位于右侧，我们必须转换不等式:

      But this is correct for the normal, mathematician set of coordinates, where X is to the right and Y to the top. And for the geodesy coordinates, as are used in GPS, where X is to the top, and Y is to the right, we have to turn the inequations:

      fAB(P) <= 0

      fAB(P) <= 0

      fBC(P) <= 0

      fBC(P) <= 0

      fCD(P) <= 0

      fCD(P) <= 0

      fDA(P) <= 0

      fDA(P) <= 0

      如果您不确定轴的方向，请小心这个简化检查 - 如果您选择了正确的不等式，请手动检查一个点.

      顺便说一句，球体上的矩形也有感觉.它是两条平行线和两条经线之间的区域，当然，主轴的方向可以任意.但根据评论，你不需要它.

      BTW, the rectangle on the sphere has sense too. It is the area between two parallels and two meridians, of course, with any orientation of the main axis. But you don't need it, according to the comment.

相关文章