Hỏi thuật toán tạo đường đồng mức

[doanduyhung 40]

Xin cho hỏi có thuật toán nào xây dựng đường đồng mức từ 1 tập hợp điểm cao độ bất kì (hoặc tập hợp điểm theo ô lưới chử nhật) không nhỉ? Tất nhiên ko dùng đến các phần mềm như Land, Nova, AnphaGroups...

[lamtecco2 856]

Xin cho hỏi có thuật toán nào xây dựng đường đồng mức từ 1 tập hợp điểm cao độ bất kì (hoặc tập hợp điểm theo ô lưới chử nhật) không nhỉ? Tất nhiên ko dùng đến các phần mềm như Land, Nova, AnphaGroups...

Đây là một thuật toán tương đối khó , theo mình được biết người ta vẫn vẽ các đường đồng mức theo phương pháp tích phân . Từ các điểm có toạ độ và cao độ người ta xây dựng lên một hệ thống lưới đa giác nội suy rồi từ đó tính ra các điểm có cùng cao độ để nối thành các đường đồng mức.

[anhcos 196]

Để tạo đường đồng mức bạn thử xem cách này:

 

Với 1 tập điểm đã cho, bạn hãy chưa quan tâm đến cao độ z.

 

Đi qua 2 bước:

 

* Bước 1: Xây dựng lưới tam giác:

 

- Tìm điểm nằm ngoài cùng nhất (có x, và Y nhỏ nhất or ngược lại)

- Từ điểm đó tìm 2 điểm gần nhất để hình thành 1 tam giác đầu tiên

- Lúc này đường bao sẽ phát triển thành 3 đường (là 3 cạnh của tam giác)

- Duyệt qua từng đoạn của đường bao, tìm điểm gần nhất với đoạn này để tạo thêm 1 tam giác mới

Đường bao mới sẽ được hình thành từ đường bao cũ kết hợp với đường bao mới và loại bỏ đường bao đang xét

Tuy nhiên sẽ có một số ngoại lệ mà bạn phải tự tìm hiểu lấy.

Quá trình này sẽ rất làm rất lâu nếu bạn không có thuật toán tìm kiếm hiệu quả.

 

* Bước 2: tạo đường đồng mức.

Từ tập điểm ta có Zmin và Zmax

Cho Z chạy từ Zmin --> Zmax để cắt từng đường của lưới tam giác đã tạo ở trên.

 

Nói chung là bạn sẽ mất rất nhiều thời gian để hoàn tất công việc này đấy.

[Nguyen Hoanh 4.663]

* Bước 1: Xây dựng lưới tam giác:

 

- Tìm điểm nằm ngoài cùng nhất (có x, và Y nhỏ nhất or ngược lại)

- Từ điểm đó tìm 2 điểm gần nhất để hình thành 1 tam giác đầu tiên

- Lúc này đường bao sẽ phát triển thành 3 đường (là 3 cạnh của tam giác)

- Duyệt qua từng đoạn của đường bao, tìm điểm gần nhất với đoạn này để tạo thêm 1 tam giác mới

Đường bao mới sẽ được hình thành từ đường bao cũ kết hợp với đường bao mới và loại bỏ đường bao đang xét

Tuy nhiên sẽ có một số ngoại lệ mà bạn phải tự tìm hiểu lấy.

Quá trình này sẽ rất làm rất lâu nếu bạn không có thuật toán tìm kiếm hiệu quả.

Trước đây tôi đã thử cách này.

Ưu điểm của nó là thuật toán đơn giản, dễ tối ưu hóa để có được thời gian thực thi nhanh (có thể tối ưu để đạt được độ phức tạp là N*ln(N) khi thực hiện chia để trị). Nhược điểm là tạo ra quá nhiều tam giác tù dẫn đến kết quả nội suy sau này có sai số lớn.

[lucton 0]

Trước đây tôi đã thử cách này.

Ưu điểm của nó là thuật toán đơn giản, dễ tối ưu hóa để có được thời gian thực thi nhanh (có thể tối ưu để đạt được độ phức tạp là N*ln(N) khi thực hiện chia để trị). Nhược điểm là tạo ra quá nhiều tam giác tù dẫn đến kết quả nội suy sau này có sai số lớn.

Bạn dùng thuật toán Trianglation gì đó

trước đây mình đã dùng để vẽ biểu đồ màu và đường đồng ứng suất từ file *.OUT của Sap

Thuật toán chia lưới tam giác của nó cực hay

[se7en 5]

Để xây dựng đường đồng mức, thì trước tiên bạn fải xây dựng được mô hình TIN, thuật toán xây dựng mô hình TIN có rất nhiều, thừơng sử dụng nhất là xây dựng hệ thống lưới tam giác Delauney. Sau đó bạn có thể dựa trên hệ thống này để nội suy ra các điểm có cùng cao độ, tập hợp các điểm cùng độ cao sẽ cho ra 1 đường đồng mức. Nói chung thuật toán tương đối phức tạp.