Как удалить лишние вершины из списка

Question

У меня есть список вершин, т.е. List<Point>, который содержит следующие точки для квадрата: (0,0), (1,0), (2,0), (3,0), (4,0), (4,1), (4,2), (4,3), (4,4), (3,4), (2,4), (1,4), (0,4), (0,3), (0,2), (0,1), (0,0)

Чтобы нарисовать квадрат, мне просто нужно четыре точки (0,0), (0,4), (4,4), (4,0), как мне удалить лишние (что делает прямую линию) точки из списка

Это не всегда квадрат, в основном я хочу уменьшить количество точек, если они образуют прямую линию. Например, (0,0), (0,1), (0,2), (0,3), (0,4) делает прямую линию вместо того, чтобы рисовать все четыре точки, было бы быстро нарисовать линию из точек (0,0), (0,4).

Answer 1

Рассмотрим три последовательных точки за раз (назовем их p0, p1, p2).Эти три точки коллинеарны (образуют одну линию), если p2 = p0 + k(p1 - p0), где k - произвольное действительное число.Мы можем выразить вышеупомянутое условие в терминах одновременных уравнений:

(x2 - x0) = k(x1 - x0)
(y2 - y0) = k(y1 - y0)

Теоретически все, что вам нужно сделать, это взять каждый набор из трех точек по очереди.Рассчитайте значение k для компонентов x и y;если они одинаковые, то линии коллинеарны, поэтому удалите p1.

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

Answer 2

http://mathworld.wolfram.com/Collinear.html

Answer 3

Один из способов сделать это автоматически - это взять точки, содержащие комбинацию minX, maxX, minY и maxY (то есть координаты с наибольшим разбросом и предполагая, что все остальные точки в массиве находятся в пределах прямоугольника).

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