Làm thế nào để kiểm tra nếu một điểm nằm trong một đa giác lồi trong tọa độ số nguyên 2D?

Question

Đa giác được đưa ra dưới dạng danh sách đối tượng Vector2I (tọa độ 2 chiều, số nguyên). Làm thế nào tôi có thể kiểm tra nếu một điểm nhất định là bên trong? Tất cả các triển khai tôi tìm thấy trên web đều thất bại đối với một số ví dụ truy cập tầm thường. Nó thực sự có vẻ là khó để viết một thực hiện chính xác. Ngôn ngữ không quan trọng vì tôi sẽ tự mình chuyển nó.

Answer 1

Nếu đó là lồi, một cách tầm thường để kiểm tra xem nó là điểm được đặt trên cùng một bên của tất cả các phân đoạn (nếu đi qua theo cùng thứ tự).

Bạn có thể kiểm tra dễ dàng với sản phẩm chéo (vì tỷ lệ thuận với cosin của góc được hình thành giữa phân khúc và điểm, những dấu có dấu dương nằm ở bên phải và dấu có dấu âm ở bên trái bên).

Đây là mã bằng 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

Phương pháp đúc hoặc cuộn dây là phổ biến nhất cho vấn đề này. Xem chi tiết Wikipedia article.

Ngoài ra, Kiểm tra this page kiếm một giải pháp tốt tài liệu trong C.

Answer 3

Hoặc từ người đàn ông đó đã viết cuốn sách xem - geometry page

Cụ this page, ông thảo luận về lý do tại sao quanh co cai trị nói chung là tốt hơn so với tia qua.

chỉnh sửa - Xin lỗi, đây không phải là Jospeh O'Rourke người đã viết cuốn sách tuyệt vời Computational Geometry in C, đó là Paul Bourke nhưng vẫn là nguồn rất tốt về thuật toán hình học.

Answer 4

cách tôi biết là điều gì đó tương tự.

bạn chọn một điểm nào đó bên ngoài đa giác có thể cách xa hình học. sau đó bạn vẽ một đường từ điểm này. tôi có nghĩa là bạn tạo một phương trình đường thẳng với hai điểm này.

sau đó cho mỗi dòng trong đa giác này, bạn kiểm tra xem chúng có giao nhau hay không.

chúng tổng số lượng các đường được giao cho bạn bên trong hoặc không.

nếu nó là số lẻ: bên

nếu nó thậm chí còn: bên ngoài

Answer 5

Chức năng pointPolygonTest trong OpenCV "xác định xem điểm nằm bên trong một đường viền, bên ngoài, hoặc nằm trên một cạnh": http://docs.opencv.org/modules/imgproc/doc/structural_analysis_and_shape_descriptors.html?highlight=pointpolygontest#pointpolygontest

Answer 6

câu trả lời của câu trả lời gần như đã hiệu quả đối với tôi ngoại trừ tôi thấy tôi đã dịch đa giác sao cho điểm bạn đang thử nghiệm giống với điểm gốc. Đây là JavaScript mà tôi đã viết để làm cho công việc này:

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

Nếu đa giác là lồi, sau đó trong C#, sau đây thực hiện phương pháp "test if always on same side", và chạy nhiều nhất tại O (n điểm đa giác) :

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