Tìm điểm trên đường cong bezier dựa trên khoảng cách từ điểm khác

Question

Vì vậy, tôi có đường cong hình khối 3D và điểm bắt đầu được tìm thấy ở bất kỳ đâu dọc theo đường cong và cần tìm thêm điểm thứ hai xuống dưới đường cong. không phải khoảng cách arclength) cách xa điểm đầu tiên.

Một vấn đề khác là nếu điểm thứ hai đến cuối đường cong và vẫn không ở khoảng cách không gian thế giới mong muốn, trong trường hợp này tôi muốn nó tiếp tục dọc theo tang cho đến khi khoảng cách đạt được.

Bất kỳ ý tưởng nào?

Answer 1

Than ôi, tôi không biết bất kỳ phương trình dạng khép kín nào cung cấp cho bạn (các) điểm mà bạn muốn. Có lẽ kỹ thuật đơn giản nhất để ước tính điểm đó là đệ quy chặt đường cong Bezier thành 2 đường Bezier nhỏ hơn bằng cách sử dụng de Casteljau's algorithm. Các đệ quy đáy khi (a) tất cả các điểm giới hạn cho đường cong đều quá gần hoặc quá xa điểm đã cho, hoặc (b) tất cả các điểm giới hạn cho đường cong là "đủ gần" để bằng khoảng cách mong muốn (có lẽ tất cả chúng đều nằm trong cùng một pixel).

Tôi chắc chắn rằng số điểm tối đa trên một đường cong Bezier nhất định là khoảng cách tuyến tính nhất định từ một số điểm nhất định là 4 điểm. (Điều này có thể xảy ra khi đường cong Bezier nhất định có giao lộ tự).

CHỈNH SỬA:

Có lẽ tôi nên đọc toàn bộ câu hỏi trước khi bắt đầu trả lời, phải không? Phân đoạn đường cong Bezier "bốn điểm" tiêu chuẩn có thể được xem như một phần của đường cong khối vô hạn dài. Có thể có một uốn cong hoặc vòng hoặc cusp tại một địa điểm, nhưng đủ xa đường cong sắc nét con đường flattens ra để gần với 2 tia thẳng, mỗi điểm trong một số hướng tùy ý. Than ôi, giải pháp trên chỉ tìm thấy các điểm nằm trên đoạn đường cong Bezier ngắn. Tôi giả sử bạn muốn (các) điểm dọc theo đường cong khối vô hạn dài đó là khoảng cách nhất định cách xa điểm đã cho, ngay cả khi chúng không nằm trên đoạn đường cong Bezier ngắn.

== de Casteljau trong == ngược

Bạn có thể chạy (trung điểm đệ quy) de thuật toán Casteljau ở chiều ngược lại, tạo ra một bốn điểm đường cong Bezier mới "kép" kích thước của người cuối cùng ở mỗi lần lặp, cho đến khi bạn có đủ lớn để bao gồm (các) điểm mong muốn. (Khi tất cả 4 điểm ban đầu là "quá gần" đến điểm đã cho, thì việc nhân đôi được đảm bảo để tạo ra một đoạn đường cong với điểm bắt đầu "quá gần", điểm kết thúc "quá xa", và sau đó bạn có thể sử dụng ở trên thuật toán để hội tụ trên một điểm đó là khoảng cách mong muốn từ điểm đã cho). Cách tiếp cận này chỉ dựa vào cộng, trừ, nhân đôi, và trung bình, vì vậy về nguyên tắc, nó phải tương đối về mặt số lượng. (Nó không bao giờ thực sự đánh giá công thức khối tại bất kỳ vị trí nào t).

== zero-Phát ==

Bạn có thể chuyển đổi từ các đại diện bốn điểm để các đại diện đa thức khối, và sử dụng bất kỳ thuật toán gốc tìm hiểu để hội tụ trên một trong những điểm mong muốn. Phương pháp của Newton sẽ hoạt động khá tốt, vì các đoạn ngắn của đường cong Bezier gần như thẳng. Chúng ta có thể điều chỉnh phương trình phương trình Newton từ Finding the Minimum Distance Between a Point and a Cubic Spline cho vấn đề này? Tôi sẽ sử dụng thuật toán bisection cho sự đơn giản trong mô tả, mặc dù nó chạy chậm hơn phương pháp Newton.

Như mọi khi, một Bezier phân khúc đường cong khối có thể được mô tả như

B(t) = (1-t)^3 * P0 + 3*(1-t)^2*t*P1 + 3*(1-t)*t^2*P2 + t^3*P3. 

(Thật không may, phương trình này không phải lúc nào cũng bằng số mạnh mẽ - đó là lý do tại sao nhiều người sử dụng giảm một nửa đệ quy sử dụng de thuật toán Casteljau thay vì).

Tôi giả sử bạn có (hoặc có thể tìm thấy) giá trị t_given cho điểm nhất định của bạn,

x_given = B(t_given).x 
y_given = B(t_given).y 

Khoảng cách giữa điểm nhất định của bạn và một số điểm khác dọc theo đường cong được cho bởi định lý Pythagore,

distance2(t) = (x_given - B(t).x)^2 + (y_given - B(t).y)^2. 
distance(t) = sqrt(distance2(t)). 

điểm (s) bạn đang tìm kiếm đang ở số không của hàm

given_distance2 = given_distance^2. 
f(t) = distance2(t) - given_distance2. 

Giả sử rằng khoảng cách cho trước không phải là zero, và các điểm nhất định có một thuật toán t_given < 1, sự chia làm hai đoạn sẽ chạy một cái gì đó giống như

left = t_given 
right = 1 // the endpoint of the given Bezier curve segment 
while(distance2(right) < given_distance2){ 
    right = right*2 
} 

Tại thời điểm này, các t_left là gần gũi hơn với những điểm nhất định so với mong muốn khoảng cách, và t_right là xa hơn khoảng cách mong muốn (hoặc có lẽ chính xác bằng nhau). Vì chúng ta có một điểm quá gần, và một điểm khác quá xa, thuật toán bisection sẽ hoạt động.

while((abs(f(right) is too big) AND (abs(left - right) is too big)){ 
    // find midpoint 
    midpoint = (t_left + t_right)/2 

Tiếp theo chúng tôi kiểm tra: phân đoạn đầu tiên còn lại ... giữa có chứa số không hoặc điểm giữa ... phải không?

if(f(left)*f(midpoint) < 0) then 
     // throw away right half 
     right = midpoint 
    else 
     // throw away left half 
     left = midpoint 
} 

return(right) 

Tại thời điểm này, "quyền" giá trị là giá trị của t, và B (bên phải) là điểm tương ứng, như vậy mà khoảng cách từ điểm đó đến điểm nhất định ban đầu là (ước tính) các trao khoảng cách.

Answer 2

Tuyên bố sự cố của bạn cần một lần tinh chỉnh hơn. Cụ thể bạn đang bị hạn chế khi yêu cầu một số điểm B là N đơn vị cách xa điểm bắt đầu A. Có thể có nhiều điểm cách N khoảng cách từ A.

Điều đó khiến bạn không thể lấy mẫu đường cong của mình khoảng cách dọc theo đường cong và sau đó tính toán một khoảng cách tuyến tính trở lại A. Nó không phải là tối ưu nhưng nó sẽ làm việc. Để xử lý nhiều điểm N, bạn sẽ phải đưa ra một quy tắc. Có thể đơn giản như điểm đầu tiên được tìm thấy.