Polygon.hpp

/*--------------------------------------------------------------------------------------------
Copyright (c) 2019, NDEVR LLC
tyler.parke@ndevr.org
  __    __   ____     _____ __     __  _______
 |  \  |  | |  __ \  |  ___|\ \   / / |   __  \
 |   \ |  | | |  \ \ | |___  \ \ / /  |  |__)  |
 |  . \|  | | |__/ / | |___   \ V /   |   _   /
 |  |\    |_|_____/__|_____|___\_/____|  | \  \
 |__| \__________________________________|  \__\
 
Subject to the terms of the Enterprise+ Agreement, NDEVR hereby grants 
Licensee a limited, non-exclusive, non-transferable, royalty-free license 
(without the right to sublicense) to use the API solely for the purpose of 
Licensee's internal development efforts to develop applications for which 
the API was provided.
 
The above copyright notice and this permission notice shall be included in all 
copies or substantial portions of the Software.
 
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE
FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
DEALINGS IN THE SOFTWARE.
 
Library: Base
File: Polygon
Included in API: True
Author(s): Tyler Parke
 *-----------------------------------------------------------------------------------------**/
#pragma once
#include <NDEVR/BaseValues.h>
#include <NDEVR/MatrixFunctions.h>
#include <NDEVR/Buffer.h>
#include <NDEVR/Vertex.h>
#include <NDEVR/Bounds.h>
#include <NDEVR/LineSegment.h>
#include <NDEVR/Plane.h>
namespace NDEVR
{
    template<class t_type, class t_vertex = Vertex<2, t_type>>
    class Polygon
    {
    public:
        Polygon()
            : m_vertices()
            , m_cache_bounds(Constant<Bounds<2, t_type, t_vertex>>::Invalid)
            , m_cache_length(Constant<t_type>::Invalid)
            , m_is_inside_cached(false)
            , m_is_convex_cached(false)
            , m_is_convex(false)
            , m_polygon_plane(Vector<3, t_type>(0, 0, 1), 0)
        {}
        Polygon(const Polygon& polygon)
            : m_vertices(polygon.m_vertices)
            , m_cache_bounds(polygon.m_cache_bounds)
            , m_cache_length(polygon.m_cache_length)
            , m_cache_constant(polygon.m_cache_constant)
            , m_cache_multiple(polygon.m_cache_multiple)
            , m_is_inside_cached(polygon.m_is_inside_cached)
            , m_is_convex_cached(polygon.m_is_convex_cached)
            , m_is_convex(polygon.m_is_convex)
            , m_polygon_plane(polygon.m_polygon_plane)
        {}
        Polygon(Polygon&& polygon) noexcept
            : m_cache_bounds(polygon.m_cache_bounds)
            , m_cache_length(polygon.m_cache_length)
            , m_is_inside_cached(polygon.m_is_inside_cached)
            , m_is_convex_cached(polygon.m_is_convex_cached)
            , m_is_convex(polygon.m_is_convex)
            , m_polygon_plane(polygon.m_polygon_plane)
        {
            std::swap(m_vertices, polygon.m_vertices);
            std::swap(m_cache_multiple, polygon.m_cache_multiple);
            std::swap(m_cache_constant, polygon.m_cache_constant);
        }
        explicit Polygon(Buffer<t_vertex>& vertices)
            : m_vertices(vertices)
            , m_cache_bounds(Constant<Bounds<2, t_type, t_vertex>>::Invalid)
            , m_cache_length(Constant<t_type>::Invalid)
            , m_is_inside_cached(false)
            , m_is_convex_cached(false)
            , m_is_convex(false)
            , m_polygon_plane(Vector<3, t_type>(0, 0, 1), 0)
        {}
        explicit Polygon(const Buffer<Vertex<3, fltp08>>& points)
            : m_cache_bounds(Constant<Bounds<2, t_type, t_vertex>>::Invalid)
            , m_cache_length(Constant<t_type>::Invalid)
            , m_is_inside_cached(false)
            , m_is_convex_cached(false)
            , m_is_convex(false)
            , m_polygon_plane(Plane<3, fltp08>::CreateBestFitPlane(points))
        {
            Matrix<fltp08> plane_transform = m_polygon_plane.projectionMatrix();
            for (uint04 n = 0; n < points.size(); n++)
            {
                add(t_vertex(plane_transform * points[n]).template as<2, t_type>());
            }
        }
        explicit Polygon(uint04 allocated_size)
            : m_vertices(allocated_size)
            , m_cache_bounds(Constant<Bounds<2, t_type, t_vertex>>::Invalid)
            , m_cache_length(Constant<t_type>::Invalid)
            , m_is_inside_cached(false)
            , m_is_convex_cached(false)
            , m_is_convex(false)
            , m_polygon_plane(Vector<3, t_type>(0, 0, 1), 0)
        {}

