如何測試一個點是否在二維整數座標中的凸多邊形內？

Question

多邊形以Vector2I對象（2維，整數座標）的列表形式給出。我如何測試給定的點是否在裏面？我在網上找到的所有實現都會因爲一些微不足道的反例而失敗。這似乎很難寫出正確的實現。這個語言並不重要，因爲我會自己移植它。

Answer 1

如果它是凸的，一個簡單的方法來檢查它是該點上的所有段的相同側鋪設（如果遍歷以相同的順序）。

你可以用叉積容易地檢查它（因爲它與段和點之間形成的夾角的餘弦成正比，帶有正號的那些位於右側，左側帶負號的位置側）。

這裏是在Python代碼：

RIGHT = "RIGHT" 
LEFT = "LEFT" 

def inside_convex_polygon(point, vertices): 
    previous_side = None 
    n_vertices = len(vertices) 
    for n in xrange(n_vertices): 
     a, b = vertices[n], vertices[(n+1)%n_vertices] 
     affine_segment = v_sub(b, a) 
     affine_point = v_sub(point, a) 
     current_side = get_side(affine_segment, affine_point) 
     if current_side is None: 
      return False #outside or over an edge 
     elif previous_side is None: #first segment 
      previous_side = current_side 
     elif previous_side != current_side: 
      return False 
    return True 

def get_side(a, b): 
    x = x_product(a, b) 
    if x < 0: 
     return LEFT 
    elif x > 0: 
     return RIGHT 
    else: 
     return None 

def v_sub(a, b): 
    return (a[0]-b[0], a[1]-b[1]) 

def x_product(a, b): 
    return a[0]*b[1]-a[1]*b[0] 

Answer 2

Ray Casting或Winding方法是最常見的這個問題。詳情請參閱Wikipedia article。

此外，檢查出​​用於C.一個證據充分的溶液

Answer 3

或從寫的書看的人 - geometry page

具體this page，他論述了爲什麼纏繞規則通常比線交叉更好。

編輯 - 對不起，這不是Jospeh O'Rourke誰寫了優秀的書Computational Geometry in C，它是保羅伯克，但仍然是一個非常非常好的幾何算法的來源。

Answer 4

我知道的方式就是這樣的。

你在多邊形之外的某個地方選取一個點，它可能離幾何很遠。 然後你從這一點畫一條線。我的意思是你用這兩點創建一個直線方程。

然後對於此多邊形中的每一行，檢查它們是否相交。

它們相交的線條數量的總和給你它是否在裏面。

如果是奇數：內部

如果是偶數：外

Answer 5

在OpenCV中的pointPolygonTest功能「確定點是否是輪廓內部，外部，或位於邊緣」： http://docs.opencv.org/modules/imgproc/doc/structural_analysis_and_shape_descriptors.html?highlight=pointpolygontest#pointpolygontest

Answer 6

fortran的答案几乎爲我工作，除了我發現我不得不翻譯多邊形，以便您測試的點與原點相同。下面是我寫的，使這項工作的JavaScript的：

function Vec2(x, y) { 
    return [x, y] 
} 
Vec2.nsub = function (v1, v2) { 
    return Vec2(v1[0]-v2[0], v1[1]-v2[1]) 
} 
// aka the "scalar cross product" 
Vec2.perpdot = function (v1, v2) { 
    return v1[0]*v2[1] - v1[1]*v2[0] 
} 

// Determine if a point is inside a polygon. 
// 
// point  - A Vec2 (2-element Array). 
// polyVerts - Array of Vec2's (2-element Arrays). The vertices that make 
//    up the polygon, in clockwise order around the polygon. 
// 
function coordsAreInside(point, polyVerts) { 
    var i, len, v1, v2, edge, x 
    // First translate the polygon so that `point` is the origin. Then, for each 
    // edge, get the angle between two vectors: 1) the edge vector and 2) the 
    // vector of the first vertex of the edge. If all of the angles are the same 
    // sign (which is negative since they will be counter-clockwise) then the 
    // point is inside the polygon; otherwise, the point is outside. 
    for (i = 0, len = polyVerts.length; i < len; i++) { 
    v1 = Vec2.nsub(polyVerts[i], point) 
    v2 = Vec2.nsub(polyVerts[i+1 > len-1 ? 0 : i+1], point) 
    edge = Vec2.nsub(v1, v2) 
    // Note that we could also do this by using the normal + dot product 
    x = Vec2.perpdot(edge, v1) 
    // If the point lies directly on an edge then count it as in the polygon 
    if (x < 0) { return false } 
    } 
    return true 
} 

Answer 7

如果多邊形是凸的，那麼在C＃中，下面實現「test if always on same side」的方法，並在大多數運行在O（多邊形點N） ：

public static bool IsInConvexPolygon(Point testPoint, List<Point> polygon) 
{ 
    //Check if a triangle or higher n-gon 
    Debug.Assert(polygon.Length >= 3); 

    //n>2 Keep track of cross product sign changes 
    var pos = 0; 
    var neg = 0; 

    for (var i = 0; i < polygon.Count; i++) 
    { 
     //If point is in the polygon 
     if (polygon[i] == testPoint) 
      return true; 

     //Form a segment between the i'th point 
     var x1 = polygon[i].X; 
     var y1 = polygon[i].Y; 

     //And the i+1'th, or if i is the last, with the first point 
     var i2 = i < polygon.Count - 1 ? i + 1 : 0; 

     var x2 = polygon[i2].X; 
     var y2 = polygon[i2].Y; 

     var x = testPoint.X; 
     var y = testPoint.Y; 

     //Compute the cross product 
     var d = (x - x1)*(y2 - y1) - (y - y1)*(x2 - x1); 

     if (d > 0) pos++; 
     if (d < 0) neg++; 

     //If the sign changes, then point is outside 
     if (pos > 0 && neg > 0) 
      return false; 
    } 

    //If no change in direction, then on same side of all segments, and thus inside 
    return true; 
}