C++程序 判断某一点或某一区域 是否在另一区域内部

代码中主要包含两个函数

//1\. 判断点point是否在区域rgn内部 1--内部 -1--边界 0--外部
template 
int isPointInRgn(const mVector &point, 
                 const std::vector > &rgn);

//2\. 判断区域B是否在区域A内部
template 
bool isRgnInRgn(const std::vector > &rgnB, 
                const std::vector > &rgnA);

使用时包含下面的头文件,然后直接调用函数即可


/*
    利用射线法判断某一点/一个区域 是否属于 另一区域
    2011 3 29 http://blog.lyqx.de/?p=592
*/

#ifndef IS_POINT_IN_RGN
#define IS_POINT_IN_RGN

#include 
#include 

template 
struct mVector //代表一个向量或一个坐标点
{
public:
    T x,y;

    mVector()
        : x(0),y(0)
    {}

    mVector(T a,T b)
    {
        set(a,b);
    }

    void set(T a,T b)
    {
        x=a;
        y=b;
    }

    //向量相加
    mVector add(const mVector &right)const
    {
        return mVector(x+right.x, y+right.y);
    }

    //向量相减
    mVector minus(const mVector &right)const
    {
        return mVector(x-right.x, y-right.y);
    }

    //向量点乘
    T multipy(const mVector &right)const
    {
        return x*right.x + y*right.y;
    }

    //判断两个向量是否平行 0--不平行 1--平行且方向相同 2--平行且方向相反
    int isParallel(const mVector &right)const
    {
        if(x*right.y == y*right.x) //平行
        {
            if(x) //x!=0
            {
                if(right.x/x >= 0) return 1;
                else return -1;
            }
            else //x==0
            {
                if(y)
                {
                    if(right.y/y >= 0) return 1;
                    else return -1;
                }
                else {return 1;}
            }
        }

        return 0;
    }

    //判断两个向量是否相交
    bool isIntersect(const mVector &right)const
    {
        return ! isParallel(right);
    }

    //判断两个向量是否垂直
    bool isPerpendicular(const mVector &right)const
    {
        return !(this->multipy(right));
    }

    //获取向量的长度
    double getLength()const
    {
        return std::sqrt(double(x*x + y*y));
    }
};

//获取一组点中的下一个点
template 
T getNextPoint(const std::vector &rgn, size_t index)
{
    if(index == rgn.size()-1 ) return rgn.at(0);
    else return rgn.at(index+1);
}

//获取一组点中的上一个点
template 
T getPrevPoint(const std::vector &rgn, size_t index)
{
    if(0 == index) return rgn.at(rgn.size()-1);
    else return rgn.at(index-1);
}

//获取向量的垂直方向 -1--向上 1--向下 0--水平
template 
int getVectorDirect(const mVector &vec)
{
    if(vec.y > 0) return -1;
    else if(vec.y <0) return 1;
    else return 0;
}

//判断点point是否在区域rgn内部 1--内部 -1--边界 0--外部
template 
int isPointInRgn(const mVector &point, const std::vector > &rgn)
{
    int num1=0, num2=0;
    for(std::vector >::size_type index=0; index != rgn.size(); index++ )
    {
        mVector nextPoint = getNextPoint(rgn,index);

        if(rgn[index].x prevVector = rgn[index].minus(getPrevPoint(rgn,index)), 
                       nextVector = getNextPoint(rgn,index).minus(rgn[index]);

            num2 += getVectorDirect(prevVector) + getVectorDirect(nextVector);

        }
        else if( (point.y > rgn[index].y && point.y < nextPoint.y)
            || (point.y > nextPoint.y && point.y < rgn[index].y) )
        {
            ++num1;
        }
        else {}//射线不经过边界线段
    }

    if((num1 + num2/2)%2) return 1;//奇数
    else return 0;
}

//判断区域B是否在区域A内部
template 
bool isRgnInRgn(const std::vector > &rgnB, const std::vector > &rgnA)
{
    for(std::vector >::size_type index = 0;
        index != rgnB.size(); index++)
    {
        if(! isPointInRgn(rgnB[index], rgnA) ) return false;
    }

    return true;
}

#endif //IS_POINT_IN_RGN

使用方法演示

#include "isPointInRgn.h"
#include 
#include 

int main()
{
    double x1,y1;

    std::vector > borderA,borderB;

    std::ifstream finA("in1.txt"), finB("in2.txt");

    while(finA>>x1>>y1)
    {
        borderA.push_back(mVector(x1,y1) );
    }

    while(finB>>x1>>y1)
    {
        borderB.push_back(mVector(x1,y1) );

    }

    std::cout<

其中in1.txt 和 in2.txt 为输入文件,内容如下

0 0
0 1
0 2
0 3
1 3
2 3
2 2
3 2
4 2
4 3
5 3
5 2
5 1
5 0
1 1
1 2
2 3
2 1

如果发现代码bug请在本页留言

代码下载:http://bit.ly/isPointInRegion 参考文章:判断区域B是否在区域A内部的快速算法 - xiaotie - 博客园

THE END