在折线内的点的算法莫名其妙地失败(AutoCAD)

本文关键字:失败 AutoCAD 算法 折线 莫名其妙 | 更新日期: 2023-09-27 18:13:18

我正在使用Autocad的。net API,我有一个算法(我没有写)来确定一个点是否位于多边形内(仅限直线)。

我已经在相同的51个多边形上反复测试了我的命令。99%的效果都很好。每隔一段时间,它会在一个或多个多边形上失败,对于我在折线的边界框内创建的超过2000个点返回false。当折线是一个简单的矩形并且所有的点都分布在折线内的网格中时,我看到它失败了。在这种情况下,它应该在2000次以上返回true。它永远不会因为1分而不及格,它会因为所有的分而不及格。我已经确认了这些点是在我期望的地方正确创建的,多边形的顶点是在我期望的地方。当它失败时,最后一个点的最后一个角度变量正好是两倍PI。

我没有做任何多线程。我正在做的唯一可能"有趣"的事情是COM与Excel的互操作。这是在使用此算法的部分提交事务之后发生的,并且我确信我正在清理所有COM对象。我无法在没有COM互操作部分的情况下重现失败,但我认为我还没有测试到足够的证据。

你知道有什么问题吗?

bool IsInsidePolygon(Polyline polygon, Point3d pt)
    {
        int n = polygon.NumberOfVertices;
        double angle = 0;
        Point pt1, pt2;
        for (int i = 0; i < n; i++)
        {
            pt1.X = polygon.GetPoint2dAt(i).X - pt.X;
            pt1.Y = polygon.GetPoint2dAt(i).Y - pt.Y;
            pt2.X = polygon.GetPoint2dAt((i + 1) % n).X - pt.X;
            pt2.Y = polygon.GetPoint2dAt((i + 1) % n).Y - pt.Y;
            angle += Angle2D(pt1.X, pt1.Y, pt2.X, pt2.Y);
        }
        if (Math.Abs(angle) < Math.PI)
            return false;
        else
            return true;
    }
    public struct Point
    {
        public double X, Y;
    };
    public static double Angle2D(double x1, double y1, double x2, double y2)
    {
        double dtheta, theta1, theta2;
        theta1 = Math.Atan2(y1, x1);
        theta2 = Math.Atan2(y2, x2);
        dtheta = theta2 - theta1;
        while (dtheta > Math.PI)
            dtheta -= (Math.PI * 2);
        while (dtheta < -Math.PI)
            dtheta += (Math.PI * 2);
        return (dtheta);
    }

在折线内的点的算法莫名其妙地失败(AutoCAD)

一些想法:

  • 浮点比较必须使用容差进行,这可能会导致某种任意结果,特别是在点位于折线上的情况下(point3d也是如此,它们必须使用容差进行比较)

  • 也许你的折线的最后一点是在同一位置的第一个,在这种情况下,角度无法计算(也许这就是为什么你得到一个双pi值的最后一点)。然后你应该测试第一个点和最后一个点是否相等。

  • 我不确定你的算法是否有效,无论折线是顺时针还是逆时针(我认为是)

  • 您可以将折线转换为区域并依赖于区域点包含方法

另一个方法。在多边形外做一个"临时"点(找到最小的X和Y,用X-1和Y-1做一个点)。然后在你的点和新的"临时"点之间画一条线。检查这条线是否与多边形相交-使用polyline.IntersectWith。如果交叉点的数量是奇数,那么你的点在里面,如果交叉点的数量是偶数,那么你的点不在里面。这适用于我,希望它会帮助你也。如果你发现实现这个有麻烦,我可以给你发一个示例代码。问候,Dobriyan Benov

我使用了Kean Walmsley的一些代码将3d行转换为2d行。但请注意,以下内容并不(总是)正确:

Point2d pt = lwp.GetPoint2dAt(i);
Point2d npt = new Point2d(lwp.GetPoint3dAt(i).X, lwp.GetPoint3dAt(i).Y);
pt == npt;

我在折线上遇到了它,有3d顶点。我最终使用了npt

http://through-the-interface.typepad.com/through_the_interface/2007/04/iterating_throu.html