[Thảo Luận] - Tìm đường tròn ngoại tiếp của danh sách điểm

[Doan Nguyen Van 494]

Chào các bác, như tiêu đề đặt ra em có bài toán như này, nếu thấy hay mời các bác cùng vào thảo luận.

Cụ thể ban đầu có 1 danh sách điểm như hình dưới:

Yêu cầu đặt ra: -Làm sao có thể tìm được đường tròn ngoại tiếp bao quanh toàn bộ danh sách điểm.

                            -Bán kính đường tròn cần tìm phải là nhỏ nhất có thể.

Các bác có giải thuật nào hay cùng thảo luận nhé.

Xin chân thành cảm ơn!

 

[Doan Van Ha 3211]

Cháu vào đây có rồi nè!

http://www.theswamp.org/index.php?topic=10561.0

[Doan Nguyen Van 494]

9 phút trước, Doan Van Ha đã nói:

Cháu vào đây có rồi nè!

http://www.theswamp.org/index.php?topic=10561.0

Cảm ơn bác đã gợi ý, cháu có tham khảo qua 1 số file thực hiện được nhưng chưa tìm ra giải thuật hợp lý hơn.

Bởi số điểm nếu càng nhiều (khoảng 1-2k điểm) thì thời gian thực thi khá chậm.

Nên cháu muốn cùng mọi người thảo luận để tìm ra giải thuật nhanh chóng hơn.

 

[DuongTrungHuy 138]

29 phút trước, Doan Nguyen Van đã nói:

 

 

 

29 phút trước, Doan Nguyen Van đã nói:

Cảm ơn bác đã gợi ý, cháu có tham khảo qua 1 số file thực hiện được nhưng chưa tìm ra giải thuật hợp lý hơn.

Bởi số điểm nếu càng nhiều (khoảng 1-2k điểm) thì thời gian thực thi khá chậm.

Nên cháu muốn cùng mọi người thảo luận để tìm ra giải thuật nhanh chóng hơn.

 

Ái chà ghê thế à.

Bạn có thể cho biết tình huống nào dẫn đến bài toán như vậy ko. Bạn muốn chính xác hay 1 sai số khá nhỏ thôi điểm tìm khoảng cách 0.1 mm chẳng hạn.

 

Chào nhé.

[Doan Nguyen Van 494]

10 phút trước, DuongTrungHuy đã nói:

 

Ái chà ghê thế à.

Bạn có thể cho biết tình huống nào dẫn đến bài toán như vậy ko. Bạn muốn chính xác hay 1 sai số khá nhỏ thôi điểm tìm khoảng cách 0.1 mm chẳng hạn.

 

Chào nhé.

Chào bác,

Bài toán trên là bước phụ:

Mục đích ban đầu là tìm được đường tròn ngoại tiếp bao quanh các đối tượng.

Đối với những hình đơn giản như bên trái thì chỉ cần lọc lấy danh sách đỉnh rồi áp dụng lisp giống của bác Hạ gửi để tìm ra đường tròn ngoại tiếp chính xác nhất.

Còn với hình như bên phải có đường tròn, hoặc ARC, hoặc PLINE chứa ARC thì ngoài danh sách đình cần lấy thêm tập hợp point nằm trên các đoạn cong đó, tập hợp này càng nhiều (tức là khoảng chia càng nhỏ ) thì đường tròn tạo ra càng chính xác, nên khi áp dụng với trường hợp này, 1 đường tròn có thể sẽ phải chia ra 1-2k điểm để áp dụng, đường tròn càng lớn thì số điểm càng nhiều, thuật toán càng chậm.

Cụ thể là như vậy đó bác.

Về sai số như bác nói thì tất nhiên càng nhỏ càng tốt, vì chủ yếu trường hợp có đường cong thì mới cần đến độ chính xác như vậy, bởi đường cong không xác định vị trí đỉnh cụ thể được

[snowman.hms 60]

ConvexHull->>

[Doan Van Ha 3211]

1 giờ} trướ}c, Doan Nguyen Van đã nói:

Chào bác,

Bài toán trên là bước phụ:

Mục đích ban đầu là tìm được đường tròn ngoại tiếp bao quanh các đối tượng.

Đối với những hình đơn giản như bên trái thì chỉ cần lọc lấy danh sách đỉnh rồi áp dụng lisp giống của bác Hạ gửi để tìm ra đường tròn ngoại tiếp chính xác nhất.

