0

私はこれらのうちの2つを持っています:

bool isPointOnShape(int a, int b)
{

}

bool isPointInShape(int a, int b)
{

}

正方形があるとします。最初の点 (左下隅) は x,y (0,0)、2 番目の点 (左上) は (0,2)、3 番目は (2,2)、4 番目は (0,2) です。 .

形状上のポイントは (0,1) (1,2) (2,1) (1,0) であり、形状上のポイントは (1,1) です。

どこかに保存できるように、形状/形状のポイントを見つけて真の値を返すにはどうすればよいですか?

4

2 に答える 2

11

直線セグメントに分割できるあらゆる形状の一般的なソリューションを提供します。

それで、あなたが推測するかもしれないように、私はあなたの「形」をループを完了するセグメントのリストとして考えることから始めます。または、ループを表す点の円形リストを配置します。たとえば、正方形は次の点のリストになります。

0, 0
0, 2
2, 2
2, 0

各ポイントから次のポイントへのセグメントがあり、最後のポイントが最初のポイントに接続していると見なしていることに注意してください。また、連続するポイントが等しくなく、最初と最後でもないことが必要です。存在する場合は、続行する前にそれらを削除する必要があります。

これで、セグメントごとにバウンディングボックスを決定できます。たとえば、このセグメントが与えられた場合：

a = (0, 2)
b = (2, 2)

次に、xの値の範囲は[0、2]で、yの値の範囲は[2、2]であり、これがそのセグメントのバウンディングボックスです。

次に必要なのは、セグメントの線のダイレクタベクトルです。これを取得するには、最初にセグメントの長さを計算します。

length = sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y))

その後：

director.x = (a.x - b.x)/length
director.y = (a.y - b.y)/length

注1：長さが0の場合、無効なセグメントがあります。そのため、繰り返しのポイントは必要ありません。

注2：直線の方程式を使用する代わりにダイレクタベクトルを使用すると、作業が簡単になります。

ここで、ポイントpが与えられると、そのポイントがセグメント内にあるかどうかを判別できます（リスト内のポイントの1つである場合）。残りのケースでは、軸に揃えられたバウンディングボックスの内側にあるかどうかを確認することから始めます。これは、範囲を確認するだけで実行できます。

if
(
    (p.x >= box.left && p.x <= box.right) &&
    (p.y >= box.top && p.y <= box.bottom) // with origin at the top-left corner
)
{
     //It is inside of the bounding box
}

そうである場合は、ポイントからラインまでの距離を計算します。0の場合は、ライン上にあります。ここで、浮動小数点演算により、距離がイプシロン以下であるかどうかをテストできます。イプシロンは非常に小さい数値です。

次の式を使用します。

distance vector = (a - p) - ((a - p) · director) * director
distance = the norm of distance vector

ここで、「・」は内積を示し、「*」は内積を示します。

残りのすべては、セグメントを反復処理することです。各セグメントについて距離を計算し、距離がイプシロン未満の場合、ポイントは「形状上」にあります。

わかりました、しかし「形で」はどうですか？

さて、トポロジーからのトリックの少しの助けを借りて、ポイントが内側にあるかどうかを判断することができます。これは、Windowsがポリゴンまたはポリラインを塗りつぶすために使用するのと同じアルゴリズムです（Microsoftペイントでフリーハンドで選択した領域内にあるものを決定するなど）。

こんなふうになります：

外側からポイントに到達するために交差する必要があるセグメントの数を数えます。数がペアの場合は外側、奇数の場合は内側です。

ポイントに到達する方向から選択できます。左を選びます。

もう一度、セグメントを繰り返し処理します。それぞれについて、それが垂直範囲にあるかどうかを判断する必要があります。そのためには、バウンディングボックスを使用します。

if ((p.y >= box.top && p.y <= box.bottom))
{
     //In the vertical range
}

ここで、セグメントが左にあるか右にあるかを判別します。

if (p.x < box.left)
{
     //The segment is at the left
}
else if (p.x > box.right)
{
     //The segment is at the right
}
else
{
     //The segment is close, need further calculation
}

セグメントが近い場合は、そのセグメントまでのベクトル距離を計算し、その方向を確認する必要があります。

ベクトル距離？まあ、私たちはすでにそれを持っています、私たちは距離を決定するためにその規範を取っています。ここで、標準を取る代わりに、x座標の符号を確認します。0未満の場合は右、0より大きい場合は左になります。0の場合...セグメントが水平であることを意味します（距離ベクトルは常にセグメントに垂直であるため）、そのセグメントをスキップできます*。

*：実際、セグメントが水平で垂直範囲にある場合、それはセグメントにあることを意味します。セグメントは「形」ですか？

ここで、左側のセグメントの数を数える必要があります。奇数の場合、ポイントはシェイプの内側にあります。それ以外の場合は出ています。これは、上、右、または下のセグメントでも実行できます。左を選んだ。

すべてのセグメントを反復処理するのにコストがかかる大きな形状の場合、データ構造を分割するスペースにセグメントを格納できます。それはこの投稿の範囲を超えています。

于 2012-11-04T09:40:22.170 に答える
4

Rectangleクラスがあり、このクラスにメンバーbottomLeftとがあると仮定するとtopRight、次のように書くことができます。

bool Rectangle::isPointOnShape(int x, int y) {
    if (x == bottomLeft.x || x == topRight.x)
        if (y > bottomLeft.y && y < topRight.y)
            return true;

    if (y == bottomLeft.y || y == topRight.y)
        if (x > bottomLeft.x && x < topRight.x)
            return true;
}

bool Rectangle::isPointInShape(int x, int y) {
    bool inX = false;
    bool inY = false;
    if (x > bottomLeft.x && x < topRight.x)
        inX = true;

    if (y > bottomLeft.y && y < topRight.y)
        inY = true;

    return (inX && inY);
}

形状が長方形でない場合、この関数はもちろん異なります。

于 2012-11-04T08:52:43.203 に答える