怎么样判断平面上一个点是不是在一个多边形内部？

Hush

多边形是由顺时针点集定义的。

有哪位知道吗？

tarkey

把多边形切成三角形，把三角形的三个顶点和那个点连起来，算角度。
如果角度和是360度则是在该三角形内。

fujingqiu

好像春节以前才刚刚讨论过吧

Hush

是吗？我找找...我考虑过把多边形切成三角形，但似乎如果多边形是凹多边形的话，切出来的三角形可能在多边形外面，有什么确定的算法吗？

dujinrui

　判断点P是否在多边形中是计算几何中一个非常基本但是十分重要的算法。以点P为端点，向左方作射线L，由于多边形是有界的，所以射线L的左端一定在多边形外，考虑沿着L从无穷远处开始自左向右移动，遇到和多边形的第一个交点的时候，进入到了多边形的内部，遇到第二个交点的时候，离开了多边形，……所以很容易看出当L和多边形的交点数目C是奇数的时候，P在多边形内，是偶数的话P在多边形外。
为了统一起见，在计算射线L和多边形的交点的时候，1。对于多边形的水平边不作考虑；2。对于多边形的顶点和L相交的情况，如果该顶点是其所属的边上纵坐标较大的顶点，则计数，否则忽略；3。对于P在多边形边上的情形，直接可判断P属于多边行。

linghuye

//如果点在多边形内,则返回值为1.
//如果点在多边形外,则返回值为0.
//在边界上返回值不确定,可能0或1.
int is_point_in_polygon_cn(const point_type* P, int n, const point_type& tp)
{
        int i, j, b = 0;
        for (i = 0, j = n-1; i < n; j = i++)
        {
                if(((P.y <= tp.y  &&  tp.y < P[j].y)   ||  
                        (P[j].y <= tp.y  &&  tp.y < P.y))  &&  
                        tp.x < (P[j].x - P.x) * (tp.y - P.y) / (P[j].y - P.y) + P.x)
                        b = !b;
        }
        return b;
}

http://www.faqs.org/faqs/graphics/algorithms-faq/

Hush

谢谢楼上两位

tarkey

。。。平面上判断？还是空间中判断？空间中判断用角度来判断应该是效率比较高的方法。

bigbook2000

角度判断是有问题的，而且计算量太大，射线法是国际上公认的算法。

tarkey

我是说判断空间中一点是否在一个三角形面上用角度法。