/*
* Copyright (c) 2006-2009 Erin Catto http://www.box2d.org
*
* This software is provided 'as-is', without any express or implied
* warranty.  In no event will the authors be held liable for any damages
* arising from the use of this software.
* Permission is granted to anyone to use this software for any purpose,
* including commercial applications, and to alter it and redistribute it
* freely, subject to the following restrictions:
* 1. The origin of this software must not be misrepresented; you must not
* claim that you wrote the original software. If you use this software
* in a product, an acknowledgment in the product documentation would be
* appreciated but is not required.
* 2. Altered source versions must be plainly marked as such, and must not be
* misrepresented as being the original software.
* 3. This notice may not be removed or altered from any source distribution.
*/

void b2PolygonShape::Set(const b2Vec2* vertices, int32 count)
{
    b2Assert(3 <= count && count <= b2_maxPolygonVertices);
    if (count < 3)
    {
        SetAsBox(1.0f, 1.0f);
        return;
    }

    int32 n = b2Min(count, b2_maxPolygonVertices);

    // Perform welding and copy vertices into local buffer.
    b2Vec2 ps[b2_maxPolygonVertices];
    int32 tempCount = 0;
    for (int32 i = 0; i < n; ++i)
    {
        b2Vec2 v = vertices[i];

        bool unique = true;
        for (int32 j = 0; j < tempCount; ++j)
        {
            if (b2DistanceSquared(v, ps[j]) < 0.5f * b2_linearSlop)
            {
                unique = false;
                break;
            }
        }

        if (unique)
        {
            ps[tempCount++] = v;
        }
    }

    n = tempCount;
    if (n < 3)
    {
        // Polygon is degenerate.
        b2Assert(false);
        SetAsBox(1.0f, 1.0f);
        return;
    }

    // Create the convex hull using the Gift wrapping algorithm
    // http://en.wikipedia.org/wiki/Gift_wrapping_algorithm

    // Find the right most point on the hull
    int32 i0 = 0;
    float32 x0 = ps[0].x;
    for (int32 i = 1; i < n; ++i)
    {
        float32 x = ps[i].x;
        if (x > x0 || (x == x0 && ps[i].y < ps[i0].y))
        {
            i0 = i;
            x0 = x;
        }
    }

    int32 hull[b2_maxPolygonVertices];
    int32 m = 0;
    int32 ih = i0;

    for (;;)
    {
        hull[m] = ih;

        int32 ie = 0;
        for (int32 j = 1; j < n; ++j)
        {
            if (ie == ih)
            {
                ie = j;
                continue;
            }

            b2Vec2 r = ps[ie] - ps[hull[m]];
            b2Vec2 v = ps[j] - ps[hull[m]];
            float32 c = b2Cross(r, v);
            if (c < 0.0f)
            {
                ie = j;
            }

            // Collinearity check
            if (c == 0.0f && v.LengthSquared() > r.LengthSquared())
            {
                ie = j;
            }
        }

        ++m;
        ih = ie;

        if (ie == i0)
        {
            break;
        }
    }

    m_count = m;

    // Copy vertices.
    for (int32 i = 0; i < m; ++i)
    {
        m_vertices[i] = ps[hull[i]];
    }

    // Compute normals. Ensure the edges have non-zero length.
    for (int32 i = 0; i < m; ++i)
    {
        int32 i1 = i;
        int32 i2 = i + 1 < m ? i + 1 : 0;
        b2Vec2 edge = m_vertices[i2] - m_vertices[i1];
        b2Assert(edge.LengthSquared() > b2_epsilon * b2_epsilon);
        m_normals[i] = b2Cross(edge, 1.0f);
        m_normals[i].Normalize();
    }

    // Compute the polygon centroid.
    m_centroid = ComputeCentroid(m_vertices, m);
}