• 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
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ệ:

[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.Bảy 20/10/2012 11:41 pm

Bài toán: tính diện tích đa giác (lồi lõm) biết toạ độ các đỉnh.
Nào, mọi người cùng thảo luận. Hãy đưa ra giải pháp của mình và giải thích nhé ;)


Dazzling V.I.T
Hãy gọi tôi là vịt :)

Hình đại diện của người dùng
VuVanHoanh
Thành viên danh dự
Thành viên danh dự
Bài viết: 1259
Ngày tham gia: T.Năm 03/06/2010 9:23 pm
Đến từ: Kim Sơn - Đông Triều - Quảng Ninh
Has thanked: 22 time
Been thanked: 137 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 VuVanHoanh » CN 21/10/2012 9:11 am

ý tưởng: chia thành các tam giác rồi tính theo công thức Hê rông.
Since 2008...
One love! :x

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 21/10/2012 11:20 am

Vậy câu hỏi là: chia như thế nào? Mình làm tay thì được, chứ với máy tính phải có một quy tắc chia thì máy nó mới làm được :)
Dazzling V.I.T
Hãy gọi tôi là vịt :)

Hình đại diện của người dùng
alexanderdna
Guru
Guru
Bài viết: 214
Ngày tham gia: T.Ba 14/07/2009 11:13 am
Đến từ: Sài Gòn
Has thanked: 3 time
Been thanked: 15 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 alexanderdna » CN 21/10/2012 11:50 am

Nếu giới hạn trong dạng đa giác lồi, có thể tính theo giải thuật sau:

Ví dụ cho đa giác lồi ABCDEF.
1. Kẻ đường thẳng AC, tức là bỏ qua đỉnh B. Ta được tam giác ABC và còn đa giác ACDEF.
2. Tiếp tục bỏ đỉnh thứ 2 trong dãy đỉnh, kẻ đường thẳng AD. Ta có tam giác ACD và đa giác ADEF.
3. Kẻ đường thẳng AE, ta được tam giác ADE và còn đa giác AEF nay cũng là một tam giác.
4. Tính diện tích các tam giác đã có và cộng ra diện tích của ABCDEF.

Rút ra nguyên tắc: tạo tam giác từ 3 đỉnh đầu tiên, thực hiện tương tự với đa giác còn lại cho tới khi đa giác chỉ còn là tam giác.

Đa giác lõm thì... hạ hồi phân giải.

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 21/10/2012 12:44 pm

Tuyệt (chính xác hơn là thực hiện thuật toán cho đến khi đa giác chỉ còn là đoạn thẳng).
Đây là một cách khá tự nhiên và hiệu quả. Vậy:
1. Xử lý đa giác lõm như thế nào?
2. Hoặc có phương pháp nào khác không?
Xin mời mọi người tiếp tục thảo luận \:D/
Dazzling V.I.T
Hãy gọi tôi là vịt :)

Hình đại diện của người dùng
bangnhatquang68
Guru
Guru
Bài viết: 791
Ngày tham gia: T.Ba 26/01/2010 12:44 pm
Đến từ: Vĩ tuyến 17
Has thanked: 20 time
Been thanked: 37 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 bangnhatquang68 » CN 21/10/2012 1:01 pm

:D
Nếu có tọa độ thì tính tích phân vùng của nó :D
Mời anh em lên facebook giao lưu nào!
http://www.facebook.com/groups/145823032176611/

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 21/10/2012 1:35 pm

Tất cả các đỉnh đều biết toạ độ. Cụ thể thì tính tích phân vùng như thế nào? Làm thế nào để chia vùng và tính chính xác tích phân?
Dazzling V.I.T
Hãy gọi tôi là vịt :)

manhtienit
Thành viên tích cực
Thành viên tích cực
Bài viết: 120
Ngày tham gia: T.Sáu 13/05/2011 9:56 am
Has thanked: 2 time
Been thanked: 9 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 manhtienit » T.Hai 22/10/2012 11:54 am

Cho mình có ý kiến 1 chút. Có đếm được số điểm ảnh phía trong của đa giác đó không? Và nếu đếm được thì từ đó suy ra diện tích được không?
Đó là ý tưởng tức thời đừng ném đá 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 22/10/2012 8:04 pm

Hoàn toàn có thể đếm được, ví dụ bạn có thể kẻ một đường nằm ngang và xác định tất cả các giao điểm với các cạnh. Tuy nhiên đếm số điểm thì không suy ra diện tích được. Nhưng mình nghĩ ý tưởng này của bạn khá thú vị, nó đã đưa ra một bài toán hoàn toàn mới: làm thế nào để đếm được số điểm (có toạ độ nguyên) trong một đa giác :)
Dazzling V.I.T
Hãy gọi tôi là vịt :)

manhtienit
Thành viên tích cực
Thành viên tích cực
Bài viết: 120
Ngày tham gia: T.Sáu 13/05/2011 9:56 am
Has thanked: 2 time
Been thanked: 9 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 manhtienit » T.Hai 22/10/2012 9:46 pm

