CGL_3_C: Polygon-Point Containment (続き4)

でもいったんいけるところまでこのままいってみよう
その後で考え直す

いけたので考え直す
たぶん解説にはもっとシンプルなのが載っていると見た

アルゴリズムの見直しもしたいけど、テストケースも見直してみたい気がしている
ただ、テストケースの見直しは考えてみるとなかなか難しい
追加ならいくらやってもいいけど
見直して整理したりしたときこれまでチェックできていたものが
テスト変更後も正しくチェックできているということを保証する方法って
あるのかな

アルゴリズムによりそうなところもあるしな
そういうのがテストケースに入るのはいいのか悪いのか
今回、たまたまx軸に平行な半直線を選んだから特殊ケースになったという
項目があってあとで付け足した
じゃあy軸に平行な半直線を選んだときに特殊になるケースは
テストケースから抜けたままにしておいていいのか
的な

そういう細々とした特殊ケースが出ないようなアルゴリズムを見つけられれば
いちばんいいんだけど

たとえば、今回半直線を使ったけど、別にこれは半直線に限る必要は
なくって、折れ線だっていいはず
面倒な特殊ケースにぶつかったら線を少し斜めにするとかずらすとか

逆に頂点の方をほんの少しずらすとか
こっちはほんの少しでもずらした結果答えが変わってくる可能性があるからダメかな

線分をひとつずつ取って半直線と交わる、ってやるよりも
点が移動していってところどころで半直線を横切る、っていうイメージのほうが
特殊ケースの考慮が減るかもな
半直線上にいる間はまだ横切ってない、とする

ONLINEの判定は先に済ませておいたほうがすっきりするかもしれない
効率上どうなのかはよくわからない

ちょっと書けそうな気がしてきた

    def contains(self, p: Point) -> Containment:
        def area(p1: Point) -> int:
            if p1.y - p.y < -EPS:
                return - 1
            elif p1.y - p.y > EPS:
                return 1
            else:
                return 0

        ps = Segment(p, Point(100000.0, p.y))

        # 辺の上にあればONLINEを返す
        for s in self.sides():
            if p.location(s) == PointLocation.ON_SEGMENT:
                # print("online")
                return Containment.ONLINE

        # pとy座標が異なる頂点から開始
        for k0, prev_p in enumerate(self.vertices):
            if area(prev_p) != 0:
                break
        prev_a = area(prev_p)

        count = 0
        k = 1
        while k <= self.n:
            # pとy座標が異なる頂点まで進む
            while True:
                k1 = (k + k0) % self.n
                cur_p = self.vertices[k1]
                cur_a = area(cur_p)
                if cur_a != 0:
                    break
                k += 1
                prev_p = cur_p

            if prev_a != cur_a and \
                Segment(prev_p, cur_p).intersects(s):
                count += 1
            prev_p = cur_p
            prev_a = cur_a
            k += 1

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

よけい長くなった・・・
やってることはわかりやすくなった気がする（しなくもない）んだけど・・・