Advertisement Jump to content
  • Advertisement
  • entries
  • comments
  • views

Convex polygon hell

Sign in to follow this  


Haven't posted in what seems like ages. Been a bit stuck on constraining polygons to convex.

However, I think it is now working. I wanted to constrain it as the user moves the mouse, so that you can't move the vertex cursor into a position that, if clicked, could create a non-convex polygon.

Been a bit of a nightmare, but it seems to be okay now. Bit complicated to explain in English, so here's some horrible code:

Vector ClosestPointToSegment(Vector Va,Vector Vb,Vector Pos)
Vector A=Pos-Va,B=Vb-Va; float T=A.Dot(B)/B.Dot(B); return(T<=0.0f ? Va : (T>=1.0f ? Vb : Va+T*B));

Vector ClosestPointToRay(Vector Va,Vector Vb,Vector Pos)
Vector A=Pos-Va,B=Vb-Va; float T=A.Dot(B)/B.Dot(B); return(T>=0.0f ? Va : Va+T*B);

Vector IntersectLines(Vector A,Vector B,Vector C,Vector D)
float M1=((B.X-A.X)!=0 ? (B.Y-A.Y)/(B.X-A.X) : 1e10f);
float M2=((D.X-C.X)!=0 ? (D.Y-C.Y)/(D.X-C.X) : 1e10f);

float C1=(A.Y-M1*A.X);
float C2=(C.Y-M2*C.X);

float DetInv=1/(M1*-1-M2*-1);

return Vector(((-1*C2-C1*-1)*DetInv),((M2*C1-M1*C2)*DetInv));

bool LinesParallel(Vector A,Vector B,Vector C,Vector D)
float M1=((B.X-A.X)!=0 ? (B.Y-A.Y)/(B.X-A.X) : 1e10f);
float M2=((D.X-C.X)!=0 ? (D.Y-C.Y)/(D.X-C.X) : 1e10f);

return fabs(M1-M2)<0.01f;

void ConstrainClockwise(std::vector &Outline,Vector &Pos)
size_t Last=Outline.size()-1;

Vector A=Outline[Last]-Outline[Last-1];

Vector B=Outline[Last]-Pos;

if(A.Dot(B)>0) Pos=ClosestPointToRay(Outline[Last],Outline[Last-1],Pos);

Vector C=Outline[Last]-Outline[0];

if(C.Dot(B)>0) Pos=ClosestPointToSegment(Outline[0],Outline[Last],Pos);

Vector D=Outline[0]-Outline[1];

if(LinesParallel(Outline[Last],Outline[0],Outline[0],Outline[1])) Pos=ClosestPointToSegment(Outline[0],Outline[Last],Pos);
else Pos=IntersectLines(Outline[0],Outline[1],Outline[Last],Pos);

The first three helper functions were taken from code on the internet, and the main function was a combination of reasoning and fiddling until it worked.

Next to implement is dragging vertices without allowing non-convex polys, but I think that will be a lot simpler - at any point consider the vertex to one side (A), the vertex being moved (B) and the vertex to the other side (C). Depending on whether the poly is clockwise or not, if the dot product of the two vectors formed by A-B and B-C is either less than or greater than zero, depending on the order of the poly, form a straight line between A and C and make B the closest point to the mouse cursor on the A-C segment.

That's the theory anyway.
Sign in to follow this  


Recommended Comments

There are no comments to display.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
  • Advertisement

Important Information

By using, you agree to our community Guidelines, Terms of Use, and Privacy Policy. is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!