kb84tkhrのブログ

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

CGL_3_C: Polygon-Point Containment (続き)

PCAD

さて戻る
辺を順番に取り出したから次は交点を求めればいいかな
点からの半直線との交点だけどどんな半直線でもいいわけだから
x軸方向への半直線がいちばん楽だろう
ヒントの絵もそんな感じになっている
といってもこれまで書いてきた関数を使うならあんまり関係ないかもしれない

で
素直なケースはいいと思うんだけど意外とめんどくさいケースがある気がする
半直線がちょうど頂点を通るとか
点が線分上にあるとか

さきにテストケースを考えてみようか
こんな図形でやったらいろいろできそうだ
まずは多めに点をつけてみて・・・

f:id:kb84tkhr:20190323215816j:plain

本質的に異なると言えるのはどれだろう
点が線分上にあって、半直線が図形に入る場合と出る場合は別だろうか
絞ってケース落とすより全部やっちゃうか

        p = Polygon([Point(1, 1),
                     Point(7, 1),
                     Point(7, 3),
                     Point(5, 5),
                     Point(5, 3),
                     Point(3, 3),
                     Point(1, 5)])
        self.assertEqual(p.contains(Point(0, 0)), CN.OUTSIDE)
        self.assertEqual(p.contains(Point(0, 1)), CN.OUTSIDE)
        self.assertEqual(p.contains(Point(1, 1)), CN.ONLINE)
        self.assertEqual(p.contains(Point(4, 1)), CN.ONLINE)
        self.assertEqual(p.contains(Point(7, 1)), CN.ONLINE)
        self.assertEqual(p.contains(Point(0, 2)), CN.OUTSIDE)
        self.assertEqual(p.contains(Point(1, 2)), CN.ONLINE)
        self.assertEqual(p.contains(Point(4, 2)), CN.INSIDE)
        self.assertEqual(p.contains(Point(7, 2)), CN.ONLINE)
        self.assertEqual(p.contains(Point(0, 3)), CN.OUTSIDE)
        self.assertEqual(p.contains(Point(1, 3)), CN.ONLINE)
        self.assertEqual(p.contains(Point(2, 3)), CN.INSIDE)
        self.assertEqual(p.contains(Point(3, 3)), CN.ONLINE)
        self.assertEqual(p.contains(Point(4, 3)), CN.ONLINE)
        self.assertEqual(p.contains(Point(5, 3)), CN.ONLINE)
        self.assertEqual(p.contains(Point(6, 3)), CN.INSIDE)
        self.assertEqual(p.contains(Point(7, 3)), CN.ONLINE)
        self.assertEqual(p.contains(Point(0, 4)), CN.OUTSIDE)
        self.assertEqual(p.contains(Point(1, 4)), CN.ONLINE)
        self.assertEqual(p.contains(Point(2, 4)), CN.ONLINE)
        self.assertEqual(p.contains(Point(4, 4)), CN.OUTSIDE)
        self.assertEqual(p.contains(Point(5, 4)), CN.ONLINE)
        self.assertEqual(p.contains(Point(6, 4)), CN.ONLINE)
        self.assertEqual(p.contains(Point(0, 5)), CN.OUTSIDE)
        self.assertEqual(p.contains(Point(1, 5)), CN.ONLINE)
        self.assertEqual(p.contains(Point(4, 5)), CN.OUTSIDE)
        self.assertEqual(p.contains(Point(5, 5)), CN.ONLINE)

こうですかわかりません

まず線上とか頂点を通るとかの特殊ケースをコメントアウトして
普通に内部外部なやつだけクリアしようかな
これしか残らない

        self.assertEqual(p.contains(Point(0,0)), CN.OUTSIDE)
        self.assertEqual(p.contains(Point(0,2)), CN.OUTSIDE)
        self.assertEqual(p.contains(Point(4,2)), CN.INSIDE)
        self.assertEqual(p.contains(Point(0,4)), CN.OUTSIDE)
        self.assertEqual(p.contains(Point(4,4)), CN.OUTSIDE)

あと半直線をどう考えるか
この前やった交差判定が使えそうなんだけれどもあれは線分どうしの交差だから

infとか使ってうまくいくようにはできてないと思うし
x,yは10000までだからx=100000くらいまでの線分として扱えばいいか

そうするとこう

    def contains(self, p: Point) -> Containment:
        ps = Segment(p, Point(100000.0, p.y))
        count = 0
        for s in self.sides():
            if ps.intersects(s):
                count += 1
        return Containment.OUTSIDE if count % 2 == 0 \
            else Containment.INSIDE

countはリスト閉包でも数えられるけどたぶんそれでは書ききれなくなるので
ループで

リスト閉包で書くとするとこう？

count = len([0 for s in self.sides() if ps.intersects(s)])

条件にあった要素を数えるだけの関数ってありそうなんだけど見つからず
まあいいや次

点が線分上にあるケースをやろうかな
これはlocationが使えそうだけどx軸に平行な半直線に限るなら
locationじゃなくてもいいくらいな気もする
まあlocationでやろう
そうするとこのテストケースの封印が解除される

        self.assertEqual(p.contains(Point(1,1)), CN.ONLINE)
        self.assertEqual(p.contains(Point(4,1)), CN.ONLINE)
        self.assertEqual(p.contains(Point(7,1)), CN.ONLINE)
        self.assertEqual(p.contains(Point(1,2)), CN.ONLINE)
        self.assertEqual(p.contains(Point(7,2)), CN.ONLINE)
        self.assertEqual(p.contains(Point(1,3)), CN.ONLINE)
        self.assertEqual(p.contains(Point(3,3)), CN.ONLINE)
        self.assertEqual(p.contains(Point(4,3)), CN.ONLINE)
        self.assertEqual(p.contains(Point(5,3)), CN.ONLINE)
        self.assertEqual(p.contains(Point(7,3)), CN.ONLINE)
        self.assertEqual(p.contains(Point(1,4)), CN.ONLINE)
        self.assertEqual(p.contains(Point(2,4)), CN.ONLINE)
        self.assertEqual(p.contains(Point(5,4)), CN.ONLINE)
        self.assertEqual(p.contains(Point(6,4)), CN.ONLINE)
        self.assertEqual(p.contains(Point(1,5)), CN.ONLINE)
        self.assertEqual(p.contains(Point(5,5)), CN.ONLINE)

線分上にあれば他の条件は関係ないからこうなるかな

   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 ps.intersects(s):
                count += 1
        return Containment.OUTSIDE if count % 2 == 0 \
            else Containment.INSIDE

OK