Sau khi nêu ra ý tưởng mà không biết anh Vịt khen hay chê, thì em có lên google hỏi thì thấy cái này tuy chưa đọc hết và cũng chẳng biết code, em hơi bị mít đặc về vấn đề đồ họa thì tìm thấy cái này nằm trong câu lạc bộ của chúng ta.
http://www.caulacbovb.com/forum/viewtopic.php?f=8&t=20721&p=115058&hilit=%C4%91%E1%BA%BFm+s%E1%BB%91+%C4%91i%E1%BB%83m+%E1%BA%A3nh#p115058

manhtienit
Thành viên tích cực
Thành viên tích cực
Bài viết: 120
Ngày tham gia: T.Sáu 13/05/2011 9:56 am
Has thanked: 2 time
Been thanked: 9 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 manhtienit » T.Hai 22/10/2012 9:54 pm

cái ý tưởng đó xuất phát từ suy nghĩ số điểm cũng chính là số đơn vị diện tích. kiểu như 1km vuông thì có 10000m vuông. Nếu đếm thành công chung ta có thể tính trong 1 đơn vị diện tích chuẩn nào nó có bao nhiêu điểm và tính tỷ lệ.hihihi
Sửa lần cuối bởi manhtienit vào ngày T.Ba 23/10/2012 10:37 pm với 1 lần sửa.

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 22/10/2012 10:09 pm

Ý tưởng của bạn mở ra một hướng mới cho bài toán tính diện tích của chúng ta: tính gần đúng. Bằng cách nào đó chia mặt phẳng của ta đang xét thành những hình vuông đơn vị đủ nhỏ để tính được diện tích đủ chính xác bằng cách đến số hình vuông nằm trong đa giác (hoặc bất kỳ một miền được giới hạn nào khác). Tuyệt :)
Mọi người cùng tiếp tục thảo luận nào.
Dazzling V.I.T
Hãy gọi tôi là vịt :)

manhtienit
Thành viên tích cực
Thành viên tích cực
Bài viết: 120
Ngày tham gia: T.Sáu 13/05/2011 9:56 am
Has thanked: 2 time
Been thanked: 9 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 manhtienit » T.Hai 22/10/2012 10:19 pm

éc như vậy mà gần đúng thôi ah?Anh đưa ra cách đếm số giao điểm của đường nẳm ngang với các cạnh hình như là không hợp lý.Và cách của em ko phải chia nhỏ đa giác thành ô vuông nếu chia nhỏ được dễ dàng thì tính diện tích tam giac như trên còn khả quan hơn.ý của e là tính số điểm ảnh trong đa giác, và tính số điểm ảnh trong 1 đơn vị diện tích và nhân tỷ lệ anh ah.

Hình đại diện của người dùng
alexanderdna
Guru
Guru
Bài viết: 214
Ngày tham gia: T.Ba 14/07/2009 11:13 am
Đến từ: Sài Gòn
Has thanked: 3 time
Been thanked: 15 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 alexanderdna » T.Hai 22/10/2012 11:17 pm

Cách của manhtienit rất là độc đáo và khai sáng, khiến mình nhớ ra mình từng dùng cách này trong một bài toán tương tự. Đó là tính diện tích của một quốc đảo dựa trên ảnh bản đồ trắng đen (màu trắng cho đất và đen cho biển). Kỹ thuật của mình lúc bấy giờ là sử dụng WinAPI GetPixel để xác định màu của điểm ảnh rồi đếm.

Với bài toán hiện tại, có thể dùng một số hàm để vẽ đa giác rồi đếm điểm ảnh từ kết quả. Mình đoán mọi thao tác có thể được thực hiện trong bộ nhớ mà không nhất thiết phải vẽ ảnh ra màn hình. Tất nhiên lúc đó không dùng GetPixel nữa, mà là một hàm tương đương cho ảnh trong bộ nhớ. Kỹ thuật này lệ thuộc vào framework.

Quay lại với cách tính đã nêu ở bài trước. Đối với đa giác lõm, khi tính tổng diện tích, ta sẽ trừ đi (tức cộng với số đối) diện tích của phần tam giác có chứa đỉnh lõm, thay vì cộng. Nhưng vấn đề nảy sinh là làm cách nào xác định một đỉnh của đa giác là lồi hay lõm?

manhtienit
Thành viên tích cực
Thành viên tích cực
Bài viết: 120
Ngày tham gia: T.Sáu 13/05/2011 9:56 am
Has thanked: 2 time
Been thanked: 9 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 manhtienit » T.Hai 22/10/2012 11:50 pm

