0

True指定された (x,y) ポイントが凸多角形の内側にある場合に返される関数を作成しようとしています。numpy や同様のインポートを使用せずに、純粋な python コードだけで作成しようとしています。

一見問題ないように見えるサンプル ソリューションを既に見つけましたが、正しく機能しておらず、その理由がわかりません。コードは次のとおりです。

def point_in_poly(x,y,poly):

  n = len(poly)
  inside = False

  p1x,p1y = poly[0]
  for i in range(n+1):
      p2x,p2y = poly[i % n]
      if y > min(p1y,p2y):
          if y <= max(p1y,p2y):
              if x <= max(p1x,p2x):
                  if p1y != p2y:
                      xints = (y-p1y)*(p2x-p1x)/(p2y-p1y)+p1x
                  if p1x == p2x or x <= xints:
                      inside = not inside
      p1x,p1y = p2x,p2y

  return inside

(9,9)、次のポリゴンについてテストすると、次のようになりますTrue。

polygon = [(0,10),(10,10),(10,0),(0,0)]
point_x = 9
point_y = 9
print point_in_poly(point_x,point_y,polygon)

しかし、ポリゴンのポイントの順序を変更すると、同じポイントに対して次のようになりますFalse。

polygon = [(0,0), (0,10), (10,0), (10,10)]
point_x = 9
point_y = 9
print point_in_poly(point_x,point_y,polygon)

誰も理由を知っていますか？ありがとう！

4

3 に答える 3

5

あなたが問題を抱えている特定のケースでは特別です: polygon = [(0,0), (0,10), (10,0), (10,10)]

ポリゴン内のポイントの順序を変更すると、アルゴリズムに大きな影響を与える可能性があります。

グラフに多角形を描くと、水平の砂時計の形をしていることがわかります。ポリゴンの境界が重なっています。地理空間分析では、視覚的および論理的に共通の交点を持つ 2 つの閉じたポリゴンがあるため、このオーバーラップは許可されません。ちなみに、ほとんどの地理空間ソフトウェアも三角形をうまく処理できません。

この場合、9,9 のポイントは、2 倍になったポリゴン境界を簡単に 2 回越えることができるため、上記の方法で使用されているレイ キャスティング アルゴリズムをだますことができます。

次のコードを実行して、何が起こっているかを確認してください。(9,9) はライン上にあり、このアルゴリズムはそれを考慮していません。(5,8) はかなり外側です:

import turtle as t
polygon = [(0,0), (0,100), (100,0), (100,100)]
t.goto(0,0)
fp = None
for p in polygon:
  t.goto(p)
  if not fp: fp=p
t.goto(fp)
t.up()
t.goto(90,90)
t.write("90,90")
t.dot(10)
t.goto(50,80)
t.write("50,80")
t.dot(10)
t.done()

このコードは (9,9) エッジ ケースを処理します: http://geospatialpython.com/2011/08/point-in-polygon-2-on-line.html

上記のコードはこの画像を描画します。

于 2013-05-04T17:30:19.837 に答える
0

ポイント9,0はポリゴンの内側ではなく[(0,10),(10,10),(10,0),(0,0)]、エッジにあります。アルゴリズムの詳細に応じて、エッジに正確にあるポイントをインまたはアウトと見なすことができます。

于 2013-05-01T20:25:33.100 に答える