按顺时针顺序排序点 | Baeldung中文网

1. Introduction

Let’s imagine that we have a set of points on a plane that we’d like to connect to draw a closed shape. First, we’d need to sort those points.

In our tutorial, we’re going to walk through a method that can sort points in clockwise order.

2. Problem Explanation

Given a set of 2D points (each represented by and coordinates), we would like to sort these points in clockwise order. To begin, we need to view these points around a center point. This center-point can be at the (0, 0) coordinates, or it could be at any arbitrary point on the 2D plane. Based on the requirements, we can choose which center point is better.

In our scenario, we’ll estimate the center point as the mean of the given points. This is shown in the following figure where we have 3 points sorted around the center point:

SP-1

There are a few points to note here. First, we aren’t estimating the convex hull (the convex that encapsulates all points), but we’d like to find a closed path that goes through all the points in a clockwise order. Thus, it is fine to sort some points in the following way:

SP 2

However, for the same set of points, if we estimate the convex hull, we’ll only include points 1, 2, 3, and 5 as follows:

SP 3

One last thing to note is that we aren’t going to cover the exceptional case where all points lie on a straight line.

3. Algorithm Idea

Let’s walk through an example given the set of points , , , , , and as shown: SP 4

The first thing we need to do is to find the center point of the given points:

SP 5

Then we estimate the angle between each point and the center:

SP 6

Since we need to sort the points in clockwise order, the first point will be point as it falls in the $4^{th}$ quadrant. Next will be point as it falls in the $3^{rd}$ quadrant. Points and are in the $2^{nd}$ quadrant; however, comes first as it is closer to $\pi$ , and is next. Finally, we have points and in the $1^{st}$ quadrant, but both are at angle 0^o . In this tutorial, we decided to break the tie by the distance from the center:

SP 7

Since point is closer to the center than point , becomes the $5^{th}$ point, and is the last point in our order:

SP 8

The final order in the given example will be , , , , , .

4. Flow-Chart

Now let’s see more details on how to design the algorithm.

From a high-level perspective, we have an array of points that we need to sort according to some criteria. We can use any sorting algorithm and provide the right comparator to do the job; however, in our case, we need to add some pre- and post-processing steps.

For the pre-processing steps, we need to loop over the points to get the center point. Then we subtract this center point from all the given points so that we translate all the points to the new origin (center point).

Next, we call our sorting algorithm (like Quicksort or Bubble-Sort) with our comparePoints function to get the points sorted according to our defined criteria. Finally, we re-add the center point to the sorted points to translate them back to the original location.

4.1. Sort Points Flow-Chart

Let’s start with the high-level idea illustrated in the following flow-chart:

SP FLOW 1

4.2. Compare Points Flow-Chart

Now let’s dig deeper inside the comparePoints function. In this function, we get two points as inputs, and we need to return true if the first point comes before the second point, and false otherwise. If we assume we have another function telling us the angle of any point relative to some center point from to $2\pi$ , then we can compare the two angles directly. In the case of a tie, we can compare the distance between each point and the center point, and then choose the smallest one.

The following flow-chart illustrates this idea. The center point is $\{0, 0\}$ because we translated all of our points around the center point in the pre-processing step:

SP FLOW 2

The details for the getAngle and getDistance functions are going to be in the pseudocode.

5. Pseudocode

Now let’s look at simple pseudocode for our algorithm. The pseudocode starts with the general algorithm of finding the center point, and then translates all the points to this center. Next we call the sort function with our custom comparePoints function. Finally, we move the sorted points back to the original locations:

algorithm sortPointsCW(Points):
    // INPUT
    //    Points = a set of 2D points
    // OUTPUT
    //    Points sorted in a clockwise order around their center

    pt_center <- (0, 0)
    for pt in Points:
        pt_center.x <- pt_center.x + pt.x
        pt_center.y <- pt_center.y + pt.y

    n <- the number of points in Points

    pt_center.x <- pt_center.x / n
    pt_center.y <- pt_center.y / n

    for pt in Points:
        pt.x <- pt.x - pt_center.x
        pt.y <- pt.y - pt_center.y

    sort Points using function comparePoints for comparison

    for pt in Points:
        pt.x <- pt.x + pt_center.x
        pt.y <- pt.y + pt_center.y

    return Points

Our comparePoints function then calls the getAngle and getDistance functions for each pair of points. The function returns true in the cases where the first angle is bigger than the second angle. In the cases where the angles are equal, or the first distance is less than the second distance:

function comparePoints(pt_center, pt_1, pt_2):
    // INPUT
    //    pt_center = the center point around which to sort
    //    pt_1, pt_2 = points to compare
    // OUTPUT
    //    Returns true if pt_1 comes before pt_2 in the clockwise order

    angle_1 <- getAngle((0,0), pt_1)
    angle_2 <- getAngle((0,0), pt_2)
    if angle_1 < angle_2:
        return true

    d1 <- getDistance((0,0), pt_1)
    d2 <- getDistance((0,0), pt_2)

    if (angle_1 = angle_2) and (d1 < d2):
        return true

    return false

Now let’s see how to estimate the angle. We’re going to assume that we’re using a function like atan2 that exists in many programming languages. This function estimates the angle using inverse tan based on the value of and , and returns the result in the range $-\pi$ to $\pi$ . In our case, we need the angle to be between and $2\pi$ . One way to do this is if the angle is less than , we add $2\pi$ . Thus, the final value of the angle will be in the desired range from to $2\pi$ :

function getAngle(pt_center, pt):
    // INPUT
    //    pt_center = the center point from which to measure the angle
    //    pt = the point whose angle is being measured
    // OUTPUT
    //    the angle (from 0 to 2*PI) of pt relative to pt_center

    x <- pt.x - pt_center.x
    y <- pt.y - pt_center.y

    angle <- atan2(y, x)

    if angle <= 0:
        angle <- 2 * PI + angle

    return angle

As for the distance, we can use simple Euclidean distance as the square root ( sqrt ) of the sum of the square of the differences for all axes. In practice, we can get rid of the square root step and return the squared distance (in our scenario the distance is always between some point and the center point):

function getDistance(pt_1, pt_2):
    // INPUT
    //    pt_1, pt_2 = the points between which to calculate the distance
    // OUTPUT
    //    the Euclidean distance between pt_1 and pt_2
    
    x <- pt_1.x - pt_2.x
    y <- pt_1.y - pt_2.y
    
    return sqrt(x * x + y * y)

Please note that the sorting algorithm itself is out of the scope of this tutorial. We can use any available sorting algorithm like Quicksort to get a complexity of $O(n\: log(n))$ .

6. Complexity

The time complexity of our algorithm is the complexity of the selected sorting algorithm. If we choose Quicksort, the overall algorithm complexity will be $O(n\: log(n))$ . The reason is that we only have loops of complexity O(n) for pre- and post-processing. Then we call the sorting algorithm with our custom compare function.

As for the space complexity, the algorithm doesn’t need to store any information apart from the center point. Therefore, the space complexity is .

7. Conclusion

In this article, we presented a method to sort points in clockwise order. The idea depends on any general sorting algorithm with some pre- and post-processing steps. We illustrated the algorithm through an example, flow-charts, and pseudocode. Finally, we provided a simple complexity analysis of space and time complexities for the presented method.

Persistence

REST

Security