Finding which point is convex in a simple polygon

[AlwaysLearning]

I have a n vertex 2D polygon.
I wish to determine if a point is the convex point.

I would prefer a method that is potentially faster than this algorithm:

Create a 2d bool map large enough to map the entire polygon onto.
0 - doesn't cover
1 - is covering (so 1 is the area which the polygon exists)

CurrPt = current point of testing
PrevPt = previous point of current
NextPt = next of current

Theoretically create a line segment from PrevPt to NextPt.
Step 1 pixel from PrevPt to NextPt
Test to see if this 1 step exists as 1 on bool map.

If true, it is concave.
If false, it is convex.

[Duthomhas]

The Wikipedia is always a good place to start.
http://en.wikipedia.org/wiki/Point_in_polygon

Good luck!

[AlwaysLearning]

Thanks for your effort. However it is not applicable.

Unfortunately the point I'm looking at is on the boundary. Which makes the point in poly algorithms unusable since it is looking to see if a pt is on the polygon or not rather than if a point is convex '-ing' a polygon.

From wiki:
Ray casting-
"If the point in question is not on the boundary of the polygon, the number of intersections is an even number if the point is outside, and it is odd if inside. "

Winding (wiki is terrible at explaining this one)
It basically counts how many points 'wrap' around the point in question. But the same issue arises since the point in question is on the boundary.

[Mitsakos]

If I understand correctly you are trying to find out if a point is on the sides of the polygon?

Then if you have the edges of the polygon, you can calculate the formulas for the lines determined by them and then check if the point belongs to one of those lines.

If I misunderstood can you explain what exactly you are trying to find?
( I was good at geometry but very bad with the english terminology :P )

[Duthomhas]

It is applicable if you use the information correctly.

To test to see if a point is concave on an otherwise convex polygon, "remove" the point from the polygon and test to see if it is inside or not.

____
/\ /\ / \
/ \/ | / .__|___
/ p | / p | point is inside == polygon is concave
\_______| \_______|


Hope this helps.

[AlwaysLearning]

Sorry mixed up terms, I meant finding a point that makes a polygon concave.
http://mathworld.wolfram.com/ConcavePolygon.html

I meant to use the made up term "concave point" (I don't think there is such a term) to describe the point(s) that is making an convex polygon into a concave one. For example, the concave point is 'B' in (b)

http://acm.pku.edu.cn/JudgeOnline/images/2007_1.jpg

Mitsakos:
I am looking for a way to determine if there is a way to find a 'concave point', B in the above example.

Duoas:

    ____________
   /  ___      |
  /  |   |     |
  |   \  |     |
  |   o\ |   a |
  |    / |_/\__|
  |    \_____
  \__________|

As weird as this looks, this is a simple polygon since none of the sides intersect.

I was considering your example in the source you gave but what are the parameters to 'block off' the pt in question? I thought about using the idea of measuring the extreme points and any points falling inside of those boundaries as being convex but the above example defeats that.

'O' is convex , it is extending itself into 'negative' space but the negative space itself is concave.

'a' is concave.

[Mitsakos]

If I understand correctly a concave point in a polygon is one that one of it's internal angles is greater than 180 degrees.

Then why don't you find the angles of each point ?
Do you have the coordinates of the points?

[AlwaysLearning]

You are correct.

How would I find if an internal angle is >180 when I have no reference to what is interior or not? (look @ polygon in last post)

IE:

I will only have this information 3 points forming

>

This could be 30 or 330 degrees.

[Mitsakos]

You can take that every two points create a vector (math vector, not c++).
Then you can find the angle of them using the vectors formulas:

(x1 * x2) + (y1 * y2)
cos( φ ) = -------------------------------------------
sqrt( x1^2 + y1^2 ) * sqrt( x2^2 + y2^2 )

[AlwaysLearning]

Doesn't that always find the smaller angle?

[Mitsakos]

I think not, let me search for it a little and I'll post again.

[EDIT]
The angle can be between -π< φ ≤π or 0≤ φ <2π which means that the angle can be 0-360 degrees. So, it will return the real angle between two points, you just have to take the right points .

[AlwaysLearning]

Ok thanks, I'll test these out.

[Mitsakos]

You can make a function with this formula and then pass as parameters the previous and the next point of the angle you want to check.
If all the returns from the function are the same (0-180 degrees or -180 - 0 degrees) then the polygon is convex. If one of them is different then the polygon is concave.

Hope this helps