Còn với hình như bên phải có đường tròn, hoặc ARC, hoặc PLINE chứa ARC thì ngoài danh sách đình cần lấy thêm tập hợp point nằm trên các đoạn cong đó, tập hợp này càng nhiều (tức là khoảng chia càng nhỏ ) thì đường tròn tạo ra càng chính xác, nên khi áp dụng với trường hợp này, 1 đường tròn có thể sẽ phải chia ra 1-2k điểm để áp dụng, đường tròn càng lớn thì số điểm càng nhiều, thuật toán càng chậm.

Cụ thể là như vậy đó bác.

Về sai số như bác nói thì tất nhiên càng nhỏ càng tốt, vì chủ yếu trường hợp có đường cong thì mới cần đến độ chính xác như vậy, bởi đường cong không xác định vị trí đỉnh cụ thể được

Lee Mac
http://www.lee-mac.com/minimumenclosingcircle.html

 

[Doan Nguyen Van 494]

32 phút trước, snowman.hms đã nói:

ConvexHull->>

 

9 phút trước, Doan Van Ha đã nói:

Lee Mac
http://www.lee-mac.com/minimumenclosingcircle.html

 

Cảm ơn các bác đã trích dẫn, 

Ở lisp này LeeMac dùng ConvexHull tính ra được CIRCLE min rồi nhưng bởi với CIRCLE và ARC thì LEE chỉ lấy 36 điểm đại diện để lọc nên có thể bị không bao hết, cái này khi cháu sửa lại thành 1-2k điểm thì tốc độ sẽ chậm đi, nhưng tốc độ thì của LEE là nhanh nhất rồi.

Chắc không có phương pháp nào khả dĩ hơn.

[Doan Van Ha 3211]

Có những bài toán thực tế phải giải gần đúng thôi.

[snowman.hms 60]

Search for fast convexhull. It really much more faster than normal.

[DuongTrungHuy 138]

Vào lúc 17/11/2020 tại 15:57, Doan Nguyen Van đã nói:

Chào bác,

Bài toán trên là bước phụ:

Mục đích ban đầu là tìm được đường tròn ngoại tiếp bao quanh các đối tượng.

 

 

Gửi bạn Doan Nguyen Van 

 

Cũng không Ok lắm nhưng cũng gửi lên xem như đóng góp cho sức sống diễn đàn với ý nghĩa Thuần Việt.

So với cái Lee-Man của bác Doan Van Ha chắc còn thua xa

 

Chúc công tác tốt.

Cad_Viet2.LSP

[Doan Nguyen Van 494]

16 phút trước, DuongTrungHuy đã nói:

 

Gửi bạn Doan Nguyen Van 

 

Cũng không Ok lắm nhưng cũng gửi lên xem như đóng góp cho sức sống diễn đàn với ý nghĩa Thuần Việt.

So với cái Lee-Man của bác Doan Van Ha chắc còn thua xa

 

Chúc công tác tốt.

Cad_Viet2.LSP

Cảm ơn bác, hình như bác gửi thiếu hàm CAL1

[DuongTrungHuy 138]

30 phút trước, Doan Nguyen Van đã nói:

Cảm ơn bác, hình như bác gửi thiếu hàm CAL1

Ái dà.

(Defunc Cal1 (d1 tx ty)

  (Setq d2 (list (+ (car d1) tx) (+ (cadr d1) ty)))

)

[LuytBui 19]

Em mạo muội đưa ra phương án này các anh xem thế nào ạ:

+) Xây dựng 2 hàm (defun Boundary_Circle(list_of_points) (...)) (viết tắt BC) và (defun Boundary_Circle_4(list_of_4_points) (...)) (viết tắt BC4)

(defun BC(alist)      ; trả về 3 điểm thuộc đường tròn bao tất cả các điểm trong alist

    (nếu (length alist = 3) trả về (alist) )

    (nếu (length alist >4) trả về (BC (car alist) (BC (cadr alist)))  )

    (nếu (length alist = 4) trả về (BC4 alist) )

)

(defun BC4(alist)    ;alist gồm 4 điểm

     (lặp lại cho đến khi tìm ra

(***)     nếu  ( (nth i alist) nằm trong đường tròn ngoại tiếp của 3 điểm còn lại của alist) trả về 3 điểm còn lại

     )

)

