Làm cách nào để xác định điểm nào nằm trong một đa giác và không phải là số điểm lớn (số điểm lớn)?

Question

Tôi đã có một tập hợp lớn các điểm dữ liệu (100.000+) được lưu trữ trong mảng 2 chiều (cột 1: toạ độ x, cột 2: toạ độ y). Tôi cũng có một số mảng 1 chiều lưu trữ thông tin bổ sung cho mỗi điểm dữ liệu. Bây giờ tôi muốn tạo các ô từ tập hợp con của các mảng 1D này chỉ bao gồm các điểm nằm trong một đa giác nhất định.

tôi đã đưa ra các giải pháp sau đây mà không phải là thanh lịch và cũng không nhanh:

#XY is the 2D array. 
#A is one of the 1D arrays. 
#poly is a matplotlib.patches.Polygon 

mask = np.array([bool(poly.get_path().contains_point(i)) for i in XY]) 

matplotlib.pylab.hist(A[mask], 100) 
matplotlib.pylab.show() 

Ông có thể vui lòng giúp tôi để cải thiện mã này? Tôi đã cố gắng chơi xung quanh với np.vectorize thay vì hiểu danh sách nhưng không thể quản lý để làm cho nó hoạt động.

Answer 1

Sử dụng matplotlib.nxutils.points_inside_poly, thực hiện kiểm tra rất hiệu quả.

Ví dụ và giải thích thêm về thuật toán 40 tuổi này tại số matplotlib FAQ.

Cập nhật: Lưu ý rằng points_inside_poly không còn được dùng kể từ phiên bản 1.2.0 của matplotlib. Sử dụng matplotlib.path.Path.contains_points để thay thế.

Answer 2

Tôi e rằng mình không quen thuộc với các thư viện bạn đang sử dụng, nhưng tôi nghĩ tôi có ý tưởng hợp lý cho thuật toán bạn có thể sử dụng và tôi sẽ thực hiện sau đó tôi chắc chắn rằng bạn có thể cải thiện nó và thực hiện nó bằng cách sử dụng các thư viện này. Ngoài ra, tôi không tuyên bố rằng đây là cách tốt nhất để đạt được điều này, nhưng tôi muốn nhận được phản hồi của tôi một cách hợp lý một cách nhanh chóng vì vậy ở đây đi.

---

Bây giờ, ý tưởng đến từ việc sử dụng sản phẩm chéo của hai vectơ trong thuật toán để tìm tập hợp lồi của một tập hợp các điểm, ví dụ: Graham's Scan. Giả sử chúng ta có hai điểm p1 và p2, xác định các vector điểm p1 và p2, từ gốc (0,0) đến (x1, y1) và (x2, y2) tương ứng. Các sản phẩm chéo của p1 x p2 đưa ra một véc tơ thứ ba p3 đó là vuông góc với cả hai p1 và p2 và có độ lớn do diện tích của hình bình hành giới hạn bởi các vectơ.

Một kết quả rất hữu ích là yếu tố quyết định của ma trận

/ x1, x2 \ 
\ y1, y2/

... đó là x1 * y2 - x2 * y1 cho độ lớn của vector p3 và dấu hiệu cho biết p3 là "sắp ra khỏi" mặt phẳng hoặc "đi vào" nó. Vấn đề quan trọng ở đây là nếu cường độ này là tích cực sau đó p2 là "bên trái" của p1 và nếu nó là tiêu cực thì p2 là "ở bên phải" của p1.

Hy vọng rằng ascii này ví dụ nghệ thuật sẽ giúp:

. p2(4, 5) 
/
/
/
/_ _ _ _ _. p1(5, 0) 

x1 * y2 - x2 * y1 = 5 * 4-0 * 5 = 20 và vì vậy p2 là "bên trái" của p1

Cuối cùng, tại sao điều này hữu ích cho chúng tôi! Nếu chúng ta có một danh sách các đỉnh của đa giác và một tập hợp các điểm khác trong biểu đồ, thì đối với mỗi cạnh của đa giác chúng ta có thể nhận được vec-tơ của cạnh đó. Chúng ta cũng có thể lấy các vectơ tham gia đỉnh bắt đầu cho tất cả các điểm khác trong biểu đồ và bằng cách kiểm tra xem chúng nằm ở bên trái hay bên phải của cạnh, chúng ta có thể loại bỏ một số điểm cho mỗi cạnh. Tất cả những thứ không được xóa vào cuối quá trình là những điểm bên trong đa giác. Dù sao, trên một số mã để làm cho một số ý nghĩa hơn về điều này!

---

Nhận một danh sách các đỉnh của đa giác của bạn theo thứ tự bạn sẽ tới thăm họ nếu bạn đang vẽ chúng trong một hướng ngược chiều kim đồng hồ, ví dụ một số hình ngũ giác có thể là:

poly = [(1, 1), (4, 2), (5, 5), (3, 8), (0, 4)]

Lấy một tập hợp chứa tất cả các điểm khác trong biểu đồ, chúng tôi sẽ dần loại bỏ các điểm không hợp lệ khỏi tập hợp này cho đến khi những điểm còn lại ở cuối quá trình chính xác là những điểm nằm trong đa giác.

points = set(['(3, 0), (10, -2), (3,3), ...])

Bit chính của mã chính nó là thực sự khá nhỏ gọn trong bao lâu nó đưa tôi viết về cách hoạt động. to_right lấy hai bộ dữ liệu đại diện cho vectơ và trả về True nếu v2 nằm ở bên phải của v1. Các vòng sau đó chỉ cần đi qua tất cả các cạnh của đa giác và loại bỏ các điểm từ bộ làm việc nếu chúng ở bên phải của bất kỳ cạnh nào.

def to_right(v1, v2): 
    return (v1[0]*v2[1] - v1[1]*v2[0]) < 0 

for i in range(len(poly)): 
    v1 = poly[i-1] 
    v2 = poly[i] 
    for p in points: 
     if(to_right(v2-v1, p-v1)): 
      points.remove(p) 

chỉnh sửa: Để làm rõ, thực tế là chúng bị xóa nếu chúng nằm bên phải trái ngược với liên kết với thứ tự các đỉnh của đa giác được chỉ định. Nếu chúng theo thứ tự chiều kim đồng hồ, bạn sẽ muốn loại bỏ các điểm nằm bên trái. Tôi không có một giải pháp đặc biệt tuyệt vời cho vấn đề này vào lúc này.

---

Dù sao, hy vọng tôi đúng về nội dung này và nó giúp ích cho người khác ngay cả khi không phải OP. Độ phức tạp tiệm cận của thuật toán này là O (mn) trong đó n là số điểm trong biểu đồ và m là số đỉnh của đa giác như trong trường hợp xấu nhất tất cả các điểm nằm trong đa giác và chúng ta phải kiểm tra mọi điểm cho mọi cạnh, không ai bị xóa.