0

我有一条线说线 L, lx + my + n = 0。现在，给定一些 K 点说，(x1,y1),(x2, y2)...(xk,yk)是否在线 L 上的 xy 平面上，我想在线 L 上找到一个点，比如 X (x0,y0)，使得 X 和“N”点之间的距离之和最小。解决这样一个问题的算法是什么。我想到了一个解决方案，首先我找到点的坐标与每个点的线 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

3

您可以使用最小二乘法，当然要进行适当的调整，因为您的问题有点不同。但是，这里是该过程的概述。

如果我们做a = -l/m和b = -n/m，我们可以写：

y = ax + b

这意味着您的直线中的点的形式为(x ,ax + b)，因此直线中的任何点(x ,y )与集合的第 i 个点之间的距离(xi, yi)为：

di = sqrt [ (x - xi)^2 + (ax + b - yi)^2 ]

现在我们必须最小化 的求和形式，0这不是一个简单的问题。在回归分析中，将距离的平方最小化是一种常用的近似方法，它的解决方案要简单得多。kdi

扩展正方形并重构我们：

di^2 = x^2 *k*(1 + a^2) + x (-2xi + 2kab - 2ayi) + (k*b^2 + yi^2 - 2byi + xi^2)

现在，计算 的di^2所有值的总和i并考虑到总和是线性算子，我们可以简单地替换xi为 的所有值的总和，xi对于yi,xi^2和yi^2(注意先计算平方值，然后将它们相加，尽管您不需要这些值）。对于不依赖于 的项i，它们将乘以k，因为它们将相加k。

现在我们将 的总和推导为零di^2，以求解方程x

d (di^2)/dx = 2k(1 + a^2) x + (-2*Sum(xi) + 2ab - 2a*Sum(yi)) = 0

最后，隔离x我们得到：

x = (2*Sum(xi) - 2kab + 2a*Sum(yi))/2k(1+a^2)

y当然会ax + b

因此，您只需要以编程方式计算 和 的总和xi，yi这应该非常简单。请检查代数，这也是理解该过程的一个很好的练习。

这是一个实现该算法并用一个简单案例检查它的示例程序。如果您的 k 点集合位于与您的点可以移动的线垂直的线上，那么最近的点应该是两条线的交点。

#include <stdio.h>

#define NUM_OF_POINTS 5

typedef struct
{
 double x;
 double y;
}point;


point findPoint (point *points, double slope, double intercept)
{
int i;
double sum_x = 0, sum_y = 0;
point your_point;


for( i = 0; i < NUM_OF_POINTS; ++i)
{
    sum_x += points[i].x;
    sum_y += points[i].y;
}

your_point.x = 2*(sum_x - NUM_OF_POINTS*slope*intercept + slope*sum_y)/(2*NUM_OF_POINTS*(1+slope*slope));

your_point.y = slope*your_point.x + intercept;

return your_point;


}

int main()
{
    int i = 0;
double slope = 1.0, intercept = 1.0;

    point point_arr [NUM_OF_POINTS], closest_point;

//Generate points in the line normal to y = slope*x + intercept

for (i = 0; i < NUM_OF_POINTS; i++)
{
    point_arr[i].x = 2.0 + i;
    point_arr[i].y = (-1.0/slope)*point_arr[i].x + 3.0;
}

closest_point = findPoint (point_arr, slope, intercept);
printf("Your point is %f, %f\n", closest_point.x, closest_point.y);


return 0;
}

直线是y = x + 1，点是在法线中生成的y = -x + 3。结果是 point (1,2)，它是两条线的交点。

DP

于 2014-06-12T17:57:29.360 回答
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

点 P 的轨迹使得 P 与给定的固定 n 个点（并非全部共线）的距离之和为常数（例如 D）是一个凸集，称为 n-椭圆，距离 D' 对应的 n-椭圆位于完全在 D 的 n 椭圆内，因为 D' < D。（2 椭圆是实际椭圆）

因此，给定线上的点之间存在唯一的（全局）最小值，并且爬山算法将起作用。

请参阅本文：n 椭圆和最小距离问题，以证明上述主张。

@DissidentPenguin：最小化 x_1 + x_2 不同于最小化 sqrt(x_1) + sqrt(x_2) （您与 sqrt(x_1 + x_2) 混淆）。

于 2014-06-13T06:07:56.720 回答
-1

我认为没有封闭形式的解决方案。

这意味着您将不得不使用数字近似值。

通用的

即，您需要实现直线double tot_dist(double x)上x的坐标并tot_dist计算距离总和的函数。

然后，您需要将它传递给可用的大量最小查找函数之一（例如，对于Mathematica、 R：optim、optimize）。

具体问题

如果您将点x沿直线移动一小段距离h，则从xto的距离X_k将根据直线与直线h*cos(a)之间a的角度而改变。这意味着您的解决方案满足 nice equation ，即，您可以使用牛顿法找到函数的零点，而不是使用通用最小化器（您将需要计算 的导数，但这应该没什么大不了的）。LxX_ksum(cos(a_k))=0double sum_cos_angle(double x)sum_cos_angle

沃罗诺伊

建议的Voronoi 图解决方案在这里不适用，因为这是一个全局问题（到所有点的距离），而 Voronoi 是针对局部问题（最近的一个点）。基本上，如果我们摆动一个点X_k，这个问题的解决方案就会改变。另一方面，Voronoi 图仅取决于最近的 2 个点的位置，因此，如果我们摆动一个远处的点，该图不会改变，因此，用它获得的任何解也不会改变。

于 2014-06-12T15:53:12.813 回答