        Bounds<2, t_type, t_vertex> bounds() const
        {
            if (IsInvalid(m_cache_bounds))
            {
                m_cache_bounds = Constant<Bounds<2, t_type, t_vertex>>::Min;
                for (uint04 i = 0; i < m_vertices.size(); i++)
                {
                    m_cache_bounds.addToBounds(m_vertices[i]);
                }
            }
            return m_cache_bounds;
        }
 

 
        const t_vertex& vertex(uint04 index) const
        {
            return m_vertices[index];
        }

 
        LineSegment<2, t_type, t_vertex> edge(uint04 index) const
        {
            return LineSegment<2, t_type, t_vertex>(vertex(index), vertex((index + 1) % m_vertices.size()));
        }

 
        inline const Buffer<t_vertex>& vertices() const
        {
            return m_vertices;
        }

 
        inline uint04 vertexCount() const
        {
            return m_vertices.size();
        }

 
        inline uint04 edgeCount() const
        {
            return m_vertices.size();
        }
        bool isConvex() const
        {
            if (!m_is_convex_cached)
            {
                if (edgeCount() < 3)
                {
                    m_is_convex = false;
                }
                else if (edgeCount() == 3)
                {
                    m_is_convex = true;
                }
                else
                {
                    m_is_convex = true;
                    t_type last_cross_prod = 0;
                    const uint04 vert_count = vertexCount();
                    for (uint04 i = 0; i < vert_count; i++)
                    {
                        const Vector<2, t_type> d1 = vertex((i + 1) % vert_count) - vertex((i + 0) % vert_count);
                        const Vector<2, t_type> d2 = vertex((i + 2) % vert_count) - vertex((i + 1) % vert_count);
                        const t_type cross_prod = d1[X] * d2[Y] - d1[Y] * d2[X];
                        if (cross_prod != cast<t_type>(0))
                        {
                            if ((last_cross_prod > cast<t_type>(0) && cross_prod < cast<t_type>(0))
                                || (last_cross_prod < cast<t_type>(0) && cross_prod > cast<t_type>(0)))
                            {
                                m_is_convex = false;
                                break;
                            }
                            last_cross_prod = cross_prod;
                        }
                    }
                }
                m_is_convex_cached = true;
            }
            return m_is_convex;
        }
 
        inline void setVertices(const Buffer<t_vertex>& vertices)
        {
            updateVertices(vertices);
        }
        inline void addVertices(const t_vertex* vertices, uint04 size)
        {
            m_vertices.addAll(vertices, size);
            invalidateCache();
        }

 
        void add(const t_vertex& vertex)
        {
            m_vertices.add(vertex);
            invalidateCache();
        }
        void insert(uint04 index, const t_vertex& vertex)
        {
            m_vertices.insert(index, vertex);
            invalidateCache();
        }
 
