Click here to Skip to main content
Click here to Skip to main content
Add your own
alternative version
Go to top

A Matrix-Based 2-D Polygon Clipping Class

, 28 Mar 2003
An article on 2-D Polygon Clipping
polyclipdemo.zip
PolyClipDemo
PolyClipDemo.clw
PolyClipDemo.dsw
PolyClipDemo.dsp
PolyClipDemo.plg
PolyClipDemo.opt
res
PolyClipDemoDoc.ico
PolyClipDemo.ico
Toolbar.bmp
polyclipdemo1.zip
PolyClipDemo.aps
PolyClipDemo.clw
PolyClipDemo.dsp
PolyClipDemo.dsw
res
PolyClipDemo.ico
PolyClipDemoDoc.ico
Toolbar.bmp
PolyClipDemo.ncb
PolyClipDemo.opt
PolyClipDemo.plg
polyclipdemoapp.zip
PolyClipDemo.exe
polyclipdemoapp1.zip
PolyClipDemo.exe
// PolygonClip.cpp: implementation of the CPolygonClip class.
//
//
// nNumVerticies = number of polygon verticies				
// nNumLines = number of lines which are present			
// double* LineX = pointer to line origin x coords			
// double* LineY = pointer to line origin y coords			
// double* VertexX = pointer to polygon verticies x coords  
// double* VertexY = pointer to polygon verticies y coords  
//
// Class & code by: John Theal
// Date complete:	 December 18, 2002
//
// NOTE: To use this class, REMOVE the #include "PolyClipDemo.h"
//		 header file declaration below and include this file
//		 and PolygonClip.h in your project.  Simply call 
//		 the relevant member functions as needed.
//////////////////////////////////////////////////////////////////////

 
#include "stdafx.h"
#include "PolyClipDemo.h"
#include "PolygonClip.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif


//////////////////////////////////////////////////////////////////////
// Construction/Destruction
// ACCEPTS: number of verticies of the polygon and number of lines
// RETURNS: nothing
//////////////////////////////////////////////////////////////////////

