Đến nội dung


Hình ảnh
- - - - -

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


  • Please log in to reply
13 replies to this topic

#1 qdzung

qdzung

    biết zoom

  • Members
  • Pip
  • 13 Bài viết
Điểm đánh giá: 0 (bình thường)

Đã gửi 15 August 2012 - 04:00 PM

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ình đã gửi
  • 0

#2 phamthanhbinh

phamthanhbinh

    biết lệnh adcenter

  • Moderator
  • PipPipPipPipPipPipPip
  • 6009 Bài viết
Điểm đánh giá: 3113 (tuyệt vời)

Đã gửi 15 August 2012 - 04:55 PM

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 ạ.
  • 0
Chúc các quý Anh trên diễn đàn luôn khỏe, đẻ thêm được nhiều thứ để mót.

#3 qdzung

qdzung

    biết zoom

  • Members
  • Pip
  • 13 Bài viết
Điểm đánh giá: 0 (bình thường)

Đã gửi 15 August 2012 - 05:21 PM

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

  • 0

#4 Nguyen Hoanh

Nguyen Hoanh

    biết lệnh adcenter

  • Moderator
  • PipPipPipPipPipPipPip
  • 4106 Bài viết
Điểm đánh giá: 4495 (đỉnh cao)

Đã gửi 15 August 2012 - 06:22 PM

Đâ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.
  • 0

#5 qdzung

qdzung

    biết zoom

  • Members
  • Pip
  • 13 Bài viết
Điểm đánh giá: 0 (bình thường)

Đã gửi 15 August 2012 - 08:26 PM

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?
  • 0

#6 Nguyen Hoanh

Nguyen Hoanh

    biết lệnh adcenter

  • Moderator
  • PipPipPipPipPipPipPip
  • 4106 Bài viết
Điểm đánh giá: 4495 (đỉnh cao)

Đã gửi 15 August 2012 - 10:44 PM

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.
  • 0

#7 qdzung

qdzung

    biết zoom

  • Members
  • Pip
  • 13 Bài viết
Điểm đánh giá: 0 (bình thường)

Đã gửi 15 August 2012 - 10:52 PM

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
  • 0

#8 anhcos

anhcos

    biết lệnh hatchedit

  • Advance Member
  • PipPipPipPip
  • 260 Bài viết
Điểm đánh giá: 170 (tàm tạm)

Đã gửi 16 August 2012 - 08:44 AM

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.
  • 0
Clear sky!

MF Rock collection.

#9 qdzung

qdzung

    biết zoom

  • Members
  • Pip
  • 13 Bài viết
Điểm đánh giá: 0 (bình thường)

Đã gửi 16 August 2012 - 12:41 PM

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

  • 0

#10 phamthanhbinh

phamthanhbinh

    biết lệnh adcenter

  • Moderator
  • PipPipPipPipPipPipPip
  • 6009 Bài viết
Điểm đánh giá: 3113 (tuyệt vời)

Đã gửi 17 August 2012 - 10:32 AM

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ề,...
  • 0
Chúc các quý Anh trên diễn đàn luôn khỏe, đẻ thêm được nhiều thứ để mót.

#11 Doan Van Ha

Doan Van Ha

    biết lệnh adcenter

  • CADViet Team
  • PipPipPipPipPipPipPip
  • 5454 Bài viết
Điểm đánh giá: 2626 (tuyệt vời)

Đã gửi 17 August 2012 - 10:45 AM

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).
  • 0

* Chỉ nên yêu cầu Lisp khi bạn làm việc đó mất cả ngày nhưng họ chỉ viết 1 giờ. Đừng nêu yêu cầu Lisp khi bạn chỉ làm 1 giờ nhưng bắt họ phải mất cả ngày.

* Nhờ viết lisp cũng như đi khám bệnh. Chỉ gởi căn cước và than sắp chết thì không bác sỹ nào cứu sống được.


#12 phamthanhbinh

phamthanhbinh

    biết lệnh adcenter

  • Moderator
  • PipPipPipPipPipPipPip
  • 6009 Bài viết
Điểm đánh giá: 3113 (tuyệt vời)

Đã gửi 17 August 2012 - 11:03 AM

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 ạ.
  • 0
Chúc các quý Anh trên diễn đàn luôn khỏe, đẻ thêm được nhiều thứ để mót.

#13 Doan Van Ha

Doan Van Ha

    biết lệnh adcenter

  • CADViet Team
  • PipPipPipPipPipPipPip
  • 5454 Bài viết
Điểm đánh giá: 2626 (tuyệt vời)

Đã gửi 17 August 2012 - 11:12 AM

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 à.
  • 1

* Chỉ nên yêu cầu Lisp khi bạn làm việc đó mất cả ngày nhưng họ chỉ viết 1 giờ. Đừng nêu yêu cầu Lisp khi bạn chỉ làm 1 giờ nhưng bắt họ phải mất cả ngày.

* Nhờ viết lisp cũng như đi khám bệnh. Chỉ gởi căn cước và than sắp chết thì không bác sỹ nào cứu sống được.


#14 qdzung

qdzung

    biết zoom

  • Members
  • Pip
  • 13 Bài viết
Điểm đánh giá: 0 (bình thường)

Đã gửi 17 August 2012 - 01:07 PM

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
  • 0