座標上の四角形の中に、点が入っているかを調べたい

はじめに

点(a,b,c,d)をもつ四角形の中に点eが入っているか、を出すためにベクトルの外積を使用します。 numpyって本当に便利ですね。

考え方

1. まず、原点から点(a,b,e)へのベクトルA,B,Eを作成。
2. 点aからbへのベクトルAB、点aからeへのベクトルAEを計算。
3. ベクトルAB、ベクトルAEの外積を計算
4. b->c,c->d,d->aに対しても2,3を実施する。
5. a->b, b->c, c->d, d->a のすべてで外積がマイナスであれば、 点は確変の左側にあるといえる ->四角形の中にある

実装

以下が実装。

def in_rect(rect,target):
    a = (rect[0][0], rect[0][1])
    b = (rect[1][0], rect[1][1])
    c = (rect[2][0], rect[2][1])
    d = (rect[3][0], rect[3][1])
    e = (target[0], target[1])

    # 原点から点へのベクトルを求める
    vector_a = numpy.array(a)
    vector_b = numpy.array(b)
    vector_c = numpy.array(c)
    vector_d = numpy.array(d)
    vector_e = numpy.array(e)

    # 点から点へのベクトルを求める
    vector_ab = vector_b - vector_a
    vector_ae = vector_e - vector_a
    vector_bc = vector_c - vector_b
    vector_be = vector_e - vector_b
    vector_cd = vector_d - vector_c
    vector_ce = vector_e - vector_c
    vector_da = vector_a - vector_d
    vector_de = vector_e - vector_d

    # 外積を求める
    vector_cross_ab_ae = numpy.cross(vector_ab, vector_ae)
    vector_cross_bc_be = numpy.cross(vector_bc, vector_be)
    vector_cross_cd_ce = numpy.cross(vector_cd, vector_ce)
    vector_cross_da_de = numpy.cross(vector_da, vector_de)

    return vector_cross_ab_ae < 0 and vector_cross_bc_be < 0 and vector_cross_cd_ce < 0 and vector_cross_da_de < 0

if __name__ == '__main__':
    rect = [[48, 43],[45, 42],[43, 38],[45, 39]]
    print(in_rect(rect, [44,45]))
    # -> False
    print(in_rect(rect, [46,41]))
    # -> True

参考

http://www.endo-yuta.com/2011/09/blog-post_06.html

Qiitaにも投稿しています。