(***):  So sánh khoảng cách đến tâm đường tròn ngoại tiếp. Cách xác định tâm đường tròn ngoại tiếp của 3 điểm dựa theo tọa độ có thể tham khảo hàm circumcircle trong http://paulbourke.net/papers/triangulate/tri.lisp

Em rất hứng thú với bài toán này nhưng chưa triển khai được vì không có thời gian.

 

 

[DuongTrungHuy 138]

11 giờ trước, LuytBui đã nói:

Em mạo muội đưa ra phương án này các anh xem thế nào ạ:

+) Xây dựng 2 hàm ....

 

Bạn viết hơi khó hiểu, hãy trình bày ý tưởng để giải bài toán đã bạn à.

 

Ta thấy ý nghĩa thực tế của bài toán là: Các vật thể bên trong khi quay theo tâm của hình tròn thì nằm trọn bên trong nó không vượt ra ngoài vòng tròn được.

[DuongTrungHuy 138]

Vào lúc 18/11/2020 tại 17:15, Doan Nguyen Van đã nói:

Cảm ơn bác, hình như bác gửi thiếu hàm CAL1

Bạn Doan Nguyen Van có ý tưởng gì về bài toán này không?

Bạn có thể nói 1 vài ý để ae tham khảo không?

 

Chào nhé!

[Doan Nguyen Van 494]

48 phút trước, DuongTrungHuy đã nói:

Bạn Doan Nguyen Van có ý tưởng gì về bài toán này không?

Bạn có thể nói 1 vài ý để ae tham khảo không?

 

Chào nhé!

Hiện cháu chỉ sửa lại lisp của LEEMAC thấy ổn, chứ ý tưởng cụ thể thì không bằng cái này nên cháu không định nêu ra bác ạ.

[DuongTrungHuy 138]

1 giờ} trướ}c, Doan Nguyen Van đã nói:

Hiện cháu chỉ sửa lại lisp của LEEMAC thấy ổn, chứ ý tưởng cụ thể thì không bằng cái này nên cháu không định nêu ra bác ạ.

À mình vừa cải tiến qua 1 thuật toán khác, với thuật toán này thì đối với “ARC“, “LWPOLYLINE”, “CIRCLE” là chính xác tuyệt đối, còn “SPLINE” thì đành sai số bạn à. À và cũng nhanh hơn cái cũ nhiều vì ko phải thử dần.

Mình biên tập xong sẽ gửi vì hơi dài dòng.

 

Chào nhé!

[Doan Nguyen Van 494]

1 giờ} trướ}c, DuongTrungHuy đã nói:

À mình vừa cải tiến qua 1 thuật toán khác, với thuật toán này thì đối với “ARC“, “LWPOLYLINE”, “CIRCLE” là chính xác tuyệt đối, còn “SPLINE” thì đành sai số bạn à. À và cũng nhanh hơn cái cũ nhiều vì ko phải thử dần.

Mình biên tập xong sẽ gửi vì hơi dài dòng.

 

Chào nhé!

Cháu cảm ơn bác ạ, mong nhận được phản hồi từ bác

[ndtnv 481]

Có thể cải tiến tốc độ và độ chính xác bằng phép chia nhị phân.

Xem đường cong kín là đường cong hở có điểm đầu = cuối

1. Tìm đường tròn qua tất cả các đỉnh

2. Nếu là đường cong, tìm gđ với đường tròn, nếu có 0 hoặc 1 gđ: đường cong nằm trong.

 a. Nếu 2 gđ: xét tđ đoạn cong nếu nằm trong chứng tỏ 2 gđ tiếp xúc đường tròn, nếu nằm ngoài tìm đường tròn mới bao trung điểm của đoạn cong.

 b. Nếu có nhiều gđ, xét từng đoạn 2 gđ kề nhau, nếu trung điểm nằm trong: đoạn đó nằm trong đường tròn.Nếu trung điểm nằm ngoài, xét như a.

      Sau đó tìm đường tròn bao trung điểm các đoạn

3. Lặp lại bước 2 đến độ chính xác cần thiết

 

[DuongTrungHuy 138]

1 giờ} trướ}c, ndtnv đã nói:

Có thể cải tiến tốc độ và độ chính xác bằng phép chia nhị phân.

Xem đường cong kín là đường cong hở có điểm đầu = cuối

1. Tìm đường tròn qua tất cả các đỉnh

