如何按顺时针/逆时针方向对所有多边形点进行排序？

问题描述

我一直在阅读有关Jarvis算法的文章，虽然它能够按顺时针方向对所有"外部点"进行排序，但内部点被忽略，如下所示：

有没有人知道有没有其他算法或我必须实现的其他方法来按时钟方向对每个点进行排序？

谢谢。

推荐答案

Graham scan中的第一步是按polar angle对每个坐标进行排序。通过选择任意(x, y)对作为您的"中心"，您可以计算每个点相对于您的中心的极角，然后根据该角度对它们进行排序。最终结果是按顺时针/逆时针方向对多边形点进行排序。

// Example program
#include <iostream>
#include <string>
#include <math.h>
#include <cmath>
#include <vector>
#include <algorithm>

class point {
  public:
    //default consructor sets point to 0,0
    point() { x=0; y=0; angle = 0; }

    //manually assign point
    point(int xin, int yin) { x=xin; y=yin; angle = 0; }

    //other constructors
    point(const point &p) { x = p.x; y = p.y; angle = p.angle; }
    point &operator=(const point &p) { x = p.x; y = p.y; angle = p.angle; return *this; }


    //get angle between this point and another
    double get_angle(point &p) {
        //check to make sure the angle won't be "0"
        if(p.x == this->x) { return 0; }

        //cast to double, or risk losing precision
        return( atan( double(p.y - this->y) / double(p.x - this->x) ) );
    }

    //for sorting based on angles
    //If you'd like, you can also modify the operator to behave differently,
    //such as checking the radii of the points if the lengths are the same - 
    //this would require some modification of the point class. 
    bool operator<(const point &p) const {
        return(angle < p.angle);
    }


    //and then there's these things
    void set_x(int xin) { x = xin; }
    void set_y(int yin) { y = yin; }
    void set_angle(double d) { angle = d; }

    int get_x() const { return x; }
    int get_y() const { return y; }
    double get_angle() const { return angle; }

  private:
    int x;
    int y;
    double angle;
};

//-----------------------------------------------------------------------------

//makes printing points easier
std::ostream &operator<<(std::ostream &os, const point &p) {
    os << "x: " << p.get_x() << "	y: " << p.get_y() << "	angle: " << p.get_angle();
    return os;
}

//=============================================================================

int main()
{
    //create a vector for points - vectors can use std::sort
    std::vector<point> points;

    point new_p(0, 0);
    for(int i=0; i<10; i++) {
        //fill the array with some random points
        //your actual data goes here - if you are using random points, don't
        //forget to seed the rng

        points.push_back(point(rand() % 100, rand() % 100));
    }


    //pick a random point to be the center
    //your data also goes here - the center doesn't have to be in the list
    point center = points[rand() % 10];

    std::cout << "center
" << center << std::endl << std::endl;

    //sort all points by polar angle
    //be sure to use &references, otherwise your changes won't go through
    for(point &p : points) {
        double angle = center.get_angle(p);
        p.set_angle(angle);
    }

    //sort the points using overloaded < operator
    //this program sorts them counterclockwise; you can flip the vector or
    //overload a different operator to get your desired effect
    std::sort(points.begin(), points.end());


    //tadaa!
    for(point &p : points) {
        std::cout << p << std::endl;
    }
}

tl；dr使用atan((y-y0) / (x-x0))可以根据某个参考点(x0, y0)计算点的极轴角度。基于这些角度的排序允许您按顺时针或逆时针方向对所有点进行排序。

祝你好运！

这篇关于如何按顺时针/逆时针方向对所有多边形点进行排序？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！