Hỏi về Lisp (thuật toán, ý tưởng, coding,...)

[DuongTrungHuy 132]

Nếu mình không nhầm thì đây là lưới TG Delauney. Gặp trường hợp này mình thường làm như sau:

-Tìm tâm và bán kính vòng tròn qua các TG (cần đổi về TG phẳng Z=0), tạo thành 1 cụm dữ liệu và chỉ làm 1 lần.

-Bấm điểm bất kỳ và chọn ra vòng tròn nào bao điểm đó, có thể 2,3 vòng tròn (điều kiện khỏang cách đến tâm < R)

-Kiểm tra cụ thể điểm đó sẽ nằm trong tam giác nào tương ứng với 2,3 vòng tròn đó.

Có thể nó không tối ưu lắm nhưng cũng đưa lên cùng bàn luận xem sao.

Đây là 1 bài toán hình học thú vị.

[Thaistreetz 539]

9 giờ trước, Doan Van Ha cho biết:

Hỏi về thuật toán:

Trên dwg tôi có rất nhiều (hàng trăm ngàn) tam giác 3D dạng Polyline 3D closed, không cắt nhau.

Bất cứ 1 point nào trên dwg hoặc là không thuộc tam giác nào, hoặc là chỉ thuộc duy nhất 1 tam giác. Nếu point nằm trên 1 cạnh/đỉnh thì thuộc nhiều tam giác.

Nếu pịck 1 point bất kỳ, làm sao chọn được 1 tam giác bao quanh point đó?

Thuật toán phải quan tâm tốc độ xử lý nhé!

 

 

Hoi_CV.dwg

1. Bác phân mảnh ngay từ quá trình tạo lưới, Với mỗi mảnh là list gồm:

- 1 list lưu số lượng xác định số tam giác sao cho tốc độ xử lý là tối ưu nhất. 10.000 - 20.000 tam giác là ok với cấu hình máy tính của năm 2008.

- 1 list là tập hợp điểm bao chọn cái mảnh đó (là tập hơp các đỉnh của tam giác tại biên) dùng để kiểm tra điểm có thuộc mảnh hay không.

2. Gán cái list các mảnh đó vào 1 biến toàn cục tại phiên làm việc để truy cập tức thì. Khi nào đóng bản vẽ thì lưu nó vào xrecod, đến lúc mở bản vẽ, gõ lệnh thực thi, nếu chưa có biến đó thì gọi từ xrecod và lại gán vào 1 biến toàn cục để dùng.

3. Khi tra điểm, thực hiện 2 việc:

- Kiểm tra điểm đó nằm trong mảnh nào.

- Dò điểm đó thuộc tam giác nào trong mảnh thỏa mãn.

 

Cái này tôi đã từng làm và chạy trên con laptop cùi của tôi 6 năm trước với tốc độ gần như là realtime, với tập hợp 10.000 điểm đến 200.000 điểm tốc độ gần như là tương đương nhau. Nhanh hay chậm giờ tùy thuộc vào cách bác viết hàm tra 1 điểm có nằm trong 1 miền đa giác.

[Doan Van Ha 3.202]

Cám ơn bạn. Nhưng lưới đã được tạo trước, và thậm chí do ai đó tạo. Còn việc pick point lại tùy thuộc user nên không thể "thực hiện ý đồ phân mảnh lúc tạo lưới" được.

[Doan Van Ha 3.202]

14 giờ trước, DuongTrungHuy cho biết:

Nếu mình không nhầm thì đây là lưới TG Delauney. Gặp trường hợp này mình thường làm như sau:

-Tìm tâm và bán kính vòng tròn qua các TG (cần đổi về TG phẳng Z=0), tạo thành 1 cụm dữ liệu và chỉ làm 1 lần.

-Bấm điểm bất kỳ và chọn ra vòng tròn nào bao điểm đó, có thể 2,3 vòng tròn (điều kiện khỏang cách đến tâm < R)

