直線から最も遠い点を見つける

Question

私は点の配列だけでなく、さらに2点（AとB）を持っています。最後の2つの点は線を形成し、私の配列内のどの点が線から最も離れているのかを調べようとしています。 Javaでこれをどうやってやるのだろうか？

私はそれがAとBからの距離を見つけるための線に沿ったものかどうか疑問に思っていますが、それは私の頭の中にうまくいきません。

追加情報： I と考えると、は線分です。これがQuickHullであるとすれば、それが違いを生むかどうかはわかりません。 私は数学や数式に関しては一番大きいとは言いませんでした。ありがとう！

Answer 1

注、 最小値はです。 abはすべての人にとって一定であるため、最小面積を持つトライアングルも最小値hを保証します。

あなたは、[x_a,x_b,x_pとy_a,y_b,y_pがa,b,pのx,y座標はそれぞれ】

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

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

• 私はこの方法が非常にエレガントだと感じていますが、それはより良い方法があると信じています。

Answer 2

私はラインセグメントではなくラインについて話していると仮定しています。まず、あなたのラインセグメントからあなたのポイントの距離を見つける必要があります。this similar questionで提案されている方法のように、すべての入力に対して最小/最大距離を見つけることができます。

編集：this top coder articleからもあなたは、単に距離を見つけることができます。

//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); 
} 

を使用すると、基本的な幾何学に精通している場合、私は、コードは自己説明を持っていると思いますが、あなたが慣れていない場合、あなたがする必要がありますあなたが問題を抱えている場合は、私たちがあなたを助けることができる記事を読んでください。あなたがcompute the areaこれらtrianles作成できる

[hがabからpからの距離である] (ab) * h /2、および：その領域で示されているアレイ内の各p各3点[a,b,p]はtrianleを形成

Answer 3

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

まず、傾き、切片形態において

ax + by + c = 0 

形でラインの方程式を計算し、これは

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

同じである今の任意の点（Pからの距離を計算しますq）を行ごとに

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

2次元以上の場合は、おそらくparametrizエドベクタ。これは、2つの点がA = (A1,...,An)とB = (B1,...,Bn)です

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

としてライン上の点を考えてのことです。 X = (X1,...,Xn)を他の点にしてください。次いでXとp(t)間の距離は、tに対応するライン上の点は、

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

の平方根である線までの距離がtこの距離を最小化するユニークな値であるp(t)までの距離です。これを計算するには、tに関して微分を取って0に設定します。ここからは非常に簡単な問題ですので、私はあなたにそのビットを残します。

さらなるヒントが必要な場合は、うまく縮小する3次元のケースについてはthis linkをチェックしてください。

Answer 4

私はすばやくGoogle検索がうまく機能しました。

http://www.codeguru.com/forum/printthread.php?t=194400

Answer 5

あなたはそれを述べてきたような問題がある場合は、各ポイントの距離を計算し、これらの最小を選択するよりもずっと良く行うことはできません。あなたはAとBを通過する。これは、あなたがAのために、このような方程式を計算することができ、フォーム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

今度は行のためのそのような方程式を計算していることは、Pの座標でxとyを代入することにより線a * x + b * y + cに平面内の任意の点Pからの距離を計算することができる：

abs(a * P.x + b * P.y + c)/sqrt(a * a + b * b)。分母は、すべての点で同じになるようにしかし、あなたはそれをigonoreと単にabs(a * P.x + b * P.y + c)はここ

最小となるポイントを選んでもよいことは、あなたがそれだたらラインに2-Dの距離を計算する方法を説明しlinkです一般化された方程式。

Answer 6

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)))); 
}