[help] Tìm đuờng nối giữa các block qua các đoạn rẽ nhánh

[qdzung 0]

Xin chào mọi nguời,

 

Mình cần mọi nguời giúp tư vấn để giải quyết bài toán sau:

 

Có các block trên bản vẽ, đuợc nối với nhau bằng các đoạn rẽ nhánh như hình. Mình viết ứng dụng để bóc tách chiều dài các đoạn cáp chạy từ các hộ riêng biệt, đi chung trên một máng cáp.

 

Mình cần tư vấn thuật toán (và nếu có sample code thì tuyệt :D) để tính toán độ dài đuờng nối giữa các block thông qua các đoạn rẽ nhánh.

Ví dụ tính chiều dài đuờng dẫn nối giữa Block 1 và Block B, giữa Block 2 tới Block A, từ Block A tới Block C.

 

Hiện tại mình đang nghiên cứu thuộc tính IntersectWith để kiểm tra việc giao nhau của các đoạn thẳng, qua đó tìm đừong đi, nhưng vẫn chưa có kết quả.

Mong mọi nguời tư vấn giúp.

 

 

[phamthanhbinh 3.146]

Xin chào mọi nguời,

 

Mình cần mọi nguời giúp tư vấn để giải quyết bài toán sau:

 

Có các block trên bản vẽ, đuợc nối với nhau bằng các đoạn rẽ nhánh như hình. Mình viết ứng dụng để bóc tách chiều dài các đoạn cáp chạy từ các hộ riêng biệt, đi chung trên một máng cáp.

 

Mình cần tư vấn thuật toán (và nếu có sample code thì tuyệt :D) để tính toán độ dài đuờng nối giữa các block thông qua các đoạn rẽ nhánh.

Ví dụ tính chiều dài đuờng dẫn nối giữa Block 1 và Block B, giữa Block 2 tới Block A, từ Block A tới Block C.

 

Hiện tại mình đang nghiên cứu thuộc tính IntersectWith để kiểm tra việc giao nhau của các đoạn thẳng, qua đó tìm đừong đi, nhưng vẫn chưa có kết quả.

Mong mọi nguời tư vấn giúp.

Hề hề hề,

Bạn hãy gửi bản vẽ cụ thể lên mới có thể xem và có cách giải quyết được bạn ạ.

Hình ảnh bạn gửi chưa thể hiện được các thuộc tính của đối tượng nên rất khó hình dung cách làm.

Theo thiển ý cá nhân, nếu bạn biết tổ chức bản vẽ sao cho các line nối có cùng thuộc tính thì vấn đề sẽ dễ dàng hơn nhiều bạn ạ.

[qdzung 0]

Hề hề hề,

Bạn hãy gửi bản vẽ cụ thể lên mới có thể xem và có cách giải quyết được bạn ạ.

Hình ảnh bạn gửi chưa thể hiện được các thuộc tính của đối tượng nên rất khó hình dung cách làm.

Theo thiển ý cá nhân, nếu bạn biết tổ chức bản vẽ sao cho các line nối có cùng thuộc tính thì vấn đề sẽ dễ dàng hơn nhiều bạn ạ.

 

Cám ơn bác Bình đã quan tâm,

 

Em gửi bản mẫu như file đính kèm.

 

Tất cả các LINE nối khi gặp rẽ nhánh đều phải break để tìm đuờng.

 

Vấn đề khó là "Tìm được đuờng đi", nghĩa là làm sao tìm đuợc từ Block 1 tới Block A sẽ phải đi qua những đoạn LINE nào, khi đó bóc tách chiều dài từ các line này sẽ giải quyết đuợc bài toán.

Mong bác advise thêm :D Từ hôm đến giờ bí quá, ko sáng ra đuợc ý gì cả.

tạm thời phuơng thức chọn block là bằng tay, tuy nhiên với số luợng lớn chắc phải add thêm Xdata bác ah

http://www.cadviet.c...1227_sample.dwg

[Nguyen Hoanh 4.663]

Đây là bài toán tìm đường ngắn nhất đơn giản mà.

 

Bạn hãy sử dụng thuật toán Floyd để tìm đường ngắn nhất nối hai nhà. Hãy search trên google thêm về thuật toán này.

 

Về cơ bản, thuật toán này dựa trên nguyên tắc sau:

Nếu các đỉnh d1, d2, d3..dn là trung gian nối giữa A và B theo con đường ngắn nhất. Thì:

A-d1 là đường đi ngắn nhất từ A đến d1. và d1-d2-..dn-B là đường đi ngắn nhất từ d1 tới B.

 

Sau khi sử dung thuật toán Floyd, ta sẽ có một ma trận 2 chiều Mxy trong đó:

M[A,B] = d1;

M[d1,B]=d2;

M[d2,B]=d3;

...

M[dn-1,B]=dn;

 

Nói một cách tổng quát, Sau khi sử dụng thuật toán Floyd, nếu M[i,j] = k có nghĩa là đỉnh kế tiếp cần đến trên con đường ngắn nhất từ i đến j là k.

[qdzung 0]

Anh Hoanh có thể chỉ giúp em được ko? Vấn đề là em chưa biết lấy event gì để tìm đường đi ngắn nhất cả.

 

Từ một Block ban đầu, làm sao để "tìm được đường" đi qua các LINE để tới block tiếp theo được anh?

[Nguyen Hoanh 4.663]

