CGL_3_C: Polygon-Point Containment (続き6)
解説を見る
半直線を実際に生成する必要はなく
これはまあ、どっちを選択するかという話かな
ヒントにlocation
のアイコンが付いてたけど、そのまま使うわけじゃない
こともあるわけか
pとgiとgi+1とaとbはこうなってる
gigi+1上に点pがあるかどうかはccwと同様の方法で調べることができます
たしかに
ここは問題ない
半直線と線分gigi+1が(内含状態を更新するように)交差するかどうかは、aとbが作る平行四辺形の面積の符号、つまりaとbの外積の大きさによって判定を行います。
「内含状態を更新するように」
お手並み拝見
まず、2つのベクトルaとbについて、それらのyの値が小さい方がaとなるように調整します。
aの先端が下にくるようにする
いろんなパターンがある
a.y = b.yの場合はどちらでもいいことにしているようだ
aとbの外積の大きさが正で(aからbへ反時計回り)
aとbの外積の大きさが0、つまりpがgi、gi+1を通る直線上にあるときは
除外されている
ちょっとわかりづらいけど、
これは、次の条件と組み合わさると、pが線分gigi+1上にあるということなので
考えなくていいわけだな
かつ、aとb(の終点)が半直線をまたいで異なる側にあるとき、交差していると判断できます。
a.y < b.y
ということからこれはa.y < 0 < b.y
ということになる
うん確かに交わる
この条件で半直線上に線分gigi+1が乗っかってるケースは自動的に除外されるな
気になるのは等号がなりたつとき
ここでは、gigi+1の端点との交差を考慮しないように、境界の条件に注意する必要があります。
端点を通るときは無視してることになってるけどそれでいいんだっけ
自分そこで苦労したんだけど・・・
端点を通るときを全く考慮しないと、こういうときうまくいかないんじゃないの?
ちょっと書いてみるか・・・
あっ
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
ちょっともったいない計算があるけど