多角形の面積の求め方について

環境/言語:[VB.NET]
分類:[.NET]

ユーザーが画像上をクリックした座標から多角形の面積を
計算するプログラムを作っています。
多角形の面積はネットで検索すると
http://homepage1.nifty.com/gfk/polygon.htm
のように割と簡単な方法で計算できそうでした。
しかし、ネットで見つけた方法では例えば
以下のような図形で４点を指定すると

座標1（1,1）
座標2（5,1）
座標3（8,4）
座標4（4,4）


Ｙ
９□□□□□□□□□□
８□□□□□□□□□□
７□□□□□□□□□□
６□□□□□□□□□□
５□□□□□□□□□□
４□□□□■■■■■□
３□□□■■■■■□□
２□□■■■■■□□□
１□■■■■■□□□□
０□□□□□□□□□□
  ０１２３４５６７８９　Ｘ

面積は12と計算されます。
これは座標点を画素セルの中心にあるとした場合の
考え方ですが､画素面積という考え方で面積20を得たいのです。
どなたか良い方法を教えて下さい。

■No27426に返信(ひで46さんの記事)
この場合、
x方向で右側にある点のx座標を+1
y方向で上側にある点のy座標を+1
すればそんな感じになりそうです。

1pixelを1x1の四角とみなしどこをその点の実座標として扱うかになります。
点の数が増えた場合、この判断をするのは結構大変そうなきもしますが。

shuさま

早速のコメントありがとうございます。
確かにこの例のような図形ならそれで良いのですが､これは
デバッグ用に用意したもので実際は複雑な形状が想定されています。
何をもって「右側」「上側」の頂点か判断するのかが分からないところです。

■No27427に返信(shuさんの記事)
> ■No27426に返信(ひで46さんの記事)
> この場合、
> x方向で右側にある点のx座標を+1
> y方向で上側にある点のy座標を+1
> すればそんな感じになりそうです。
>
> 1pixelを1x1の四角とみなしどこをその点の実座標として扱うかになります。
> 点の数が増えた場合、この判断をするのは結構大変そうなきもしますが。

■No27428に返信(ひで46さんの記事)
> デバッグ用に用意したもので実際は複雑な形状が想定されています。

たとえば、底面5ドット、高さ4ドットの直角三角形を描いたときに

□□□□□□□　□□□□□□□　□□□□□□□
□□□□□■□　□□□□□■□　□□□□□■□
□□□□■■□　□□□■■■□　□□□□■■□
□□□■■■□　□□■■■■□　□□■■■■□
□■■■■■□　□■■■■■□　□■■■■■□
□□□□□□□　□□□□□□□　□□□□□□□

のいずれで描画されるのかを、計算で求めることが困難なのであれば
アンチエイリアスを切った状態で Bitmap クラスに描画してみて、
そこから画素を広い出していくという方法はどうでしょう。

■No27428に返信(ひで46さんの記事)
> 何をもって「右側」「上側」の頂点か判断するのかが分からないところです。
>
ひとつの方法として、
(1)すべての点のx座標、y座標のそれぞれ平均値を出す(pt1とする)
(2)pt1から左に一番遠い点(pt2とする)は四角の左側(x+0)
,pt1から右に一番遠い点(pt3とする)は四角の右側(x+1)とする
(3)その他の点(pt4)はpt2,pt3の割合で
　　　pt4.x += (pt4.x-pt2.x) / (pt3.x - pt2.x)
とする
(4),(5) (2),(3)のy方向の計算
(6)これで求めた各点に対し面積を計算する。

pt1の求め方をいろいろ変えてみるのもいいかもしれません。

■No27430に返信(shuさんの記事)

最大、最少の点をpt2,pt3とすればpt1はいらなかったかもmm

魔界の仮面弁士さん、アドバイスありがとうございます。

その後、情報処理学会の雑誌の記事でまさにズバリを見つけました。
http://www.ipsj.or.jp/07editj/promenade/4501.pdf
この記事でもJAVAの描画toolkitで頂点座標からPolygonを
描画した上で全ての点がPolygon内にあるかを調べて内部に
ある点をカウントするという方法が「ずるい解答」の例として
載ってました（しらみつぶしに調べるのは時間がかかるので
分割して計算する方法の記載や「ずるくない方法」の記載もあり）。
魔界の仮面弁士さんの方法もこれのWindows版として使えそうですね。
時間がかからず正解が得られるなら「ずるい解答」は私は大好きです。

多角形の面積計算問題は純粋な幾何の世界からデジタル画像の
世界に変わるだけで､これだけ面倒になるのですね。

多角形面積機能の実装は時間をかけて取り組む必要ありそうです。

魔界の仮面弁士さん、shuさん、アドバイスありがとうございました。

■No27429に返信(魔界の仮面弁士さんの記事)
> ■No27428に返信(ひで46さんの記事)
>>デバッグ用に用意したもので実際は複雑な形状が想定されています。
> 
> たとえば、底面5ドット、高さ4ドットの直角三角形を描いたときに
> 
> □□□□□□□　□□□□□□□　□□□□□□□
> □□□□□■□　□□□□□■□　□□□□□■□
> □□□□■■□　□□□■■■□　□□□□■■□
> □□□■■■□　□□■■■■□　□□■■■■□
> □■■■■■□　□■■■■■□　□■■■■■□
> □□□□□□□　□□□□□□□　□□□□□□□
> 
> のいずれで描画されるのかを、計算で求めることが困難なのであれば
> アンチエイリアスを切った状態で Bitmap クラスに描画してみて、
> そこから画素を広い出していくという方法はどうでしょう。

前回の投稿からだいぶ時間が経ってしまいましたが、解決の目処が立ちましたので
お知らせの投稿をさせていただきます。
＞情報処理学会の雑誌の記事でまさにズバリを見つけました。
＞http://www.ipsj.or.jp/07editj/promenade/4501.pdf
と書きましたが、良く読むと頂点座標が格子上に設定されており、
頂点座標を画素の中心とする私の問題とちょっと違ってました。
その後､その違いを吸収すべく、色々ソースを変更してみましたが､
うまくいかず。
そこでまたネットを検索し､
「多角形の塗りつぶし。ソリッド・スキャン・コンバージョンの紹介です。」
http://fussy.web.fc2.com/algo/
を見つけました。塗り潰しも画素のカウントも同じとの考えで参考にして
プログラム組んでます。
それまで色々な多角形形状に対応して分岐が複雑になって、わけがわからなくなって
いたソースがすっきりしそうです。
アドバイス頂いた皆さん､ありがとうございました。
上記サイトは他にも色々なアルゴリズムが紹介されていて今後も何かの
役にたちそうです。