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

Question

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

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

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

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

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

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

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

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

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

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

Answer 1

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

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

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

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

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

Мои выводы:

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

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

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