CPolygonClip::CPolygonClip(unsigned int nNumVerticies, unsigned int nNumLines)	
{
	m_nNumVerticies = nNumVerticies;
	m_nNumLines = nNumLines;
	
	// Pointer initializations
	m_ppbSignChangeTable = 0;
	m_pnNumSignChanges = 0;
	m_pnIntersectsPerLine = 0;
	m_pnUniquesPerLine = 0;
	m_ppnDetSignTable = 0;
	m_ppdIntersectionY = 0;
	m_ppdIntersectionX = 0;
	m_ppdTempIntrX = 0;
	m_ppdTempIntrY = 0;
	
	// Setup and initialize the dynamic arrays
	if ( !(m_pnNumSignChanges = new unsigned int[nNumLines]) )
	{
		// Don't want to throw an exception from a constructor
		AfxMessageBox("m_pnNumSignChanges\n Out of memory.", MB_OK);
		AfxAbort();
	}

	if ( !(m_pnIntersectsPerLine = new unsigned int[nNumLines]) )
	{
		AfxMessageBox("m_pnIntersectsPerLine\n Out of memory.", MB_OK);
		AfxAbort();
	}

	if ( !(m_pnUniquesPerLine = new unsigned int[nNumLines]) )
	{
		AfxMessageBox("m_pnUniquesPerLine\n Out of memory.", MB_OK);
		AfxAbort();
	}

	// Initialize the sign change table
	if ( !(m_ppbSignChangeTable = new bool*[nNumLines]) )
	{
		AfxMessageBox("m_ppbSignChangeTable\n Out of memory.", MB_OK);
		AfxAbort();
	}
	
	if ( !(m_ppnDetSignTable = new int*[nNumLines]) )
	{
		AfxMessageBox("m_ppnDetSignTable\n Out of memory.", MB_OK);
		AfxAbort();
	}

	// Dynamically create the two dimensional arrays...
	for (unsigned int i = 0; i < nNumLines; i++)
	{
		m_ppbSignChangeTable[i] = new bool[nNumVerticies];
		m_ppnDetSignTable[i] = new int[nNumVerticies];
	}

	// Initialise all elements:
	// FALSE for m_ppbSignChangeTable
	// 0 for m_ppnDetSignTable
	for (i = 0; i < nNumLines; i++) 
	{
		// operator 'new' allocates a tag at the end of the dynamically
		// allocated array -> if this tag is overrun by assigning values
		// past the end of the array index, when the array is deallocated using
		// delete[], an ASSERT with "Damage After Normal Block" will occur...
		ASSERT(i < nNumLines);	

		*(m_pnNumSignChanges + i) = 0;
		*(m_pnIntersectsPerLine + i) = 0;
		*(m_pnUniquesPerLine + i) = 0;
		for (unsigned int j = 0; j < nNumVerticies; j++)
		{
			m_ppbSignChangeTable[i][j] = false;
			m_ppnDetSignTable[i][j] = 0;
		}
	}
	
	if ( !(m_ppdIntersectionX = new double*[nNumLines]) )
	{
		AfxMessageBox("m_ppdIntersectionX\n Out of memory.", MB_OK);
		AfxAbort();
	}

	if ( !(m_ppdIntersectionY = new double*[nNumLines]) )
	{
		AfxMessageBox("m_ppdIntersectionY\n Out of memory.", MB_OK);
		AfxAbort();
	}

	if ( !(m_ppdTempIntrX = new double*[nNumLines]) )
	{
		AfxMessageBox("m_ppdTempIntrX\n Out of memory.", MB_OK);
		AfxAbort();
	}

	if ( !(m_ppdTempIntrY = new double*[nNumLines]) )
	{
		AfxMessageBox("m_ppdTempIntrY\n Out of memory.", MB_OK);
		AfxAbort();
	}

	// Dynamically create the two dimensional intersection arrays...
	for (i = 0; i < m_nNumLines; i++) 
	{
		ASSERT(i < m_nNumLines);
			
		// Extensive error handling as this code is used in mission-critical environment
		if ( !(m_ppdIntersectionX[i] = new double[MaxDetChanges]) )
			AfxAbort();
		
		if ( !(m_ppdIntersectionY[i] = new double[MaxDetChanges]) )
			AfxAbort();	
			
		if ( !(m_ppdTempIntrX[i] = new double[MaxDetChanges]) )
			AfxAbort();	
			
		if ( !(m_ppdTempIntrY[i] = new double[MaxDetChanges]) )
			AfxAbort();	
	}

	// Populate above arrays with negative values...(screen coords assumed positive ie: MM_TEXT)
	for (i = 0; i < m_nNumLines; i++)
	{
		ASSERT(i < m_nNumLines);
		
		for (unsigned int j = 0; j < MaxDetChanges; j++)
		{
			ASSERT(j < MaxDetChanges);
			m_ppdIntersectionX[i][j] = -1;
			m_ppdIntersectionY[i][j] = -1;
			m_ppdTempIntrX[i][j] = -1;
			m_ppdTempIntrY[i][j] = -1;
		}
	}

	m_bDetermCalcFlag = FALSE;		// checks if determinants have been evaluated prior to CalcIntersects()
	m_bIntersectionFlag = FALSE;	// Ensures intersects have been determined prior to drawing
}

CPolygonClip::~CPolygonClip()
{
	// Free the heap
	delete[] m_pnIntersectsPerLine;
	delete[] m_pnUniquesPerLine;
	delete[] m_pnNumSignChanges;

	// Free the pointers to pointers
	for (unsigned int i = 0; i < m_nNumLines; i++)
	{
		// Avoid "Damage After Normal Block ASSERT"
		ASSERT(i < m_nNumLines);

		delete[] m_ppbSignChangeTable[i];
		delete[] m_ppnDetSignTable[i];
		
		delete[] m_ppdIntersectionX[i];
		delete[] m_ppdIntersectionY[i];
	}

	delete[] m_ppbSignChangeTable;
	delete[] m_ppnDetSignTable;

	delete[] m_ppdIntersectionX;
	delete[] m_ppdIntersectionY;
}


//////////////////////////////////////////////////////////////////////
// CPolygonClip::CalcSiDeterm()
// ACCEPTS: pointers to line start (subscript 1) and end (subscript 2) 
//			coordinates, ie: LineX1, LineY1, LineX2, LineY2...
//			and pointers to the polygon verticies: PolyVertexX, PolyVertexY
//
// RETURNS: pointer to array that holds the number of determinant sign
//			changes indexed by line number