        void replace(uint04 index, const t_vertex& vector)
        {
            if (m_vertices[index] != vector)
            {
                m_vertices[index] = vector;
                invalidateCache();
            }
        }
        void simplify()
        {
            if (vertexCount() <= 1)
                return;
            for (uint04 i = 0; i < vertexCount() - 1; i++)
            {
                if (vertex(i).template as<2, t_type>() == vertex(i + 1).template as<2, t_type>())
                {
                    remove(i + 1);
                    i--;
                }
                else if (i > 0 && edge(i).template isParallel<t_type>(edge(i - 1), cast<t_type>(0.00001)))
                {
                    remove(i);
                    i--;
                }
            }
            while (vertexCount() > 0 && vertex(vertexCount() - 1).template as<2, t_type>() == vertex(0).template as<2, t_type>())
            {
                remove(vertexCount() - 1);
            }
            while (vertexCount() > 2 && edge(edgeCount() - 1).template isParallel<t_type>(edge(0), cast<t_type>(0.00001)))
            {
                remove(0);
            }
        }
        void flip()
        {
            uint04 iMax = vertexCount() / 2;
 
            if (vertexCount() % 2 != 0)
                iMax += 1;
 
            for (uint04 i = 1; i < iMax; ++i)
                std::swap(m_vertices[i], m_vertices[vertexCount() - i]);
            invalidateCache();
        }
        void remove(uint04 index)
        {
            m_vertices.removeIndex(index);
            invalidateCache();
        }
        void clear()
        {
            m_vertices.clear();
            invalidateCache();
        }
        template<class t_new_type, class t_new_vertex_type = Vertex<2, t_new_type>>
        Polygon<t_new_type, t_new_vertex_type> as() const
        {
            Polygon<t_new_type, t_new_vertex_type> poly;
            for(uint04 i = 0; i < vertexCount(); i++)
            {
                poly.add(t_new_vertex_type(vertex(i).template as<2, t_new_type>()));
            }
            return poly;
        }
        t_type perimeter() const
        {
            if(IsInvalid(m_cache_length))
            {
                if(vertexCount() > 0)
                {
                    m_cache_length = cast<t_type>(0);
                }
                if (vertexCount() > 1)
                {
                    for (uint04 i = 0; i < edgeCount(); i++)
                    {
                        m_cache_length += edge(i).template length<t_type>();
                    }
                }
            }
            return m_cache_length;
        }
        bool contains(const Vertex<2, t_type>& vector) const
        {
            if (!bounds().template as<2, t_type>().contains(vector))
                return false;
            cacheBoundaryCheck();
            uint04 last = vertexCount() - 1;
            bool odd_vertices = false;
            for (uint04 current = 0; current < vertexCount(); ++current)
            {
                if ((m_vertices[current][Y] < vector[Y] && m_vertices[last][Y] >= vector[Y])
                    || (m_vertices[last][Y] < vector[Y] && m_vertices[current][Y] >= vector[Y]))
                {
                    odd_vertices ^= ((vector[Y] * m_cache_multiple[current] + m_cache_constant[current]) < vector[X]);
                }
                last = current;
            }
            return odd_vertices;
        }
 
        template<class t_precision>
        IntersectionTypes contains(const LineSegment<2, t_type, t_vertex>& line) const
        {
            if (m_vertices.size() <= 2)
                return IntersectionTypes::e_outside;
            if (!bounds().intersects(line))
                return IntersectionTypes::e_outside;
            bool is_inside = contains(line.vertex(A));
            if (contains(line.vertex(B)) != is_inside)
                return IntersectionTypes::e_mixed;
 
            for (uint04 i = 0; i < edgeCount(); i++)
            {
                LineSegment<2, t_type, t_vertex> current_edge = edge(i);
                if (current_edge.template intersects<t_precision>(line))
                    return IntersectionTypes::e_mixed;
            }
            return is_inside ? IntersectionTypes::e_inside : IntersectionTypes::e_outside;
        }
        template<class t_precision>
        IntersectionTypes contains(const Bounds<2, t_type, t_vertex>& o_bounds) const
        {
            if(vertexCount() <= 2)
                return IntersectionTypes::e_outside;
            if (!bounds().intersects(o_bounds))
                return IntersectionTypes::e_outside;
            const t_vertex v1(o_bounds[MIN][X], o_bounds[MIN][Y]);
            const t_vertex v2(o_bounds[MAX][X], o_bounds[MIN][Y]);
            const t_vertex v3(o_bounds[MAX][X], o_bounds[MAX][Y]);
            const t_vertex v4(o_bounds[MIN][X], o_bounds[MAX][Y]);
 
            const bool is_inside = contains(v1);
            if(contains(v2) != is_inside) return IntersectionTypes::e_mixed;
            if(contains(v3) != is_inside) return IntersectionTypes::e_mixed;
            if(contains(v4) != is_inside) return IntersectionTypes::e_mixed;
            // If all of the bounding points are outside, we need only prove that a single polygon vertex is
            // inside (Which is cheap)
            if(!is_inside) for (uint04 i = 0; i < edgeCount(); i++)
            {
                if (o_bounds.contains(vertex(i)))
                    return IntersectionTypes::e_mixed;
            }
            for(uint04 i = 0; i < edgeCount(); i++)
            {
                const LineSegment<2, t_type, t_vertex> current_edge = edge(i);
                if(current_edge.template intersects<t_precision>(LineSegment<2, t_type>(v1, v2))) return IntersectionTypes::e_mixed;
                if(current_edge.template intersects<t_precision>(LineSegment<2, t_type>(v2, v3))) return IntersectionTypes::e_mixed;
                if(current_edge.template intersects<t_precision>(LineSegment<2, t_type>(v3, v4))) return IntersectionTypes::e_mixed;
                if(current_edge.template intersects<t_precision>(LineSegment<2, t_type>(v4, v1))) return IntersectionTypes::e_mixed;
            }
            return is_inside ? IntersectionTypes::e_inside : IntersectionTypes::e_outside;
        }
        
