0

I'm using the .NET API for Autocad, I have an algorithm (which I did not write) for determining if a point lies within a polygon (straight lines only).

I have been testing my command on the same 51 polygons repeatedly. 99% it will work perfectly. Every once in a while it will fail on 1 or more of the polygons, returning false for over 2000 points I am creating inside the bounding box of the polyline. I have seen it fail when the polyline isa simple rectangle and all of the points lie distributed in a grid within the polyline. It should have returned true over 2000 times in that case. It will never fail for just 1 of the points, it will fail all of them. I have confirmed that the points are being correctly created where I expect them to be and that the vertices of the polygon are where I expect them to be. When it fails, the last angle variable for the last point is at exactly double PI.

I am not doing any multi-threading. The only possibly 'funny' thing I am doing is COM Interop with Excel. This is happening after the transaction has been committed for the part with this algorithm, and I am sure I am cleaning up all my COM objects. I have not been able to reproduce the failure without the COM Interop part but I don't think I've tested it enough yet to have enough absence of evidence.

Any ideas what could be wrong?

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);
    }
4

3 回答 3

1

一些想法：

  • 浮点比较必须使用容差进行，这可能会导致任意结果，尤其是在点位于折线上的情况下（point3d 的注释相同，必须使用容差进行比较）

  • 可能折线的最后一个点与第一个点位于同一位置，在这种情况下，无法计算角度（也许这就是为什么最后一个点得到双倍 pi 值的原因）。然后你应该测试是第一个点和最后一个点是相等的。

  • 无论折线是顺时针还是逆时针，我都不确定您的算法是否有效（我认为是的）

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

于 2013-05-16T19:52:03.427 回答
1

另一种方法。在多边形外做一个“临时”点（找到最小的 X 和 Y 并用 X-1 和 Y-1 做一个点）。然后在你的点和新的“临时”点之间划一条线。检查这条线是否穿过多边形 - 使用 polyline.IntersectWith。如果交叉点的数量是奇数 - 那么你的点在里面，如果交叉点的数量是偶数 - 你的点不在里面。这对我有用，希望它也能帮助你。如果您在实施时遇到问题，我可以向您发送示例代码。问候， 多布里扬·贝诺夫

于 2015-02-28T20:05:48.850 回答
0

我使用 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

于 2016-10-19T09:16:47.877 回答