• Vui lòng đọc nội qui diễn đàn để tránh bị xóa bài viết
  • Tìm kiếm trước khi đặt câu hỏi

[Thảo luận] Tính diện tích đa giác bất kỳ

Đây là nơi để các bạn trao đổi về cấu trúc dữ liệu và giải thuật

Điều hành viên: Điều hành

Hình đại diện của người dùng
taykhongbatgiac
Guru
Guru
Bài viết: 84
Ngày tham gia: T.Năm 10/11/2005 2:50 pm
Đến từ: Chùa
Been thanked: 7 time

Re: [Thảo luận] Tính diện tích đa giác bất kỳ

Gửi bàigửi bởi taykhongbatgiac » T.Sáu 26/10/2012 2:54 pm

Máu thế! Đẩy lên đầu thấy mà ghê!
dazzlingvit đã viết:...
Vậy có cách cải tiến nào để vừa tăng tốc, vừa tính chính xác không?
...

Tích phân là phương pháp tính diện tích tổng quát nhất, áp dụng được cho mọi đa giác và mọi miền có giới hạn nói chung.
Tuy nhiên, nếu chỉ giới hạn trong các đa giác lồi và lõm (không tính đa giác phức hay đa giác tự cắt) thì có thể dùng "mẹo fill" thế này:
- Vẽ đa giác lên mặt phẳng toạ độ (có quy ước kích thước điểm ảnh tương ứng với độ dài d nào đó);
- Giả sử Xmin, Xmax là cực tiểu và cực đại trong tập các toạ độ X (i) các đỉnh. Xác định (bằng tính toán chứ không vẽ) các giao điểm của đường thẳng đứng x = (Xmin + Xmax)/2 với các cạnh của đa giác và sắp xếp các giao điểm theo chiều tăng hoặc giảm dần. Khi đó một điểm bất kỳ nằm giữa 2 giao điểm đầu tiên (nếu trùng nhau thì giữa 2 giao điểm tiếp theo,...) sẽ chắc chắn nằm bên trong đa giác;
- Fill đa giác từ điểm đó với màu khác màu cạnh đa giác;
- Lưu hình ảnh thành file *.BMP;
- Đọc file ảnh để tính tổng số điểm ảnh có màu fill (N1) và số điểm ảnh có màu cạnh (N2);
- Diện tích đa giác xấp xỉ d*d*(N1 + N2/2).

Nếu dùng "mẹo" này thì độ chính xác phụ thuộc vào quy ước kích thước 1 pixel, càng nhỏ thì độ chính xác càng tăng, nhưng file BMP sẽ rất lớn, lơi hại gần giống như khi lấy tích phân - dx càng nhỏ thì làm càng lâu. :)


Nhân bớt học bớt phi lý (Lê Lèo). Không chat, không messages, không mail, không offline.

Hình đại diện của người dùng
dazzlingvit
Guru
Guru
Bài viết: 960
Ngày tham gia: T.Ba 18/01/2011 10:21 am
Đến từ: Sinh ra từ hư vô, sống trong thế giới ảo...
Has thanked: 7 time
Been thanked: 112 time
Liên hệ:

Re: [Thảo luận] Tính diện tích đa giác bất kỳ

Gửi bàigửi bởi dazzlingvit » T.Sáu 26/10/2012 3:34 pm

taykhongbatgiac đã viết:Máu thế! Đẩy lên đầu thấy mà ghê!

Thấy tinh thần anh em có vẻ đi xuống, mà vấn đề thì vẫn chưa giải quyết xong, lại chưa dùng chức năng đó bao giờ nên bấm thử xem nó như thế nào :))
taykhongbatgiac đã viết:- Vẽ đa giác lên mặt phẳng toạ độ (có quy ước kích thước điểm ảnh tương ứng với độ dài d nào đó);
- Giả sử Xmin, Xmax là cực tiểu và cực đại trong tập các toạ độ X (i) các đỉnh. Xác định (bằng tính toán chứ không vẽ) các giao điểm của đường thẳng đứng x = (Xmin + Xmax)/2 với các cạnh của đa giác và sắp xếp các giao điểm theo chiều tăng hoặc giảm dần. Khi đó một điểm bất kỳ nằm giữa 2 giao điểm đầu tiên (nếu trùng nhau thì giữa 2 giao điểm tiếp theo,...) sẽ chắc chắn nằm bên trong đa giác;
- Fill đa giác từ điểm đó với màu khác màu cạnh đa giác;
- Lưu hình ảnh thành file *.BMP;
- Đọc file ảnh để tính tổng số điểm ảnh có màu fill (N1) và số điểm ảnh có màu cạnh (N2);
- Diện tích đa giác xấp xỉ d*d*(N1 + N2/2).

Mình chưa hiểu cách làm của bạn. Rốt cục bạn "tính", hay "vẽ" đây?
Dazzling V.I.T
Hãy gọi tôi là vịt :)

Hình đại diện của người dùng
taykhongbatgiac
Guru
Guru
Bài viết: 84
Ngày tham gia: T.Năm 10/11/2005 2:50 pm
Đến từ: Chùa
Been thanked: 7 time

Re: [Thảo luận] Tính diện tích đa giác bất kỳ

Gửi bàigửi bởi taykhongbatgiac » T.Sáu 26/10/2012 9:26 pm

dazzlingvit đã viết:Mình chưa hiểu cách làm của bạn. Rốt cục bạn "tính", hay "vẽ" đây?

Đã nói rồi, dùng "mẹo fill" thì có chỗ phải vẽ (tạo ranh fill), có chỗ chỉ tính (nếu vẽ thì phải fill nhiều vùng). Cái quan trọng là vẽ hay tính đều bằng chương trình, chứ không phải vừa bằng tay vừa bằng chương trình, hay thậm tệ hơn, chỉ bằng tay và calculator(!)

