Cách tính điểm gần nhất của đường và đường cong? .. hoặc đường cong và đường cong?

Question

Với các điểm của đường thẳng và đường cong bezier bậc hai, bạn tính toán điểm gần nhất như thế nào?

Answer 1

Tôi chỉ muốn cung cấp cho bạn một vài gợi ý, trong trường hợp Q.B.Curve // ​​segment: để có được tính toán đủ nhanh, tôi nghĩ trước tiên bạn nên nghĩ đến việc sử dụng một loại 'bounding box' cho thuật toán của bạn. Say P0 là điểm đầu tiên của QB Curve, P2 điểm thứ hai, P1 điểm kiểm soát, và P3P4 phân khúc thì:

1. Tính khoảng cách từ P0, P1, P2 để P3P4
2. nếu P0 HOẶC P2 là điểm gần nhất -> đây là điểm gần nhất của đường cong từ P3P4. kết thúc: =).
3. nếu P1 là điểm gần nhất và Pi (i = 0 hoặc 1) điểm gần nhất thứ hai, khoảng cách giữa PiPC và P3P4 là ước tính khoảng cách bạn tìm kiếm có thể là đủ chính xác tùy theo nhu cầu của bạn.
4. nếu bạn cần phải chính xác hơn: tính P1 ', là điểm trên Q.B là gần nhất từ ​​P1: bạn tìm thấy nó áp dụng công thức BQC với t = 0,5. -> khoảng cách từ PiP1 'đến P3P4 là một ước tính chính xác hơn - nhưng tốn kém hơn -.
5. Lưu ý rằng nếu dòng được xác định bởi P1P1 'cắt nhau P3P4, P1' là điểm gần nhất của QBC từ P3P4.
6. nếu P1P1' không giao nhau P3P4, sau đó bạn đang trên may mắn, bạn phải đi theo con đường khó khăn ...

Bây giờ nếu (và khi nào) bạn cần chính xác:

suy nghĩ về sử dụng thuật toán phân chia và chinh phục trên tham số của đường cong: gần nhất với P3P4 ?? P0P1 'hoặc P1'P2 ??? nếu nó là P0P1 '-> t là giữa 0 và 0,5 để tính Pm cho t = 0,25. Bây giờ là gần nhất từ ​​P3P4 ?? P0Pm hoặc PmP1 '?? nếu nó là PmP1 '-> tính Pm2 cho t = 0,25 + 0,125 = 0,375 thì gần nhất? PmPm2 hoặc Pm2P1 '??? vv bạn sẽ đến giải pháp chính xác trong thời gian không, như 6 lần lặp lại và độ chính xác của bạn trên t là 0,004 !! bạn có thể dừng tìm kiếm khi khoảng cách giữa hai điểm trở thành dưới một giá trị đã cho. (và không có sự khác biệt giữa hai tham số, vì thay đổi nhỏ về tham số, điểm có thể ở xa) trên thực tế nguyên tắc của thuật toán này là xấp xỉ đường cong với các phân đoạn ngày càng chính xác hơn.

Đối với trường hợp đường cong/đường cong tôi sẽ đầu tiên 'hộp' chúng cũng để tránh tính toán vô dụng, vì vậy đầu tiên sử dụng phân đoạn/phân đoạn tính toán, sau đó (có thể) phân đoạn/đường cong tính toán, và chỉ khi cần thiết đường cong/đường cong tính toán.

Đối với đường cong/đường cong, hãy phân chia và chinh phục các tác phẩm, khó giải thích hơn nhưng bạn có thể tìm ra. : =)

hy vọng bạn có thể tìm thấy sự cân bằng tốt của bạn cho tốc độ/độ chính xác với điều này: =)

