Concave and Convex Polygon

Question

0.00/5 (No votes)

See more:

How can I identify and remove those four red points drawn in image at below link.
http://pritesharyan.weebly.com/question.html[^]

Those four points make that polygon a concave polygon that’s why I want to remove it.

My goal is to convert concave polygon to convex by removing this kind of point by identifying and removing those points.

IS THERE ANY MATHEMATICAL WAY TO IDENTIFY AND REMOVE THIS KIND OF POINTS?

Thanks.

Posted 30-Nov-10 23:40pm

Pritesh Aryan

Updated 1-Dec-10 0:45am

v9

Add a Solution

1 solution

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Sauro Viti · Accepted Answer · 2010-12-01T00:43:00

To identify such points is quite simple:

consider the point Pn and the two segments adiacent to the point; they are S1 = Pn - Pn-1 and S2 = Pn+1 - Pn
now consider the scalar and vectorial product of the two segments:
- S1 * S2 = |S1| * |S2| * cos(alpha)
- S1 ^ S2 = |S1| * |S2| * sin(alpha)
where alpha is the angle that S1 must be rotated by to get aligned to S2
to compute the scalar and vectorial products, we will use the formula below:
- S1 * S2 = (X1 - Xn-1) * (Xn+1 - Xn) + (Yn - Yn-1) * (Yn+1 - Yn)
- S1 ^ S2 = (Xn - Xn-1) * (Yn+1 - Yn) - (Yn - Yn-1) * (Xn+1 - Xn)
now, to get alpha you can use the following formula:
finally, the point Pn should be removed if the value obtained for alpha is greater than zero and your sequence of points describe a clock-wise polygon or, if the value of alpha is less than zero and your sequence of points give a counterclock-wise polygon