回覆列表
  • 1 # 小紅的甜心

    演算法是假設你沿著邊走,如果是凸的就會一直向一個方向轉彎,例如都向左拐,突然向右拐說明不是凸的

    /*

    * 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;

    }

  • 中秋節和大豐收的關聯?
  • dota單挑最給力的英雄,前期中期後期出裝和技巧?