Chuyển đến nội dung
Diễn đàn CADViet
Học AutoCAD Online cùng CADViet
Jin Yong

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

Các bài được khuyến nghị

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

Hoi_CV.png

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác

Nếu bạn chỉ quan tâm kết quả (để đi tiếp giải quyết vấn đề tiếp theo) thôi thi có hàm:

dos_isinsidecurve

Verifies a point lies inside of a closed, planar curve.

Trong DOS_LIB đó bạn.

  • Like 1

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác
Ngay bây giờ, DuongTrungHuy cho biết:

Nếu bạn chỉ quan tâm kết quả (để đi tiếp giải quyết vấn đề tiếp theo) thôi thi có hàm:

dos_isinsidecurve

Verifies a point lies inside of a closed, planar curve.

Trong DOS_LIB đó bạn.

Cám ơn bạn (like)! Mình biết DOS_LIB nhưng không ưa dùng. Với lại vì không đọc được code nên không biết liệu tốc độ xử lý có tốt không.

Mình đang quan tâm tới thuật toán, như đã nói ở trên.

 

  • Like 1

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác

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ị.

  • Like 1

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác
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

Hoi_CV.png

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.

  • Like 1

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác

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.

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác
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.

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác
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.

 

Delauney.png

  • Like 1

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác

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.

  • Like 1

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác

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!

 

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác
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. :,D

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác
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. :,D

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 :(

 

  • Vote giảm 1

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác
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

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác
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.

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác
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.

 

  • Like 1

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác
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!

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác

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"

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác
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.

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác

 

 

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

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác

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

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác
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 ^^

  • Like 1

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác
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 độ!

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác

Tạo một tài khoản hoặc đăng nhập để nhận xét

Bạn cần phải là một thành viên để lại một bình luận

Tạo tài khoản

Đăng ký một tài khoản mới trong cộng đồng của chúng tôi. Điều đó dễ mà.

Đăng ký tài khoản mới

Đăng nhập

Bạn có sẵn sàng để tạo một tài khoản ? Đăng nhập tại đây.

Đăng nhập ngay


×