A Matrix-Based 2-D Polygon Clipping Class

// 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;
	}
}