Nói tóm lại, ta đang bàn về lập trình tính diện tích đa giác, máy làm theo chương trình chứ không phải mắt và tay, đúng không? :))
Nhân bớt học bớt phi lý (Lê Lèo). Không chat, không messages, không mail, không offline.

Hình đại diện của người dùng
dazzlingvit
Guru
Guru
Bài viết: 960
Ngày tham gia: T.Ba 18/01/2011 10:21 am
Đến từ: Sinh ra từ hư vô, sống trong thế giới ảo...
Has thanked: 7 time
Been thanked: 112 time
Liên hệ:

Re: [Thảo luận] Tính diện tích đa giác bất kỳ

Gửi bàigửi bởi dazzlingvit » CN 28/10/2012 12:12 pm

Tất nhiên là bằng chương trình rồi, và mình phải mô tả đủ cụ thể chứ không thể nói chung chung được =))
Nếu áp dụng cách làm của bạn thì câu hỏi là:
- Vẽ như thế nào (vẽ đoạn thẳng vào một lưới điểm)?
- Fill như thế nào?
- Tính các giao điểm xong thì nó tương ứng với điểm nào trên hình vẽ?
Đó là các vấn đề cần phải mô tả cụ thể.
Mọi người tiếp tục bàn luận nhé. Gợi ý là có thuật toán tính chính xác ngon bổ rẻ nhé :)
Dazzling V.I.T
Hãy gọi tôi là vịt :)

DoremonA
Thành viên tâm huyết
Thành viên tâm huyết
Bài viết: 441
Ngày tham gia: T.Sáu 29/07/2011 1:00 pm
Has thanked: 11 time
Been thanked: 145 time

Re: [Thảo luận] Tính diện tích đa giác bất kỳ

Gửi bàigửi bởi DoremonA » T.Hai 12/11/2012 5:49 pm

Úp nào! Tham gia cho vui nhà vui cửa chút :). Có gì sai sót anh em đừng quăng tạ em nhen ^_^.
Cũng Giống như đa giác lồi tính tuần tự S tam giác (Nếu tính được thì Polygon trừ Tam giác đó đi). Bây giờ xét trường hợp S tam giác đó có cộng dồn hay hủy. Cho 1 điểm bất kỳ nằm trong Tam giác đang xét. Dùng Phương thức Ray Casting để biết nó có nằm trong Đa giác hay không? ( Đa giác chứ không phải tam giác nhen). Nếu điểm đang xét nằm trong Đa giác thì Tam giác đó có thể tính và cộng vào. Nếu không nằm trong đa giác thì không tính, nhảy qua Tam giác tiếp theo
Tóm lại: Nếu 1 điểm bất kỳ nằm trong tam giác đang xét (không nằm trên cạnh) mà nằm trong Đa giác thì Tam giác đó có thể tính diện tích để cộng vào. ngược lại thì hủy không cộng
Không biết có OKie hay không :)

duongtranhoang
Thành viên chính thức
Thành viên chính thức
Bài viết: 23
Ngày tham gia: T.Sáu 11/01/2013 12:49 am
Has thanked: 1 time

Re: [Thảo luận] Tính diện tích đa giác bất kỳ

Gửi bàigửi bởi duongtranhoang » T.Tư 20/02/2013 8:59 pm

mọi người thảo luận tiếp nào!

duongtranhoang
Thành viên chính thức
Thành viên chính thức
Bài viết: 23
Ngày tham gia: T.Sáu 11/01/2013 12:49 am
Has thanked: 1 time

Re: [Thảo luận] Tính diện tích đa giác bất kỳ

Gửi bàigửi bởi duongtranhoang » T.Tư 20/02/2013 9:01 pm

...!

duongtranhoang
Thành viên chính thức
Thành viên chính thức
Bài viết: 23
Ngày tham gia: T.Sáu 11/01/2013 12:49 am
Has thanked: 1 time

Re: [Thảo luận] Tính diện tích đa giác bất kỳ

Gửi bàigửi bởi duongtranhoang » T.Năm 21/02/2013 10:53 am

với hình bất kì có thể theo nguyên tắc:

Chia hình thành các vùng được giới hạn bằng đường đơn trị. Tích phân các vùng đó bằng cách cộng các mảnh nhỏ hình chữ nhật hoặc hình thang rồi thì cộng trừ các vùng đó.

Ví dụ hình sau:
Hình ảnh

Hình đại diện của người dùng
dazzlingvit
Guru
Guru
Bài viết: 960
Ngày tham gia: T.Ba 18/01/2011 10:21 am
Đến từ: Sinh ra từ hư vô, sống trong thế giới ảo...
Has thanked: 7 time
Been thanked: 112 time
Liên hệ:

Re: [Thảo luận] Tính diện tích đa giác bất kỳ

Gửi bàigửi bởi dazzlingvit » T.Hai 25/02/2013 12:40 am

Chúc mừng bạn @duongtranhoang đã đưa được ra cách tính tốt nhất cho trường hợp đa giác không tự cắt (lồi hoặc lõm). Với cách này chỉ cần 1 vòng lặp đơn giản là có thể tính được diện tích.
Vậy với đa giác tự cắt thì tính như thế nào? Xin mời các bạn tiếp tục thảo luận.
Dazzling V.I.T
Hãy gọi tôi là vịt :)


Quay về “Cấu trúc dữ liệu và giải thuật”

Đang trực tuyến

Đang xem chuyên mục này: Không có thành viên nào trực tuyến.1 khách