CGL_3_C: Polygon-Point Containment (続き)
さて戻る
辺を順番に取り出したから次は交点を求めればいいかな
点からの半直線との交点だけどどんな半直線でもいいわけだから
x軸方向への半直線がいちばん楽だろう
ヒントの絵もそんな感じになっている
といってもこれまで書いてきた関数を使うならあんまり関係ないかもしれない
で
素直なケースはいいと思うんだけど意外とめんどくさいケースがある気がする
半直線がちょうど頂点を通るとか
点が線分上にあるとか
さきにテストケースを考えてみようか
こんな図形でやったらいろいろできそうだ
まずは多めに点をつけてみて・・・
本質的に異なると言えるのはどれだろう
点が線分上にあって、半直線が図形に入る場合と出る場合は別だろうか
絞ってケース落とすより全部やっちゃうか
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