求助～一个算法～～～

starcat2004

一个四边形，定义如下：
typedef        struct _tag_sjmVertex
{
        double        x;
        double        y;
} sjmVertex;

// 四边形的定义
typedef        struct _tag_sjmQuadrangle
{
        sjmVertex        LeftTop;
        sjmVertex        LeftBottom;
        sjmVertex        RightTop;
        sjmVertex        RightBottom;
} sjmQuadrangle;

如何判断一个点（double x, double y）是否在这个四边形内？ [em4] [em7]

kingmark

我笨。所以我的解法也比较蠢。切成两个三角形。判断两次。运气好，就只要一次。

starcat2004

kingmark: Re: 求助～一个算法～～～

我笨。所以我的解法也比较蠢。切成两个三角形。判断两次。运气好，就只要一次。

那么怎么判断是否在三角形内？ [em24]

kingmark

starcat2004: Re: Re: 求助～一个算法～～～


那么怎么判断是否在三角形内？ [em24]

：（
从该点引垂线，看是否与三角形相交。
还有很多其他方法，google去找吧。

fujingqiu

这种技术没什么用的，就透露给你吧：
每条边确定一个直线，这直线的方程形式如下：ax+by+c=0;
将点的坐标带入多项式ax+by+c。如果=0,此点在线上；如果>0，此点在线左边；如果<0，此点在线右边。
三条直线就有三个多项式，分别带入，如果符号相同就说明在同一侧。
如果构造直线的时候三个顶点是依次带入的，在同一侧意味着在三角形内部。
对于三角形和凸多边形都一样。

kingmark

http://msdn.microsoft.com/library/default.asp?url=/library/en-us/gdi/regions_6q3y.asp
http://msdn.microsoft.com/library/default.asp?url=/library/en-us/gdi/regions_3bn2.asp

什么样的多边形都可以。

fujingqiu

kingmark: Re:求助～一个算法～～～

http://msdn.microsoft.com/library/default.asp?url=/library/en-us/gdi/regions_6q3y.asp
http://msdn.m...

这倒是个好办法

jiacat

从点引一射线,与任何形状相交点为奇数在内部,为偶数在外部

zybx

先做排斥实验，如果点在四边形的外包矩形之外，就不用继续判断。
然后假设4个顶点为v1,v2,v3,v4，所求顶点为v0
那么边可以表示为v2-v1,v3-v2,v4-v3,v1-v4这样4个向量，
和对应向量v0-v1,v0-v2,v0-v3,v0-v4做叉乘，
如果得到的4个结果都大于或都小于0（取决于顶点的顺逆时针），那么点在内部。
如果有等于0的值，则在边界。
其余在外部。
这个方法可推广到任意多个顶点的多边形：）