Nếu bạn tư duy 'Từ một Block ban đầu, làm sao để "tìm được đường" đi qua các LINE để tới block tiếp theo' thì vấn đề sẽ dẫm chân tại chỗ và bế tắc.

 

Bạn nên tách riêng bài toán thành 2 phần.

 

Phần 1: Mô hình hóa line và block thành một mảng 2 chiều chứa mối liên hệ giữa cách đỉnh với nhau. Đỉnh là đầu mút của 1 line (sẽ là 1 block hoặc 1 điểm giao 2 line).

Phần 2: Xử lý tính toán trên mảng 2 chiều (còn gọi là ma trận) này bằng thuật toán Floyd, sau đó cập nhật lại mô hình ở Phần 1.

[qdzung 0]

Nếu bạn tư duy 'Từ một Block ban đầu, làm sao để "tìm được đường" đi qua các LINE để tới block tiếp theo' thì vấn đề sẽ dẫm chân tại chỗ và bế tắc.

 

Bạn nên tách riêng bài toán thành 2 phần.

 

Phần 1: Mô hình hóa line và block thành một mảng 2 chiều chứa mối liên hệ giữa cách đỉnh với nhau. Đỉnh là đầu mút của 1 line (sẽ là 1 block hoặc 1 điểm giao 2 line).

Phần 2: Xử lý tính toán trên mảng 2 chiều (còn gọi là ma trận) này bằng thuật toán Floyd, sau đó cập nhật lại mô hình ở Phần 1.

hi,

cám ơn anh nhiều lắm. Nhờ hướng dẫn của bác bài toán của em trở nên nhẹ nhàng hơn

Khi nào hoàn thành sẽ nhờ anh góp ý thêm :D

[anhcos 196]

Bài này kiểu như lý thuyết đồ thị và tìm đường đi ngắn nhất, khi mô hình hóa các line thành một cây, ta có thể tìm đường đi từ node này đến node khác.

Trước đây tôi toàn dùng kiểu con trỏ, rất dễ làm, mà giờ nếu sử dụng họ Visual basic thì phải triển khai dữ liệu kiểu khác.

[qdzung 0]

mình tìm đuợc đoạn lisp này đúng yêu cầu cần tìm. Mọi nguời có thể giải thích thêm vào đuợc ko ah? em ko có kinh nghiệm về lsp nhiều lắm.

 

http://www.cadviet.c...31227_test2.lsp

[phamthanhbinh 3.146]

mình tìm đuợc đoạn lisp này đúng yêu cầu cần tìm. Mọi nguời có thể giải thích thêm vào đuợc ko ah? em ko có kinh nghiệm về lsp nhiều lắm.

 

http://www.cadviet.c...31227_test2.lsp

Hề hề hề,

Cám ơn bạn về cái lisp này.

Tuy nhiên sau khi test thử vài trường hợp thì mình nhận thấy nó chỉ đúng trong một số trường hợp đường phân nhánh đơn giản. Với nững trường hợp phức tạp hơn như tại một nút có hai hay nhiều đường tới thì lisp tính hơi loạn và không hẳn đã trả về tuyến ngắn nhất.

Theo mình đọc thử cái lisp thì hình như nó không dùng thuật toán floyd như bác hoành đã mô tả.

Việc mần mò kỹ nó mình chưa làm được do chưa có nhiều thời gian để ngâm.

Hề hề hề,...

[Doan Van Ha 3.180]

Bác PTB!

Lisp đó chỉ tính và chỉ ra 1 tuyến nối đầu và cuối thôi. Còn nó không tìm được tuyến ngắn nhất (trong lisp đã chú thích điều này).

[phamthanhbinh 3.146]

Bác PTB!

Lisp đó chỉ tính và chỉ ra 1 tuyến nối đầu và cuối thôi. Còn nó không tìm được tuyến ngắn nhất (trong lisp đã chú thích điều này).

Hề hề hề,

Có khi nó còn trả ra tới hai ba tuyến lận bác ạ.

[Doan Van Ha 3.180]

Nhìn code thì tôi nghĩ là nó chỉ trả về 1 tuyến duy nhất. Mặc dầu tuyến này nó đi ngoằn nghoèo, nhiều khi dòm thấy như là vài ba tuyến. Bác thử delete theo thứ tự các phần tử của tập chọn xem có đúng là 1 hay nhiều tuyến. Tôi không có bản vẽ để ra nhiều tuyến nên không test được bác à.

[qdzung 0]

Hề hề hề,

Cám ơn bạn về cái lisp này.

Tuy nhiên sau khi test thử vài trường hợp thì mình nhận thấy nó chỉ đúng trong một số trường hợp đường phân nhánh đơn giản. Với nững trường hợp phức tạp hơn như tại một nút có hai hay nhiều đường tới thì lisp tính hơi loạn và không hẳn đã trả về tuyến ngắn nhất.

Theo mình đọc thử cái lisp thì hình như nó không dùng thuật toán floyd như bác hoành đã mô tả.

Việc mần mò kỹ nó mình chưa làm được do chưa có nhiều thời gian để ngâm.

Hề hề hề,...

bản thân lsp cũng chú thích là chỉ để tìm đuờng bác ah, nhưng cái hay là họ dùng một biết fuzz căn khoảng để bắt điểm.

Mình luời học lsp quá :D vì làm trên cả excel với cad nên cứ dùng vba thôi