Найти углы / ребра на форме (минимальные вершины, которые могут определить эту форму) - PullRequest
Новая
       66

Найти углы / ребра на форме (минимальные вершины, которые могут определить эту форму)

0 голосов
/ 23 октября 2018

Я пытаюсь получить углы следующей формы:

enter image description here

Под углами я подразумеваю это (красные точки):

enter image description here

Минимальное количество точек, которые могут определять эту форму.

И я реализовал следующее: 

    public Shape Optimize()
    {
        // If the vertices are null or empty this can't be executed
        if (vertices.IsNullOrEmpty())
            return this; // In this case, return the same instance.

        if (!edges.IsNullOrEmpty())
            edges = null; //Reset edges, because a recalculation was requested

        // The corners available on each iteration
        var corners = new Point[] { Point.upperLeft, Point.upperRight, Point.downLeft, Point.downRight };

        //The idea is to know if any of the following or previous vertice is inside of the the array from upside, if it is true then we can add it.

        Point[] vs = vertices.ToArray();

        for (int i = 0; i < vertices.Count - 1; ++i)
        {
            Point backPos = i > 0 ? vs[i - 1] : vs[vertices.Count - 1],
                  curPos = vs[i], //Punto actual
                  nextPos = i < vertices.Count - 1 ? vs[i + 1] : vs[0];

            // We get the difference point between the actual point and the back & next point
            Point backDiff = backPos - curPos,
                  nextDiff = nextPos - curPos,
                  totalDiff = nextPos - backPos;

            if (corners.Contains(backDiff) || corners.Contains(nextDiff) || corners.Contains(totalDiff))
                AddEdge(curPos, center); // If any of the two points are defined in the corners of the point of before or after it means that the actual vertice is a edge/corner
        }

        return this;
    }

Это работает с прямоугольными фигурами, но повернутые фигуры очень четкие, поэтому этот код работает не очень хорошо:

enter image description here

  • Синие пиксели (на этом фото и ниже) переменная vertices, обработанная методом Optimize.
  • Пиксели зеленого цвета - это обнаруженные углы / края (на обеих фотографиях).

Норезкость формы определяет только боковой наклон, так что я могу сделать, чтобы улучшить это?

Кроме того, я протестировал Accord.NET BaseCornersDetector унаследованные классы , но лучший результат достигается при HarrisCornersDetector , но:

enter image description here

Многие края / углы являются необходимыми, и онинаходятся не в нужном месте (см. первое фото).

1 Ответ

0 голосов
/ 23 октября 2018

Что ж, после нескольких часов исследований я нашел библиотеку под названием Simplify.NET , которая внутренне выполняет алгоритм Рамера-Дугласа-Пекера .

Также вы можетеинтересует алгоритм Брезенхема , с этим алгоритмом вы можете нарисовать линию, используя две точки .

С помощью этого алгоритма вы можете проверить, не слишком ли велик ваш допуск,сравнивая фактические точки и точки, которые выводит этот алгоритм, и создавая некоторый процентный калькулятор сходства.

Наконец, интересно упомянуть Вогнутый корпус и Выпуклый корпус алгоритмы.

Все это связано с Unity3D.

Мои выводы:

enter image description here

enter image description here

И моя реализация .

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

Вы можете увидеть пример реализации здесь .Спасибо @ Bunny83.

...