kb84tkhrのブログ

何を書こうか考え中です あ、あと組織とは関係ないってやつです 個人的なやつ

CGL_3_C: Polygon-Point Containment (続き6)

解説を見る

半直線を実際に生成する必要はなく

これはまあ、どっちを選択するかという話かな
ヒントにlocationのアイコンが付いてたけど、そのまま使うわけじゃない
こともあるわけか

pとgiとgi+1とaとbはこうなってる

f:id:kb84tkhr:20190329222426p:plain

gigi+1上に点pがあるかどうかはccwと同様の方法で調べることができます

f:id:kb84tkhr:20190329222529p:plain

たしかに
ここは問題ない

半直線と線分gigi+1が(内含状態を更新するように)交差するかどうかは、aとbが作る平行四辺形の面積の符号、つまりaとbの外積の大きさによって判定を行います。

「内含状態を更新するように」
お手並み拝見

まず、2つのベクトルaとbについて、それらのyの値が小さい方がaとなるように調整します。

f:id:kb84tkhr:20190329222629p:plain

aの先端が下にくるようにする
いろんなパターンがある
a.y = b.yの場合はどちらでもいいことにしているようだ

aとbの外積の大きさが正で(aからbへ反時計回り)

f:id:kb84tkhr:20190329222818p:plain

aとbの外積の大きさが0、つまりpがgi、gi+1を通る直線上にあるときは
除外されている
ちょっとわかりづらいけど、
これは、次の条件と組み合わさると、pが線分gigi+1上にあるということなので
考えなくていいわけだな

かつ、aとb(の終点)が半直線をまたいで異なる側にあるとき、交差していると判断できます。

a.y < b.yということからこれはa.y < 0 < b.yということになる

f:id:kb84tkhr:20190329222917p:plain

うん確かに交わる
この条件で半直線上に線分gigi+1が乗っかってるケースは自動的に除外されるな
気になるのは等号がなりたつとき

ここでは、gigi+1の端点との交差を考慮しないように、境界の条件に注意する必要があります。

端点を通るときは無視してることになってるけどそれでいいんだっけ
自分そこで苦労したんだけど・・・
端点を通るときを全く考慮しないと、こういうときうまくいかないんじゃないの?

f:id:kb84tkhr:20190329223122p:plain

ちょっと書いてみるか・・・

あっ
a.y < EPS && b.y < EPSになってるのか

   def contains(self, p: Point) -> Containment:
        x = False
        for s in self.sides():
            a = s.p1 - p
            b = s.p2 - p
            if abs(a.cross(b)) < EPS and a.dot(b) < EPS:
                return Containment.ONLINE
            if a.y > b.y:
                tmp = a
                a = b
                b = tmp
            if a.y < EPS < b.y and a.cross(b) > EPS:
                x = not x

a.y = 0のときは含まれるんだ
a.y < -EPS && b.y < EPSじゃないんだ

上の書き方だと、a.y < 0 < b.yじゃなくてa.y <= 0 < b.yなんだな

完全にまたいでなくても、y座標がpと同じところから上に向いて伸びてる線分は
カウントするってことだ

なるほどね

自分のコードをその方針で直してみる
あんまり頑張らない程度に

    def contains(self, p: Point) -> Containment:
        ps = Segment(p, Point(100000.0, p.y))
        count = 0

        for s in self.sides():
            if p.location(s) == PointLocation.ON_SEGMENT:
                return Containment.ONLINE
            if s.p1.y > s.p2.y:
                s = s.reverse()
            l1 = s.p1.location(ps)
            l2 = s.p2.location(ps)
            if l1 != PointLocation.COUNTER_CLOCKWISE and \
                l2 == PointLocation.COUNTER_CLOCKWISE and \
                ps.intersects(s):
                count += 1

        return Containment.OUTSIDE if count % 2 == 0 \
            else Containment.INSIDE

これでもAC
ちょっともったいない計算があるけど