ジオフェンス Ruby 用のポリゴン オブジェクトを作成する
概要
Ruby で、経度と緯度の点の配列 (各点が配列の順序で次の点に接続される) を受け取る Polygon オブジェクトを書きたいと考えています。さて、私の主な質問は、点をプラグインして、それが多角形の内側か外側かを確認できるように、2 つの点の間のエッジ (線) を表現する最善の方法は何でしょうか?
この機能を簡単に追加できる gem はありますか?
これがこれまでに書いたコードのすべてです
class Polygon
attr_reader :vertices
def initialize(vertices)
@vertices = vertices
end
end
解決策
これは、指定された点が凸多角形の内側 (またはエッジ上) にあるかどうかを判断する 1 つの方法です。 （OPは、ポリゴンが凸状であることを質問に対するコメントで確認したことに注意してください。）
コード
def inside?(vertices, test_point)
vs = vertices + [vertices.first]
xi, yi = vertices.reduce([0,0]) { |(sx,sy),(x,y)| [sx+x, sy+y] }.map { |e|
e.to_f/vertices.size } # interior point
x, y = test_point
vs.each_cons(2).all? do |(x0,y0),(x1,y1)|
if x0 == x1 # vertical edge
(xi > x0) ? (x >= x0) : (x <= x0)
else
k, slope = line_equation(x0,y0,x1,y1)
(k + xi*slope > yi) ? (k + x*slope >= y) : (k + x*slope <= y)
end
end
end
def line_equation(x0,y0,x1,y1)
s = (y1-y0).to_f/(x1-x0)
[y0-s*x0, s]
end
多角形は直線ではない(つまり、すべての頂点が同一直線上にない)と仮定しました。
例
vertices = [[5,1],[2,4], [2,8], [6,10], [9,6]]
inside?(vertices, [6,7]) #=> true
inside?(vertices, [9,9]) #=> false
inside?(vertices, [5,1]) #=> true
説明
例の多角形のグラフを次に示します。
多角形の各エッジを両方向に無限に延長すると、平面を 2 つの部分に分割する線が形成されます。特定の点が多角形内 (エッジ上の点を含む) に存在するには、その点が、多角形を含むエッジによって形成されるすべての線の側面上になければなりません。
この例では、矢印は [5,1] と [2,4] を通過する線、および [2,4] と [2,8] を通過する線に該当する側を示しています。 [5,1] と [2,4] を通る直線の方程式は次のようになります。
y = 6.0 - x
したがって、この直線の両側の点は、6.0 - x <= y および 6.0 - x >= y で与えられます。各エッジにどの不等式が適用されるかを判断するには、多角形の内部点が必要です。凸型なので、凸型の頂点の組み合わせが多くても問題ありません。たとえば、連続する 3 つの頂点が同一直線上にない場合は、たとえば、隣接しない 2 つの頂点の平均を使用できます。すべての頂点の平均である点を使用することを選択しました。これは、3 つ以上の (すべてではない) 連続する頂点が同一直線上にある場合でも、内部点になります。
xi, yi = vertices.reduce([0,0]) { |(sx,sy),(x,y)| [sx+x, sy+y] }.map { |e|
e.to_f/vertices.size }
#=> [4.8, 5.8]
最初の 2 つの頂点を通過する線に戻ると、次のことがわかります。
6.0 - x = 6.0 - 4.8 = 1.2 => (1.2 < 5.8) => true
したがって、内点は次の式で与えられる半空間内にあります。
6 - x <= y
したがって、次のテストを適用して、対象の点 [6,7] がこの半空間内にあるかどうかを確認します。
6.0 - 6.0 = 0 <= 7.0
ポイント [9,9] と同様にそうです。点 [2,2] を考慮すると、次のことがわかります。
6.0 - 2.0 = 4.0 > 2.0
したがって、反対の結論が得られ、内部から false が返されますか?
ここで、[6,10] と [9,6] を通る直線について考えてみましょう。その方程式は次のとおりです。
y = 18.0 - 1.333*x
として
18.0 - 1.33*xi => 18.0 - 1.333*4.8 = 11.6 => (11.6 < 5.8) => false
したがって、多角形を含むこの線に関連付けられた半空間は、次の不等式によって与えられます。
18.0 - 1.333*x >= y
この不等式を使用して、点がこの半空間内に収まるかどうかをテストできます。 [6,7] の場合:
18.0 - 1.333*6 #=> (10.0 >= 7) #=> true
[9,9] の場合:
18.0 - 1.333*9 #=> (6.0 >= 7) #=> false