0

私は行 L と言う行を持っていますlx + my + n = 0。ここで、いくつかの K ポイントが与えられた場合、ライン L 上の xy 平面上で、またはそうでない場合、 X と「N」ポイント間の距離の合計が最小になるよう(x1,y1),(x2, y2)...(xk,yk)に、ライン L 上のポイントを見つけたいとします。(x0,y0)そんな疑問を解決するアルゴリズムとは。最初に、各点から線 L に垂直な点の座標を見つける解決策を考えました(x1,y1),(x2, y2)...(xk,yk)。次に、垂線が線 L と交わるすべての点の平均点を見つけて、最小点を見つけました。しかし、そのようなアプローチは間違っています。問題を解決するための正しい方法を提案してください。これが私のコードです

#include <stdio.h>
#include <math.h>
typedef struct
{
     int x;
     int y;
}point;

double distance(point * A, double x, double y)
{
    return sqrt(pow(A->x - x, 2) + pow(A->y - y, 2));
}


int main()
{
    int i = 0 , j = 0, test = 0, number_of_warehouse = 0, A = 0, B = 0, C = 0;
    point * point_array , *closest_points, sum;
    double avgx = 0.0, avgy  = 0.0, Total_dist = 0.0;
    scanf("%d", &test);

    while (test--)
    {
        scanf("%d", &number_of_warehouse);
        point_array = malloc (sizeof(point) * number_of_warehouse);
        closest_points = malloc (sizeof(point) * number_of_warehouse);
        scanf("%d%d%d", &A, &B,&C);
        sum.x = 0;
        sum.y = 0;
        avgx = 0;
        avgy = 0;
        for(i = 0; i < number_of_warehouse; ++i)
        {
            scanf("%d%d", &(point_array[i].x), &(point_array[i].y));
            closest_points[i].x = (B*(B * point_array[i].x - A * point_array[i].y) - A *C)/ (A*A + B*B);
            closest_points[i].y = (A*((-1)* B * point_array[i].x + A * point_array[i].y) - B *C)/ (A*A + B*B);
            sum.x +=  closest_points[i].x;
            sum.y +=  closest_points[i].y;
        }
        Total_dist = 0.0;
        avgx = sum.x / number_of_warehouse;
        avgy = sum.y / number_of_warehouse;
        for(i = 0; i < number_of_warehouse; ++i)
        {
            Total_dist += distance(point_array + i, avgx, avgy);
        }
        printf("%.6f", Total_dist);
    }
    return 0;
}
4

4 に答える 4

2

ソリューションを次のように数学的に表すことができます:-

lx + my + n = 0

and 

Say you want to minimize squared distances then :-

S = sum((xk-x)^2 + (yk-y)^2) for all N points.

y = (n-mx)/l from line equation

S = sum((xk-x)^2 + (yk-(n-mx)/l)^2)

S = sum((xk-x)^2 + (ykl-n+mx)^2/l^2))

Diff wrt to x for minimizing 

S = sum(2*(xk-x) + 2m*(ykl-n+mx)/l^2) = 0

Distributing summation

S = sum(xk) - sum(x) + (m/l^2)*( l*sum(yk) - sum(n) + m*sum(x))) = 0

S = sum(xk) - N*x + (m/l^2)*(l*sum(yk) - N*n + m*N*x) = 0

(1-m^2/l^2)*N*x = sum(xk) + (m/l^2)*(l*sum(yk)-N*n)

Find x using the equation and then find y using line equation
于 2014-06-13T06:18:09.107 に答える
-1

クローズドフォームのソリューションはないと思います。

これは、数値近似を使用する必要があることを意味します。

ジェネリック

つまり、 は線上の座標でありdouble tot_dist(double x)、距離の合計を計算する関数を実装する必要があります。xtot_dist

次に、利用可能な膨大な数の最小検索関数の 1 つにそれを渡す必要があります (たとえば、Mathematicaの場合、R: optim、optimize )。

問題固有の

点をx線に沿ってわずかに移動するhと、 からxまでの距離は、線と線の間の角度X_kによって変化しh*cos(a)ます。つまり、一般的な最小化ツールを使用する代わりに、ニュートン法を使用して関数のゼロを見つけることができます ( の導関数を計算する必要がありますが、これは大したことではありません)。 ）。aLxX_ksum(cos(a_k))=0double sum_cos_angle(double x)sum_cos_angle

ボロノイ

これはグローバルな問題 (すべてのポイントまでの距離) であり、ボロノイはローカルな問題 (最も近い1 つのポイント) のためのものであるため、提案されたボロノイ ダイアグラムのソリューションはここでは適用できません。基本的に、一点を小刻みに動かすと、この問題の解決策が変わります。一方、ボロノイ図は最も近い 2 点の位置のみに依存するため、1 つの遠い点を小刻みに動かしても、図は変化せず、それによって得られる解も変化しません。X_k

于 2014-06-12T15:53:12.813 に答える