2

ポイントの配列と、さらに2つのポイント（AとB）があります。最後の2つのポイントは線を形成し、配列内のどのポイントが線から最も遠いのかを見つけようとしています。Javaでこれを行うにはどうすればよいですか？

AとBからの距離を見つけるという線に沿ったものなのだろうかと思いますが、それは私の頭の中にうまく収まりません。

追加情報：線分だと思います。これがQuickHullであることを考えると、それが違いを生むかどうかはわかりません。数学と数式に関しては、私はこれまで最高ではなかったので、説明が多ければ多いほどよいでしょう。ありがとう！

4

5 に答える 5

5

配列内のそれぞれの3つのポイント[a,b,p]はそれぞれ、三角形を形成することに注意してください。その面積は次のよう にp表されます。(ab) * h /2hpab

これらの三角形が作成する面積を計算し、最小値を選択できます。abすべての人にとって一定であるため、最小の面積を持つトライアンルにも最小のが含まれることが保証されますh。

[各三角形の面積]を使用して見つけることができます

T=(1/2)* abs((x_a - x_p) * (y_b-y_a) - (x_a - x_b)* (y_p - y_a))

[ここでx_a,x_b,x_p、とはそれぞれy_a,y_b,y_pのx,y座標ですa,b,p]。

  • この方法は非常にエレガントだと思いますが、もっと良い方法があると思います。
于 2012-02-23T18:32:12.927 に答える
1 
    ArrayList<Point> points=new ArrayList();//YOUR POINTS


    Point a=new Point(1,1);
    Point b=new Point(1,1);
    Point ABcenter=new Point((a.x+b.x)/2,(a.y+b.y)/2);//THE CENTER OF THE A AND B POINTS ,USE A OR B IF YOU WANT
    int furthestid=0;
    float furthestdis=0;
    for(int c=0;c<points.size();c++)
    {
        if(calculate_distance(ABcenter.x,ABcenter.y,points.get(c).x,points.get(c).y)>furthestdis)
        {
            furthestid=c;
        }
    }

//closestid  now contains the id of the furthest point ,use it like this points.get(c).x ...




public static double calculate_distance (float x1,float y1,float x2 ,float y2){
        return Math.sqrt((((x1-x2) * (x1-x2)) + ((y1- y2) * (y1- y2))));
}
于 2012-02-23T18:50:26.250 に答える
0

私はあなたが線ではなく線分について話していると仮定しています。最初に、線分からのポイント距離を見つける必要があります。この同様の質問で提案されている方法でそれを行うことができます。その後、すべての入力にわたって最小/最大距離を見つけます。

編集：また、このトップコーダーの記事からあなたは簡単に距離を見つけることができます：

//Compute the dot product AB ⋅ BC
int dot(int[] A, int[] B, int[] C){
    AB = new int[2];
    BC = new int[2];
    AB[0] = B[0]-A[0];
    AB[1] = B[1]-A[1];
    BC[0] = C[0]-B[0];
    BC[1] = C[1]-B[1];
    int dot = AB[0] * BC[0] + AB[1] * BC[1];
    return dot;
}
//Compute the cross product AB x AC
int cross(int[] A, int[] B, int[] C){
    AB = new int[2];
    AC = new int[2];
    AB[0] = B[0]-A[0];
    AB[1] = B[1]-A[1];
    AC[0] = C[0]-A[0];
    AC[1] = C[1]-A[1];
    int cross = AB[0] * AC[1] - AB[1] * AC[0];
    return cross;
}
//Compute the distance from A to B
double distance(int[] A, int[] B){
    int d1 = A[0] - B[0];
    int d2 = A[1] - B[1];
    return sqrt(d1*d1+d2*d2);
}
//Compute the distance from AB to C
//if isSegment is true, AB is a segment, not a line.
double linePointDist(int[] A, int[] B, int[] C, boolean isSegment){
    double dist = cross(A,B,C) / distance(A,B);
    if(isSegment){
        int dot1 = dot(A,B,C);
        if(dot1 > 0)return distance(B,C);
        int dot2 = dot(B,A,C);
        if(dot2 > 0)return distance(A,C);
    }
    return abs(dist);
}

基本的なジオメトリに精通している場合、コードには自己説明があると思いますが、精通していない場合は、記事を読む必要があります。問題がある場合は、私たちがお手伝いします。

于 2012-02-23T18:31:42.530 に答える
0

私はあなたがユークリッド距離を意味すると仮定しています。飛行機で作業している場合、答えは簡単です。

まず、次の形式で直線の方程式を計算します

ax + by + c = 0

スロープインターセプト形式では、これはと同じです

y = (-a/b)x + (-c/b)

次に、任意の点（p、q）から線までの距離を次のように計算します。

|a*p + b*q + c| / (a^2 + b^2)^(1/2)

2次元を超える場合は、パラメーター化されたベクトルの観点から考えるのがおそらく最も簡単です。これは、ライン上のポイントを次のように考えることを意味します

p(t) = (A1 + (B1-A1)*t, A2 + (B2-A2)*t, ..., An + (Bn-An)*t)

ここで、2つのポイントはとA = (A1,...,An)ですB = (B1,...,Bn)。X = (X1,...,Xn)他の点にしましょう。X次に、との間の距離、p(t)に対応する線上の点tは、の平方根です。

[(A1-X1) + (B1-A1)t]^2 + ... + [(An-Xn) + (Bn-An)t]^2

線までの距離は、この距離を最小化する一意の値p(t)である場所までの距離です。tそれを計算するには、に関する導関数を取り、にt設定し0ます。ここからは非常に簡単な問題なので、少しお任せします。

さらにヒントが必要な場合は、このリンクをチェックして、3次元の場合を確認してください。

于 2012-02-23T18:34:11.773 に答える
0

問題があなたが述べたとおりである場合、各ポイントの距離を計算し、これらの最小のものを選択するよりもはるかに優れた方法はありません。

ただし、AとBを通過する線の一般化された線方程式を使用すると、距離の計算を少し簡略化できます。これは、次の形式の方程式になります。ax + by + c = 0

2つの任意の点を通る直線について、このような方程式を非常に簡単に計算できます。

x * (A.y - B.y) + y * (B.x - A.x) + A.x * B.y - A.y * B.x、

すなわちa = A.y - B.y、b = B.x - A.xおよびc = A.x * B.y - A.y * B.x

a * x + b * y + c直線のこのような方程式を計算したので、 xとyをPの座標に置き換えることにより、平面内の任意の点Pから直線までの距離を計算できます。

abs(a * P.x + b * P.y + c) / sqrt(a * a + b * b)。abs(a * P.x + b * P.y + c)ただし、分母はすべてのポイントで同じになるため、分母を無視して、最小のポイントを選択するだけで済みます。

一般化された方程式ができたら、線までの2次元距離を計算する方法を説明するリンクを次に示します。

于 2012-02-23T18:37:46.520 に答える