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

Question

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

javascriptgeometrygeolocation

6

我有三个点 (lat, lon)，它们形成了一个三角形。如何判断一个点是否在这个三角形内部？

- thikonom

这不是一个欧拉计划问题吗？ - Carl Norum

2

你的三角形有多大？它是否足够小，可以假设表面是平坦的，还是需要使用球面几何？ - Mark Byers

1

除了Mark所说的，你如何定义“内部”和“外部”？如果你的点是檀香山、曼谷和拉各斯，那么三角形的边大致沿赤道延伸，北极是内部还是南极是内部？ - Philip Potter

首先，我有一个起点A。我计算了一个距离为500米、方位角为60度的点B。点C也是500米，但方位角为120度。我想知道一个点是否在角度范围为60度（从60到120）的区域内。B和C具有相同的经度。我不知道我是否帮助了你。 - thikonom

8个回答

5

这里是一个基于重心坐标解法实现的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);
}

据说这种解决方案比基于向量叉积的解决方案更快。

- Grumdrig

3

大多数语言都包含此功能。在Java中，它是Polygon.contains()。只需要从您的点创建一个多边形，然后在测试点上调用contains()即可。详见：http://docs.oracle.com/javase/7/docs/api/java/awt/Polygon.html

- Cerin

1

这并不是语言本身，而是与该语言提供的框架有关。了解软件的功能总是很好的。对于像查找一个点是否在三角形内这样简单的问题，我认为使用多边形可能不是最佳/最有效的解决方案。 - Christo

我同意@Christo的观点。你并不总是可以使用awt。 - Timothy Groote

这并不理想，因为Polygon.contains()支持任何类型的多边形，因此，该算法比其他答案中提供的手动（但直接）解决方案要复杂得多。此外，awt不是Java开发人员通常热衷于使用的一组类。 - Clint Eastwood

2

你可以使用点-多边形测试。

这很简单。从你的点向东画一条线，长度足够大。计算该线与多边形相交的次数。如果是偶数，则你的点在多边形外部；如果是奇数，则在内部。

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

- George Silva

1

如果您使用此方法，请确保处理边缘情况 - 两条平行线可以有无限多个交点。 - John P

1

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

如果是这样，像重心坐标这样简单的方法将非常有效。

- tfinniga

棘手的部分是当它是一个嵌入在三维球体上的二维空间时，三角形的边不是直线，而是大圆弧。从技术上讲，你仍然可以使用重心坐标，但距离函数是不同的，你必须处理周期性，并且这只是一个巨大的麻烦。你所想要的答案与大型或位置不便的三角形的二维三角形答案并不完全相符。 - tfinniga

0

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

- Michelle Six

1

这个例子中有太多的“魔法”。CrossProduct从未被解释过。 - Timothy Groote

0

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

你会发现，如果其中一个顶点在球体的顶部或底部，可能会遇到一些麻烦，因为在我的情况下phi并没有真正被定义。你最终会得到一个奇点。你基本上得到了一个正方形，这使得检查你的点是否在其中变得更容易。

在所有其他情况下，如果你已经将你的点转换成(lat, lon)/(theta, phi)，那么只需按@Michelle Six所描述的方法使用即可。

- Christo

0

尝试使用射线投射算法。

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

这个实现起来非常简单。

- codenheim

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Eric · Accepted Answer

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