ラケットを使ってポイントがポリゴンの内側にあるかどうかを調べるには

Question

私は、特定の緯度と経度の座標を与えられて、そのポイントが存在する近隣を出力するプロジェクトを進めています。私は緯度と経度の座標都市内のいくつかの近所の境界線を上にしてください。ファイルから近隣のデータを読み込み、ファイルからテストポイントを読み込む必要があります。私はラケットプログラミング言語を使用しています。

これまでのところ、ファイルを読み込んで各地域のポイントのリストを作成することができましたが、今は止まっています。私は、各近隣のポリゴンを作成し、そのポリゴンの内側にポイントがあるかどうかをチェックするメソッドを用意しました。しかし、私はラケットを使用してそれを行う方法を把握することはできません。

ポイントがそのポリゴンの内側にある場合、または問題を解決するためのより良い方法を見つける方法を知る手助けがありますか？

Answer 1

私は宿題/課題を解決したくないので、今はコードを投稿しません。しかし、私はいくつかのヒントを投稿します。以下の画像で

ルック：

はどのように我々はCがOBとDが外にあるエッジOAとの間にあることを知ることができますか？簡単なことですが、いくつかの角度を比較します。OCとOAの間の角度がOBとOAの間の角度より小さい場合、Cは明らかにOAよりもOBに近いです。

今、角度をいくつかのベクトルだけを知るようにするにはどうすればよいですか？我々は単調な余弦を使うことができます：それは引数の増加とともに減少します。従って、OCとOAとの間の角度の余弦は、OBとOAの間の角度の余弦よりも大きく、角度の余弦は、ODとOAの間の余弦よりも大きい。

次のステップは、余弦を計算する方法を理解することです。ベクトルのドット積は、その値がオペランドの長さの積より大きい角度の余弦であることを助けます。つまり：

cos(OC; OA) = dotproduct(OC; OA)/(length(OA) * length(OC)) 

2Dでのドット積は単純です：

あなたはあなたのポイントが Cとして、あるいは Dと同じ状況にあるかどうかを確認する簡単なテストを持っている必要があり、上記のすべてを組み合わせる

dotproduct(OC; OA) = (C.x - O.x) * (A.x - O.x) + (C.x - O.x) * (A.x - O.x) 

：前のエッジよりも1つのエッジに近いか否か。

これで、ポリゴンのすべてのエッジでこれを繰り返す必要があります。テストが述語である場合はfoldでこれを行うことができます。

注：これは、ポリゴンが凸である場合にのみ機能します。凹面ポリゴンの場合は、さらにテストを追加する必要があります。

セカンドノート：DまたはCまたはその両方がOA線以下である場合の図では、何が起こるのだろうか？これを考えて、上記のfoldメソッドのいくつかの変更があるかどうかを確認してください。

最後のメモ：数週間後に、割り当てが終了したと仮定して、完全なコードを投稿します。また、その時私は上記の注釈の質問に答えるでしょう。