Làm cách nào để xác định thời điểm hai điểm di chuyển hiển thị với nhau?

Question

Giả sử tôi có hai điểm, Point1 và Point2. Tại bất kỳ thời điểm nào, những điểm này có thể ở các vị trí khác nhau-- chúng không nhất thiết phải tĩnh.

Point1 được đặt tại vị trí nào đó tại thời điểm t và vị trí của nó được xác định bởi các hàm liên tục x1 (t) và y1 (t) cho các tọa độ x và y tại thời điểm t. Các hàm này không thể phân biệt được, chúng được tạo thành từ các đoạn thẳng.

Điểm 2 là giống nhau, với x2 (t) và y2 (t), mỗi hàm có cùng thuộc tính.

Những trở ngại có thể ngăn chặn khả năng hiển thị là đa giác đơn giản (và bất động).

Làm cách nào để tìm các điểm ranh giới cho mức hiển thị?

tức là có hai loại ranh giới: nơi các điểm trở nên hiển thị và trở nên vô hình.

Đối với một đường biên trở thành hiển thị i, tồn tại một số ϵ> 0, như vậy đối với bất kỳ số thực a, ∈ (i-ϵ, i), Point1 và Point2 không hiển thị (tức là đoạn đường kết nối (x1(a), y1(a)) đến (x2(a), y2(x)) vượt qua một số trở ngại).

Đối với b ∈ (i, i + ϵ) chúng hiển thị.

Và đó là cách khác để trở thành vô hình.

Nhưng tôi có thể tìm được ranh giới chính xác như vậy không và nếu có thì làm cách nào?

Answer 1

Thật dễ dàng để check if two lines intersect. Sử dụng điều này để kiểm tra giao điểm của đường (p1, p2) và mỗi cạnh đa giác. Nếu bạn có bất kỳ giao lộ nào, đường thẳng (p1, p2) bị cản trở bởi một số chi tiết.

Nếu bạn cần khoảng thời gian (tại đó p1 và p2 không nằm trong tầm nhìn), bạn có thể thực hiện kiểm tra ở trên cho các giá trị t khác nhau (tốt nhất là với sự khác biệt tương đối nhỏ) và giữa "visible-t" và "vô hình-t", bạn có thể thực hiện tìm kiếm nhị phân cho đến khi đạt đến một ngưỡng đủ nhỏ, chẳng hạn như eps.

Answer 2

Thay đổi hiển thị chỉ có thể xảy ra khi một đỉnh chướng ngại vật nằm trên đoạn đường Point1-Point2. Vì vậy, tính thời gian của tất cả các va chạm đỉnh như vậy. (Trực giác này phải là một thử nghiệm tương đối đơn giản vì các điểm cuối đang di chuyển tuyến tính, nhưng tôi sẽ cần phải thực sự làm việc thông qua nó để kiểm tra. Tôi sẽ cho nó đi sau và quay lại.)

Bây giờ bạn có a tập hữu hạn các lần va chạm. Đối với mỗi loại, hãy kiểm tra xem phân đoạn có cắt bất kỳ cạnh vật cản nào khác không. Nếu có, cạnh đó điều chỉnh khả năng hiển thị và thời gian không phải là ranh giới hiển thị. Nếu không, bạn có thể kiểm tra khả năng hiển thị tại (t- & epsilon;) và (t + & epsilon;) để xác định bản chất của thay đổi.

Bạn sẽ cần phải có chính sách về một số trường hợp cạnh, chẳng hạn như khi đỉnh nằm trên đường kết nối cho một khoảng liên tục. Tôi nghĩ rằng tất cả những điều này có thể được đun sôi cho câu hỏi liệu các điểm (và các cạnh được xem kết thúc) có đục không.

Cập nhật

Quá trình xác định những va chạm đỉnh thực sự là hợp lý đơn giản, nó chỉ liên quan đến việc giải quyết một phương trình bậc hai một chút tẻ nhạt trong t.Bạn cần phải làm điều này cho mỗi đỉnh cho từng phân đoạn chuyển động từng phần, vì vậy tôi đoán chi phí sẽ là O (n * m) cho n khoảng thời gian đỉnh và m. (Nếu khoảng thời gian của chức năng vị trí không đồng bộ, bạn sẽ cần phải chia nhỏ chúng để trở thành như vậy.)

