Обнаружение дуг и отрезков по совокупности точек

Question

Я готовлюсь к созданию программы для обнаружения дуг и отрезков из набора точек (x, y), которые следуют друг за другом и, как правило, они создают замкнутый многоугольник. Я просто не знаю с чего начать. Может быть, кто-то знает библиотеку "готов к работе" (можно заплатить), которая так за меня думает? Или, может быть, некоторые предложения алгоритмов, которые относительно легко реализовать? Я ищу любые советы.

Answer 1

Если ваши точки точно не попадают на дуги и сегменты, но вы пытаетесь найти наиболее близкое соответствие, см .: 'https://en.wikipedia.org/wiki/Curve_fitting'.

Если ваши точки точно следуют дугам или отрезкам, возможно, это закрытое решение подойдет вам. Предполагается, что дуги состоят как минимум из 4 точек. Вы можете создать дугу с любыми 3 точками, поэтому невозможно определить, должны ли они быть дугой или отрезком (если вы не используете угловой угол). С 4 точками вы можете сравнить, если точки (0,1,2) и (0,1,3) являются частью одной и той же дуги.

При создании дуговых объектов из 3-х точек, внутри рассчитывается радиус и центр, чтобы можно было их сравнивать. Чтобы найти круг из 3-х точек: https://math.stackexchange.com/questions/213658/get-the-equation-of-a-circle-when-given-3-points

     PolyCurve ArcsAndLines(List<Point3d> points)
    {
        var curve = new PolyCurve();
        Arc current = Arc.Unset;

        for (int i = 0; i < points.Count - 1; i++)
        {
            var areEqual = false;

            if (i + 3 < points.Count)
            {
                var arcA = new Arc(points[i], points[i + 1], points[i + 2]);
                var arcB = new Arc(points[i], points[i + 1], points[i + 3]);
                areEqual = AreEqual(arcA, arcB);
            }

            if (areEqual)
            {
                var start = current == Arc.Unset ? points[i] : current.StartPoint;
                current = new Arc(start, points[i + 1], points[i + 3]);
            }
            else
            {
                if (current != Arc.Unset)
                {
                    curve.Append(current);
                    current = Arc.Unset;
                    i++;
                }
                else
                {
                    curve.Append(new Line(points[i], points[i + 1]));
                }
            }
        }

        return curve;
    }

    bool AreEqual(Arc a, Arc b)
    {
        const double tol = 0.001;

        bool sameRadius = Math.Abs(a.Radius - b.Radius) < tol;
        if (!sameRadius) return false;

        bool sameCenter = a.Center.DistanceTo(b.Center) < tol;
        return sameCenter;
    }

'Кривая' - это список, содержащий отрезки линии и дуги.

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