Nội suy cao độ bằng thuật toán tam giác Delaunay?

[redsea_tq 16]

Chào các bác trên diễn đàn!

em đang hoàn thiện nốt một ứng dụng nhỏ có liên quan đến nội suy cao độ và đang dùng thuật toán Delaunay, có đọc tài liệu bằng tiếng Việt và cũng hiểu sơ qua về thuật toán. xong do trình độ có hạn nên vẫn còn nhiều chỗ chưa hiểu. Kính mong trên diễn đàn nếu ai biết thuật toán này thỉ chỉ giúp em, em xin chân thành cám ơn!

[anhcos 196]

Link này có thể hữu ích cho bạn.

[redsea_tq 16]

Link này có thể hữu ích cho bạn.

Cám ơn bạn Anhcos, thuật toán của mình có thể khái quát như sau:

-tạo pline kín bao quanh hệ thống điểm cần tạo lưới tam giác.

-từ một cạnh bất kỳ nào đó của pline, tìm thêm một điểm trong hệ thống điểm ban đầu tạo với cạnh pline thành một tam giác thoả mãn điều kiện denaulay.

-lặp lại...

vướng mắc của mình là lặp lại đến khi nào? Nếu lặp lại cho đến khi số cạnh đường bao <3 thì sẽ có trường hợp lưới tam giác phát triển thẳng đứng chia đôi tập hợp điểm ra làm 2 phần => sẽ có một phần không tạo được mạng tam giác(cái này mình đang suy nghĩ, chưa làm nên không biết có đúng không)

Thuật toán của mình như vậy không biết có đúng không, mong diễn đàn chỉ giúp!

[anhcos 196]

Nếu lặp lại cho đến khi số cạnh đường bao <3 thì sẽ có trường hợp lưới tam giác phát triển thẳng đứng chia đôi tập hợp điểm ra làm 2 phần => sẽ có một phần không tạo được mạng tam giác(cái này mình đang suy nghĩ, chưa làm nên không biết có đúng không)

Thuật toán của mình như vậy không biết có đúng không, mong diễn đàn chỉ giúp!

 

Đoạn màu đỏ mình vẫn chưa hiểu ý lắm.

Bạn có thể post lên vài hình liên quan xem sao.

[DuongTrungHuy 128]

Thuật toán của mình như vậy không biết có đúng không, mong diễn đàn chỉ giúp!

Theo Mình hiểu thì đây là 1 bài toán lớn chứ không nhỏ như Bạn nghĩ. Nó là bài toán cốt lõi trong các phần mềm vẽ bình đồ.

Về giải thuật Bạn có thể theo hướng này xem sao!

- Đầu tiên tìm 4 điểm đặc biệt ngoài tập điểm đã có, thông thường là 4 điểm xmin,xmax,ymin,ymax.

- Từ 4 điểm "cực trị" đó Bạn lấy 1 điểm bất kỳ trong tập đã có để tạo nên lưới tam giác đầu tiên T.

- Xét 1 điểm P tiếp theo. Bạn tháo các tam giác trong tập T đã tạo ở trên mà nếu có điểm P này thì không thoả điều kiện Delaunay các tam giác này gọi là tập T1 và tập T sau khi xóa bớt là T2.

- Tìm biên bao lồi của tập T1 này.

- Thêm vào tập T2 1 lưới tam giac mới là các tam giác tạo ra từ biên bao lồi trên và điểm P, và ta có tập T mới

- Làm liên tục đến khi hết các điểm trong tập điểm đã cho thì thôi.

Nó hơi dài dòng Mình diễn đạt như vậy Bạn xem thử có giúp ích được gì không!

 

 

TB. Để nội suy cao độ cũng có nhiều giải pháp khác. Nếu được, Bạn đưa 1 số điểm cao độ lên để Mình tham khảo thêm, chứ dùng Delauney chỉ để nội suy thì hơi phức tạp.

Good Luck!

[redsea_tq 16]

Cám ơn bạn Huy va Anhcos, mình đang tiếp tục nghiên cứu để hoàn thiện, khi nào hòm hòm thì mình sẽ post lên mong mọi người giúp! Hiện tại mình cũng đã nội suy được rồi nhưng còn một số điểm rơi vào vùng chết do thuật toán của mình là tìm 1 tam giác bao điểm đó chứ không phải tạo ra mạng tam giác. đơn giản hơn nhưng thiếu chính xác. Chúc mọi người cuối năm vui vẻ!