Алгоритм для точек внутри полилинии необъяснимо дает сбой (AutoCAD)

Я использую .NET API для Autocad, у меня есть алгоритм (который я не писал) для определения того, находится ли точка внутри многоугольника (только прямые линии).

Я неоднократно тестировал свою команду на одном и том же 51 полигоне. 99% будет работать идеально. Время от времени он дает сбой на одном или нескольких полигонах, возвращая false для более чем 2000 точек, которые я создаю внутри ограничивающей рамки полилинии. Я видел, как это терпит неудачу, когда полилиния представляет собой простой прямоугольник, и все точки распределены по сетке внутри полилинии. В этом случае он должен был вернуть true более 2000 раз. Он никогда не подведет только по одному из пунктов, он подведет все. Я подтвердил, что точки создаются правильно там, где я их ожидаю, и что вершины многоугольника находятся там, где я их ожидаю. Когда это не удается, последняя угловая переменная для последней точки находится точно в двойном 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);
    }

c# com autocad
person Steve M    schedule 13.05.2013    source источник

Ответы (3)


arrow_upward
1
arrow_downward

Некоторые идеи:

  • сравнение с плавающей запятой должно выполняться с использованием допуска, это может привести к произвольным результатам, особенно в случае, когда точка лежит на полилинии (то же замечание для point3d, их необходимо сравнивать с использованием допуска)

  • возможно, последняя точка вашей полилинии находится в том же месте, что и первая, в этом случае угол не может быть вычислен (возможно, поэтому вы получаете двойное значение числа пи для последней точки). Затем вы должны проверить, что первая и последняя точки равны.

  • Я не уверен, что ваш алгоритм работает независимо от того, идет ли ломаная линия по часовой стрелке или против часовой стрелки (я думаю, да)

  • вы можете преобразовать свою полилинию в область и положиться на метод сдерживания точки области

person loic    schedule 16.05.2013
comment
Я обнаружил, что алгоритм неисправен, я закончил преобразование его в регион с помощью BREP API. - person Steve M; 19.05.2013

arrow_upward
1
arrow_downward

другой метод. Сделайте одну «временную» точку за пределами полигона (найдите минимум X и Y и сделайте точку с X-1 и Y-1). Затем проведите линию между вашей точкой и новой «временной» точкой. Проверяем, пересекает ли эта линия многоугольник — используйте polyline.IntersectWith. Если количество точек пересечения нечетное - ваша точка внутри, если количество точек пересечения четное - ваша точка не внутри. Это работает для меня, надеюсь, это поможет и вам. Если у вас возникнут проблемы с реализацией этого, я могу отправить вам пример кода. С уважением, Добриян Бенов

person Dobriyan Benov    schedule 28.02.2015

arrow_upward
0
arrow_downward

Я использовал некоторый код от Кина Уолмсли для преобразования 3D-линий в 2D-линии. Но имейте в виду, что следующее не (всегда) верно:

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

pt == npt;

Я столкнулся с этим, используя его на полилинии с трехмерными вершинами. В итоге я использовал npt.

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

person Woestebanaan    schedule 19.10.2016