Polygon Class - Anyone willing to share?

This topic is 4907 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

Hey all, I'm in need of a polygon class and before I sit down to write it, I figured I'd ask if anyone already has and is willing to share. Basically I'm looking to use it for collision detection. Something along these lines: Polygon polygon = new Polygon(); polygon.AddPoint(x, y); polygon.AddPoint(x2, y2); polygon.AddPoint(x3, y3); if(polygon.Insertects(polygon2)) // Collision! You get the idea - the more points you add, the more complex your shape becomes. I can't seem to find one anywhere. Thanks.

Share on other sites
Wait!!

Noone change his ranking, he's uber 1337!!

Share on other sites
CorsixPolygon.h:
#pragma once#include <vector>#include <math.h>#include <windows.h>struct POINTf{	float x;	float y;};struct CorsixLine{	POINTf Point[2];	RECT Bound; //Bounding rectangle	void Translate(CorsixLine* dest,float x, float y); //Translate by x,y into dest};class CorsixPolygon{protected:	#define lower(a,b) (a<b?a:b)	#define higher(a,b) (a>b?a:b)	std::vector<POINTf>		m_vPoints; //Vector of points	std::vector<CorsixLine>	m_vLines; //Vector of lines	RECT					m_rBound; //Bounding rectangle	bool					m_bUpdated; //Are lines up to date with points?	POINTf					m_ptRotationCenter;public:	CorsixPolygon();	void CalculateBounds();	void CalculateLines();	void AddPoint(POINTf pt);	void AddPoint(float x,float y);	bool PointInside(float x, float y);//Checks if x,y is inside the polygon	void Clear();//Erases the polygon	RECT GetBounds();	std::vector<POINTf>* GetPoints();	std::vector<CorsixLine>* GetLines();	bool TestCollision(POINTf us,POINTf pt);	bool TestCollision(float ourx, float oury, float x, float y);	void Translate(CorsixPolygon* dest,float x, float y,bool IgnorePoints = false); //Translate by x,y into dest	void Rotate(float radians);	void SetRotationCenter(POINTf center);};bool CheckPolyCollide(POINTf Pos1,CorsixPolygon Poly1,POINTf Pos2,CorsixPolygon Poly2);

