Điểm kiểm tra cho vị trí của nó so với thân lồi trong log (n)

Question

Tôi có một tập hợp các điểm 2D S và tôi cần kiểm tra xem điểm đầu vào q có ở trong hay bên ngoài thân lồi của S.

Vì đó là về quyết định nhị phân, tôi đã suy nghĩ về mặt lý thuyết có thể đạt được O(log(N)) bằng cách sử dụng cây quyết định.

Tuy nhiên tôi không biết cách sắp xếp dữ liệu và cách thuật toán sẽ trông như thế nào để thực sự nhận được câu trả lời trong O(log(N)).

Trong khi nghiên cứu với ý tưởng này trong tâm trí, tôi đã tìm thấy này:

Làm thế nào chúng ta có thể tìm thấy hai trường hợp, những nhanh hơn? Tìm kiếm nhị phân. Chỉ cần tìm kiếm x trong tọa độ đầu tiên của các điểm trong hai chuỗi. Nếu nó nằm trong chuỗi, bạn đã tìm thấy một đường ngang qua một đỉnh (và bạn không cần phải cẩn thận để biết loại đường nào, một trong hai). Nếu x không phải là tọa độ của một đỉnh trong chuỗi, hai giá trị gần nhất của nó là số cho bạn biết phân đoạn tia nào từ (x, y) có thể là . Vì vậy, chúng tôi có thể kiểm tra xem một điểm có trong đa giác lồi trong thời gian O (log n).

Nó chỉ ra rằng có cấu trúc dữ liệu có thể kiểm tra xem một điểm là trong một đa giác tùy ý (hoặc một số đa giác đó là in) trong cùng O (log n) thời gian ràng buộc. Nhưng chúng phức tạp hơn, vì vậy Tôi không có thời gian để mô tả chúng ở đây; Tôi sẽ nói về chúng tại một số điểm trong ICS 164.

