確定一個點是否在由給定經度/緯度的3點形成的三角形內

Question

我有3點（lat，lon）形成一個三角形。如何找到一個點是否在這個三角形內？

Answer 1

主要問題是您是否可以使用2D逼近（換句話說，您的三角形是否足夠小）。

如果是這樣，那麼簡單的重心座標就可以很好地工作。

Answer 2

大多數語言都包含此功能。在Java中它是Polygon.contains（） http://docs.oracle.com/javase/7/docs/api/java/awt/Polygon.html

只需從你的點創建一個多邊形，然後在你的測試點上調用contains（）。

Answer 3

嘗試使用光線投射算法。

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

這是實現非常簡單。

Answer 4

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 5

您可以使用點多邊形測試。

很簡單。從你的角度畫一條線到東方足夠的距離。計算該線與您的plygon相交的次數。如果它是平衡的，你的觀點在外面，如果奇怪的話，它的內部。

適用於任何類型的多邊形。

Answer 6

我今天做了這樣的事情！還有（lat，lon），實際上（theta，phi），儘管我更瞭解我正在使用的網格。我正在使用（theta，phi）與0 < = theta < = PI & = phi < = 2 * PI。

如果其中一個頂點位於球體的頂部或底部，可能會遇到一些麻煩，因爲在我的情況下，phi並未真正定義。你最終會得到一個奇點。你基本上有一個正方形，這使得更容易檢查你的觀點是否在其中。

在所有其他情況下，如果您已將點轉換爲（lat，lon）/（theta，phi）。使用@Michelle Six描述的方法應該很簡單。

Answer 7

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 8

這裏是一個Javascript實現重心座標解discussed here：

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

據說這比跨產品基礎的解決方案更快。