11

図

上の画像を参照してください。基本的に、点が線分の範囲内にあるかどうかを確認する簡単なテストが必要です。私が持っている情報 (または必要に応じて入力) は、点の座標と、線分の終点の座標です。私が望む出力は単純なブール値です。これを簡単な方法で確認するにはどうすればよいですか？

4

4 に答える 4

14

インナーを使えば簡単に均一チェックができます。2 つのベクトル間の内積は、2 つのベクトルの長さと 2 つの間の角度の余弦の積、またはベクトルの 1 つの長さと (直交) 投影の長さの積として幾何学的に視覚化できます。そのベクトルによって決定されるライン上に他のの。

あなたの状況では、セグメントのエンドポイントの 1 つから考慮中のポイントにベクトルを投影すると、投影が2 つのエンドポイントを接続するvセグメント上にある場合に限り、ポイントは許可された領域内にあります。sそして、それは

0 <= v·s <= s·s

(端点を通るセグメントに垂直な線を除外する場合は厳密な不等式)

public static boolean inRange(double start_x, double start_y, double end_x, double end_y,
                              double point_x, double point_y) {
    double dx = end_x - start_x;
    double dy = end_y - start_y;
    double innerProduct = (point_x - start_x)*dx + (point_y - start_y)*dy;
    return 0 <= innerProduct && innerProduct <= dx*dx + dy*dy;
}
于 2013-07-10T23:14:07.693 に答える
2

太線の端点を通る垂直な点線の方程式を決定するのは難しくありません。

太線を点とで定義します。すると、傾きがあります(x1, y1)(x2, y2)

m = (y 2 - y 1 ) / (x 2 - x 1 )

したがって、すべての垂直線は次の形式になります

y(x) = ( -1 / m )x + c

これを使用して、 および(それぞれ)を通過する垂線の方程式を決定できます。これは、すべての有効なポイントが存在する必要がある領域の境界を本質的に表します。(x1, y1)(x2, y2)

y a (x) = (-1/m)x + y 1 + x 1 /m
y b (x) = (-1/m)x + y 2 + x 2 /m

したがって、任意の点について、(x*, y*)それが有効な領域にあるかどうかを判断するには、

y a (x*) <= y* <= y b (x*)

（または大きい場合はその逆）ya(x*)

次のようにしてください。

public static boolean check(double x1, double y1, double x2, double y2,
            double x, double y) {

    if (x1 == x2) {  // special case
        return y1 < y2 ? (y1 <= y && y <= y2) : (y2 <= y && y <= y1);
    }

    double m = (y2 - y1) / (x2 - x1);
    double r1 = x1 + m * y1;
    double r2 = x2 + m * y2;
    double r = x + m * y;
    return r1 < r2 ? (r1 <= r && r <= r2) : (r2 <= r && r <= r1);
}
于 2013-07-10T22:13:14.197 に答える