(http://www.ics.uci.edu/~eppstein/161/960307.html)

Vì vậy, bạn có bất kỳ ý tưởng:

1. Làm thế nào cấu trúc dữ liệu nên trông giống như để có được nó xuống trong O(log(N))?
2. Thuật toán sẽ như thế nào?

Answer 1

Chỉ xử lý một chuỗi trước tiên. Chúng tôi muốn kiểm tra xem liệu (qx, qy) có nằm trên một chuỗi phân đoạn đường lồi hay không.

Phần đắt tiền là tìm kiếm nhị phân trên danh sách các tọa độ x để tìm điểm lớn nhất nhỏ hơn điểm truy vấn của bạn. Tất cả bạn cần cho điều này là một loạt các điểm của chuỗi được sắp xếp theo thứ tự x. Sau đó, nó đơn giản là "điểm trên dòng?" kiểm tra.

Bây giờ, chúng tôi muốn xem liệu một điểm có nằm trong đa giác lồi hay không. Nếu bạn đại diện cho các cạnh của đa giác lồi đó như là một chuỗi trên và một chuỗi thấp hơn, thì đó là giao điểm của những thứ bên dưới chuỗi trên với những thứ ở trên chuỗi dưới. Vì vậy, nó là hai tìm kiếm nhị phân.

(Ngay cả khi bạn đã nhận được điểm theo thứ tự sắp xếp theo chiều kim đồng hồ hoặc thứ gì đó, bạn có thể tìm các tọa độ nhỏ nhất và lớn nhất x trong đa giác trong thời gian lôgarit bằng tìm kiếm nhị phân hoặc tìm kiếm bốn điểm. thậm chí phải tính toán trước các chuỗi trên và dưới nếu bạn không muốn.)

EDIT: Tôi thấy rằng câu hỏi của bạn cũng có thể được phân tích cú pháp là "cấu trúc dữ liệu vị trí điểm trông ilke?" thay vì "làm cách nào để lưu trữ vỏ lồi để cho phép thử nghiệm bên trong/bên ngoài hiệu quả?"

Điều tự nhiên là nghiên cứu vị trí điểm trong bối cảnh tổng quát hơn một chút so với thử nghiệm bên trong-bên ngoài. Có

CGAL có thể làm vị trí điểm theo một vài cách khác nhau. Nó được viết bởi những người thông minh với một sự hiểu biết tốt về các thuật toán họ đang thực hiện và các máy tính các thuật toán sẽ sử dụng. Bạn có thể sẽ không thể tìm thấy bất cứ điều gì quá nhanh hơn mà vẫn hoạt động chính xác.

Với điều đó đã nói, Haran và Halperin compared thực hiện các thuật toán khác nhau của CGAL. Họ đã sử dụng một máy tính hiện đại vào năm 2008 và họ tạo ra rất nhiều dữ liệu thử nghiệm và thử các chiến lược vị trí điểm khác nhau của CGAL trên mỗi trường hợp thử nghiệm. Trong số những thứ khác, chúng có trường hợp khoảng 1,4 triệu cạnh được đặt ngẫu nhiên trong đó cấu trúc dữ liệu tốt nhất của chúng chỉ cần khoảng 190 micro giây để trả lời truy vấn vị trí điểm.

Điều này rất nhanh khi xem xét sự phức tạp của các thuật toán vị trí điểm điển hình --- Tôi không thể tự làm điều đó. Và lý thuyết cho chúng ta biết rằng nó phát triển như O (log n). Tuy nhiên, rằng O (log n) là một số đơn đặt hàng của cường độ chậm hơn so với thời gian O (log n) phải mất để tìm kiếm một mảng được sắp xếp. Ghi nhớ điều đó khi bạn làm hình học tính toán; các hằng số quan trọng và chúng thường không nhỏ.

Answer 2

Bạn có thể thực hiện việc này bằng thuật toán quét (như rasterization, nói sử dụng đường quét ngang). Xây dựng các cạnh được sắp xếp của đỉnh là n * log (n), nhưng một khi sắp xếp bạn có thể tìm thấy thiết lập đường quét dựa trên điểm q và tìm các cạnh mà đường quét đi qua.

Rasterization được đơn giản hóa trong trường hợp lồi vì bạn không phải lo lắng về sự lõm trong đường quét.

Một phác thảo đơn giản là đi xung quanh đa giác, xây dựng các đối tượng cạnh, sử dụng cuộn dây để xác định các cạnh trái và phải. Tất cả các giá trị y cho mỗi điểm đi vào một danh sách được sắp xếp (hoặc mảng, hoặc thiết lập, hoặc bản đồ, bất cứ điều gì).

Điểm q.y của bạn được sử dụng để tra (các) cạnh ở bên trái và bên phải, sau đó bạn có thể xác định xem q.x có nằm giữa các tọa độ trái và phải không. Bạn có thể tính toán vỏ lồi đầu tiên để đảm bảo các cạnh trái/phải của bạn bị lồi.

(Wow, trong việc tìm kiếm ra raster quét chuyển đổi, tôi đi qua các ghi chú từ lớp undergrad của tôi here từ năm sau khi tôi tốt nghiệp.)

Answer 3

Vấn đề này có thể được phân loại như một point-location vấn đề cổ điển.

• Các tiền xử lý sẽ bao gồm tính thân lồi cho tập hợp các điểm, và các đoạn thẳng của thân lồi sẽ được sử dụng trong bước tiếp theo (hoặc toàn bộ CH như một vùng).

• Có rất nhiều thuật toán truy vấn thời gian chuẩn O(log n) cho loại sự cố này (http://en.wikipedia.org/wiki/Point_location) như hình tam giác Kirkpatrick, bản đồ hình thang ngẫu nhiên, v.v.

Cũng lưu ý rằng trong kỳ vọng, số lượng các điểm trong CH(S) là O(log N) nơi N là số tổng điểm trong S. Vì vậy, số lượng các đoạn đường được xem xét cho vị trí điểm đã được giảm xuống còn O(log N), có nghĩa là thời gian truy vấn thực sự là O (nhật ký nhật ký N) theo kỳ vọng (về tổng số điểm trong S).

Answer 4

struct point { 
    LL x,y ; 
} C[100010]; 


/*return area of triangle */ 
LL areaTriangle(const point &a, const point &b, const point &c) { 
    return (a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y)); 
} 

/*An user define function to calculate where a point p inside a convex hull or not */ 

bool inConvexPoly(int N, const point p) { 

/*Input: C is an array with vertex x, y of a convex hull, points must be anticlock-wise, If it's clockwise then just reverse it. p is a point and we have to find does p inside polygon C or not*/ 

/*Most important part, finding two point using binay search such that point p may be lie inside the trianle 
    made by those two points and point0 or point p may be lie inside the triangle which is 
    made by point0, point_last, point_start */ 


LL start = 1, last = N - 1; 
while(last - start > 1) { 
    LL mid = (start + last) >> 1; 
    if(areaTriangle(C[0], C[mid], p) < 0) last = mid; 
    else start = mid; 
} 

/*Area of triangle form by point0, start point and last point*/ 
LL r0 = abs(areaTriangle(C[0], C[start], C[last])); 


/*If point p is inside a triangle then the area of that triangle must be equal to 
    the area ((point0, poin1, p) + (point0, point2, p) + (point1, point2, p)) 
    here point0 = C[0], point1 = C[start], point2 = C[last]*/ 

LL r1 = abs(areaTriangle(C[0], C[start], p)); 
LL r2 = abs(areaTriangle(C[0], C[last], p)); 
LL r3 = abs(areaTriangle(C[start], C[last], p)); 

/*Point p must not lie on any border line of the convex hull, So if the area is 0 then that three point lie on the 
    same line */ 

LL r4 = areaTriangle(C[0], C[1], p); 
LL r5 = areaTriangle(C[0], C[N - 1], p); 

/*If the area of triangle form by point0, start and last point is equal to area 
    from by triangle (point0, last, p) + (point0, start, p) + (last, start, p) 
    and p don't lie on start-last line, point0-point1 line, point0-point[N - 1] line 
    then the point p inside the convex hull */ 


return (r0 == (r1 + r2 + r3) && r3 != 0 && r4 != 0 && r5 != 0); 
} 

/*Try to draw picture for better understand */ 

//End 

Answer 5

Bạn có thể làm điều đó trong Nhật ký (h) trong đó h là số điểm là điểm thân đã được tính toán. Nó là hoàn toàn sai lầm rằng nó bị ràng buộc bởi Log (n) mặc dù đây là những gì được viết trong Wikipedia.

Bạn nên lưu ý rằng Wikipedia "Convex hull algorithms" được lọc bởi David Eppstein mà bạn giới thiệu. Anh chàng này ngăn chặn thông tin hữu ích được thêm vào. Nếu anh chàng đó chấp nhận thêm thông tin hữu ích (thuật toán mới) và sẽ hiểu nó, anh ta sẽ nhận ra rằng bạn có thể đạt được mục tiêu của mình trong O (Log h) .Vui lòng xem trang Wikipedia để biết lịch sử của trang.

Trong thuật toán Ouellet convex Hull AVL bạn có thể sử dụng kết quả trung gian (cây avl theo góc phần tư) và xem trực tiếp bên trong. Bạn sẽ đạt được mục tiêu của mình một cách nhanh nhất có thể (hiệu suất tốt nhất: Nhật ký (h)).

2 điểm quan trọng:

• Bạn cần phải xác định các góc phần tư thứ nhất. Bạn nên kiểm tra xem nó có thể là một ranh giới góc phần tư không. Sau đó, sử dụng điểm gốc duy nhất cho góc phần tư, hoặc sử dụng sản phẩm chéo với điểm đầu tiên và cuối cùng của góc phần tư để biết nếu nó ở bên phải (trong trường hợp sản phẩm chéo, nếu không có góc phần tư là một điểm thân tàu - không cần phải xác định góc phần tư).
• Điểm được sắp xếp theo tọa độ x.

Nếu tôi có thể tìm thấy thời gian, tôi sẽ thêm giao diện vào lớp học của mình để kiểm tra/thêm điểm mới một cách linh hoạt. Nhưng bạn có thể làm điều đó ngay bây giờ: lấy kết quả trung gian lồi lồi và sử dụng nó trực tiếp (xem 2 điểm quan trọng).

Answer 6

Giải pháp thay thế sử dụng các góc:

Chọn một số điểm C bên trong thân lồi bằng cách sử dụng một số phỏng đoán bạn chọn.

Chọn một số dòng L đi qua C, ví dụ đường song song với trục OX.

Đối với mọi điểm P trên thân lồi, tính toán góc giữa đường CP và L và sử dụng nó để sắp xếp các điểm thân lồi.

Bây giờ nếu bạn muốn biết nếu một số điểm T nằm bên trong thân lồi, tính góc giữa các đường CT và L và sử dụng tìm kiếm nhị phân tìm các điểm trong thân lồi, chỉ sau và trước nó (A và B tương ứng).

Bây giờ bạn chỉ cần kiểm tra xem T có ở cùng một bên của đường AB so với C (bên trong) hay không (bên ngoài).