如何从列表中删除多余的顶点 [英] How do I remove redundant vertices from list

问题描述

我有顶点列表，例如 List< Point> ，其中包含以下的平方点：$ b​​ $ b（0,0），
（1 ，0），
（2,0），
（3,0），
（4,0），
（4,1），
（4 ，2），
（4,3），
（4,4），
（3,4），
（2,4），
（1 （0,4），
（0,4），
（0,3），
（0,2），
（0,1），
（0 ，0）

只需要四点（0,0），（0,4），（4,4），（4,0），我如何从列表中删除多余（这使得直线）点？$ / b
$ b

它并不总是正方形，基本上我想减少点的数量，如果它们形成直线。例如（0,0），（0,1），（0,2），（0,3），（0,4）是直线，而不是绘制所有四个点，所以可以快速地从点（0,0），（0,4）。

解决方案

code> p0 ， p1 ， p2 ）。如果 p2 = p0 + k（p1-p0）其中 k ，这三点是共线的（形成单行）是一个任意的实数。我们可以用联立方程式来表示上述条件：

pre $ x $ c $（x2 - x0）= k（x1 - x0）
（y2 - y0）= k（y1 - y0）

理论上，做的是依次取每组三点。计算x分量和y分量的 k 的值;如果它们是相同的，那么线是共线的，所以删除 p1 。

实际上，由于定点或浮点的局限性，在一般情况下是棘手的。一旦坐标被量化，应该共线的点可能不是很共线。因此，在进行比较时，您可能需要考虑一些误差。

I have list of vertices i.e List<Point>, which contains following points for square: (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)

To draw a square I just need four points (0,0), (0,4), (4,4), (4,0), how do I remove redundant (which makes straight line) points from list?

It is not always square, basically I want to reduced the number of points if they form straight line. For example (0,0), (0,1), (0,2), (0,3), (0,4) makes straight line instead of drawing all four points it would be quick to draw a line from points (0,0), (0,4).

解决方案

Look at three successive points at a time (let's call them p0, p1, p2). These three points are collinear (form a single line) if p2 = p0 + k(p1 - p0) where k is an arbitrary real number. We can express the above condition in terms of simultaneous equations:

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

In theory, all you need to do is takes each set of three points in turn. Calculate the value of k for the x components and y components; if they are the same, then the lines are collinear, so delete p1.

In practice, this becomes more tricky in the general case due to the limitations of fixed-point or floating-point. Points that should be collinear may not be quite collinear once their coordinates have been quantised. So you may need to allow for some error margin when doing the comparisons.

这篇关于如何从列表中删除多余的顶点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！