PDF文档解析表格、形状后续处理-短线段生成闭合的最小多边形

我们根据线段打断处理得到了一组被打断的小线段，接下来我们将这些小线段生成多边形。代码如下：

typedef struct _tagAssociatedLine
{
    Vertex pt;
    std::vector vecLine;
    _tagAssociatedLine() : pt{ 0.,0. } {}
}AssociatedLine;

//获取下一条线段
Segment  GetNextLine(const Segment& currentLine, std::vector& vecAssociated, bool& bValuable)
{
	bValuable = true;
	Segment nextLine = {};
	nextLine.start = { 0., 0., };
	nextLine.end = { 0., 0., };
	for (int i = 0; i < vecAssociated.size(); i++)
	{
		AssociatedLine& associatedLine = vecAssociated[i];
		if (currentLine.end == associatedLine.pt) //找到与当前线段终点相等的交点pt的关联对象
		{
			for (int j = 0; j < associatedLine.vecLine.size(); j++)  //遍历交点pt关联对象中的关联线段
			{
				std::vector& lines = associatedLine.vecLine;
				if (lines[j].start ==  currentLine.end && lines[j].end == currentLine.start)
				{
					//从象限角排序数组中找到方向线段的下一个位置的线段
					if (j == (lines.size() - 1))
						nextLine = lines[0];
					else
						nextLine = lines[j + 1];
					return nextLine;
				}
			}
		}
	}
	bValuable = false;
	return nextLine;
}

void RemoveisolatedLine(const std::vector& input, std::vector& output)
{
	//先处理两端都孤立的线段
	std::vector vecTmp;
	if (input.size() < 2)
		return;
	for (int i = 0; i < input.size(); i++)
	{
		for (int j = 0; j < input.size(); j++)
		{
			if (i == j)
				continue;
			Vertex point;
			if (IsCross(input[i], input[j], point)) {
				vecTmp.push_back(input[i]);
				break;
			}
		}
	}

	//再处理一端孤立的线段
	for (int i = 0; i < vecTmp.size(); i++)
	{
		std::vector crossPoint;
		for (int j = 0; j < vecTmp.size(); j++)
		{
			Vertex point;
			if (IsCross(vecTmp[i], vecTmp[j], point)) {
				crossPoint.push_back(point);
			}
		}

		bool bEqual = false;
		for (int m = 0; m < crossPoint.size(); m++)
		{
			if (vecTmp[i].start == crossPoint[m])
			{
				bEqual = true;
				break;
			}
		}
		if (bEqual)
		{
			for (int n = 0; n < crossPoint.size(); n++)
			{
				if (vecTmp[i].end == crossPoint[n])
				{
					output.push_back(vecTmp[i]);
					break;
				}
			}
		}
	}
}

void GetCrossPoints(const std::vector& input, std::vector& vecCrossPoint)
{
	for (int i = 0; i < input.size(); i++)
	{
		vecCrossPoint.push_back(input[i].start);
		vecCrossPoint.push_back(input[i].end);
	}
	//去除重复的点
	int n = vecCrossPoint.size();
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < i; j++) {
			if (vecCrossPoint[i] == vecCrossPoint[j]) {
				n--;
				for (int k = i; k < n; k++) {
					vecCrossPoint[k] = vecCrossPoint[k + 1];
				}
				i--;
			}
		}
	}

	vecCrossPoint.erase(vecCrossPoint.begin() + n, vecCrossPoint.end());
}

void GetDirectedLine(const std::vector& input, std::vector& vecDirectedLine)
{
	for (int i = 0; i < input.size(); i++)
	{
		vecDirectedLine.push_back(input[i]);
		Segment temp;
		temp.start = input[i].end;
		temp.end = input[i].start;
		vecDirectedLine.push_back(temp);
	}
}

std::vector SortLine(std::vector& lines)
{
	if (lines.size() < 2)
		return lines;
	for (int i = 0; i < lines.size() - 1; i++)
	{
		int minIndex = i;
		double dxmin = lines[i].end.x - lines[i].start.x;
		double dymin = lines[i].end.y - lines[i].start.y;
		double dAnglemin = atan2(dymin, dxmin);
		dAnglemin = (180. / 3.141592652589793) * dAnglemin;
		if (abs(dAnglemin) <= 0.1)
			dAnglemin = 0.;
		if (dAnglemin < -0.1)
			dAnglemin += 360;
		for (size_t j = i + 1; j < lines.size(); j++)
		{
			double dx = lines[j].end.x - lines[j].start.x;
			double dy = lines[j].end.y - lines[j].start.y;
			double dAngle = atan2(dy, dx);
			dAngle = (180. / 3.141592652589793) * dAngle;
			if (abs(dAngle) <= 0.1)
				dAngle = 0.;
			if (dAngle < -0.1)
				dAngle += 360;
			if (dAngle < dAnglemin)
			{
				minIndex = j;
				dAnglemin = dAngle;
			}
		}
		std::swap(lines[minIndex], lines[i]);
	}
	return lines;
}

