Sign in to follow this  
_Krish_

How to find inner contour of polygons.

Recommended Posts

Hi, i have points of a polygon(it can be concave or convex). i need to find the inner contor points of the polygon for a given line thickness. i need some mathematical operations to find those points. any body please help me Krish

Share this post


Link to post
Share on other sites
Hey, I never had a problem like this, so I found it challenging and just started to expirement :P

This is what I came up with:


(Sorry for the poor drawing, but I only had openoffice installed and I m short on time right now)

- The red vectors are the outlines of the polygon.
- 2 blue vectors represent the unit-vectors of the outline vectors at each point
- The green vectors are the 2 blue unit-vectors added together
- The black is the orthogonal unit-vector of the green one (which can be multiplyed by the thickness to get thicker lines as this one points to the inside)

You can also get the black vector by inverting the first blue vector.

With that knowledge it shouldn't be too hard. There are probably other solutions for this, but this just came to my mind.
But you should remember that you won't get a line thickness in 3D (just incase you want to do this) because the inner vectors are always at the polygon-points-plane.

//Edit: You must also take the angle difference (between the outline and the vector pointing into the polygon) into account.

Share this post


Link to post
Share on other sites
thank you,
i need to implement this operations in my program.
there was some other methods where i had to deal with infinity.
so i need a solution which must be simple and no infiniy.


Krish

Share this post


Link to post
Share on other sites
Quote:
Original post by J-Fox
- The black is the orthogonal unit-vector of the green one (which can be multiplyed by the thickness to get thicker lines as this one points to the inside)


Shouldn't line thickness be perpendicular to the edge? The black vector isn't perpendicular to the edges.

Share this post


Link to post
Share on other sites
I'm not saying that it can't be used, I'm just saying you can't use a constant thickness factor with it.
You have to use some more trigonometry to get its true length. If you know the length and angle of one side
of a triangle, you can get the remaining sides.

Share this post


Link to post
Share on other sites
At every corner ABC, you want to find contour point that corresponds to B.
In code:
Vector Normal(Vector V){
return Vector(-V.y,V.x)
}
void Normalize(Vector &V){/// modifies V to make it have length 1.
l=1/sqrt(V.x*V.x + V.y*V.y)
V.x*=l;
V.y*=l;
}
...

N1=Normal(A-B);
N2=Normal(B-C);
Normalize(N1);
Normalize(N2);
D=(N1+N2);
s=D.x*D.x+D.y*D.y;
D=D*2*r/s;

where r is thickness. All capital letters are vectors.
How it works:
N1 and N2 are inward pointing normals. (or outward, depend to winding order)
let alpha= angle ABC
Sum of normals gives a vector which is pointing towards the contour point, and has length equal to 2*sin(alpha/2) [easy to see if you make a drawing]

Angle between D and AB is alpha/2
When contour point is at distance l along the line D , its distance to AB (and BC) is
l*sin(alpha/2) = r
l = r/sin(alpha/2)
Length of D is already equal to 2*sin(alpha/2) . So, when we multiply D by 2*r/[length of d squared] , we obtain length sin(alpha/2)*2*2*r/(2*sin(alpha/2))^2 = r/sin(alpha/2)

Share this post


Link to post
Share on other sites
friends,
i solved the problem in this way,

for a corner ABC i found two points p and Q in a perpendicular distance(line thickness) from AB, and two points R and S in a perpendicular distance(line thickness) from BC, then i found intersection PQ and RS, the point is the contour point corresponding to B.

thanks guys,

_Krish_

Share this post


Link to post
Share on other sites
FYI Dmytry's solution is equivalent to explicitly building the lines and intersecting.

But if your current solution is working then it's probably good enough for now ;)

Share this post


Link to post
Share on other sites

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

Sign in to follow this