(0,0)からまでの 2 次元の空間領域があります(MAX_X, MAX_Y)。
この空間の領域内に、いくつかの線を描きます。線は領域の周囲と交差し、互いに交差する場合もあります。このように、これらの線は空間の領域をサブ領域に分割し、それらを合計すると、空間の領域全体が得られます。
この領域内には、いくつかのポイントがあり(x,y)ます。私は決定しなければならない
これをJavaでコーディングしようとしていますが、言語はそれほど重要ではありません。これらの 2 つのタスクを達成する方法がわかりません。誰かが私にヒントを与えることができれば、本当に感謝しています。
それは確かにかなり数学的な質問です。問題について考えると、解決策は非常に複雑および/または高価になると思います（計算に関して）。
サブリージョンのリストRから始め、1つの要素（リージョン全体）から始めます。次に、行のリストをループします。すべての線について、すべてのRをループします。線がリージョンと交差する場合は、2つに分割します。ラインエリア交差点チェックのヘルプは、ネット上で簡単に利用できるはずです。線と凸状領域の交点を探すだけです。このアルゴリズムの問題は、実行時間が約O（n ^ 3）になることです。n行のO（n）×エリアのO（n）×交差点チェックのO（n）（ただし、最後の部分を大幅に高速化して、O（n ^ 2）に下げることができる場合があります。終わり）。
どの領域に特定の点が含まれているかを確認することは、凸解析の古典的な問題です。そのために利用できるアルゴリズムがあるはずです。あなたがやりたいことは、あなたの線をループして、あなたのポイントがその線の「左または右」であるかどうかをチェックすることだと思います。最初のステップでサブリージョンをラインにリンクすると、O（n）に適切なサブリージョンが表示されます。
最初の問題は、より洗練されたアルゴリズムを使用するとかなり迅速に解決でき、前述のように、説明した問題は大幅に高速化できます。
基本的に、あなたが凸解析を見ている主題に関するより多くの情報が必要な場合。
ただし、それでもまったく役に立たない場合は、おそらく頭がおかしいでしょう（攻撃は意図されていません。ここでは、非常に複雑な数学を扱っています）。
これは、計算幾何学のかなり難しい問題です。考えられるアプローチは、元の長方形の平面細分割によって結果の領域を表すことです。サブディビジョンは、二重接続エッジ リスト (DCEL)で表されます。これは、有向半辺のリスト、領域 (面) のリスト、および頂点(線の交点) のリストで構成されます。これらのデータはすべて完全に相互接続されているため、他のデータが与えられたときに任意のデータを見つけることは非常に効率的です。
DCEL は、元の四角形である 1 つの領域から開始し、1 行ずつ追加して、繰り返し作成されます。ラインを追加するとは、現在の DCEL をこのラインでカットし、より洗練された DCEL を取得することを意味します。
最終的な DCEL が構築されると、ポイントを含む領域の検索とマーキングに使用できます。領域は凸多角形であるため、ポイントが領域内にあるかどうかのテストは効率的に行うことができます。
DCEL に関する優れた本は、M. de Berg, et.al.: Computational Geometry です。また、Web 上でも多くのリソースを見つけることができます。また、実装とさまざまなソフトウェア パッケージも見つかります。