Jump to content
  • Advertisement
Sign in to follow this  
GroZZleR

Polygon Class - Anyone willing to share?

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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;
}

//Constructor
CorsixPolygon::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 value
bool 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 value
bool 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 value
bool 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 value
bool 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!

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!