-Kiểm tra cụ thể điểm đó sẽ nằm trong tam giác nào tương ứng với 2,3 vòng tròn đó.

Có thể nó không tối ưu lắm nhưng cũng đưa lên cùng bàn luận xem sao.

Đây là 1 bài toán hình học thú vị.

Làm vậy cũng được nhưng:

1). Phải duyệt qua tất cả tam giác >> e lâu lắm.

2). Nếu đã duyệt qua tất cả tam giác thì đâu cần tạo đường tròn làm gì, mà chỉ cần xét điểm đó nằm trong tam giác nào thôi.

[gia_bach 1.551]

9 giờ trước, Doan Van Ha cho biết:

Cám ơn bạn. Nhưng lưới đã được tạo trước, và thậm chí do ai đó tạo. Còn việc pick point lại tùy thuộc user nên không thể "thực hiện ý đồ phân mảnh lúc tạo lưới" được.

Cơ bản là thuật toán "chia để trị" như Thatstreet đã viết ở trên.

Từ 1 lưới tổng, ta chia thành nhiều lưới cấp 1 nhỏ hơn, tiếp tục chia lưới cấp 1 thành nhiều lưới cấp 2 .....

- xác định diểm đã cho nằm trong lưới cấp 1 nào:  trong hình đính kém là lưới có màu YELLOW

- trong lưới cấp 1 YELLOW, xác định đc diểm nằm trong lưới cấp 2 có màu CYAN

- trong lưới cấp 2 CYAN, xác định đc diểm nằm trong lưới cấp 3,4  hoặc lưới tam giác cơ bản.

 

Vấn đề chính là chọn số lương tam giác trong 1 lưới sao cho tối ưu nhất.

 

[DuongTrungHuy 132]

Bạn Đoàn Văn Hạ:

1) Đúng là duyệt qua các tam giác thì khá lâu.

2) Sở dĩ tạo đường tròn là để tìm nhanh hơn. Kiểm tra 1 điểm trong 1 đường tròn nhanh hơn trong tam giác.

3) Bạn cũng có thể phân lưới tam giác thành 2 tầng (theo chiều cao chẳng hạn) để duyệt nhanh hơn (giảm 1 nửa). Đúng là lúc đó ta sẽ lâu hơn vì thêm động tác phân lưới tam giác thành 2 nhưng nếu số lượng điểm pick kiểm tra điểm nhiều thì vẫn có lợi vì mỗi lần tính chỉ phân 1 lần.

[Doan Van Ha 3.202]

Tôi mới nghĩ ra thuật toán thế này. Mọi người cho nhận xét để tìm phương án tối ưu hơn:

- Zoom cho tất cả tam giác (TG) nằm trong screen.

- Qua điểm pick P tạo 2 đường vuông góc ngang (d1) và đứng (d2) trong giới hạn screen (chỉ lấy các điểm mút p1 p2 và q1 q2 chứ không cần vẽ).

- Chọn 2 tập ss1 và ss2 bằng "fence" theo p1 p2 và q1 q2.

- Lấy tập nhỏ bỏ tập lớn, ví dụ được là ss1.

- Duyệt ss1 xem TG nào chứa P thì tóm cổ hắn. Nếu không có TG nào chứa P thì P nằm ngoài tất cả TG.

Ưu điểm của pp này là chỉ xử lý trên tập ss1 (nói chung rất nhỏ so với tập toàn bộ TG là ss).

Nhược điểm là chọn fence nên nếu TG vẽ bằng nét đứt thì nguy hiểm.

Mọi người cho ý kiến thêm!

 

[timmaimotnguoi 8]