unsigned int* CPolygonClip::CalcSiDeterm(double *LineX1, double *LineY1, 
										 double *LineX2, double *LineY2, 
										 double *PolyVertexX, double *PolyVertexY)
{
	int nNumSignChanges;		// Tracks number of determinant sign changes

	// Loop through the number of lines and calculate all 
	// possible S_i values...
	for (unsigned int LineNo = 0; LineNo < m_nNumLines; LineNo++)
	{
		ASSERT(LineNo < m_nNumLines);		// Avoid "Damage after normal block" ASSERT
		nNumSignChanges = 0;

		for (unsigned int VertNo = 0; VertNo < m_nNumVerticies; VertNo++)
		{
			ASSERT(VertNo < m_nNumVerticies);
			
			// Calculate the determinant (3x3 square matrix)
			double dS_i = TurboDeterm(PolyVertexX[VertNo], LineX1[LineNo], LineX2[LineNo],
									  PolyVertexY[VertNo], LineY1[LineNo], LineY2[LineNo]);
			
			// Check the determinant result
			switch (VertNo) 
			{
				case 0:
					if (dS_i == 0)		// we have hit a vertex
						m_ppnDetSignTable[LineNo][VertNo] = 0;

					else if (dS_i > 0)
						m_ppnDetSignTable[LineNo][VertNo] = 1;		// +'ve

					else if (dS_i < 0)
						m_ppnDetSignTable[LineNo][VertNo] = -1;		// -'ve

					m_ppbSignChangeTable[LineNo][0] = FALSE;		// First element will NEVER be a sign change
					break;
				default:
					if (dS_i == 0)
						m_ppnDetSignTable[LineNo][VertNo] = 0;
				
					else if (dS_i > 0)
						m_ppnDetSignTable[LineNo][VertNo] = 1;

					else if (dS_i < 0)
						m_ppnDetSignTable[LineNo][VertNo] = -1;
			
					// Check for sign change
					if (m_ppnDetSignTable[LineNo][VertNo - 1] != m_ppnDetSignTable[LineNo][VertNo])
					{
						m_ppbSignChangeTable[LineNo][VertNo] = TRUE;
						nNumSignChanges++;
						*(m_pnNumSignChanges + LineNo) = nNumSignChanges;	// Intersects / line
					}
					else
						m_ppbSignChangeTable[LineNo][VertNo] = FALSE;
			}
		}
	}
	ASSERT(m_pnNumSignChanges != NULL);
	
	m_bDetermCalcFlag = TRUE;	// Calculation successful

	return m_pnNumSignChanges;
}


//////////////////////////////////////////////////////////////////////
// CPolygonClip::TurboDeterm()
// ACCEPTS: matrix elements 11, 12, 13, 21, 22, 23
// RETURNS: the determinant of the matrix!

double CPolygonClip::TurboDeterm(double Elem11, double Elem12, double Elem13, 
								 double Elem21, double Elem22, double Elem23)
{
	// The third row of the 3x3 matrix is (1,1,1)
	return   Elem11 * (Elem22 - Elem23)
		   - Elem12 * (Elem21 - Elem23)
		   + Elem13 * (Elem21 - Elem22);
	
}


//////////////////////////////////////////////////////////////////////
// CPolygonClip::CalculateIntersections()
// ACCEPTS: pointers to line start and end coordinate arrays,
//			polygon verticies and number of determinant sign
//			changes (ie: number of intersections)
// RETURNS: true (success) or false (failure)

