Area of a convex polygon (Incinerator) - ポリゴンの面積を求めよ

どんな問題？

Area of a convex polygon
http://www.checkio.org/mission/area-of-a-convex-polygon/

凸型ポリゴンの面積を求めよ。
頂点の数は 3 <= N <= 8 とする。
浮動小数点の誤差を考慮し、答えは±0.1の差を許容する。

引数は、ポリゴンの頂点座標 [x,y]のリストが渡される。（頂点の座標は整数値）
戻り値は、floatで面積を返す。

例題：

checkio([[1, 1], [9, 9], [9, 1]]) == 32
checkio([[4, 10], [7, 1], [1, 4]]) == 22.5
checkio([[1, 2], [3, 8], [9, 8], [7, 1]]) == 40
checkio([[3, 3], [2, 7], [5, 9], [8, 7], [7, 3]]) == 26
checkio([[7, 2], [3, 2], [1, 5], [3, 9], [7, 9], [9, 6]]) == 42
checkio([[4, 1], [3, 4], [3, 7], [4, 8], [7, 9], [9, 6], [7, 1]]) == 35.5

convex polygon というのは凸型のポリゴンだそうだ。凹型は concave polygon というそうな。

問題文の「≤」ってなんだ？と思ったら、「≦」と同じ不等号らしい。初めて見た。
不等号 - Wikipedia …Chromeだと文字化けあり

どうやって解く？

ポリゴンを三角形に分割して求めるのだろうけど、そもそも3点の座標から三角形の面積ってどうやって求めるんだ？三角形の面積といえば、底辺×高さ÷2 しか知らないぞ。・・・助けてWikipedia先生～

3点から三角形の面積を求める

3点から面積を求める公式

$http://upload.wikimedia.org/math/3/2/f/32f967328ca04765e6804a07e6d1dbc7.png$
三角形 - Wikipedia

ポリゴンの面積

Wikipediaに多角形の面積の公式も載っていた。

外積…ってなんだったっけ？（汗）内積はなんとなく覚えてるけど。
まあ、ようするに、上の三角形の面積を全部足し合わせるってことだよな。

三角形とポリゴンの面積は、こちらの説明もわかりやすかった。

公式が分かれば、あとは簡単。

ポリゴンを三角形に分割する

ポリゴンの最初の頂点を、三角形の共通の頂点とする。残りの2点をずらしていけば、ポリゴンを三角形に分割できる。

def divide_into_triangles(poly):
    for i in range(len(poly) - 2):
        yield poly[0], poly[i + 1], poly[i + 2]

三角形の面積

3頂点の座標から面積を求める関数。上の公式を当てはめただけ。

def calc_triangle_area(pts):
    (ax, ay), (bx, by), (cx, cy) = pts
    return abs((ax - cx) * (by - ay) - (ax - bx) * (cy - ay)) / 2

まとめ

def checkio(data):
    def divide_into_triangles(poly):
        for i in range(len(poly) - 2):
            yield poly[0], poly[i + 1], poly[i + 2]

    def calc_triangle_area(pts):
        (ax, ay), (bx, by), (cx, cy) = pts
        return abs((ax - cx) * (by - ay) - (ax - bx) * (cy - ay)) / 2

    return sum(calc_triangle_area(tri) for tri in divide_into_triangles(data))

これで公開！

これは簡単だった。

summer_tree_home

Check iOでPython3をマスターするぜっ