        decltype(auto) begin()
        {
            return m_vertices.begin();
        }
        decltype(auto) begin() const
        {
            return m_vertices.begin();
        }
 
        decltype(auto) begin(uint04 index) const
        {
            return m_vertices.begin(index);
        }
        decltype(auto) begin(uint04 index)
        {
            return m_vertices.begin(index);
        }
 
        decltype(auto) end()
        {
            return m_vertices.end();
        }
        decltype(auto) end() const
        {
            return m_vertices.end();
        }
        template<class t_precision>
        IntersectionTypes contains(const Triangle<2, t_type, t_vertex>& tri) const
        {
            //Check each vertex, if some are inside, or some are outside, we know we are mixed
            if(m_vertices.size() <= 2)
                return IntersectionTypes::e_outside;
            //if (!bounds().intersects(tri))
                //return outside;
            bool is_inside = contains(tri.vertex(A));
            if(contains(tri.vertex(B)) != is_inside) return IntersectionTypes::e_mixed;
            if(contains(tri.vertex(C)) != is_inside) return IntersectionTypes::e_mixed;
 
            // If all of the triangles points are outside, we need only prove that a single polygon vertex is
            // inside (Which is cheap)
            if (!is_inside) for (uint04 i = 0; i < edgeCount(); i++)
            {
                if (tri.contains(vertex(i)))
                    return IntersectionTypes::e_mixed;
            }
            for (uint04 i = 0; i < edgeCount(); i++)
            {
                const LineSegment<2, t_type, t_vertex> current_edge = edge(i);
                if(current_edge.template intersects<t_precision>(tri.edge(A, B))) return IntersectionTypes::e_mixed;
                if(current_edge.template intersects<t_precision>(tri.edge(B, C))) return IntersectionTypes::e_mixed;
                if(current_edge.template intersects<t_precision>(tri.edge(C, A))) return IntersectionTypes::e_mixed;
            }
            return is_inside ? IntersectionTypes::e_inside : IntersectionTypes::e_outside;
        }
 
        template<class t_precision, class t_other_vertex>
        IntersectionTypes contains(const Polygon<t_type, t_other_vertex>& poly) const
        {
            if (m_vertices.size() <= 2 || poly.edgeCount() == 0)
                return IntersectionTypes::e_outside;
            if (!bounds().intersects(poly.bounds()))
                return IntersectionTypes::e_outside;
 
            IntersectionTypes type = contains<t_precision>(poly.edge(0));
            if (type == IntersectionTypes::e_mixed || (type == IntersectionTypes::e_outside && poly.contains(vertex(0))))
                return IntersectionTypes::e_mixed;
            for (uint04 i = 1; i < poly.edgeCount(); i++)
            {
                if (type != contains<t_precision>(poly.edge(i)))
                    return IntersectionTypes::e_mixed;
            }
            
            return type;
        }
 
        Polygon clip(const Bounds<t_vertex::NumberOfDimensions(), t_type>& bounds) const
        {
            if (bounds.template as<2, t_type>().template contains<true>(this->bounds().template as<2, t_type>()))
                return *this;
            if (!bounds.template as<2, t_type>().intersects(this->bounds()))
                return Polygon();
            Polygon polygon(vertexCount());
            for (uint04 ii = 0; ii < vertexCount() - 1; ++ii)
            {
                LineSegment<t_vertex::NumberOfDimensions(), t_type> line(vertex(ii), vertex(ii + 1));
                line = intersection(bounds, line);
                if (IsValid(line))
                {
                    if (polygon.vertexCount() == 0 || polygon.vertex(polygon.vertexCount() - 1) != polygon.vertex(A))
                        polygon.add(line.vertex(A));
                    polygon.add(line.vertex(B));
                }
            }
            LineSegment<t_vertex::NumberOfDimensions(), t_type> line(vertex(vertexCount() - 1), vertex(0));
            if (IsValid(line))
            {
                line = intersection(bounds, line);
                if (IsValid(line))
                {
                    if (polygon.vertexCount() == 0 || polygon.vertex(polygon.vertexCount() - 1) != polygon.vertex(A))
                        polygon.add(line.vertex(A));
                    polygon.add(line.vertex(B));
                }
            }
            
            polygon.simplify();
            return polygon;
        }
 