Chỉnh sửa: Hãy suy nghĩ tôi tìm thấy cho các trường hợp chung một giải pháp tốt đẹp :-) Bạn nên lặp trên (bên trong) giới hạn hình tam giác của mỗi BQC Vì vậy, chúng ta có tam giác T1, điểm A, B, C có tham số 't' tA, tB, tC. và tam giác T2, điểm D, E, F, có tham số t tD, tE, tF. Ban đầu chúng ta có tA = 0 tB = 0.5 tC = 1.0 và tương tự cho T2 tD = 0, tE = 0.5, tF = 1.0 Ý tưởng là gọi một thủ tục đệ quy sẽ chia T1 và/hoặc T2 thành hình chữ nhật nhỏ hơn cho đến khi chúng ta là ok với độ chính xác đạt được. Bước đầu tiên là tính toán khoảng cách từ T1 từ T2, theo dõi các phân đoạn là gần nhất trên mỗi tam giác. Đầu tiên 'lừa': nếu trên T1 đoạn là AC, sau đó dừng đệ quy trên T1, điểm gần nhất trên Curve 1 là A hoặc C. nếu T2 là đoạn gần nhất là DF, sau đó dừng recursivity trên T2, điểm gần nhất trên Curve2 là D hoặc F. Nếu chúng ta dừng đệ quy cho cả hai -> khoảng cách trả về = min (AD, AF, CD, CF). sau đó nếu chúng ta có đệ quy trên T1, và phân đoạn AB gần nhất, T1 mới trở thành: A '= AB = điểm của đường cong với tB = (tA + tC)/2 = 0,25, C = cũ B. tương tự cho T2: áp dụng đệ quy cần thiết và gọi cùng một thuật toán trên T1 mới và T2 mới. Dừng thuật toán khi khoảng cách tìm thấy giữa T1 và T2 trừ đi khoảng cách tìm thấy giữa các T1 và T2 trước đó là dưới ngưỡng. chức năng có thể trông giống như ComputeDistance (curveParam1, A, C, shouldSplitCurve1, curveParam2, D, F, shouldSplitCurve2, previousDistance) trong đó các điểm lưu trữ các tham số t của chúng.

lưu ý rằng khoảng cách (đường cong, phân đoạn) chỉ là một trường hợp cụ thể của thuật toán này và bạn nên thực hiện khoảng cách (tam giác, tam giác) và khoảng cách (phân đoạn, hình tam giác). Chúc vui vẻ.

Answer 2

Điểm phù hợp với tiêu chuẩn là điểm gần nhất. Tôi có nghĩa là u vẽ một đường trực giao với đường thẳng. . Nếu đường thẳng đó là trực giao với đường cong thì điểm giao nhau là điểm gần nhất

Answer 3

1. Phương pháp xấu đơn giản - bằng cách lặp đi từng điểm từ đường cong thứ nhất và đi theo điểm từ đường cong thứ hai và nhận tối thiểu 2 .Định nghĩa hàm toán học của khoảng cách giữa các đường cong và giới hạn calc của hàm này như:

| Fcur1 (t) -Fcur2 (t) | -> 0

Fs là vectơ.

Tôi nghĩ chúng ta có thể tính toán đạo hàm này cho xác định extremums và nhận được gần nhất và bàn cách điểm

Tôi nghĩ về điều này một thời gian sau đó, và bài trả lời đầy đủ.

Answer 4

Có tồn tại một bài báo khoa học liên quan đến câu hỏi này từ INRIA: Computing the minimum distance between two Bézier curves (PDF here)

Answer 5

Xây dựng vấn đề của bạn về phân tích tiêu chuẩn: Bạn đã có một số lượng để giảm thiểu (khoảng cách), do đó bạn xây dựng một phương trình cho này số lượng và tìm các điểm mà các dẫn xuất đầu tiên bằng không. Tham số hóa với một tham số duy nhất bằng cách sử dụng tham số của đường cong p, là từ 0 cho điểm đầu tiên và 1 cho điểm cuối cùng.

Trong trường hợp đường thẳng, phương trình khá đơn giản: Nhận tọa độ x/y từ phương trình của đường spline và tính toán khoảng cách đến đường nhất định thông qua phương trình vectơ (sản phẩm vô hướng với đường chuẩn).

Trong trường hợp của đường cong, giải pháp phân tích có thể trở nên khá phức tạp. Bạn có thể muốn sử dụng một kỹ thuật giảm thiểu số như Nelder-Mead hoặc, vì bạn có một vấn đề liên tục 1D, bisection đơn giản.

Answer 6

Tôi đã từng viết một công cụ để thực hiện một tác vụ tương tự. Bezier splines thường là đa thức khối tham số. Để tính toán bình phương của khoảng cách giữa một phân đoạn khối và một đường thẳng, đây chỉ là bình phương của khoảng cách giữa hai hàm đa thức, chính nó chỉ là một hàm đa thức khác! Lưu ý rằng tôi đã nói bình phương của khoảng cách, không phải là căn bậc hai.