std::vector GetAssociated(const std::vector& DirectedLine, const Vertex& pt)
{
	std::vector AssociatedLine;
	//找到与点pt关联的线段
	for (int j = 0; j < DirectedLine.size(); ++j)
	{
		if (DirectedLine[j].start == pt)
		{
			AssociatedLine.push_back(DirectedLine[j]);
		}
	}
	std::vector vecSortedLine;//排序后的数组

	//对关联线段根据象限角大小进行排序
	vecSortedLine = SortLine(AssociatedLine);
	return vecSortedLine;
}

void GetAssociatedLine(const std::vector& DirectedLine, const std::vector& crossPoint, std::vector& vecAssociatedLine)
{
	//找到每一个交点的关联线段
	for (int i = 0; i < crossPoint.size(); ++i)
	{
		AssociatedLine AssociatedEnt;
		AssociatedEnt.pt = crossPoint[i]; 
		AssociatedEnt.vecLine = GetAssociated(DirectedLine, crossPoint[i]);
		vecAssociatedLine.push_back(AssociatedEnt);
	}
}

void GetClosedAreas(const std::vector& DirectedLine, std::vector& vecAssociated, std::vector>& vecAllClosedAreas)
{
	//提取任意一条有向线段作为提取封闭图形的第一条线段
	for (int i = 0; i < DirectedLine.size(); i++)
	{
		bool bIsClosed = true;
		std::vector vecClosedArea;
		vecClosedArea.push_back(DirectedLine[i]);
		bool bValuable = true;
		Segment m_nextLine;
		m_nextLine = GetNextLine(DirectedLine[i], vecAssociated, bValuable);

		if (!bValuable)
			continue;

		vecClosedArea.push_back(m_nextLine);
		while (m_nextLine.start != DirectedLine[i].start && m_nextLine.end != DirectedLine[i].end)
		{
			m_nextLine = GetNextLine(m_nextLine, vecAssociated, bValuable);
			if (!bValuable)
			{
				bIsClosed = false;
				break;
			}
			else
				vecClosedArea.push_back(m_nextLine);
		}
		if (bIsClosed)
			vecAllClosedAreas.push_back(vecClosedArea);//获得以DirectedLine[i]为起始线段的封闭区域
	}
}

bool IsOverlap(const std::vector& AreaLeft, const std::vector& AreaRight)
{
	//若两个闭合区域重叠,其size()必然相同
	if (AreaLeft.size() != AreaRight.size())
		return false;
	for (unsigned int i = 0; i < AreaLeft.size(); i++)
	{
		Segment m_lineLeft = AreaLeft[i];
		bool bEqualLine = false;
		for (unsigned int j = 0; j < AreaRight.size(); j++)
		{
			if (m_lineLeft.start == AreaRight[j].start && m_lineLeft.end == AreaRight[j].end ||
				m_lineLeft.start == AreaRight[j].end && m_lineLeft.end == AreaRight[j].start)
			{
				bEqualLine = true;
			}
		}
		if (bEqualLine == false)
			return false; //只要有一条线段不相同,必然不重合
	}
	return true;
}

std::vector>& RemoveOverlapArea(std::vector>& poly)
{
	int n = poly.size();
	if (n < 2) //只有一个闭合区域
		return poly;

	//去除重叠的区域
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < i; j++)
		{
			if (IsOverlap(poly[i], poly[j]))
			{
				n--;
				for (int k = i; k < n; k++)
				{
					poly[k] = poly[k + 1];
				}
				i--;
			}
		}
	}

	std::vector>::iterator it1, it2;
	it1 = poly.begin() + n;
	it2 = poly.end();
	poly.erase(it1, it2);
	return poly;
}

//判断点集合pointsA是否包含在点集合pointsB中(B的点数量大于A的点数量)
bool IsContainPoints(std::vector& pointsA, std::vector& pointsB)
{
	int nSizeA = pointsA.size();
	int nSizeB = pointsB.size();
	//若B中包含有A,B的顶点数量要大于A的顶点数量
	if (nSizeA >= nSizeB)
	{
		return false;
	}
	for (int i = 0; i < nSizeA; i++) //遍历小区域A的顶点
	{
		bool isEqual = false;
		for (int j = 0; j < nSizeB; j++) //遍历大区域B的顶点
		{
			if (pointsA[i] == pointsB[j])
			{
				isEqual = true;
				break;
			}
		}
		if (!isEqual)
		{
			return false; //只要A中的任意顶点,在B中找不到,则说明A不包含在B中
		}
	}

	return true; //在B中可以找到A中所有的顶点,说明A包含在B中
}