Command: (command "-TEXT "&4&","&4&","&0&"  "&123")
("_>

Mấy Bác cho e hỏi cái lỗi này là sao vậy ạ :( mò mãi ko biết được lỗi gì 

[Danh Cong 422]

10 phút trước, timmaimotnguoi cho biết:

Command: (command "-TEXT "&4&","&4&","&0&"  "&123")
("_>

Mấy Bác cho e hỏi cái lỗi này là sao vậy ạ :( mò mãi ko biết được lỗi gì 

Là lỗi đang thiếu dấu nháy kép chứ sao  Mà câu cú lệnh lisp gì be bét thế kia, không chạy được đâu bạn ơi. 

[timmaimotnguoi 8]

Ngay bây giờ, Danh Cong cho biết:

Là lỗi đang thiếu dấu nháy kép chứ sao  Mà câu cú lệnh lisp gì be bét thế kia, không chạy được đâu bạn ơi. 

Bình thường viết bên excel chỉ cần: "-TEXT "&4&","&4&","&0&"  "&123"

Như vậy là pates sang cad vào dòng command là được. Nên mình muốn có cái dòng command xem nó có được không. Mà thiếu nháy " này là ở chổ nào vậy bác :(

 

[Danh Cong 422]

34 phút trước, timmaimotnguoi cho biết:

Bình thường viết bên excel chỉ cần: "-TEXT "&4&","&4&","&0&"  "&123"

Như vậy là pates sang cad vào dòng command là được. Nên mình muốn có cái dòng command xem nó có được không. Mà thiếu nháy " này là ở chổ nào vậy bác :(

 

Bạn đang "râu ông nọ cắm  cằm bà kia" . Excel đâu phải là AutoCad.   Tham khảo bài này: http://kts-duy.blogtiengviet.net/?cat=193596

[DuongTrungHuy 132]

1 giờ trước, Doan Van Ha cho biết:

Tôi mới nghĩ ra thuật toán thế này. Mọi người cho nhận xét để tìm phương án tối ưu hơn:

- Zoom cho tất cả tam giác (TG) nằm trong screen.

- Qua điểm pick P tạo 2 đường vuông góc ngang (d1) và đứng (d2) trong giới hạn screen (chỉ lấy các điểm mút p1 p2 và q1 q2 chứ không cần vẽ).

- Chọn 2 tập ss1 và ss2 bằng "fence" theo p1 p2 và q1 q2.

- Lấy tập nhỏ bỏ tập lớn, ví dụ được là ss1.

- Duyệt ss1 xem TG nào chứa P thì tóm cổ hắn. Nếu không có TG nào chứa P thì P nằm ngoài tất cả TG.

Ưu điểm của pp này là chỉ xử lý trên tập ss1 (nói chung rất nhỏ so với tập toàn bộ TG là ss).

Nhược điểm là chọn fence nên nếu TG vẽ bằng nét đứt thì nguy hiểm.

Mọi người cho ý kiến thêm!

 

Hì... Nếu dùng Cad trợ thủ thì đây là 1 ý hay.

Nhưng nếu vẽ nét đứt thì đúng chịu vì có thể bắt được tam giác ngoài vùng, còn tam giác đang tìm thì bị "khuất" và nếu lúc này vội kết luận thì có thể không chính xác.

[ndtnv 481]

1 giờ trước, Doan Van Ha cho biết:

Tôi mới nghĩ ra thuật toán thế này. Mọi người cho nhận xét để tìm phương án tối ưu hơn:

- Zoom cho tất cả tam giác (TG) nằm trong screen.

- Qua điểm pick P tạo 2 đường vuông góc ngang (d1) và đứng (d2) trong giới hạn screen (chỉ lấy các điểm mút p1 p2 và q1 q2 chứ không cần vẽ).

- Chọn 2 tập ss1 và ss2 bằng "fence" theo p1 p2 và q1 q2.

- Lấy tập nhỏ bỏ tập lớn, ví dụ được là ss1.

- Duyệt ss1 xem TG nào chứa P thì tóm cổ hắn. Nếu không có TG nào chứa P thì P nằm ngoài tất cả TG.

Ưu điểm của pp này là chỉ xử lý trên tập ss1 (nói chung rất nhỏ so với tập toàn bộ TG là ss).

Nhược điểm là chọn fence nên nếu TG vẽ bằng nét đứt thì nguy hiểm.

Mọi người cho ý kiến thêm!

 

Sao không chọn ss2 là fence các tam giác trong ss1 hay chọn ss là giao của ss1 và ss2.

 

[Doan Van Ha 3.202]

1 phút trước, ndtnv cho biết:

Sao không chọn ss2 là fence các tam giác trong ss1 hay chọn ss là giao của ss1 và ss2.

 

Hoan hô giải pháp lấy giao của ss1 và ss2!

[tien2005 242]

Lấy phần giao ss1 và ss2 chưa chắc nhanh hơn cách kiểm trong tập nhỏ của Bạn (1 phát ăn ngay). Vì ss1 và ss2 phải duyệt qua lẫn nhau kết quả là ss sẽ có 1-2 đối tượng (theo minh hoạ của Bạn là 2) khi đó bạn mới kiểm tra point trong tập giao ss

Để hạn chế nhược điểm nét đứt của fence tại sao không dùng "C" hay "CP"

[Doan Van Ha 3.202]

5 giờ trước, tien2005 cho biết:

Lấy phần giao ss1 và ss2 chưa chắc nhanh hơn cách kiểm trong tập nhỏ của Bạn (1 phát ăn ngay). Vì ss1 và ss2 phải duyệt qua lẫn nhau kết quả là ss sẽ có 1-2 đối tượng (theo minh hoạ của Bạn là 2) khi đó bạn mới kiểm tra point trong tập giao ss

Để hạn chế nhược điểm nét đứt của fence tại sao không dùng "C" hay "CP"

Cám ơn bạn.

- Ý 1: tôi thấy cách của ndtnv tốt hơn cách của tôi. Giải thích khá dài dòng.

- Ý 2: "C" hay "CP" cũng không phải là không bị ảnh hưởng của nét đứt, còn nếu lấy C hoặc CP quá rộng thì ss sẽ lớn.

[hiepttr 538]

 

 

13 giờ trước, Doan Van Ha cho biết:

 

Nhược điểm là chọn fence nên nếu TG vẽ bằng nét đứt thì nguy hiểm.

Mọi người cho ý kiến thêm!

 

Bác có thể set LTSCALE sysvar bằng một số lớn thật lớn, xong rồi trả lại

[kstdkhang 2]

Theo mình nghĩ : duyệt qua tất cả các điểm tạo nên các tam giác đó lấy 6 đỉnh gần point nhất. Lần lượt duyệt 3 điểm trong 6 đỉnh với điều kiện tổng 3 góc 3 đỉnh đó so với point đang xét bằng 180 độ thì đó là tam giác chứa point cần tìm

[Tue_NV 3.912]

52 phút trước, hiepttr cho biết:

 

 

Bác có thể set LTSCALE sysvar bằng một số lớn thật lớn, xong rồi trả lại

 

Bài toán đang quan tâm đến tốc độ xử lý nên việc sử dụng LTSCALE sysvar là cái không khả thi ^^

[Doan Van Ha 3.202]

7 giờ trước, kstdkhang cho biết:

Theo mình nghĩ : duyệt qua tất cả các điểm tạo nên các tam giác đó lấy 6 đỉnh gần point nhất. Lần lượt duyệt 3 điểm trong 6 đỉnh với điều kiện tổng 3 góc 3 đỉnh đó so với point đang xét bằng 180 độ thì đó là tam giác chứa point cần tìm

1). Không có gì làm niềm tin để chắc chắn 6 điểm gần nhất có 3 điểm chứa point. Tại sao không phải là 5 hay 7?

2). Duyệt tất cả thì không phải là điều mong muốn rồi.

@all: bỏ qua việc xét đường hidden, đừng quan tâm nữa, vì thực tế ít vẽ như vậy.

Vấn đề cốt lõi là thuật toán về tốc độ!

[DuongTrungHuy 132]

LUẬN BÀN:

Mình nghĩ cũng không hẳn dùng Fence là không duyệt tam giác:

 

Phải chăng trong Fence thì Cad cũng phải duyệt các tam giác, có điều Cad duyệt nhanh hơn vì các đối tượng đó nó đã có địa chỉ sẵn trong máy nên truy nhanh hơn còn khi lập trình gán biến v.v... ta đã làm cho nó chậm đi.Tất nhiên vì ý của tác giả muốn tốc độ thì dùng trong môi trường Cad dùng Cad trợ thủ là tối ưu. như trong trường hợp này cũng có thể ta không tia từ trái qua phải màn hình mà chỉ tia từ trái đến điểm Pick và từ dưới đến điểm Pick cũng được

 

Chẳng hạn như mình nghĩ mỗi đối tượng trong Cad đều có 1 tên thật sự (mã DXF 5) nhưng khi mở bản vẽ thì nó sẽ cho 1 cái SYM mã -1 (-1 . <Entity name: 7eed6830>) những tên này nhớ trong bộ nhớ RAM nên truy nhập nhanh hơn là truy cập qua tên thật của nó.

 

Luận 1 ít cho vui vậy, các bạn cùng suy gẫm.

 

Cũng có 1 cách có thể nhanh chậm thì tùy ta cứ đưa lên cho phong phú: Tạo nên 1 LIST (hay mảng nếu dùng ngôn ngữ khác) chứa trọng tâm các tam gíac và lưu trữ cho lần sau. Dùng lệnh Poly để tạo nên HATCH tại điểm đó, bắt Poy tam giác và tính trọng tâm. Duyệt qua các trọng tâm tam giác nếu kc<0.0000001 thì OK

 

[kstdkhang 2]

Có thể dùng thuật toán vết dầu loang được không nhỉ

[Doan Van Ha 3.202]

1 giờ} trướ}c, kstdkhang cho biết:

Có thể dùng thuật toán vết dầu loang được không nhỉ

Vâng, có thể "loang" dần vùng chọn đối tượng từ nhỏ đến to. Nhưng nên chọn bước nhảy để loang như thế nào cho tối ưu tốc độ cũng là vấn đề khó.

[Doan Van Ha 3.202]

Hiện nay loạt bài "Hỏi về thuật toán" từ 07/11/2017 đến nay xin dừng ở đây. Lý do: với thuật toán chọn tập ss ở trên đã giải quyết bài toán gần như tức thì nên đã đạt y/c.

Cám ơn mọi người đã quan tâm.

[Thaistreetz 539]

Mình thì lại dị ứng với việc phải zoom xong trả lại screen vì đã vài lần gặp hiện tượng màn hình nháy nháy trong quá trình xử lý.

Ý tưởng của bác DVH là khá hay. Nhưng nếu áp dụng thì mình sẽ chỉ áp dụng d1 và d2 trong chính cái màn hình screen tại thời điểm lấy tọa độ điểm tra. Vừa đỡ nháy màn hình do zoom, lại vừa cho tốc độ nhanh hơn vì đối tượng chọn được ít hơn nhiều lần. tất nhiên có rủi ro về việc d1 và d2 khi đó không cắt tam giác nào do zoom quá lớn các cạnh tam giác vượt ra khỏi screen. Nhưng cái này dựa trên việc đánh giá thói quen người dùng, chẳng ai zoom vào tận trong cái tam giác khi pick cả.

 

Có lẽ đây là bài toán tra cao độ tại 1 điểm bất kỳ trên lưới tam giác bằng 1 cú pick chuột.
Còn nếu là 1 yêu cầu tra theo thời gian thực (tức là rê con trỏ tới đâu nó báo luôn cao độ tới đó) thì thế nào? Khi đó rõ ràng giải pháp phân mảnh, phân tầng vẫn cho hiệu quả tốt hơn. Nếu có chậm thì cũng chỉ chậm 1 lần duy nhất là lần đầu chạy lệnh