        Plane<3, t_type> plane() const
        {
            return m_polygon_plane;
        }
        void setPlane(const Plane<3, t_type>& plane)
        {
            m_polygon_plane = plane;
        }
        bool hasClockwiseWinding() const
        {
            t_type sum = 0;
            for (uint04 i = 0; i < edgeCount(); i++)
            {
                auto side = edge(i);
                sum += (side[B][X] - side[A][X]) * (side[B][Y] + side[A][Y]);
            }
            return sum > 0.0;//this is also half surface area
        }
        bool operator==(const Polygon& polygon) const
        {
            return m_vertices == polygon.m_vertices && m_polygon_plane == polygon.m_polygon_plane;
        }
        bool operator!=(const Polygon& polygon) const
        {
            return m_vertices != polygon.m_vertices || m_polygon_plane != polygon.m_polygon_plane;
        }
        bool isEquivalent(const Polygon& polygon, fltp08 epsilon)
        {
            if (bounds().template as<2, fltp08>() != polygon.bounds().template as<2, fltp08>())
                return false;
            if (abs(perimeter() - polygon.perimeter()) > epsilon)
                return false;
            for (uint04 i = 0; i < polygon.edgeCount(); i++)
            {
                bool found = false;
                for (uint04 n = 0; n < edgeCount(); n++)
                {
                    if (edge(n).template as<2, fltp08>().template isCollinear<fltp08>(polygon.edge(i).template as<2, fltp08>(), epsilon))
                    {
                        found = true;
                        break;
                    }
                }
                if (!found)
                    return false;
            }
            return true;
        }
        Polygon opheimSimplification(t_type min_tol, t_type max_tol) const
        {
 
            uint04 count = vertexCount();
            t_type min_tol2 = min_tol * min_tol;    // squared minimum distance tolerance
            t_type max_tol2 = max_tol * max_tol;    // squared maximum distance tolerance
 
            // validate input and check if simplification required
            if (count < 3 || min_tol2 == 0 || max_tol2 == 0)
                return *this;
            // define the ray R(r0, r1)
            uint04 r0 = 0;  // indicates the current key and start of the ray
            uint04 r1 = 0;  // indicates a point on the ray
            bool rayDefined = false;
 
            // keep track of two test points
            uint04 pi = r0;     // the previous test point
            uint04 pj = pi;    
 
            Polygon poly;
            poly.add(vertex(r0));
            for (uint04 j = 1; j < count; ++j)
            {
                pi = pj++;
 
                t_type dist_squared = distanceSquared(vertex(r0), vertex(pj));
                if (!rayDefined) {
                    // discard each point within minimum tolerance
                    if (dist_squared < min_tol2)
                        continue;
                    // the last point within minimum tolerance pi defines the ray R(r0, r1)
                    r1 = pi;
                    rayDefined = true;
                }
 
                // check each point pj against R(r0, r1)
                if (dist_squared < max_tol2)
                {
                    t_vertex v = vertex(r1) - vertex(r0);        // vector r1 --> r2
                    t_vertex w = vertex(pj) - vertex(r0);        // vector r1 --> p
 
                    t_type cv = dot(v, v);    // squared length of v
                    t_type cw = dot(w, v);    // project w onto v
 
                    if (cw <= 0) 
                    {
                        // projection of w lies to the left of r1 (not on the ray)
                        if (distanceSquared(vertex(pj), vertex(r0)) < min_tol2)
                            continue;
                    }
                    else
                    {
                        // avoid problems with divisions when value_type is an integer type
                        t_type fraction = cv == 0 ? 0 : cw /cv;
 
 
                        t_vertex proj = vertex(r0) + (fraction * (vertex(r1) - vertex(r0)));
 
                        if (distanceSquared(vertex(pj), proj) < min_tol2)
                            continue;
                    }
                }
                poly.add(vertex(pi));
                r0 = pi;
                rayDefined = false;
            }
            return poly;
        }
        Polygon& operator=(const Polygon& poly)
        {
            m_vertices = poly.m_vertices;
            m_cache_bounds = poly.m_cache_bounds;
            m_cache_length = poly.m_cache_length;
            m_cache_constant = poly.m_cache_constant;
            m_cache_multiple = poly.m_cache_multiple;
            m_is_inside_cached = poly.m_is_inside_cached;
            return *this;
        }
        Polygon& operator=(Polygon&& poly)
        {
            std::swap(m_vertices, poly.m_vertices);
            m_cache_bounds = poly.m_cache_bounds;
            m_cache_length = poly.m_cache_length;
            m_cache_constant = poly.m_cache_constant;
            m_cache_multiple = poly.m_cache_multiple;
            m_is_inside_cached = poly.m_is_inside_cached;
            return *this;
        }
        bool validate() const
        {
            for (uint04 i = 0; i < edgeCount(); i++)
            {
                auto seg_to_check = edge(i);
                for (uint04 n = i + 2; n < edgeCount(); n++)
                {
                    if (n == i || (n == edgeCount() - 1 && i == 0))
                        continue;
                    auto seg = edge(n);
                    if (IsValid(seg_to_check.template intersection<fltp08>(seg, 0.000000001)))
                    {
                        lib_assert(false, "Bad polygon");
                        return false;
                    }
                }
            }
            return true;
        }
    private: 

 
        inline void invalidateCache() const
        {
            m_cache_length = Constant<t_type>::Invalid;
            m_is_inside_cached = false;
            m_is_convex_cached = false;
            m_cache_constant.clear();
            m_cache_multiple.clear();
            m_cache_bounds = Constant<Bounds<2, t_type, t_vertex>>::Invalid;
        }

 
        void updateVertices(const Buffer<t_vertex>& vertices)
        {
            m_vertices = vertices;
            invalidateCache();
        }

 
        void cacheBoundaryCheck() const
        {
            if(m_is_inside_cached)
                return;
            m_cache_constant.setSize(m_vertices.size());
            m_cache_multiple.setSize(m_vertices.size());
            uint04 jj = m_vertices.size() - 1;
            for(uint04 ii = 0; ii < m_vertices.size(); ++ii)
            {
                if(m_vertices[jj][Y] == m_vertices[ii][Y])
                {
                    m_cache_constant[ii] = cast<fltp08>(m_vertices[ii][X]);
                    m_cache_multiple[ii] = 0;
                }
                else 
                {
                      m_cache_constant[ii] = m_vertices[ii][X]
                        - cast<fltp08>(m_vertices[ii][Y] * m_vertices[jj][X])
                        / cast<fltp08>(m_vertices[jj][Y] - m_vertices[ii][Y])
                        + cast<fltp08>(m_vertices[ii][Y] * m_vertices[ii][X])
                        / cast<fltp08>(m_vertices[jj][Y] - m_vertices[ii][Y]);
                    m_cache_multiple[ii] = cast<fltp08>(m_vertices[jj][X] - m_vertices[ii][X])
                        / cast<fltp08>(m_vertices[jj][Y] - m_vertices[ii][Y]);
                }
                jj = ii;
            }
            m_is_inside_cached = true;
        }
        
