演算法是假設你沿著邊走,如果是凸的就會一直向一個方向轉彎,例如都向左拐,突然向右拐說明不是凸的
/*
* Variable polygon is a vector of points.
* Returns true if polygon is convex, otherwise false.
*/
public boolean checkConvexity()
{
if (polygon.size() < 3) return false;
Point p;
Point v;
Point u;
int res = 0;
for (int i = 0; i < polygon.size(); i++)
p = polygon.get(i);
Point tmp = polygon.get((i+1) % polygon.size());
v = new Point();
v.x = tmp.x - p.x;
v.y = tmp.y - p.y;
u = polygon.get((i+2) % polygon.size());
if (i == 0) // in first loop direction is unknown, so save it in res
res = u.x * v.y - u.y * v.x + v.x * p.y - v.y * p.x;
else
int newres = u.x * v.y - u.y * v.x + v.x * p.y - v.y * p.x;
if ( (newres > 0 && res < 0) || (newres < 0 && res > 0) )
return false;
}
return true;
演算法是假設你沿著邊走,如果是凸的就會一直向一個方向轉彎,例如都向左拐,突然向右拐說明不是凸的
/*
* Variable polygon is a vector of points.
* Returns true if polygon is convex, otherwise false.
*/
public boolean checkConvexity()
{
if (polygon.size() < 3) return false;
Point p;
Point v;
Point u;
int res = 0;
for (int i = 0; i < polygon.size(); i++)
{
p = polygon.get(i);
Point tmp = polygon.get((i+1) % polygon.size());
v = new Point();
v.x = tmp.x - p.x;
v.y = tmp.y - p.y;
u = polygon.get((i+2) % polygon.size());
if (i == 0) // in first loop direction is unknown, so save it in res
res = u.x * v.y - u.y * v.x + v.x * p.y - v.y * p.x;
else
{
int newres = u.x * v.y - u.y * v.x + v.x * p.y - v.y * p.x;
if ( (newres > 0 && res < 0) || (newres < 0 && res > 0) )
return false;
}
}
return true;
}