//判断点是否在闭合区域内
bool IsPointInPolygon(const Vertex& p, std::vector& points, double des = 0.01)
{
	int nCount = points.size();
	// 交点个数  
	int nCross = 0;
	for (int i = 0; i < nCount; i++)
	{
		Vertex p1 = points[i];
		Vertex p2 = points[(i + 1) % nCount];// 点P1与P2形成连线  

		Segment seg(p1, p2);
		if (IsPointOnSegment(p, seg))
			return false;

		if (abs(p1.y - p2.y) <= abs(des)) continue;
		if (p.y < min(p1.y, p2.y) && abs(p.y - min(p1.y, p2.y)) > abs(des))
			continue;
		if (p.y >= max(p1.y, p2.y) || abs(p.y - max(p1.y, p2.y)) <= abs(des))
			continue;
		// 求交点的x坐标（由直线两点式方程转化而来）   
		double x = (double)(p.y - p1.y) * (double)(p2.x - p1.x) / (double)(p2.y - p1.y) + p1.x;

		// 只统计p1p2与p向右射线的交点  
		if (x > p.x)
			nCross++;
	}

	if ((nCross % 2) == 1)
		return true;
	else
		return false;
}

//判断多边形B的所有边的中心点存在在区域A内部的情况（不在区域A边上）
bool IsContainLine(const std::vector& linesA, const std::vector& linesB)
{
	if (linesA.size() < linesB.size())
		return false;

	bool bIsContainLine = false;
	for (int i = 0; i < linesB.size(); i++)
	{
		auto& lineB = linesB[i];
		Vertex centerPoint;
		centerPoint.x = (lineB.start.x + lineB.end.x) / 2.;
		centerPoint.y = (lineB.start.y + lineB.end.y) / 2.;
		std::vector PloyVertex;
		GetCrossPoints(linesA, PloyVertex);
		if (IsPointInPolygon(centerPoint, PloyVertex))
		{
			bIsContainLine = true;
			break;
		}
	}
	return bIsContainLine;
}

//移除大区域包含小区域的图形
//只有一种情况：大区域的交点包含小区域所有的交点
std::vector> GetRemoveContainPoly(const std::vector>& InPolys, std::vector>& outPolys)
{
	int nSize = InPolys.size();
	for (int i = 0; i < nSize; i++)
	{
		auto& m_AreaA = InPolys[i]; //获得区域A
		std::vector m_PointsA;
		GetCrossPoints(m_AreaA, m_PointsA);//获得区域A所有的顶点
		bool m_bContain = false;
		for (int j = 0; j < nSize; j++)
		{
			if (j == i)
				continue;
			auto& m_AreaB = InPolys[j]; //获得区域B
			std::vector m_PointsB;
			GetCrossPoints(m_AreaB, m_PointsB);//获得区域B的所有顶点
			//判断A中是否包含有其他区域B
			//判断方法：当A和B的顶点数不相同时,若区域A包含区域B的所有顶点,则可能包含，须进一步判断
			if (IsContainPoints(m_PointsB, m_PointsA)) //A中可能包含有B
			{
				//再判断区域B的所有边中点是否存在在区域A内部，如存在，删除A
				if (IsContainLine(m_AreaA, m_AreaB))
				{
					m_bContain = true;
					break;
				}
			}
		}
		if (!m_bContain) //区域A中没有包含其他区域
			outPolys.push_back(m_AreaA);
	}
	return outPolys;
}

以下为函数调用：

	//移除孤立的线段（两端孤立跟一端孤立）
	std::vector vecNonisolatedLines;
	RemoveisolatedLine(vecSegments, vecNonisolatedLines);

	//获取所有的交点
	std::vector vecCrossPoints;
	GetCrossPoints(vecNonisolatedLines, vecCrossPoints);

	//生成有向线段
	std::vector vecDirectedLines;
	GetDirectedLine(vecNonisolatedLines, vecDirectedLines);

	//交点与线段关联
	std::vector vecAssociatedLines;
	GetAssociatedLine(vecDirectedLines, vecCrossPoints, vecAssociatedLines);

	//生成闭合区域
	std::vector> vecPolys;
	GetClosedAreas(vecDirectedLines, vecAssociatedLines, vecPolys);

	//去除重叠的区域
	RemoveOverlapArea(vecPolys);

	//去除内部仍包含有图形的区域
	std::vector> RemoveContainPoly;
	GetRemoveContainPoly(vecPolys, RemoveContainPoly);
	//去除包含内部顶点的多边形
	std::vector> vecResultPolys;
	for (int i = 0; i < RemoveContainPoly.size(); i++)
	{
		bool bEnable = true;
		std::vector PloyVertex;
		GetCrossPoints(RemoveContainPoly[i], PloyVertex);
		for (int j = 0; j < vecCrossPoints.size(); j++)
		{
			Vertex currentPoint = vecCrossPoints[j];
			if (IsPointInPolygon(currentPoint, PloyVertex))
			{
				bEnable = false;
				break;
			}
		}
		if (bEnable)
			vecResultPolys.push_back(RemoveContainPoly[i]);
	}

经测试《PDF文档解析表格、形状后续处理-长线段打断为短线段》中线段生成的闭合多边形为9个。结果与预期一致。