Tìm tất cả các điểm chung cho hai vòng tròn

Question

Trong Python, làm cách nào để tìm tất cả các điểm nguyên chung cho hai vòng kết nối?

Ví dụ: hãy tưởng tượng giao điểm giống như biểu đồ Venn của hai vòng tròn (có kích thước bằng nhau), với các điểm trung tâm (x1,y1) và (x2,y2) và bán kính r1=r2. Ngoài ra, chúng tôi đã biết hai điểm giao nhau của các vòng kết nối là (xi1,yi1) và (xi2,yi2).

Làm cách nào để tạo danh sách tất cả các điểm (x,y) chứa trong cả hai vòng một cách hiệu quả? Tức là, sẽ đơn giản để vẽ một ô chứa các nút giao nhau và lặp lại qua nó, kiểm tra xem một điểm nhất định có nằm trong cả hai vòng tròn, nhưng có cách nào tốt hơn không?

Answer 1

Vì vậy, bạn muốn tìm các điểm mạng nằm trong cả hai vòng kết nối?

Phương pháp bạn đề xuất vẽ một hộp và lặp qua tất cả các điểm trong hộp có vẻ đơn giản nhất đối với tôi. Nó có thể sẽ hiệu quả, miễn là số điểm trong hộp có thể so sánh với số điểm trong giao lộ.

Và ngay cả khi nó không hiệu quả nhất có thể, bạn không nên cố gắng tối ưu hóa nó cho đến khi bạn có lý do chính đáng để tin rằng đó là một nút cổ chai thực sự.

Answer 2

Hãy nhớ rằng có bốn trường hợp ở đây.

1. Vòng tròn không cắt nhau, nghĩa là "khu vực chung" trống.
2. Một vòng tròn nằm hoàn toàn trong vòng khác, có nghĩa là "khu vực chung" là vòng tròn nhỏ hơn/bên trong. Cũng lưu ý rằng trường hợp thoái hóa của trường hợp này là nếu chúng là cùng một vòng tròn đồng tâm, trường hợp này phải được đặt cho các tiêu chí mà chúng là các vòng tròn đường kính bằng nhau mà bạn đã chỉ định.
3. Hai vòng tròn chạm vào một điểm giao nhau.
4. Trường hợp "chung" ở đó sẽ có hai điểm giao nhau. Từ đó, bạn có hai vòng cung xác định vùng kín. Trong trường hợp đó, phương pháp vẽ hộp có thể hoạt động ngay bây giờ, tôi không chắc chắn có một phương pháp hiệu quả hơn để xác định những gì được chứa bởi giao lộ. Tuy nhiên, hãy lưu ý rằng nếu bạn chỉ quan tâm đến khu vực, có a formula cho điều đó.

Answer 3

Bạn cũng có thể muốn xem xét các thuật toán cắt khác nhau được sử dụng trong phát triển đồ họa. Tôi đã sử dụng các thuật toán cắt để giải quyết rất nhiều vấn đề tương tự như những gì bạn đang yêu cầu ở đây.

Answer 4

Nếu vị trí và bán kính trong vòng kết nối của bạn có thể thay đổi với độ chi tiết nhỏ hơn lưới của bạn, thì bạn sẽ kiểm tra một loạt điểm.

Bạn có thể giảm thiểu số điểm bạn kiểm tra bằng cách xác định khu vực tìm kiếm một cách thích hợp. Nó có chiều rộng tương đương với khoảng cách giữa các điểm giao nhau, và chiều cao tương đương với

r1 + r2 - D

với D là sự tách biệt của hai trung tâm. Lưu ý rằng hình chữ nhật này nói chung không được căn chỉnh với các trục X và Y. (Điều này cũng cho bạn kiểm tra xem liệu hai vòng tròn có giao nhau không!)

Thực ra, bạn chỉ cần kiểm tra một nửa số điểm này.Nếu bán kính là như nhau, bạn chỉ cần kiểm tra một phần tư của chúng. Tính đối xứng của vấn đề sẽ giúp bạn ở đó.

Answer 5

Tôi giả định bởi "tất cả các điểm" nghĩa là "tất cả các pixel". Giả sử màn hình của bạn là NX x pixel. Có hai mảng

int x0[NY], x1[NY]; initially full of -1. 

Giao lộ là hình thoi, giữa hai đường cong. Lặp lại giá trị x, y dọc theo mỗi đường cong. Tại mỗi giá trị y (nghĩa là, nơi đường cong đi qua y + 0,5), lưu trữ giá trị x trong mảng. Nếu x0 [y] là -1, lưu trữ nó trong x0, lưu trữ nó trong x1.

Cũng theo dõi các giá trị thấp nhất và cao nhất của y.

Khi bạn hoàn thành, chỉ cần lặp qua các giá trị y và tại mỗi y, lặp lại các giá trị x giữa x0 và x1, nghĩa là, for (ix = x0[iy]; ix < x1[iy]; ix++) (hoặc ngược lại).

Điều quan trọng là phải hiểu rằng pixel không phải là điểm mà x và y là số nguyên. Thay vì pixel là các ô vuông nhỏ giữa các đường lưới. Điều này sẽ ngăn cản bạn gặp vấn đề về trường hợp cạnh.

Answer 6

Bạn sắp hoàn tất. Lặp lại các điểm trong hộp nên khá tốt, nhưng bạn có thể làm tốt hơn nếu cho tọa độ thứ hai bạn lặp lại trực tiếp giữa các giới hạn.

Giả sử bạn lặp lại dọc theo trục x trước, sau đó cho trục y, thay vì lặp lại giữa các hộp co lại, nơi mỗi vòng tròn cắt đường x, cụ thể hơn là bạn quan tâm đến tọa độ y của các điểm giao nhau, và lặp lại giữa những người đó (chú ý làm tròn)

Khi bạn làm điều này, bởi vì bạn đã biết bạn đang ở trong vòng kết nối, bạn có thể bỏ qua toàn bộ kiểm tra. Nếu bạn có nhiều điểm thì bạn bỏ qua rất nhiều kiểm tra và bạn có thể nhận được một số cải tiến về hiệu suất.

Để cải thiện thêm, bạn có thể chọn trục x hoặc trục y để giảm thiểu số lần bạn cần tính điểm giao nhau.