凸包不返回正确路径（C++ 中的格雷厄姆扫描）

Question

我已经完成了预期输出的算法：

p00 - p01,
p01 - p03 ,
p03 - p10,
p10 - p12 ,
p12 - p00

但我得到的是这个：

Convex hull:
p00 - p01
p01 - p03
p03 - p05
p05 - p10
p10 - p00

积分：
p00: (-5,-6)
p01: (6,-4)
p02: (5.5,-3)
p03: (8,0)
p04: (5,0)
p05: (4,2)
p06: (1,3)
p07: (0,2)
p08: (-1,1)
p09: (-1.5,2)
p10: (-1.5,6)
p11: (-5.5,1.5)
p12: (-8,-1)

我已经尝试了很长时间才能把它做好，但有些我做不到。谁能帮忙？我正在使用 C++

下面是我的代码：
我有 3 类 Vector2D、Point2D 和 Point2DSet 我的 Graham 扫描实现在Point2DSet 中的 buildConvexHull 函数。

Vector2D.cpp

#include "Vector2D.h"


Vector2D::Vector2D(double aX, double aY): fX(aX), fY(aY){ }

void Vector2D::setX(double aX){ fX = aX;}

double Vector2D::getX() const { return fX; }

void Vector2D::setY(double aY) { fY = aY;}

double Vector2D::getY() const { return fY; }

Vector2D Vector2D::operator+(const Vector2D& aRHS) const
{
    return (fX + aRHS.fX, fY + aRHS.fY);
}

Vector2D Vector2D::operator-(const Vector2D& aRHS) const
{
    return (fX - aRHS.fX, fY - aRHS.fY);;
}

double Vector2D::magnitude() const
{
    return sqrt((fX * fX) + (fY * fY));
}

double Vector2D::direction() const
{
    return atan(fY/fX);
}

double Vector2D::dot(const Vector2D& aRHS) const
{
    return (this->getX() * aRHS.getX()) + (this->getY() * aRHS.getY());
}

double Vector2D::cross(const Vector2D& aRHS) const
{
    return (this->getX() * aRHS.getY()) - (aRHS.getX() * this->getY());
}

double Vector2D::angleBetween(const Vector2D& aRHS) const
{
    double dntmr = magnitude() * aRHS.magnitude();
    if (dntmr > 0.0)
    {

    return acos(this->dot(aRHS) / (this->magnitude() * aRHS.magnitude()));

    }

    return  acos(1.0/1.0);
}

std::ostream& operator<<(std::ostream& aOutStream, const Vector2D& aObject)
{
    aOutStream << " ( " << aObject.fX << ", " << aObject.fY << " )\n";
    return aOutStream;
}

std::istream& operator>>(std::istream& aInStream, Vector2D& aObject)
{
    aInStream >> aObject.fX;
    aInStream >> aObject.fY;
    return aInStream;
}

Point2D

#include "Point2D.h"

static const Point2D gCoordinateOrigin;

// Private function gets direction in reference to aOther
double Point2D::directionTo(const Point2D& aOther) const 
{
    return (aOther.fPosition - fPosition).direction(); 
}

// Private Function to get magnitude in reference to aOther
double Point2D::magnitudeTo(const Point2D& aOther) const 
{
    return (aOther.fPosition - fPosition).magnitude();
}


Point2D::Point2D() : fId(" "), fPosition(0,0), fOrigin(&gCoordinateOrigin) { }

Point2D::Point2D(const std::string& aId, double aX, double aY) : fId(aId), fPosition(aX,aY), fOrigin(&gCoordinateOrigin) { }

Point2D::Point2D(std::istream &aIStream) : fOrigin(&gCoordinateOrigin)
{
    aIStream >> fId >> fPosition;
}


const std::string& Point2D::getId() const { return fId; }

void Point2D::setX(const double& aX) { fPosition.setX(aX); }

void Point2D::setY(const double& aY) { fPosition.setY(aY); }

const double Point2D::getX() const { return fPosition.getX(); }

const double Point2D::getY() const { return fPosition.getY(); }

void Point2D::setOrigin(const Point2D& aPoint) { fOrigin = &aPoint;}


Vector2D Point2D::operator-(const Point2D& aRHS) const
{
    return (fPosition - aRHS.fPosition);
}

// Return Direction with reference to origin
double Point2D::direction() const
{
    return fOrigin->directionTo(*this);
}

// Return Direction with reference to origin
double Point2D::magnitude() const
{
    return fOrigin->magnitudeTo(*this);;
}

bool Point2D::isCollinear(const Point2D& aOther) const
{
    if (fPosition.cross(aOther.fPosition) == 0) 
    {

        return true;
    }

    return false;
}

// Check to see if the point is Clockwise or not
bool Point2D::isClockwise(const Point2D& aP0, const Point2D& aP2) const
{
    double val = (fPosition.getY() - aP0.fPosition.getY()) * (aP2.fPosition.getX() - fPosition.getX()) -
        (fPosition.getX() - aP0.fPosition.getX()) * (aP2.fPosition.getY() - fPosition.getY());

    double val2 = fPosition.angleBetween(aP2.fPosition) - fPosition.angleBetween(aP0.fPosition);
    if (val < 0 ) 
    {

        return false;
    }

    return true;
}

bool Point2D::operator<(const Point2D& aRHS) const
{
    if (fPosition.getY() < aRHS.getY()) 
    {
        return true;
    }
    return false;
}