bool CPolygonClip::CalculateIntersections(double *LineX1, double *LineX2, 
										  double *LineY1, double *LineY2, 
										  double *PolyVertexX, double *PolyVertexY, 
										  unsigned int nMaxNumSignChanges)
{
	double dDeltaX;
	double dDeltaY;

	double dPolyLineSlope;		// Slope of polygon line segment
	double dBPoly;

	double dDeltaYLine;
	double dDeltaXLine;

	double dSlopeLine;			// Slope of intersecting line
	double dBLine;

	try
	{
		if (!m_bDetermCalcFlag)
			throw "ERROR.\n Call CalcSiDeterm() prior to CalculateIntersections()";

		if ( (nMaxNumSignChanges == 0) || (nMaxNumSignChanges < 0) )
			throw "ERROR.\n There are no intersections defined for this polygon.";


		// Now, analyse the result tables from CalcSiDeterm() and extract
		// the vertex pairs by iterating through the sign change table.  If
		// a vertex sign and another vertex sign PRIOR to it are different,
		// store the spanning verticies and note the line coordinates.
		// If line is horizontal, points should be ordered by increasing x,
		// otherwise by increasing y
		for (unsigned int LineNo = 0; LineNo < m_nNumLines; LineNo++)
		{
			ASSERT(LineNo < m_nNumLines);
			unsigned int nIntrNum = 0;		// Tracks number of intersections
			
			for (unsigned int VertNo = 0; VertNo < m_nNumVerticies; VertNo++)
			{
				ASSERT(VertNo < m_nNumVerticies);

				if (m_ppbSignChangeTable[LineNo][VertNo])	// If true, create equation of the line
				{
					nIntrNum++;

					// Equation of polygon segment
					dDeltaX = PolyVertexX[VertNo] - PolyVertexX[VertNo - 1];	// Ok here as 1st element ALWAYS false
					dDeltaY = PolyVertexY[VertNo] - PolyVertexY[VertNo - 1];

					// Store spanning verticies between which the intersect occurs
					dVertex[LineNo][nIntrNum] = VertNo;
					dVertexPrior[LineNo][nIntrNum] = VertNo - 1;

					// Formulate equation of intersection line
					dDeltaYLine = LineY2[LineNo] - LineY1[LineNo];
					dDeltaXLine = LineX2[LineNo] - LineX1[LineNo];

					if (dDeltaX == 0)	// Polygon line segment is vertical - trap it
					{
						dSlopeLine = dDeltaYLine / dDeltaXLine;
						dBLine = LineY2[LineNo] - dSlopeLine * LineX2[LineNo];

						m_ppdIntersectionX[LineNo][nIntrNum] = PolyVertexX[VertNo];
						m_ppdIntersectionY[LineNo][nIntrNum] = dSlopeLine * m_ppdIntersectionX[LineNo][nIntrNum] + dBLine;

						// Trap error
						if ( (m_ppdIntersectionX[LineNo][nIntrNum] < -1) || (m_ppdIntersectionY[LineNo][nIntrNum] < -1) )
							throw "ERROR.\n Negative intersection for dDeltaX = 0";
					}
					else if (dDeltaXLine == 0)	// Intersection line is vertical
					{
						dPolyLineSlope = dDeltaY / dDeltaX;
						dBPoly = PolyVertexY[VertNo] - dPolyLineSlope * PolyVertexX[VertNo];

						m_ppdIntersectionX[LineNo][nIntrNum] = LineX2[LineNo];
						m_ppdIntersectionY[LineNo][nIntrNum] = dPolyLineSlope * m_ppdIntersectionX[LineNo][nIntrNum] + dBPoly;
						
						if ( (m_ppdIntersectionX[LineNo][nIntrNum] < -1) || (m_ppdIntersectionY[LineNo][nIntrNum] < -1) )
							throw "ERROR.\n Negative intersection for dDeltaXLine = 0";
					}
					else if (dDeltaY == 0)	// Polygon segment is horizontal
					{
						dSlopeLine = dDeltaYLine / dDeltaXLine;
						dBLine = LineY2[LineNo] - dSlopeLine * LineX2[LineNo];

						m_ppdIntersectionY[LineNo][nIntrNum] = PolyVertexY[VertNo];
						m_ppdIntersectionX[LineNo][nIntrNum] = (m_ppdIntersectionY[LineNo][nIntrNum] - dBLine) / dSlopeLine;

						if ( (m_ppdIntersectionX[LineNo][nIntrNum] < -1) || (m_ppdIntersectionY[LineNo][nIntrNum] < -1) )
							throw "ERROR.\n Negative intersection for dDeltaY = 0";
					}
					else if (dDeltaYLine == 0)	// Line segment horizontal
					{
						dPolyLineSlope = dDeltaY / dDeltaX;
						dSlopeLine = 0;

						dBPoly = PolyVertexY[VertNo] - dPolyLineSlope * PolyVertexX[VertNo];
						dBLine = LineY2[LineNo] - dSlopeLine * LineX2[LineNo];

						m_ppdIntersectionY[LineNo][nIntrNum] = dBLine;
						m_ppdIntersectionX[LineNo][nIntrNum] = (m_ppdIntersectionY[LineNo][nIntrNum] - dBPoly) / dPolyLineSlope;

						if ( (m_ppdIntersectionX[LineNo][nIntrNum] < -1) || (m_ppdIntersectionY[LineNo][nIntrNum] < -1) )
							throw "ERROR.\n Negative intersection for dDeltaYLine = 0";
					}
					else	// default case
					{
						// Calculate the slope and y-intercepts of polygon segment
						dPolyLineSlope = dDeltaY / dDeltaX;
						dBPoly = PolyVertexY[VertNo] - dPolyLineSlope * PolyVertexX[VertNo];

						// slope and intercept of the line
						dSlopeLine = dDeltaYLine / dDeltaXLine;
						dBLine = LineY2[LineNo] - dSlopeLine * LineX2[LineNo];

						// Solve the linear equations for the intersection points
						m_ppdIntersectionX[LineNo][nIntrNum] = (dBPoly - dBLine) / (dSlopeLine - dPolyLineSlope);
						m_ppdIntersectionY[LineNo][nIntrNum] = dSlopeLine * m_ppdIntersectionX[LineNo][nIntrNum] + dBLine;

						if ( (m_ppdIntersectionX[LineNo][nIntrNum] < -1) || (m_ppdIntersectionY[LineNo][nIntrNum] < -1) )
							throw "ERROR.\n Negative intersection point.";
					}
					// Store intersects per line indexed by line number
					*(m_pnIntersectsPerLine + LineNo) = nIntrNum;
				}	
			}		
		}		

		// if no exceptions, we have succeeded.
		m_bIntersectionFlag = TRUE;
		return true;	
	}
	catch (char* aErrorCondition)
	{
		AfxMessageBox(aErrorCondition);
		return false;
	}
}