    private: 
        Buffer<t_vertex> m_vertices;

 
        mutable Bounds<2, t_type, t_vertex> m_cache_bounds;

 
        mutable t_type m_cache_length;

 
        mutable Buffer<fltp08> m_cache_constant;

 
        mutable Buffer<fltp08> m_cache_multiple;

 
        mutable bool m_is_inside_cached;
        mutable bool m_is_convex_cached;
        mutable bool m_is_convex;
        Plane<3, t_type> m_polygon_plane;
    };
 
    template<class t_type, class t_vertex, uint01 t_row_dims, uint01 t_col_dims>
    inline Polygon<t_type, t_vertex> operator*(const Matrix<t_type, t_row_dims, t_col_dims>& matrix, const Polygon<t_type, t_vertex>& poly)
    {
        Polygon<t_type, t_vertex> polygon(poly.vertexCount());
        for (uint04 i = 0; i < poly.vertexCount(); i++)
        {
            polygon.add(matrix * poly.vertex(i));
        }
        return polygon;
    }
 
    template<class t_type, class t_vertex>
    static bool IsInvalid(const Polygon<t_type, t_vertex>& poly)
    {
        Polygon<t_type, t_vertex> polygon(poly.vertexCount());
        for (uint04 i = 0; i < poly.vertexCount(); i++)
        {
            if(IsInvalid(poly.vertex(i)))
                return true;
        }
        return false;
    }
    template<class t_type, class t_vertex>
    static bool IsValid(const Polygon<t_type, t_vertex>& poly)
    {
        Polygon<t_type, t_vertex> polygon(poly.vertexCount());
        for (uint04 i = 0; i < poly.vertexCount(); i++)
        {
            if (IsInvalid(poly.vertex(i)))
                return false;
        }
        return true;
    }
    
}