2

我有一个点数组，还有两个点（A 和 B）。最后两个点形成一条线，我试图找出我的数组中的哪些点离这条线最远。我将如何在 Java 中做到这一点？

我想知道这是否是为了找到与 A 和 B 之间的距离，但这在我的脑海中并不好。

附加信息：我认为这是一个线段。鉴于这是 QuickHull，我不知道它是否有所作为。在数学和公式方面，我从来都不是最伟大的，所以更多的解释会更好。谢谢！

4

5 回答 5

5

请注意，数组中每个点[a,b,p]的每 3 个点p形成一个三角形，其面积表示为：(ab) * h /2 [其中h距离p为ab]

您可以计算这些三角形创建的面积，并选择最小的. 由于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

我假设你的意思是欧几里得距离。如果你在飞机上工作，那么答案很简单。

首先，计算表格中线的方程

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)

其中两点是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

您可以很容易地为通过两个任意点的线计算这样的方程：

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)最小的点

这是一个链接，它解释了如何在拥有广义方程后计算到一条线的二维距离。

于 2012-02-23T18:37:46.520 回答
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 回答