令周围的坐标中心坐标 - JAVA [英] Order coordinates around center coordinate - JAVA

问题描述

我试图创建一个算法，订单围绕一个特定点的坐标，在此情况下;的中间点。

I'm trying to create an algorithm that orders coordinates around one certain point, in this case; the middle point.

我发现：<一href="http://stackoverflow.com/questions/11352110/arranging-coordinates-into-clockwise-order">this后，我碰到这个答复：

I have found: this post, and I came across this reply:

- 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.

由于我是比较新的这种算法，我决定问这里。上述书面答复使有些道理给我，但我不知道是什么意思这一点。

Since I am relatively new to this kind of algorithms I decided to ask it here. The reply written above makes somewhat sense to me, but I have no idea what is meant with that.

示例：

图：点击打开

具有图像上面，（2,2）的将是中心（绿点）。 如果一个人会得出一个圈围绕中心，它会走在红色的广场，这将是有序的，如：

Having the image above, (2,2) would be the center (green dot). If one would draw an 'circle' around that center, and it would go along the red squares, it would be ordered like:

（0,4） - >（2,4） - >（2,3） - >（4,3） - >（3,0） - >（1,1）

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

如果它会从屏幕左侧的顶部角落ofcourse开始。但是你明白了吧。

如果有人可以点我到正确的方向和/或给我一些伪code，我会大大AP preciate吧。

If someone could point me into the right-direction and/or give me some pseudo code, i'd greatly appreciate it.

谢谢！

推荐答案

所引用的答案给出了一个非常高层次的描述。你实际上并不需要的极坐标。特别是，你并不需要点到原点的距离。所有你需要的是x轴和，它从原点到各点的直线之间的夹角。

The quoted answer gives a very high level description. You don't actually need polar coordinates. Particularly, you don't need the distance of the points to the origin. All you need is the angle between the x-axis and the line that goes from the origin to the respective point.

根据这些角度，你可以创建一个比较，然后用<一个href="https://docs.oracle.com/javase/8/docs/api/java/util/Collections.html#sort-java.util.List-java.util.Comparator-"相对=nofollow>集合＃排序以点列表进行排序，通过这个比较。

Based on these angles, you can create a Comparator, and then use Collections#sort to sort the list of points, passing in this comparator.

有许多自由度的实现的细节。但是，这里有一个 MCVE ，使用一些我已经随时可以在这里从几何实用工具包，我写的方法：

There are many degrees of freedom for the details of the implementation. However, here is a MCVE, using some of the methods that I had readily available here from a geometry utilities package that I wrote:

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的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！