Về cơ bản, đối với bất kỳ điểm nào trên phân đoạn khối, người ta có thể tính toán bình phương của khoảng cách từ điểm đó đến đường thẳng.Đây sẽ là đa thức bậc 6. Chúng ta có thể thu nhỏ hình vuông của khoảng cách đó không? Vâng. Giá trị tối thiểu phải xảy ra khi đạo hàm của đa thức đó bằng không. Vì vậy, phân biệt, nhận được một đa thức bậc 5. Sử dụng công cụ tìm kiếm gốc yêu thích của bạn để tạo ra tất cả các gốc số. Jenkins & Traub, bất cứ điều gì. Chọn giải pháp chính xác từ bộ rễ đó, không bao gồm bất kỳ giải pháp nào phức tạp, và chỉ chọn một giải pháp nếu nó nằm bên trong phân đoạn khối được đề cập. Đảm bảo bạn loại trừ các điểm tương ứng với cực đại địa phương của khoảng cách.

Tất cả điều này có thể được thực hiện hiệu quả và không có trình tối ưu hóa lặp lại bên cạnh trình tìm gốc đa thức cần được sử dụng, do đó không yêu cầu sử dụng các công cụ tối ưu yêu cầu giá trị bắt đầu, chỉ tìm một giải pháp gần giá trị bắt đầu đó. Ví dụ, trong hình 3-d tôi cho thấy một đường cong được tạo ra bởi một tập hợp các điểm trong 3-d (màu đỏ), sau đó tôi lấy một tập hợp các điểm nằm trong một vòng tròn bên ngoài, tôi tính toán gần nhất điểm trên đường cong bên trong từ mỗi đường, vẽ một đường thẳng xuống đường cong đó. Những điểm khoảng cách tối thiểu này được tạo ra bởi lược đồ nêu trên.

Answer 7

Trong trường hợp của một đường cong Bézier và một dòng

Có ba ứng cử viên cho điểm gần nhất với dòng:

1. Nơi trên đoạn đường cong Bézier song song với dòng (nếu có một địa điểm như vậy),
2. Một đầu của đoạn đường cong,
3. Đầu kia của đoạn đường cong.

Kiểm tra cả ba; khoảng cách ngắn nhất sẽ thắng.

Trong trường hợp của hai đường cong Bézier

Phụ thuộc nếu bạn muốn kết quả phân tích chính xác, hoặc nếu một kết quả số được tối ưu hóa là đủ tốt.

kết quả phân tích

Cho hai đường cong Bézier Một (t) và B (s), bạn có thể lấy được phương trình cho định hướng địa phương của họ A ' (t) và B ' (s). Các cặp điểm mà Một ' (t) = B' (s) là ứng cử viên, nghĩa là liên kết (t, s) mà các đường cong là địa phương song song.Tôi đã không được chọn, nhưng tôi cho rằng Một ' (t) - B' (s) = 0 có thể được giải quyết phân tích. Nếu các đường cong của bạn giống như những gì bạn thể hiện trong ví dụ của mình, chỉ nên có một giải pháp hoặc không có giải pháp cho phương trình đó, nhưng có thể có hai (hoặc vô hạn trong trường hợp các đường cong giống nhau nhưng được dịch - trong trường hợp đó bạn có thể bỏ qua điều này vì người chiến thắng sẽ luôn là một trong những điểm cuối của đoạn đường cong).

Trong cách tiếp cận tương tự như đường viền trường hợp đường cong ở trên, hãy kiểm tra từng cặp điểm này, cộng với điểm cuối đoạn đường cong. Khoảng cách ngắn nhất sẽ thắng.

kết quả bằng số

Hãy nói rằng các điểm trên hai đường cong Bézier được định nghĩa là Một (t) và B (s). Bạn muốn giảm thiểu khoảng cách d (t, s) = | Một (t) - B (s) |. Đó là một hai tham số bài toán tối ưu đơn giản: tìm ra s và t giảm thiểu d (t, s) với các khó khăn 0 ≤ t ≤ 1 và 0 ≤ s ≤ 1 .

Kể từ d = SQRT ((xA - xB) ² + (Ya - YB) ²), bạn cũng có thể chỉ hạn chế tối đa các chức năng f (t, s) = [d (t, s)] ² để lưu phép tính căn bậc hai.

Có numerous ready-made methods cho các vấn đề tối ưu hóa như vậy. Chọn và chọn.

---

Lưu ý rằng trong cả hai trường hợp trên, bất kỳ thứ gì bậc cao hơn đường cong Bézier bậc hai có thể cho bạn nhiều hơn một địa phương tối thiểu, vì vậy đây là điều cần chú ý. Từ các ví dụ bạn đưa ra, có vẻ như các đường cong của bạn không có điểm uốn, vì vậy mối quan tâm này có thể không áp dụng trong trường hợp của bạn.