¿Cómo quito vértices redundantes de la lista

Question

tengo lista de vértices, es decir, List<Point>, que contiene siguientes puntos para plaza: (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)

para dibujar un cuadrado sólo necesito cuatro puntos (0,0), (0,4), (4,4), (4,0), ¿cómo puedo eliminar redundante (lo que hace en línea recta) puntos de la lista?

No siempre es cuadrado, básicamente quiero reducir el número de puntos si forman recta línea. Por ejemplo (0,0), (0,1), (0,2), (0,3), (0,4) hace una línea recta en lugar de dibujar los cuatro puntos, sería rápido trazar una línea desde los puntos (0,0), (0,4).

Answer 1

Mire tres puntos sucesivos a la vez (llamémoslos p0, p1, p2). Estos tres puntos son colineales (forman una sola línea) si p2 = p0 + k(p1 - p0) donde k es un número real arbitrario. Podemos expresar la condición anterior en términos de ecuaciones simultáneas:

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

En teoría, todo lo que necesita hacer es toma cada conjunto de tres puntos a su vez. Calcule el valor de k para los componentes x y y; si son iguales, entonces las líneas son colineales, entonces borre p1.

En la práctica, esto se vuelve más complicado en el caso general debido a las limitaciones de punto fijo o coma flotante. Los puntos que deberían ser colineales pueden no ser bastante colineales una vez que se han cuantificado sus coordenadas. Por lo tanto, es posible que deba permitir algún margen de error al hacer las comparaciones.

Answer 2

Una forma de hacerlo automáticamente sería tomar los puntos que contienen una combinación de minX, maxX, minY y maxY (es decir, las coordenadas más extendidas y suponiendo que todos los demás puntos están dentro de los límites del rectángulo).

Es posible que desee dar más detalles y limitaciones si esto no responde a la pregunta que tiene en mente.

Answer 3

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