CorsixPolygon.cpp:
#include "stdafx.h"#include "CorsixPolygon.h"//Purpose: Translate line based on its "real world" position//In://   x - x position of line in "real world"//   y - y position of line in "real world"//In/Out://   dest - where to put translated line//Out://   (none)void CorsixLine::Translate(CorsixLine* dest,float x, float y){	*dest = *this;	dest->Bound.top += y;	dest->Bound.bottom += y;	dest->Bound.left += x;	dest->Bound.right += x;	dest->Point[0].x += x;	dest->Point[0].y += y;	dest->Point[1].x += x;	dest->Point[1].y += y;}//ConstructorCorsixPolygon::CorsixPolygon() 	: m_bUpdated(true){	m_ptRotationCenter.x = 0;	m_ptRotationCenter.y = 0;}//Purpose: Calcualte bounding rectangle for polygon//In://   (none)//In/Out://   (none)//Out://   (none)void CorsixPolygon::CalculateBounds(){	std::vector<POINTf>::iterator itr = m_vPoints.begin();	m_rBound.left = m_rBound.right = itr->x;	m_rBound.top = m_rBound.bottom = itr->y;	for(;itr != m_vPoints.end();++itr)	{		m_rBound.left = lower(m_rBound.left,itr->x);		m_rBound.top = lower(m_rBound.top,itr->y);		m_rBound.right = higher(m_rBound.right,itr->x);		m_rBound.bottom = higher(m_rBound.bottom,itr->y);	}}//Purpose: Convert vector of points into lines//In://   (none)//In/Out://   (none)//Out://   (none)void CorsixPolygon::CalculateLines(){	m_vLines.clear();	CorsixLine Ln;	for (unsigned float cv=0;cv<m_vPoints.size();++cv)	{		Ln.Point[0] = m_vPoints[cv];		Ln.Point[1] = m_vPoints[(cv==m_vPoints.size()-1?0:cv+1)];		Ln.Bound.top = lower(Ln.Point[0].y,Ln.Point[1].y);		Ln.Bound.left = lower(Ln.Point[0].x,Ln.Point[1].x);		Ln.Bound.bottom = higher(Ln.Point[0].y,Ln.Point[1].y);		Ln.Bound.right = higher(Ln.Point[0].x,Ln.Point[1].x);		m_vLines.push_back(Ln);	}	m_bUpdated = true;}//Purpose: Add a point to the end of the polygon//In://   pt - point//In/Out://   (none)//Out://   (none)void CorsixPolygon::AddPoint(POINTf pt){	if(!m_vPoints.size())	{		m_rBound.left = m_rBound.right = pt.x;		m_rBound.top = m_rBound.bottom = pt.y;	}	else	{		m_rBound.left = lower(m_rBound.left,pt.x);		m_rBound.top = lower(m_rBound.top,pt.y);		m_rBound.right = higher(m_rBound.right,pt.x);		m_rBound.bottom = higher(m_rBound.bottom,pt.y);	}	m_vPoints.push_back(pt);	m_bUpdated = false;}//Purpose: Add a point to the end of the polygon//In://   x - x co-ord of point//   y - y co-ord of point//In/Out://   (none)//Out://   (none)void CorsixPolygon::AddPoint(float x,float y){	if(!m_vPoints.size())	{		m_rBound.left = m_rBound.right = x;		m_rBound.top = m_rBound.bottom = y;	}	else	{		m_rBound.left = lower(m_rBound.left,x);		m_rBound.top = lower(m_rBound.top,y);		m_rBound.right = higher(m_rBound.right,x);		m_rBound.bottom = higher(m_rBound.bottom,y);	}	POINTf tmp;	tmp.x = x;	tmp.y = y;	m_vPoints.push_back(tmp);	m_bUpdated = false;}//Purpose: Check if point is inside the polygon//In://   x - x co-ord of point//   y - y co-ord of point//In/Out://   (none)//Out://   boolean valuebool CorsixPolygon::PointInside(float x, float y){	if(m_vPoints.size() < 3)		return false;	if ((x < m_rBound.left) || (x > m_rBound.right) || (y < m_rBound.top) || (y > m_rBound.bottom))		return false;	if(!m_bUpdated)		CalculateLines();	bool inside = false;	POINTf cp,np;	for (std::vector<CorsixLine>::iterator itr = m_vLines.begin();itr != m_vLines.end();++itr)	{		cp = itr->Point[0];		np = itr->Point[1];		if ((((cp.y <= y) && (y < np.y)) || ((np.y <= y) && (y < cp.y))) &&		(x < (np.x - cp.x) * (y - cp.y) / (np.y - cp.y) + cp.x))		{			inside = !inside;		}	}	return inside;}//Purpose:Erase polygon//In://   (none)//In/Out://   (none)//Out://   (none)void CorsixPolygon::Clear(){	m_vPoints.clear();	m_bUpdated = false;}RECT CorsixPolygon::GetBounds(){	return m_rBound;}std::vector<POINTf>* CorsixPolygon::GetPoints(){	return &m_vPoints;}std::vector<CorsixLine>* CorsixPolygon::GetLines(){	if(!m_bUpdated)		CalculateLines();	return &m_vLines;}//Purpose: Check if "real world" point is inside polygon based on our "real world" position//In://   us - our "real world" position//   pt - point to test//In/Out://   (none)//Out://   boolean valuebool CorsixPolygon::TestCollision(POINTf us,POINTf pt){	return TestCollision(us.x,us.y,pt.x,pt.y);}//Purpose: Check if "real world" point is inside polygon based on our "real world" position//In://   ourx - our x co-ord in real world//   oury - our y co-ord in real world//   x - x co-ord of point to test//   y - y co-ord of point to test//In/Out://   (none)//Out://   boolean valuebool CorsixPolygon::TestCollision(float ourx, float oury, float x, float y){	if ((x < (ourx+m_rBound.left)) || (x > (ourx+m_rBound.right)) || (y < (oury+m_rBound.top)) || (y > (oury+m_rBound.bottom)))		return false;	return PointInside(x-ourx,y-oury);}//Purpose: Translate polygon based on its "real world" position//In://   x - x position of line in "real world"//   y - y position of line in "real world"//   IgnorePoints - wether or not to translate points//In/Out://   dest - where to put translated line//Out://   (none)void CorsixPolygon::Translate(CorsixPolygon* dest,float x, float y,bool IgnorePoints){	if(!m_bUpdated)		CalculateLines();	*dest = *this;	for (unsigned float cl = 0;cl < m_vLines.size();++cl)		m_vLines[cl].Translate(&dest->m_vLines[cl],x,y);	dest->m_rBound.top += y;	dest->m_rBound.bottom += y;	dest->m_rBound.left += x;	dest->m_rBound.right += x;	if(!IgnorePoints)	{		for(std::vector<POINTf>::iterator itr = dest->m_vPoints.begin();itr != dest->m_vPoints.end();++itr)		{			itr->x += x;			itr->y += y;		}	}}//Purpose: Set the center of rotation for the polygon//In://   center - center of rotation//In/Out://   (none)//Out://   (none)void CorsixPolygon::SetRotationCenter(POINTf center){	m_ptRotationCenter = center;}//Purpose: Rotate the polygon by the given number of radians//In://   radians - number of radians to rotate//In/Out://   (none)//Out://   (none)void CorsixPolygon::Rotate(float radians){	double c = cos(radians), s = sin(radians);	for(std::vector<POINTf>::iterator itr = m_vPoints.begin();itr != m_vPoints.end();++itr)	{		float oldx = itr->x;		itr->x = ((c * (itr->x-m_ptRotationCenter.x)) - (s * (itr->y-m_ptRotationCenter.y)) + m_ptRotationCenter.x);		itr->y = ((s * (oldx-m_ptRotationCenter.x)) + (c * (itr->y-m_ptRotationCenter.y)) + m_ptRotationCenter.y);		if(itr == m_vPoints.begin())		{			m_rBound.left = m_vPoints[0].x;			m_rBound.top = m_vPoints[0].y;			m_rBound.right = m_vPoints[0].x;			m_rBound.bottom = m_vPoints[0].y;		}		else		{			m_rBound.left = lower(m_rBound.left,itr->x);			m_rBound.top = lower(m_rBound.top,itr->y);			m_rBound.right = higher(m_rBound.right,itr->x);			m_rBound.bottom = higher(m_rBound.bottom,itr->y);		}	}	m_bUpdated = false;}//Purpose: Check if two polygons have collided//In://   Pos1 - "real world" position of Poly1//   Poly1 - A Polygon//   Pos2 - "real world" position of Poly2//   Poly2 - A Polygon//In/Out://   (none)//Out://   boolean valuebool CheckPolyCollide(POINTf Pos1,CorsixPolygon Poly1,POINTf Pos2,CorsixPolygon Poly2){	CorsixPolygon Polygons[2]; //Space for our translated polygons	Poly1.Translate(Polygons,Pos1.x,Pos1.y); //Translate Poly1	Poly2.Translate(&Polygons[1],Pos2.x,Pos2.y); //Translate Poly2	RECT Rects[2] = {Polygons[0].GetBounds(),Polygons[1].GetBounds()}; //Bounding rectangles, init to bounds of polygons	if(Rects[0].left <= Rects[1].right && Rects[1].left <= Rects[0].right && //Check if bounding rectangles collide		Rects[0].top <= Rects[1].bottom && Rects[1].top <= Rects[0].bottom) //(if not then quit early)	{		double	IntersectX,IntersectY,m[2],b[2]; //m = gradient, b = y intercept		float	vc[2]; //vc = VerticalCheck		int		iv,nv; //iv = is verical, nv = not vertical		std::vector<CorsixLine>::iterator ItrA, ItrB;		std::vector<POINTf>::iterator itr;		//Loop through points of Poly1 and check if any of them are inside Poly2 (->collided)		for(itr = Polygons[0].GetPoints()->begin();itr != Polygons[0].GetPoints()->end();++itr)			if(Polygons[1].TestCollision(0,0,itr->x,itr->y))				return true;		//Loop through points of Poly2 and check if any of them are inside Poly1 (->collided)		for(itr = Polygons[1].GetPoints()->begin();itr != Polygons[1].GetPoints()->end();++itr)			if(Polygons[0].TestCollision(0,0,itr->x,itr->y))				return true;		//Loop though lines and check for interception...		for(ItrA = Polygons[0].GetLines()->begin();ItrA != Polygons[0].GetLines()->end();++ItrA) //Loop though Poly1's lines		{			Rects[0] = ItrA->Bound; //Get bounding rectangle			vc[0] = ItrA->Point[0].x - ItrA->Point[1].x; //Check if vertical (0=yes)			if(vc[0])			{				m[0] = ((ItrA->Point[0].y - ItrA->Point[1].y) / vc[0]); //If not vertical, find gradient				b[0] = ItrA->Point[0].y - (m[0] * ItrA->Point[0].x); //Find y-intercept			}			for(ItrB = Polygons[1].GetLines()->begin();ItrB != Polygons[1].GetLines()->end();++ItrB) //Loop though Poly2's lines			{				Rects[1] = ItrB->Bound; //Get bounding rectangle				if(Rects[0].left <= Rects[1].right && Rects[1].left <= Rects[0].right && //Check if bounding rectangles collide					Rects[0].top <= Rects[1].bottom && Rects[1].top <= Rects[0].bottom) //(if not then skip)				{					vc[1] = ItrB->Point[0].x - ItrB->Point[1].x; //Check if vertical (0=yes)					if(vc[1])					{						m[1] = ((ItrB->Point[0].y - ItrB->Point[1].y) / vc[1]); //If not vertical, find gradient						b[1] = ItrB->Point[0].y - (m[1] * ItrB->Point[0].x); //Find y-intercept					}					if(vc[0] == 0 || vc[1] == 0) //If we have any vertical lines					{						if(vc[0] == 0 && vc[1] == 0)						{							return true;						}						else						{							// Check if they collide							iv = (vc[0]?1:0);							nv = (iv?0:1);							if(b[nv] <= Rects[iv].bottom && b[nv] >= Rects[iv].top && Rects[nv].left <= Rects[iv].left && Rects[nv].right >= Rects[iv].left)								return true;						}						continue;					}					IntersectX = (b[1] + (-(b[0]))) / (m[0] + (-(m[1]))); //Find XIntercept					IntersectY = m[0] * IntersectX + b[0]; //Find YInercept					//if(Polygons[0].PointInside(IntersectX,IntersectY) || Polygons[1].PointInside(IntersectX,IntersectY))					//	return true;					if(IntersectX >= Rects[0].left && IntersectX <= Rects[0].right && IntersectY >= Rects[0].top && IntersectY <= Rects[0].bottom						&& IntersectX >= Rects[1].left && IntersectX <= Rects[1].right && IntersectY >= Rects[1].top && IntersectY <= Rects[1].bottom						)//&& ((float)b[0]) == ((float)IntersectY - (m[0] * IntersectX)) && ((float)b[1]) == ((float)IntersectY - (m[1] * IntersectX)))						return true;				}			}		}	}	return false;}

Usage:
CorsixPolygon polygon = new CorsixPolygon();polygon.AddPoint(x, y);polygon.AddPoint(x2, y2);polygon.AddPoint(x3, y3);if(CheckPolyCollide(position_of_polygon,polygon,position_of_polygon2,polygon2)// Collision!

Thanks Corsix.

• What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 9
• 13
• 9
• 9
• 15
• Forum Statistics

• Total Topics
634077
• Total Posts
3015360
×