• entries
743
1924
• views
584744

# Convex polygon hell

118 views

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];	A=Vector(-A.Y,A.X);		Vector B=Outline[Last]-Pos;	if(A.Dot(B)>0) Pos=ClosestPointToRay(Outline[Last],Outline[Last-1],Pos);	Vector C=Outline[Last]-Outline[0];	C=Vector(-C.Y,C.X);		if(C.Dot(B)>0) Pos=ClosestPointToSegment(Outline[0],Outline[Last],Pos);	Vector D=Outline[0]-Outline[1];	D=Vector(-D.Y,D.X);	if(D.Dot(Outline[0]-Pos)<1.0f)		{	    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.

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

• ### What is your GameDev Story?

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

(You must login to your GameDev.net account.)

×