65.9K
CodeProject 正在变化。 阅读更多。
Home

一个基于矩阵的二维多边形裁剪类

<sup>73</sup>Zeppelin
starIconstarIconstarIcon
emptyStarIcon
starIcon
emptyStarIcon

3.50/5 (40投票s)

2003年1月7日

CDDL

8分钟阅读

viewsIcon

206288

downloadIcon

4680

关于二维多边形裁剪的文章。

Quick shot of the demo application.

引言

该代码是一个二维多边形裁剪算法，能够精确地确定一条线与多边形边界的相交点。该代码适用于凹多边形和凸多边形，形状完全任意，并能处理任何线方向。此外，用于保存线和多边形坐标的所有数组都是动态分配的，因此多边形顶点和相交线的数量限制仅取决于可用内存量。代码中使用了错误检查，以确保不会越界访问动态数组。

背景

该代码是在开发癌症放射治疗剂量计算程序时编写的。对于这些计算，需要精确地确定某些解剖和机械特征与辐射场的相交点。因此，诞生了CPolygonClip。由于在临床环境中的实现，该代码快速、准确且健壮。由于时间限制，一些方法和函数已被省略，但将在未来添加。

理论或工作原理

这是文章中比较复杂的数学部分。当然，您可以在不阅读此部分的情况下使用该类，但最好在深入研究之前了解您正在处理的内容。幸运的是，大多数程序员都具备理解这些材料所需的数学基础。
总的来说，多边形裁剪是一种数学技术，用于评估两个三维物体是否相交。在本篇文章的更有限的上下文中，多边形裁剪用于确定线段与多边形的相交点。为了实现CPolygonClip类，我们做了两个假设。首先，多边形的顶点按顺时针方向排列。其次，设备上下文的坐标系假定为MM_TEXT，尽管将该类的输出转换为任何其他系统相对简单。要定义线段，我们使用起点 P1(x1,y1) 和终点 P2(x2,y2)，而多边形由一系列顶点 Vi(Xi,Yi)，i = 1..n 定义。（见图。）

Polygon clipping illustration.

每个点的坐标被认为是z分量为1的向量的分量。现在，令

Si = determinant(Vi, P1, P2) 或者，

Matrix determinant.

Si 代表一条直线的方程，其符号对于位于直线任一侧的点将是固定的。因此，通过在两个连续顶点之间搜索Si的符号变化，可以确定是否存在直线与多边形边界的交点。找到符号变化将保证多边形与由P1和P2定义的线段相交。此计算对所有可能与多边形边界相交的线重复进行。一旦计算出所有直线的Si值，S的符号变化总数就表示直线与多边形的相交总数。自然，给定直线的Si的符号变化总数表明该直线与多边形相交的次数。Si还可以用于确定直线是否恰好与多边形顶点相交（共线相交）。这种情况由条件Si = 0表示。在找到相交数量后，现在可以确定相交点的坐标。这是通过构建一个包含两个未知数的线性方程组来完成的。解这些方程并获得交点是微不足道的。我们需要两个方程

y = mline*x + bline

和

y = mpoly*x + bpoly

其中 y 是 y 坐标，mline 是直线的斜率，mpoly 是跨越交点的两个顶点之间的多边形段的斜率，x 是 x 坐标，bline 和 bpoly 分别是直线和多边形的 y 截距。通过使 y 值相等，即使一个方程等于另一个方程，可以轻松求解这些方程。这允许我们计算 x，即 x 轴上的交点坐标。一旦知道 x，就可以使用任何一个方程来确定 y。坐标点 (x,y) 就是直线与多边形的交点。对于垂直线或斜率相同的线，必须格外小心，因为上述方程在这些情况下无法求解。

使用代码

只需将 .h 和 .cpp 文件插入您当前的工程即可开始使用。根据需要调用成员函数。编译器可能会报告一些转换警告，但这些主要是由于屏幕绘图调用（例如，double 到 int）引起的，在屏幕上绘制点时并不特别重要。

该类总共包含 7 个函数和 4 个可调参数。如前所述，使用的每个数组都是动态分配的，因此可以使用任何任意多边形形状和任意数量的直线（受可用内存限制）。CPolygonClip类使用以下方式构造：

CPolygonClip(unsigned int nNumVerticies, unsigned int nNumLines);
其中传递的参数是多边形的顶点数和需要计算交线的数量。传递的顶点数必须比多边形中的实际顶点数多一个——多边形的最后一个顶点必须是多边形第一个顶点的副本。
unsigned int* CalcSiDeterm(double* LineX1, double* LineY1, 
			          double* LineX2, double* LineY2, 
			          double* PolyVertexX, double* PolyVertexY);