const Point2D& Point2D::getOrigin() const { return *fOrigin;}


std::ostream& operator<<(std::ostream& aOStream, const Point2D& aObject) 
{
    aOStream << aObject.fId << " : " << aObject.fPosition;
    return aOStream;
}

std::istream& operator>>(std::istream& aIStream, Point2D& aObject)
{
    aIStream >> aObject.fId >> aObject.fPosition;
    return aIStream;
}

Point2DSet

#include "Point2DSet.h"

#include <fstream>
#include <stdexcept>
#include <algorithm>

void Point2DSet::add(const Point2D& aPoint)
{
    fPoints.push_back(aPoint);
}

void Point2DSet::add(Point2D&& aPoint)
{
    fPoints.push_back(aPoint);
}

void Point2DSet::removeLast()
{
    fPoints.pop_back();
}

bool Point2DSet::doesNotTurnLeft(const Point2D& aPoint) const
{
    return fPoints[size()-1].isClockwise(fPoints[size()-2],aPoint);
}

// Comparator function for Stable_sort
bool orderByCoordinates(const Point2D& aLeft, const Point2D& aRight)
{
    return aLeft < aRight;
}

//Comparator function for Stable_sort
bool orderByPolarAngle(const Point2D& aLHS, const Point2D& aRHS)
{
    if (aLHS.isCollinear(aRHS))
    {
        return aLHS.magnitude() > aRHS.magnitude();
    }
    

    return aLHS.direction() < aRHS.direction();
}

void Point2DSet::populate(const std::string& aFileName)
{
    std::ifstream INPUT(aFileName);

    //std::ifstream INPUT("Pointers.txt");

    std::string id;
    double x;
    double y;

    while (INPUT >> id >> x >> y)
    {
        Point2D z(id, x, y);
        add(z);
    }

    INPUT.close();

}

void Point2DSet::buildConvexHull(Point2DSet& aConvexHull)
{
    aConvexHull.clear();
    sort(orderByCoordinates);
    sort(orderByPolarAngle);
    aConvexHull.add(fPoints[0]); // Origin (Smallest y-coordinate)
    aConvexHull.add(fPoints[1]); //
    //aConvexHull.add(fPoints[2]); 

    if (fPoints[2].isCollinear(fPoints[1])) {
        aConvexHull.add(fPoints[2]);
    }
//*/
    for(size_t i = 3; i < size(); i++) 
    {
        if (fPoints[i - 1].isCollinear(fPoints[i]))
        {
            continue; //i++;
        }
        if(aConvexHull.doesNotTurnLeft(fPoints[i]))
        {
            aConvexHull.removeLast();
        }
        aConvexHull.add(fPoints[i]);
    }//*/
    
}

size_t Point2DSet::size() const
{
    return fPoints.size();
}

void Point2DSet::clear()
{
    fPoints.clear();
}

void Point2DSet::sort(Comparator aComparator)
{
    stable_sort(fPoints.begin(), fPoints.end(), aComparator);
}

const Point2D& Point2DSet::operator[](size_t aIndex) const
{
    return fPoints[aIndex];
}

Point2DSet::Iterator Point2DSet::begin() const
{
    return fPoints.begin();
}

Point2DSet::Iterator Point2DSet::end() const
{
    return fPoints.end();
}

热烈欢迎任何其他改进。谢谢！

Answer 1

您的代码中存在一些问题。让我们从 Vector2D::direction() 开始，你应该使用 atan2，here 解释为什么。之后我们就可以正确的对点进行排序了。

现在主要算法。经过一些更改后，它看起来是：

aConvexHull.clear();
// Get points with bigger magnitude first.
sort(orderByMagnitudeDescending);
sort(orderByPolarAngle);

// We want to have the lowest point as the first element.
rotatePointsByLowest();

aConvexHull.add(fPoints[0]); // Origin (Smallest y-coordinate)
aConvexHull.add(fPoints[1]);
for(size_t i = 2; i < size(); i++) 
{
    if (fPoints[i - 1].isCollinear(fPoints[i]))
    {
        continue; //i++;
    }
    
    // There should be a loop instead of an if statement.
    while (aConvexHull.fPoints.size() > 2 && aConvexHull.doesNotTurnLeft(fPoints[i]))
    {
        aConvexHull.removeLast();
    }
    aConvexHull.add(fPoints[i]);
}//*/

算法需要找到最低点，然后根据角度遍历其余点。我添加了一个辅助函数 Point2DSet::rotatePointsByLowest:

void Point2DSet::rotatePointsByLowest() {
    auto lowestPoint = fPoints.begin();
    for (auto iterator = fPoints.begin() + 1;iterator != fPoints.end(); iterator++) {
        if (iterator->fPosition.fY < lowestPoint->fPosition.fY) {
            lowestPoint = iterator;
        } else if ((iterator->fPosition.fY == lowestPoint->fPosition.fY) && (iterator->fPosition.fX < lowestPoint->fPosition.fX)) {
            lowestPoint = iterator;
        }
    }
    std::rotate(fPoints.begin(), lowestPoint, fPoints.end());
}

应该应用更多的改进，但我想保持最小的更改以显示导致错误结果的问题。

Link 用于测试您的项目：https://onlinegdb.com/_ZXmQF2vJ

凸包不返回正确路径（C++ 中的格雷厄姆扫描）

Convex Hull Not Returning Right Path ( Graham Scan in C++)

c++

c++11

c++17

convex-hull

grahams-scan