2. Nếu là đường cong, tìm gđ với đường tròn, nếu có 0 hoặc 1 gđ: đường cong nằm trong.

 a. Nếu 2 gđ: xét tđ đoạn cong nếu nằm trong chứng tỏ 2 gđ tiếp xúc đường tròn, nếu nằm ngoài tìm đường tròn mới bao trung điểm của đoạn cong.

 b. Nếu có nhiều gđ, xét từng đoạn 2 gđ kề nhau, nếu trung điểm nằm trong: đoạn đó nằm trong đường tròn.Nếu trung điểm nằm ngoài, xét như a.

      Sau đó tìm đường tròn bao trung điểm các đoạn

3. Lặp lại bước 2 đến độ chính xác cần thiết

 

Chào bạn.

Mình cũng làm như vậy đó Bạn. Ở đây mình chia poly ra 10 đoạn thử dần, tìm thấy min thì dừng lại, nhảy lui 1 bước, lấy bước tiếp theo bằng bước cũ chia 10, lại đi tìm giá trị min, thấy thì thì dừng lại nếu bước đạt yêu cầu thì stop còn chưa đạt yêu cầu thì làm tiếp. Đối với bài toán này như đã nói chỉ với loại SPLINE thì mình tính gần đúng, còn các đối tượng còn lại thì mình tính chính xác luôn không thử dần.

 

Thuật toán nhị phân mình dùng trong tìm kiếm 1 giá trị trong 1 danh sách giá trị đã được sắp xếp.

 

Chào nhé!

[DuongTrungHuy 138]

Vào lúc 17/11/2020 tại 14:57, Doan Van Ha đã nói:

Cháu vào đây có rồi nè!

http://www.theswamp.org/index.php?topic=10561.0

Chào bác Doan Van Ha!

 

Bác cho hỏi có hàm tìm điểm xa nhất (thay vì gần nhất đã có vlax-curve-getClosestPointTo) không nhỉ.

Huy đã viết thuật toán cho hàm này, :) nhưng ko dám đưa lên, sợ lại bị chê là thích đi xe đạp :)

 

Cán ơn Bác nhé! 

[alisp 73]

2 giờ trước, DuongTrungHuy đã nói:

Chào bác Doan Van Ha!

 

Bác cho hỏi có hàm tìm điểm xa nhất (thay vì gần nhất đã có vlax-curve-getClosestPointTo) không nhỉ.

Huy đã viết thuật toán cho hàm này, :) nhưng ko dám đưa lên, sợ lại bị chê là thích đi xe đạp :)

 

Cán ơn Bác nhé! 

  Hàm xa nhất chưa có đâu bác, vì vlisp không biết hàm đó dùng vào việc gì, bác cứ yên tâm đưa lên, nếu người ta cười thì chắc chỉ nói bác thích đi xe tăng thôi mà, có gì đâu!! Hehe!!

  Nói vui thôi, không có ý gì đâu.

[DuongTrungHuy 138]

4 giờ trước, alisp đã nói:

  Hàm xa nhất chưa có đâu bác, vì vlisp không biết hàm đó dùng vào việc gì, ...

Hàm này để giải quyết bài toán này đó bạn.

Hi.

[DuongTrungHuy 138]

Cà phê sáng Chủ nhật.

 

Thuật toán tìm điểm xa nhất của 1 SPLINE hoặc POLYLINE

Ta có 1 Spline (S) và điểm M cần tìm điểm xa nhất từ M đến Spline.

-         Tạo 1 vòng tròn bao ngoài (S) và tâm ở M.

-         Trên vòng tròn lấy 1 điểm bất kỳA1, dùng lệnh cad chọn được điểm gần nhất  từ A1 đến (S) là A2

-         Từ M nối A2 cắt vòng tròn tại A3

-         Lại từ A3 tìm điểm gần nhất đến (S) có A4

-         Tiếp tục làm cho đến khi đến được điểm cần tìm với độ chính xác cần thiết ở đây là điểm A12

Nói chung 1 đường Spline thường có nhiều điểm cực trị địa phương (cực đại, cực tiểu) nên ta chọn nhiều điểm trên đường tròn thì sẽ được nhiều điểm xa nhất như hình trái. So sánh giữa các đoạn đến cực trị đó ta tìm được điểm N duy nhất có khoảng cách max đến (S)

 

Chúc các Bạn buổi sáng vui vẻ!

 

PS. Mình mới viết nên chưa bẫy lối được nhiều, có gì các bạn ý kiến thêm.

Cad_Viet2.LSP