此函数计算传递给它的所有线的 Si 行列式。LineX1 和 LineY1 是指向包含 P1 的 x 和 y 坐标对的数组的指针，而 LineX2 和 LineY2 是指向包含 P2 的 x 和 y 坐标对的数组的指针。PolyVertexX 和 PolyVertexY 是指向包含多边形顶点 x 和 y 坐标的数组的指针。同样，重要的是这些数组的最后一个元素是多边形第一个顶点的副本。CalcSiDeterm 返回一个指向数组的指针，该数组按行号索引保存每条线的交点数。
bool CPolygonClip::CalculateIntersections(double *LineX1, double *LineX2, 
double *LineY1, double *LineY2, 
double *PolyVertexX, double *PolyVertexY, 
unsigned int nMaxNumSignChanges)
CalculateIntersections() 相当直观。它只是计算多边形与线之间的交点坐标。它接受与 CalcSiDeterm() 相同的参数，除了最后一个参数 nMaxNumSignChanges，它表示所有给定线的最大符号变化次数。这由 FindArrayMax() 返回，下面将对其进行描述。
unsigned int CPolygonClip::FindArrayMax(unsigned int *pNumChanges)
FindArrayMax() 仅接受数组的指针并从中提取最大值。此输出作为参数 nMaxNumSignChanges 传递给 CalculateIntersections()。
void CPolygonClip::Draw(CDC *pDC)
此函数仅在交点位置绘制蓝色点。最后，
double CPolygonClip::TurboDeterm(double Elem11, double Elem12, 
                                 double Elem13, double Elem21, double Elem22, 
                                 double Elem23)
是一个辅助函数，它接受矩阵的前六个元素，计算 3x3 矩阵的快速行列式。
CheckValidPoint(CPoint *lpVertexPoints, int nCount, CPoint aPoint)
该类的私有方法，可防止检测到不位于有限直线上的点。

该类的一个典型用法如下：
	//////////////////////////////////
	//    BEGIN POLYGON CLIPPING	
	//////////////////////////////////
	m_pPolygonClip = new CPolygonClip(NumberOfVerticies, NumberOfLines);
	ASSERT(m_pPolygonClip != NULL);

	unsigned int* pnSignChanges = 0;
	
	// Calculate the determinants
	pnSignChanges = m_pPolygonClip->CalcSiDeterm(pLineX1, pLineY1, 
                                  pLineX2, pLineY2, pPolyVertsX, pPolyVertsY);

       // Find maximum number of intersections
       unsigned int nNumChanges = m_pPolygonClip->FindArrayMax(pnSignChanges);

	// Calculate line/polygon intersections
	bool bSuccess = m_pPolygonClip->CalculateIntersections(pLineX1, 
                                       pLineX2, pLineY1, pLineY2, pPolyVertsX, 
                                       pPolyVertsY, nNumChanges);

	// should include some other error 
	// handling routine...try/catch, etc...
	// (this will do for now)
	ASSERT(bSuccess);		

	// Draw the intersection points
	m_pPolygonClip->Draw(pDC);
	//////////////////////////////////
	//    END POLYGON CLIPPING		
	//////////////////////////////////

不要忘记在完成特定类的实例后调用析构函数。

关注点

这里有几点需要注意。不幸的是，由于编写该类的应用程序，有必要按特定顺序调用类的成员函数。存在标志以确保调用按正确的顺序进行。这更多地是由于临床软件的架构，而不是其他任何原因。
其次，动态内存分配有点麻烦——尤其是来自 FORTRAN 背景，其中数组的索引是从 1 开始的。将来，我可能会为此利用二维数组类，以使生活更轻松。
目前，这不是类的完整实现。由于某些原因，我不得不提取部分代码以使其可用。因此，一些函数尚未实现，因为它们还需要进行修剪。其中包括用于确定线段的哪个部分位于多边形边界内部/外部的函数，以及将一些信息转储到 ASCII 文件的函数。
我选择使用矩阵方法而不是向量代数方法，因为我认为它更优雅，并且矩阵比向量代数更适合计算机实现。
无论如何，我认为这提供了一个快速易用的基本多边形裁剪实现，我在互联网上找不到现成的例程。

演示应用程序相当静态，仅显示一个多边形（红色）和一些黑色线条。蓝色点表示交点。但是，所有计算都是在运行时完成的（已将所有工作代码放在 OnDraw() 中），所以这不仅仅是一些预先绘制的图片。随意尝试多边形顶点和线方向，以查看其效果。

更新日期：2003 年 3 月 13 日

发现对于有限直线，检测到了实际上不在直线上的点，并且计算了交点。为了纠正这一点，添加了一个私有成员函数，该函数可以检测仅位于线段上的点，而不是无限直线上的点。

版本历史

构造函数中的错误处理可以更好一些……

版本 1.0：初始发布。

版本 1.1：修复了允许计算不一定位于直线上的点的交点的错误实现。

© . All rights reserved.