Chỉ xem xét một khoảng thời gian và thang tỷ lệ nằm trong khoảng [0,1]. Mỗi hàm vị trí là tuyến tính trong t, vì vậy hãy xác định x1(t) = x10 + x1m * t (ví dụ: x10 là giá trị bắt đầu và x1m là độ dốc) và tương tự cho y1(t), x2(t) và y2(t). Đối với một đỉnh V = (vx, vy), thời gian (nếu có) mà tại đó V nằm trên đoạn thẳng nối các điểm được cho bởi phương trình At^2 + Bt + C = 0, trong đó:

A = x1m * y2m - x2m * y1m 
B = vx * (y1m - y2m) + vy * (x2m - x1m) 
    + x10 * y2m - x20 * y1m 
    + y20 * x1m - y10 * x2m 
C = vx * (y10 - y20) + vy * (x20 - x10) 
    + x10 * y20 + x20 * y10 

(Hoặc một cái gì đó như thế Với khả năng sai sót phiên mã. từ phía sau phong bì, tôi đặc biệt khuyên bạn nên tự mình làm việc đó trước khi thực hiện!)

Nếu điều này có giải pháp thực sự trong phạm vi [0,1], chú của Bob. Nếu nó giảm xuống còn 0 = 0 hoặc somesuch, thì điểm chính là trên toàn bộ thời gian, trong trường hợp đó bạn phải xem xét chính sách của mình.

Answer 3

Ok, tôi có một bức tranh rõ ràng hơn về vấn đề này ngay bây giờ và được lấy cảm hứng từ gợi ý @walkytalky, đây là một câu trả lời hình học hơn.

Bạn đã đề cập rằng p1 và p2 đi dọc theo các đoạn đường thẳng. Tôi không biết các phân khúc này có được căn chỉnh theo cách sao cho cả hai p1 và p2 luôn bắt đầu các phân đoạn mới cùng một lúc. Tuy nhiên, bạn luôn có thể cắt một đoạn đường thẳng thành hai đoạn thẳng (có cùng độ dốc) sao cho cả p1 và p2 luôn bắt đầu các đoạn đường mới cùng một lúc.

Giả p1 hành trình dọc theo đường A-B, và p2 hành trình (cùng một lúc) cùng C-D như một tham số t đi từ 0 đến 1. (Tức là, lúc t=0.5, p1 là ở giữa A-B và p2 trong giữa C-D.)

Bằng cách để cho Ax và Ay biểu thị x và y tọa độ của điểm A (và tương tự cho B, C và D), chúng tôi có thể bày tỏ p1 và 01.230.như chức năng của t theo cách sau:

p1(t) = (Ax + t*(Bx - Ax), Ay + t(By - Ay)) 
p2(t) = (Cx + t*(Dx - Cx), Cy + t(Dy - Cy)) 

(. Ví dụ, khi t=0, Ax + t*(Bx - Ax) đánh giá để Ax, và khi t=1 nó để đánh giá Bx)

Để tìm mỗi "một-vertex- được-qua-by-giữa-p1-and-p2" -time chúng ta làm như sau:

Đối với mỗi trở ngại đỉnh v=(Vx, Vy) chúng ta cần phải tìm một t để p1(t), p2(t) và v phù hợp với nhau.

Điều này có thể được thực hiện bằng cách giải các phương trình sau đây (hai phương trình, và hai không rõ, t và k):

Vx=p1(t).x + k*(p2(t).x - p1(t).x) 
Vy=p1(t).y + k*(p2(t).y - p1(t).y)` 

Nếu k nằm giữa 0 và 1, đa giác đỉnh v thực sự là giữa dòng (mở rộng) A-B và dòng (mở rộng) C-D. Nếu t cũng nằm trong khoảng từ 0 đến 1, thì đỉnh v thực sự được chuyển qua đường p1-p2 trong thời gian các điểm di chuyển dọc theo các đoạn này (vì khi đó, t là 1,3 điểm sẽ nằm trên phân khúc mới).

Khi tất cả các "-đỉnh-là-qua-by-giữa-p1-và-p2" -times đã được tính toán, đó là một nhiệm vụ đơn giản để tìm ra phần còn lại. (Tức là, hãy tìm hiểu xem đó có phải là loại "trở thành trong tầm nhìn", "trở thành-out-of-sight" hoặc "không" loại đi qua):

Đối với tất cả các cặp t0 và t1 của đỉnh liên tiếp- thời gian trôi qua, bạn kiểm tra xem dòng p1((t1-t0)/2)-p2((t1-t0)/2) có miễn phí giao lộ với cạnh đa giác hay không. Nếu nó không có giao lộ, các điểm sẽ nằm trong tầm nhìn của toàn bộ thời gian (t0-t1), nếu không chúng sẽ không nhìn thấy toàn bộ thời gian (vì không có đỉnh nào khác được chuyển trong khoảng thời gian này).