确定一个点是否位于由给定纬度/经度的 3 个点组成的三角形内

Question

我有 3 个点（ lat ， lon ）形成一个三角形。我如何找到一个点是否在这个三角形内？

Answer 1

Java 代码只是三角形，即 3 个点。

    public static boolean pntInTriangle(double px, double py, double x1, double y1, double x2, double y2, double x3, double y3) {

    double o1 = getOrientationResult(x1, y1, x2, y2, px, py);
    double o2 = getOrientationResult(x2, y2, x3, y3, px, py);
    double o3 = getOrientationResult(x3, y3, x1, y1, px, py);

    return (o1 == o2) && (o2 == o3);
}

private static int getOrientationResult(double x1, double y1, double x2, double y2, double px, double py) {
    double orientation = ((x2 - x1) * (py - y1)) - ((px - x1) * (y2 - y1));
    if (orientation > 0) {
        return 1;
    }
    else if (orientation < 0) {
        return -1;
    }
    else {
        return 0;
    }
}

Answer 2

这是重心坐标解决方案的 Javascript 实现此处讨论：

// Returns true if point P inside the triangle with vertices at A, B and C
// representing 2D vectors and points as [x,y]. Based on                        
// http://www.blackpawn.com/texts/pointinpoly/default.html
function pointInTriange(P, A, B, C) {
  // Compute vectors        
  function vec(from, to) {  return [to[0] - from[0], to[1] - from[1]];  }
  var v0 = vec(A, C);
  var v1 = vec(A, B);
  var v2 = vec(A, P);
  // Compute dot products
  function dot(u, v) {  return u[0] * v[0] + u[1] * v[1];  }
  var dot00 = dot(v0, v0);
  var dot01 = dot(v0, v1);
  var dot02 = dot(v0, v2);
  var dot11 = dot(v1, v1);
  var dot12 = dot(v1, v2);
  // Compute barycentric coordinates
  var invDenom = 1.0 / (dot00 * dot11 - dot01 * dot01);
  var u = (dot11 * dot02 - dot01 * dot12) * invDenom;
  var v = (dot00 * dot12 - dot01 * dot02) * invDenom;
  // Check if point is in triangle
  return (u >= 0) && (v >= 0) && (u + v < 1);
}

据说速度更快比基于跨产品的解决方案。

Answer 3

您可以使用点多边形测试。

这很简单。从你的点到东画一条线，距离足够远。计算该线与您的多边形相交的次数。如果是偶数，你的点就在外面，如果是奇数，你的点就在里面。

这适用于任何类型的多边形。

Answer 4

大多数语言都包含此功能。在 Java 中是 Polygon.contains()
http://docs.oracle.com/javase/ 7/docs/api/java/awt/Polygon.html

只需从您的点创建一个多边形，然后在您的测试点上调用 contains() 即可。

Answer 5

主要问题是您是否可以为此使用二维近似（换句话说，您的三角形是否足够小）。

如果是这样，像重心坐标这样的简单东西就可以很好地工作。

Answer 6

尝试光线投射算法。

http://en.wikipedia.org/wiki/Point_in_polygon

实现起来非常简单。

Answer 7

function SameSide(p1,p2, a,b)
    cp1 = CrossProduct(b-a, p1-a)
    cp2 = CrossProduct(b-a, p2-a)
    if DotProduct(cp1, cp2) >= 0 then return true
    else return false

function PointInTriangle(p, a,b,c)
    if SameSide(p,a, b,c) and SameSide(p,b, a,c)
        and SameSide(p,c, a,b) then return true
    else return false

在下面的链接中进行了解释

http://www.blackpawn.com/texts/pointinpoly/default .html

Answer 8

我今天就做了这样的事！还有（lat，lon），实际上是（theta，phi），尽管我对我正在使用的网格了解更多。我正在使用 (theta, phi) 0 <= theta <= PI && 0 <= phi <= 2*PI。

您会发现，如果其中一个顶点位于球体的顶部或底部，您可能会遇到一些麻烦，因为在我的情况下 phi 并未真正定义。你最终会在那里得到一个奇点。基本上你已经得到了一个正方形，这样可以更轻松地检查你的点是否位于其中。

在所有其他情况下，如果您已将点转换为 (lat, lon) / (theta, phi)。只需使用@Michelle Six 描述的方法应该很简单。