Is a polygon convex?
Hoss
or not they define a convex polygon?
News Reader
> Given a set of N > 3 2D points (x, y), how would you determine whether
> or not they define a convex polygon?
on the same side of the line defined by P(i) and P(i+1) for all i
(convex case).
-- NR
Kaba
Dave Eberly
news:MPG.242b29204...@news.cc.tut.fi...
I just get a blank page when I click this link.
The OP's subject line is "Is a polygon convex?" I assume the intent is that
the polygon is simple and now you need to determine whether it is convex.
Does your response change in this case?
Of interest:
"A History of Linear-time Convex Hull Algorithms for Simple Polygons"
http://cgm.cs.mcgill.ca/~athens/cs601/
--
Dave Eberly
http://www.geometrictools.com
Hoss
points. I need to determine whether or not they define a simple,
convex polygon.
I also cannot use any information about the ordering of the vertices
(either CW or CCW) because I am actually going to use this information
in another algorithm which is doing just that: ordering the vertices
of a simple convex polygon CCW. That algorithm relies on the vertices
being a convex simple poly
Daniel Pitts
happens when its not? Can you detect that after or during the run of the
algorithm? That might give you your answer.
--
Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>
Kaba
> I just get a blank page when I click this link.
Hmm.. It shows fine to me. I don't know what the problem might be.
Anyway, the image shows a polygon that intersects itself, but still
fulfills the requirement of always turning to the same direction.
> The OP's subject line is "Is a polygon convex?" I assume the intent is that
> the polygon is simple and now you need to determine whether it is convex.
> Does your response change in this case?
Yes.
Simple + turning condition <=> convex
(at least intuitively, haven't proved).
Hoss
Daniel,
good idea, but I dont think it will work (in some cases). Consider a
simple polygon that is "almost convex" (hopefully you can see my
drawing)
x x
x
x x
These vertices can still be put into a strictly CCW ordering if you
pick the right starting vertex, but its not a convex polygon. So I
guess convex-ness is an additional requirement that I want to put on.
TR Oltrogge
"Hoss" <todd....@gmail.com> wrote in message
news:31deb69d-e896-44c6...@k19g2000prh.googlegroups.com...
> Given a set of N > 3 2D points (x, y), how would you determine whether
> or not they define a convex polygon?
Given the points are in order, successively calculate the cross product of
the vector coming into each vertex with the vector leaving that vertex and
see if these cross products all have the same sign...
/* POLYGON
A program to show that testing for the sign of the cross product of
vectors
formed by the two sides of a polygon vertex will tell if you are turning
left
or turning right. A polygon where all of the cross products have the same
sign is guaranteed to be convex and thus a chord between any two vertices
will lie entirely within the polygon.
*/
#include <stdio.h>
#include <stdlib.h>
//Define a 2D polygon as a set of vertices in the X-Y plane
struct vertex {
float x;
float y;
} v[5]={{0,0},{1,0},{1,1},{0.5,1.2},{0,1}}; //A polygon with 5 vertices in
the X-Y plane
int main() {
int current,prior,next,n=5,turn_direction;
float vz; //Magnitude of cross product, which is a vector in the Z direction
for (current=0 ; current<n ; current++) {
if (current==0) //If current vertex we're considering is the
first one
prior=n-1; //Prior vertex is last one
else
prior=current-1; //Else prior vertex is current minus one
if (current==(n-1)) //If current vertex is last one
next=0; //Next vertex is first one
else
next=current+1; //Else it's simply current plus one
/*
Form cross product of vector from prior vertex to current one with
vector from current vertex to next one
*/
vz= (v[current].x-v[prior] .x)*(v[next] .y-v[current].y)
-(v[next] .x-v[current].x)*(v[current].y-v[prior] .y);
printf("vz=%f\n",vz); //Print its value as a FYI
if (current==0) //If we just did the first vertex
turn_direction=(vz<0.0 ? 0 : 1); //Compute direction of the turn
and save it
else {
if ((vz<0.0 ? 0 : 1) != turn_direction)
printf("polygon is not convex at vertex %d\n",current);
}
}
return(0);
}
Hoss
Dave Eberly
> Interesting idea. However, note that I said "I also cannot use any
> information about the ordering of the vertices"
Which is why you are doomed to fail.
mike
bb08cb...@v13g2000pro.googlegroups.com>, todd....@gmail.com says...
you can't confirm that it is a convex algorithm. Consider four points
A,B,C,D that form teh vertices of a square. If you assume that the sides
of the polygon are AB,BC,CD,DA then it is convex (i.e. a square), but if
the sides are AC,CB,BD,DA then it is not convex (i.e. has a 'bow-tie'
shape).
What you might want to ask is "can the points form a convex polygon?"
and the answer to this will be "Yes" if and only if there are no points
within the interior of the convex hull formed by the set of points. An
alternate test would be to construct the convex hull of the set of
points and check that all the points form part of the convex hull
(ensuring that the CH algorithm includes all points that are on the
boundary). If this is the case then once again the answer is "Yes".
--
Mike
mike
dNOSPA...@usemydomain.com says...
> "Hoss" <todd....@gmail.com> wrote in message
> news:7bad7115-9e0e-4f97...@d19g2000prh.googlegroups.com...
> > Interesting idea. However, note that I said "I also cannot use any
> > information about the ordering of the vertices"
>
> Which is why you are doomed to fail.
>
--
Mike
Ron Francis
That's one that I didn't think of!
Thanks Kaba.
Regards
Ron Francis
www.RonaldFrancis.com
a.h....@gmail.com
> "Kaba" <n...@here.com> wrote in messagenews:MPG.242b3d2ac...@news.cc.tut.fi...
Why not compute the convex polygon from the set of points and then
determine if each point was used? Graham scan could be used for that
(http://en.wikipedia.org/wiki/Graham_scan), which can also signal when
a point is dropped from the output-polygon.
Andre
Ben C
You can use the same idea, but flip the sense of the "the same side as"
whenever you pass a crossing.
But for all purposes I've encountered, if a polygon is non-simple, it's
bad enough without worrying about whether it's convex or not. You
probably need to cut it up into simple polys first, and then cut those
up into convex polys (perhaps via monotone polys).
I can't think of anything useful to do with the information that a
non-simple polygon has all convex vertices, but maybe I should read the
rest of this thread first.