与えられたポリゴンの内側または境界にある与えられた点をチェックするか、Pythonではないかをチェックするプログラム

ポリゴンを表すデカルト点[（x1、y1）、（x2、y2）、...、（xn、yn）]のリストがあり、xとyの2つの値があるとします。 （x、y）がこのポリゴンの内側にあるのか、境界上にあるのかを確認してください。

したがって、入力がpoints =[（0、0）、（1、3）、（4、4）、（6、2）、（4、0）] pt =（3、1）>

その場合、出力はTrueになります

これを解決するには、次の手順に従います-

• ans：=False
• 0からポリゴンのサイズ-1までの範囲のiの場合、実行します
  • （x0、y0）：=ポリゴン[i]
  • （x1、y1）：=ポリゴン[（i + 1）ポリゴンのmodサイズ]
  • pt [1]がy0、y1の最小値とy0、y1の最大値の範囲内にない場合、
    • 次の反復に進む
  • pt [0]
  • 次の反復に進む
• cur_x：=x0（x0がx1と同じ場合）それ以外の場合x0 +（pt [1]-y0）*（x1-x0）/（y1-y0）
• ans：=ans XOR（pt [0]> cur_xがtrueの場合は1、それ以外の場合は0）

理解を深めるために、次の実装を見てみましょう-

例

class Solution:
   def solve(self, polygon, pt):
      ans = False
      for i in range(len(polygon)):
         x0, y0 = polygon[i]
         x1, y1 = polygon[(i + 1) % len(polygon)]
         if not min(y0, y1) < pt[1] <= max(y0, y1):
            continue
         if pt[0] < min(x0, x1):
            continue
         cur_x = x0 if x0 == x1 else x0 + (pt[1] - y0) * (x1 - x0) / (y1 - y0)
         ans ^= pt[0] > cur_x
      return ans

ob = Solution()
points = [(0, 0), (1, 3), (4, 4), (6, 2), (4, 0)]
pt = (3, 1)
print(ob.solve(points, pt))

入力

[(0, 0), (1, 3), (4, 4), (6, 2), (4, 0)], (3, 1)

出力

True