Mình có để 1 link ngay trong diễn dàn về tính số điểm ảnh của 1 vùng có màu đỏ rồi đó mà.Đúng như anh Vịt nói cách đếm số điểm ảnh này giải quyết được trong mọi vùng được giới hạn, khép kín (lồi lõm cung).
Còn về xác định đỉnh lồi lõm mình có cách này ko biết có hợp lý không nhưng cũng xin đưa ra để lấy ý kiến góp ý thêm.1 đa giác lõm ít nhất có 4 đỉnh, nếu đã biết trước các tọa độ thì mình xác định 4 điểm: Cao nhất, Phải nhất, Dưới nhất, Trái nhất. Bước đầu tiên mình xác định được đường thẳng nối 2 đỉnh Cao nhất và Phải nhất, Vậy nếu trong các đỉnh còn lại (trừ 4 đỉnh trên) nằm dưới đường thẳng này thì đỉnh đó lõm.
Tương tự cho các đỉnh còn lại.

manhtienit
Thành viên tích cực
Thành viên tích cực
Bài viết: 120
Ngày tham gia: T.Sáu 13/05/2011 9:56 am
Has thanked: 2 time
Been thanked: 9 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 manhtienit » T.Hai 22/10/2012 11:54 pm

Hic hic viết xong lại thấy còn trường hợp đa giác lõm phức

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.Ba 23/10/2012 8:11 am

alexanderdna đã viết:Quay lại với cách tính đã nêu ở bài trước. Đối với đa giác lõm, khi tính tổng diện tích, ta sẽ trừ đi (tức cộng với số đối) diện tích của phần tam giác có chứa đỉnh lõm, thay vì cộng. Nhưng vấn đề nảy sinh là làm cách nào xác định một đỉnh của đa giác là lồi hay lõm?

Mọi người tiếp tục tìm hướng giải quyết nào :-bd
Dazzling V.I.T
Hãy gọi tôi là vịt :)

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.Ba 23/10/2012 8:48 am

manhtienit đã viết:éc như vậy mà gần đúng thôi ah?Anh đưa ra cách đếm số giao điểm của đường nẳm ngang với các cạnh hình như là không hợp lý.Và cách của em ko phải chia nhỏ đa giác thành ô vuông nếu chia nhỏ được dễ dàng thì tính diện tích tam giac như trên còn khả quan hơn.ý của e là tính số điểm ảnh trong đa giác, và tính số điểm ảnh trong 1 đơn vị diện tích và nhân tỷ lệ anh ah.

Lúc đầu mình tưởng bạn muốn đếm số điểm có toạ độ nguyên :D
Bài toán đưa ra là "tính diện tích", vì thế cách của bạn là phương pháp gần đúng. Vì nếu kích thước của một điểm ảnh càng nhỏ thì diện tích tính được bằng cách đếm số điểm ảnh càng gần với diện tích thực của hình mình muốn tính. Khi ta chia thành cách hình vuông "vô cùng nhỏ", ta sẽ được diện tích cần tính. Đó cũng là nguyên tắc tích phân đó :)
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.Ba 23/10/2012 9:16 am

Ý tôi là thế này:

Đa giác lồi hay lõm, thậm chí tự cắt cũng thế cả - dùng tích phân.
Tại vị trí {t,0} bất kỳ, ta có nhiệm vụ xác định có bao nhiêu trong tổng số n cạnh giao nhau với đường thẳng x=t (trong hình là các đường màu xanh), sắp xếp các giao điểm theo thứ tự tăng (hoặc giảm) dần rồi tính tổng các đoạn thẳng giữa 2 điểm cắt [2i] -> [2i+1].
Chú ý:
- Nếu giao điểm [2i] trùng với [2i+1] (tức tại đỉnh hoặc giao điểm của hai cạnh trong đa giác tự cắt) thì đoạn này có độ dài bằng 0, chứ không được tính gộp thành 1 giao điểm.
- Nếu một cạnh nằm trọn trên đường thẳng x=t thì không gọi là cắt nhau, nên không có giao điểm.
Tập tin đính kèm
dtdg.JPG
Minh hoạ bài viết
dtdg.JPG (11.48 KiB) Đã xem 8823 lần
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 11:16 am

taykhongbatgiac đã viết:Ý tôi là thế này:

Đa giác lồi hay lõm, thậm chí tự cắt cũng thế cả - dùng tích phân.
Tại vị trí {t,0} bất kỳ, ta có nhiệm vụ xác định có bao nhiêu trong tổng số n cạnh giao nhau với đường thẳng x=t (trong hình là các đường màu xanh), sắp xếp các giao điểm theo thứ tự tăng (hoặc giảm) dần rồi tính tổng các đoạn thẳng giữa 2 điểm cắt [2i] -> [2i+1].
Chú ý:
- Nếu giao điểm [2i] trùng với [2i+1] (tức tại đỉnh hoặc giao điểm của hai cạnh trong đa giác tự cắt) thì đoạn này có độ dài bằng 0, chứ không được tính gộp thành 1 giao điểm.
- Nếu một cạnh nằm trọn trên đường thẳng x=t thì không gọi là cắt nhau, nên không có giao điểm.

Bài toán ở đây là tính diện tích đa giác, tức là các cạnh đều là đoạn thẳng. 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?
Xin mời mọi người tiếp tục thảo luận và đưa ra ý tưởng \:D/
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