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先生~
ポリゴンの面積
外積…ってなんだったっけ?(汗) 内積はなんとなく覚えてるけど。
まあ、ようするに、上の三角形の面積を全部足し合わせるってことだよな。
三角形とポリゴンの面積は、こちらの説明もわかりやすかった。
公式が分かれば、あとは簡単。
ポリゴンを三角形に分割する
ポリゴンの最初の頂点を、三角形の共通の頂点とする。残りの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))
これで公開!
これは簡単だった。