c++ - 多边形内部或边界内的点

Question

我正在使用 http://www.ecse.rpi.edu/~wrf/Research/Short_Notes/pnpoly.html 中的算法,但是当输入点在边界内时，该算法对我来说是错误的。谁能帮我解决边界问题？感谢您的帮助。

这是主要功能

#include <iostream>
#include <Polygon.h>
using namespace std;

int main()
{
    vector<Point> v;
    //v.push_back(make_pair(3.0,3.0));
    v.push_back(make_pair(1.0,1.0));
    v.push_back(make_pair(1.0,5.0));
    v.push_back(make_pair(5.0,5.0));
    v.push_back(make_pair(5.0,1.0));
    Polygon *p = new Polygon(v);
    cout << "A: " << p->IsInside(make_pair(1.0,3.0)) << endl;
    cout << "B: " << p->IsInside(make_pair(3.0,1.0)) << endl;
    cout << "C: " << p->IsInside(make_pair(5.0,3.0)) << endl;
    cout << "D: " << p->IsInside(make_pair(3.0,5.0)) << endl;
    delete p;
    return 0;
}

这是检查函数

bool Polygon::IsInside(Point p)
{
    /*determine whether a point is inside a polygon or not
     *  polygon's vertices need to be sorted counterclockwise
     *  source :
     *      http://www.ecse.rpi.edu/~wrf/Research/Short_Notes/pnpoly.html
    */
    bool ans = false;
    for(size_t c=0,d=this->vertices.size()-1; c<this->vertices.size(); d=c++)
    {
        if( ((this->vertices[c].y > p.y) != (this->vertices[d].y > p.y)) &&
            (p.x < (this->vertices[d].x - this->vertices[c].x) * (p.y - this->vertices[c].y) /
                (this->vertices[d].y - this->vertices[c].y) + this->vertices[c].x) )
           ans = !ans;
    }
    return ans;
}

Answer 1

来自网站文档:“PNPOLY 将平面划分为多边形内部的点和多边形外部的点。边界上的点被分类为内部或外部。......”请再次阅读网站上提供的文档。它回答了您的问题。最后，您可能不得不忍受浮点计算的模糊性。