从一组线段中得出四边形的算法

原始的需求是使用OpenCV的直线检测算法（例如LSD）之后，得到一组线段。然后需要从这些线段得到类似矩形的四边形，用于检测经过透视变换的矩形物体。这些线段不一定首尾相接，彼此之间可能相交或有一定距离。

以下是需求图：

使用从线段中寻找四边形的算法之后，得到了以下结果：

算法的步骤为：

1、从线段中挑出4条，顺序不同的组合只有3种。

2、对于每一种组合，由于每一条线段都有2个方向，那么就会有8种组合。

3、对于每一个组合，首先检查相邻线段的夹角，排除太小或太大的（相对于90度）。

4、继而检查相邻线段的顶点距离，排除距离太远的。

5、最后，求出四条相邻线段的交点，以这4个交点作为最终透视矩形的四个顶点。

算法代码如下：

/// <summary>
/// 线段组成四边形
/// </summary>
/// <param name="segs">线段列表</param>
/// <param name="maxDistSum">最大距离和</param>
/// <returns>四边形列表</returns>
public static List<PolygonScore> FormQuadrangle(Segment2D[] segs, double maxDistSum)
{int len = segs.Length;List<int[]> combines = new List<int[]>();for (int i = 0; i < len - 3; i++){for (int j = i + 1; j < len - 2; j++){for (int k = j + 1; k < len - 1; k++){for (int l = k + 1; l < len; l++){combines.Add(new int[] { i, j, k, l });combines.Add(new int[] { i, j, l, k });combines.Add(new int[] { i, k, j, l });}}}}List<RectInfo> rects = new List<RectInfo>();for (int i = 0; i < combines.Count; i++){int[] combine = combines[i];var seg1 = segs[combine[0]];var seg2 = segs[combine[1]];var seg3 = segs[combine[2]];var seg4 = segs[combine[3]];double cos1 = CosAngle(seg1.Vec, seg1.Length, seg2.Vec, seg2.Length);if (Math.Abs(cos1) > 0.5){continue;}double cos2 = CosAngle(seg2.Vec, seg2.Length, seg3.Vec, seg3.Length);if (Math.Abs(cos2) > 0.5){continue;}double cos3 = CosAngle(seg3.Vec, seg3.Length, seg4.Vec, seg4.Length);if (Math.Abs(cos3) > 0.5){continue;}double cos4 = CosAngle(seg4.Vec, seg4.Length, seg1.Vec, seg1.Length);if (Math.Abs(cos4) > 0.5){continue;}var doubleSegs = new Segment2D[] { seg1, seg1.Reverse(), seg2, seg2.Reverse(), seg3, seg3.Reverse(), seg4, seg4.Reverse() };bool found = false;for (int i1 = 0; i1 < 2; i1++){for (int i2 = 2; i2 < 4; i2++){double d1 = PointPoint(doubleSegs[i1].P2, doubleSegs[i2].P1);if (d1 > maxDistSum){continue;}for (int i3 = 4; i3 < 6; i3++){double d2 = PointPoint(doubleSegs[i2].P2, doubleSegs[i3].P1) + d1;if (d2 > maxDistSum){continue;}for (int i4 = 6; i4 < 8; i4++){double d3 = PointPoint(doubleSegs[i3].P2, doubleSegs[i4].P1);double d4 = PointPoint(doubleSegs[i4].P2, doubleSegs[i1].P1);double dd = d2 + d3 + d4;if (dd < maxDistSum){rects.Add(new RectInfo(new Segment2D[] { doubleSegs[i1], doubleSegs[i2], doubleSegs[i3], doubleSegs[i4] }, dd));found = true;}if (found){break;}}if (found){break;}}if (found){break;}}if (found){break;}}}rects.Sort();List<PolygonScore> polygons = new List<PolygonScore>();foreach (RectInfo rect in rects){polygons.Add(new PolygonScore(new Point2D[] {Intersect(rect.Segments[0],rect.Segments[1]),Intersect(rect.Segments[1],rect.Segments[2]),Intersect(rect.Segments[2],rect.Segments[3]),Intersect(rect.Segments[3],rect.Segments[0])}, rect.DistSum));}return polygons;
}

使用上面的代码对下图进行简单测试：