[求助]：[求助]：点与AcDbPolyline的关系

liwu2008

如何判定点与AcDbPolyline的关系，内部，外部，其上
有代码的能否共享

RedCAD

纯粹的几何学问题，在GOOGLE中用”几何学“搜索一下就可以了。

cadrd

你提了一个难题埃? 假如polyline自交的话，判断就更加困难了，希望有计算几何的高手解决，俺也学一招！

cutechun

纯数学问题！！http://astronomy.swin.edu.au/~pbourke/geometry/insidepoly/

suave

楼主所谓的pL线是闭合的吗？
一般是分为：
1。直线考虑在直线的上方，下方（或称左边，右边）和直线上。
2。多边形则考虑是多边形外，多边形内和在多边形边上。

第一种点坐标直接带入直线方程，判断方程与0的大小就行。
第二种
判断点P是否在多边形中是计算几何中一个非常基本但是十分重要的算法。以点P为端点，向左方作射线L，由于多边形是有界的，所以射线L的左端一定在多边形外，考虑沿着L从无穷远处开始自左向右移动，遇到和多边形的第一个交点的时候，进入到了多边形的内部，遇到第二个交点的时候，离开了多边形，……所以很容易看出当L和多边形的交点数目C是奇数的时候，P在多边形内，是偶数的话P在多边形外。

　　但是有些特殊情况要加以考虑。如图下图(a)(b)(c)(d)所示。在图(a)中，L和多边形的顶点相交，这时候交点只能计算一个；在图(b)中，L和多边形顶点的交点不应被计算；在图(c)和(d) 中，L和多边形的一条边重合，这条边应该被忽略不计。如果L和多边形的一条边重合，这条边应该被忽略不计。

为了统一起见，我们在计算射线L和多边形的交点的时候，1。对于多边形的水平边不作考虑；2。对于多边形的顶点和L相交的情况，如果该顶点是其所属的边上纵坐标较大的顶点，则计数，否则忽略；3。对于P在多边形边上的情形，直接可判断P属于多边行。由此得出算法的伪代码如下：

    count ← 0;
    以P为端点，作从右向左的射线L;
    for 多边形的每条边s
     do if P在边s上
          then return true;
        if s不是水平的
          then if s的一个端点在L上
                 if 该端点是s两端点中纵坐标较大的端点
                   then count ← count+1
               else if s和L相交
                 then count ← count+1;
    if count mod 2 = 1
      then return true;
    else return false;


　　其中做射线L的方法是：设P'的纵坐标和P相同，横坐标为正无穷大（很大的一个正数），则P和P'就确定了射线L。

　　判断点是否在多边形中的这个算法的时间复杂度为O(n)。

　　另外还有一种算法是用带符号的三角形面积之和与多边形面积进行比较，这种算法由于使用浮点数运算所以会带来一定误差，不推荐大家使用。



　　

bacchus

你是做什么项目