围绕中心坐标排序坐标 - JAVA

Question

在这种情况下，我正在尝试创建一种算法来围绕某个特定点对坐标进行排序；中间点。

我找到了：this post，我看到了这个回复：

- Find the center of the "circle," i.e., the average X and average Y
- Shift the X and Y values so all are relative to the new center.
- Convert to polar coordinates and sort by angle.

由于我对这种算法比较陌生，所以我决定在这里提问。上面写的回复我觉得有点意思，但我不知道那是什么意思。

示例：

图片：click to open

上面的图像，(2,2) 将是中心（绿点）。如果围绕该中心画一个 'circle'，并且沿着红色方块，它的顺序如下：

(0, 4)-> (2,4) -> (2,3) -> (4,3) -> (3,0) -> (1,1)

如果它从课程的左上角开始。但是你明白了。

如果有人能指出正确的方向and/or给我一些伪代码，我将不胜感激。

谢谢！

Answer 1

您可能希望将坐标视为向量并计算它们距中心点的长度。有了这些结果，您可以简单地按长度排序。

Answer 2

引用的答案给出了非常高层次的描述。您实际上并不需要极坐标。特别是，您不需要点到原点的距离。您只需要 x 轴与从原点到相应点的线之间的角度。

根据这些角度，你可以创建一个Comparator，然后使用Collections#sort对点列表进行排序，传入这个比较器。

实现细节有很多自由度。然而，这里有一个 MCVE，使用了一些我在此处编写的几何实用程序包中很容易获得的方法：

import java.awt.Point;
import java.awt.geom.Point2D;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Random;

public class SortPointsByAngle
{
    public static void main(String[] args)
    {
        Point center = new Point(2,2);
        List<Point> points = new ArrayList<Point>();
        points.add(new Point(0, 4));
        points.add(new Point(2, 4));
        points.add(new Point(2, 3));
        points.add(new Point(4, 3));
        points.add(new Point(3, 0));
        points.add(new Point(1, 1));

        List<Point> copy = new ArrayList<Point>(points);
        Collections.shuffle(copy, new Random(0));

        System.out.println("shuffled : "+stringFor(copy));
        Collections.sort(copy, 
            Collections.reverseOrder(byAngleComparator(center)));
        System.out.println("sorted   : "+stringFor(copy));
        System.out.println("reference: "+stringFor(points));
    }

    private static String stringFor(List<Point> points)
    {
        StringBuilder sb = new StringBuilder();
        boolean first = true;
        for (Point p : points)
        {
            if (!first)
            {
                sb.append(",");
            }
            first = false;
            sb.append("("+p.x+","+p.y+")");
        }
        return sb.toString();
    }

    /**
     * Creates a comparator that compares points by the angle that the line
     * between the given center and the point has to the x-axis.
     * 
     * @param center The center
     * @return The comparator
     */
    public static Comparator<Point2D> byAngleComparator(
        Point2D center)
    {
        final double centerX = center.getX();
        final double centerY = center.getY();
        return new Comparator<Point2D>()
        {
            @Override
            public int compare(Point2D p0, Point2D p1)
            {
                double angle0 = angleToX(
                    centerX, centerY, p0.getX(), p0.getY());
                double angle1 = angleToX(
                    centerX, centerY, p1.getX(), p1.getY());
                return Double.compare(angle0, angle1);
            }
        };
    }

    /**
     * Computes the angle, in radians, that the line from (x0,y0) to (x1,y1) 
     * has to the x axis
     * 
     * @param x0 The x-coordinate of the start point of the line
     * @param y0 The y-coordinate of the start point of the line
     * @param x1 The x-coordinate of the end point of the line
     * @param y1 The y-coordinate of the end point of the line
     * @return The angle, in radians, that the line has to the x-axis
     */
    private static double angleToX(
        double x0, double y0, double x1, double y1)
    {
        double dx = x1 - x0;
        double dy = y1 - y0;
        double angleRad = Math.atan2(dy, dx); 
        return angleRad;
    }
}

输出为

shuffled : (3,0),(2,4),(2,3),(1,1),(4,3),(0,4)
sorted   : (0,4),(2,4),(2,3),(4,3),(3,0),(1,1)
reference: (0,4),(2,4),(2,3),(4,3),(3,0),(1,1)

围绕中心坐标排序坐标 - JAVA

Order coordinates around center coordinate - JAVA

java

algorithm

coordinates