//////////////////////////////////////////////////////////////////////
// CPolygonClip::FindArrayMax
// ACCEPTS: Pointer to array of elements
// RETURNS: Maximum element in the array

unsigned int CPolygonClip::FindArrayMax(unsigned int *pNumChanges)
{
	unsigned int iIndex;
	unsigned int iLargest(0);

	// Find largest value
	iLargest = *pNumChanges;

	for (iIndex = 0; iIndex < m_nNumLines; iIndex++)
	{
		if (*(pNumChanges + iIndex) > iLargest)
			iLargest = *(pNumChanges + iIndex);
	}

	return iLargest;
}


//////////////////////////////////////////////////////////////////////
// CPolygonClip::Draw()
// ACCEPTS: Pointer to a device context
// RETURNS: void. 
// Draws a coloured circle in the active view about the 
// intersection point read from the intersection 
// tables of the class .
// NOTE: Assumes MM_TEXT mode...

void CPolygonClip::Draw(CDC *pDC)
{
	try
	{
		// Ensure intersects have been determined
		if (!m_bIntersectionFlag)
			throw "ERROR.\n Cannot draw before CalculateIntersections()";

		CRect GridDotRect;		// Bounding rect for grid dot
		CPoint GridPoint;		// point on the grid

		CPen aPen;
		if ( !(aPen.CreatePen(PS_SOLID, PenSize, RGB(0, 0, 255))) )	// blue pen	
			throw "ERROR.\n CPolygonClip::Draw() could not initialize pen.";
		CPen* pOldPen = pDC->SelectObject(&aPen);
		
		ASSERT(pOldPen != NULL);
	
		CBrush aBrush;
		if ( !(aBrush.CreateSolidBrush(RGB(0, 0, 255))) )		// blue brush
			throw "ERROR.\n CPolygonClip::Draw() could not initialize brush.";
		CBrush* pOldBrush = (CBrush*)pDC->SelectObject(&aBrush);
		
		ASSERT(pOldBrush != NULL);
		
		for (unsigned int LineNo = 0; LineNo < m_nNumLines; LineNo++)
		{
			if (LineNo >= m_nNumLines)
				throw "ERROR.\n Line index exceeded during draw.";

			for (unsigned int VertNo = 0; VertNo < m_nNumVerticies; VertNo++)
			{
				if (VertNo >= m_nNumVerticies)
					throw "ERROR.\n Vertex index exceeded during draw.";

				GridPoint.x = m_ppdIntersectionX[LineNo][VertNo];
				GridPoint.y = m_ppdIntersectionY[LineNo][VertNo];

				if ( (GridPoint.x != -1) && (GridPoint.y != -1) )
				{
					GridDotRect.top = GridPoint.y - DotSize;
					GridDotRect.bottom = GridPoint.y + DotSize;
					GridDotRect.left = GridPoint.x - DotSize;
					GridDotRect.right = GridPoint.x + DotSize;

					pDC->MoveTo(GridPoint);

					pDC->Ellipse(GridDotRect);	// Place a dot
				}
			}
		}

		// Release the DC's
		pDC->SelectObject(pOldPen);
		pDC->SelectObject(pOldBrush);
	}
	catch (char* aErrorCondition)
	{
		AfxMessageBox(aErrorCondition);
		return;
	}
}

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article, along with any associated source code and files, is licensed under The Common Development and Distribution License (CDDL)

Share

About the Author

73Zeppelin
Other
Anonymous Proxy Anonymous Proxy
No Biography provided

| Advertise | Privacy | Mobile
Web02 | 2.8.140916.1 | Last Updated 29 Mar 2003
Article Copyright 2003 by 73Zeppelin
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid