Polygon.hpp

Go to the documentation of this file.

/*--------------------------------------------------------------------------------------------
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
{
    /**--------------------------------------------------------------------------------------------------
    Class: Polygon
    
    \brief An N-sided polygon.
    
    Author: Tyler Parke
    
    Date: 2017-11-19
    **/
    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)
        {}
 
        /**--------------------------------------------------------------------------------------------------
                Gets the bounds.
 
        Author: Tyler Parke
 
        Date: 2017-11-19
 
        \returns A Bounds&lt;2,t_type&gt;
        **/
        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;
        }
 
 
        /**--------------------------------------------------------------------------------------------------
                Vertices the given index.
 
        Author: Tyler Parke
 
        Date: 2017-11-19
 
        Parameters:
        index -  Zero-based index of the.
 
        \returns A reference to a const t_vertex.
        **/
 
        const t_vertex& vertex(uint04 index) const
        {
            return m_vertices[index];
        }
 
        /**--------------------------------------------------------------------------------------------------
                Edges the given index.
 
        Author: Tyler Parke
 
        Date: 2017-11-19
 
        Parameters:
        index -  Zero-based index of the.
 
        \returns A LineSegment&lt;2,t_type,t_vertex&gt;
        **/
 
        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()));
        }
 
        /**--------------------------------------------------------------------------------------------------
                Gets the vertices.
 
        Author: Tyler Parke
 
        Date: 2017-11-19
 
        \returns A reference to a const Buffer&lt;t_vertex&gt;
        **/
 
        inline const Buffer<t_vertex>& vertices() const
        {
            return m_vertices;
        }
 
        /**--------------------------------------------------------------------------------------------------
                Vertex count.
 
        Author: Tyler Parke
 
        Date: 2017-11-19
 
        \returns An uint04.
        **/
 
        inline uint04 vertexCount() const
        {
            return m_vertices.size();
        }
 
        /**--------------------------------------------------------------------------------------------------
                Edge count.
 
        Author: Tyler Parke
 
        Date: 2017-11-19
 
        \returns An uint04.
        **/
 
        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;
        }
        /**--------------------------------------------------------------------------------------------------
                Sets the vertices.
 
        Author: Tyler Parke
 
        Date: 2017-11-19
 
        Parameters:
        vertices -  The vertices.
        **/
 
        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();
        }
 
        /**--------------------------------------------------------------------------------------------------
                Adds vertex.
 
        Author: Tyler Parke
 
        Date: 2017-11-19
 
        Parameters:
        vertex -  The vertex to add.
        **/
 
        void add(const t_vertex& vertex)
        {
            m_vertices.add(vertex);
            invalidateCache();
        }
 
        /**--------------------------------------------------------------------------------------------------
                Inserts.
 
        Author: Tyler Parke
 
        Date: 2017-11-19
 
        Parameters:
        index -     Zero-based index of the.
        vertex -     The vertex.
        **/
 
        void insert(uint04 index, const t_vertex& vertex)
        {
            m_vertices.insert(index, vertex);
            invalidateCache();
        }
 
        /**--------------------------------------------------------------------------------------------------
                Replaces.
 
        Author: Tyler Parke
 
        Date: 2017-11-19
 
        Parameters:
        index -     Zero-based index of the.
        vector -    The vector.
        **/
 
        void replace(uint04 index, const t_vertex& vector)
        {
            if (m_vertices[index] != vector)
            {
                m_vertices[index] = vector;
                invalidateCache();
            }
        }
 
        /**--------------------------------------------------------------------------------------------------
                Removes all duplicate adjacent vertices.
 
        Author: Tyler Parke
 
        Date: 2017-05-16
 
        Parameters:
        index -  The index to removeRows.
        **/
        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();
        }
        /**--------------------------------------------------------------------------------------------------
                Removes the given index.
        
        Author: Tyler Parke
        
        Date: 2017-11-19
        
        Parameters:
        index -  The index to removeRows.
        **/
 
        void remove(uint04 index)
        {
            m_vertices.removeIndex(index);
            invalidateCache();
        }
 
        /**--------------------------------------------------------------------------------------------------
                Clears this object to its blank/initial state.
        
        Author: Tyler Parke
        
        Date: 2017-11-19
        **/
 
        void clear()
        {
            m_vertices.clear();
            invalidateCache();
        }
 
        /**--------------------------------------------------------------------------------------------------
                Gets as.
        
        Author: Tyler Parke
        
        Date: 2017-11-19
        
        \returns A Polygon&lt;t_new_type,t_new_vertex_type&gt;
        **/
        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;
        }
 
        /**--------------------------------------------------------------------------------------------------
                Gets the perimeter.
        
        Author: Tyler Parke
        
        Date: 2017-11-19
        
        \returns A t_type.
        **/
 
        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;
        }
 
        /**--------------------------------------------------------------------------------------------------
                Query if this object contains the given vector.
        
        Author: Tyler Parke
        
        Date: 2017-11-19
        
        Parameters:
        vector -  The const t_vertex&amp; to test for containment.
        
        \returns True if the object is in this collection, false if not.
        **/
 
        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 outside;
            if (!bounds().intersects(line))
                return outside;
            bool is_inside = contains(line.vertex(A));
            if (contains(line.vertex(B)) != is_inside)
                return 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 mixed;
            }
            return is_inside ? inside : outside;
        }
 
        /**--------------------------------------------------------------------------------------------------
                Determines if this collection contains a given object.
        
        Author: Tyler Parke
        
        Date: 2017-11-19
        
        Parameters:
        bounds -  The const Bounds&lt;2,t_type,t_vertex&gt;&amp; to test for containment.
        
        \returns The IntersectionTypes.
        **/
        template<class t_precision>
        IntersectionTypes contains(const Bounds<2, t_type, t_vertex>& o_bounds) const
        {
            if(vertexCount() <= 2)
                return outside;
            if (!bounds().intersects(o_bounds))
                return 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 mixed;
            if(contains(v3) != is_inside) return mixed;
            if(contains(v4) != is_inside) return 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 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 mixed;
                if(current_edge.template intersects<t_precision>(LineSegment<2, t_type>(v2, v3))) return mixed;
                if(current_edge.template intersects<t_precision>(LineSegment<2, t_type>(v3, v4))) return mixed;
                if(current_edge.template intersects<t_precision>(LineSegment<2, t_type>(v4, v1))) return mixed;
            }
            return is_inside ? inside : 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();
        }
        
 
        /**--------------------------------------------------------------------------------------------------
                Determines if this collection contains a given object.
        
        Author: Tyler Parke
        
        Date: 2017-11-19
        
        Parameters:
        tri -  The const Triangle&lt;2,t_type,t_vertex&gt;&amp; to test for containment.
        
        \returns The IntersectionTypes.
        **/
        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 outside;
            //if (!bounds().intersects(tri))
                //return outside;
            bool is_inside = contains(tri.vertex(A));
            if(contains(tri.vertex(B)) != is_inside) return mixed;
            if(contains(tri.vertex(C)) != is_inside) return 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 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 mixed;
                if(current_edge.template intersects<t_precision>(tri.edge(B, C))) return mixed;
                if(current_edge.template intersects<t_precision>(tri.edge(C, A))) return mixed;
            }
            return is_inside ? inside : 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 outside;
            if (!bounds().intersects(poly.bounds()))
                return outside;
 
            IntersectionTypes type = contains<t_precision>(poly.edge(0));
            if (type == mixed || (type == outside && poly.contains(vertex(0))))
                return mixed;
            for (uint04 i = 1; i < poly.edgeCount(); i++)
            {
                if (type != contains<t_precision>(poly.edge(i)))
                    return 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 (!IsInvalid(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 (!IsInvalid(line))
            {
                line = intersection(bounds, line);
                if (!IsInvalid(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
        }
        /**--------------------------------------------------------------------------------------------------
                Equality operator.
        
        Author: Tyler Parke
        
        Date: 2017-11-19
        
        Parameters:
        polygon -  The polygon.
        
        \returns True if the parameters are considered equivalent.
        **/
 
        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 (!IsInvalid(seg_to_check.template intersection<fltp08>(seg, 0.000000001)))
                    {
                        lib_assert(false, "Bad polygon");
                        return false;
                    }
                }
            }
            return true;
        }
    private: 
 
        /**--------------------------------------------------------------------------------------------------
                Invalidate cache.
        
        Author: Tyler Parke
        
        Date: 2017-11-19
        **/
 
        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;
        }
 
        /**--------------------------------------------------------------------------------------------------
                Updates the vertices described by the given vertices.
        
        Author: Tyler Parke
        
        Date: 2017-11-19
        
        Parameters:
        vertices -  The vertices.
        **/
 
        void updateVertices(const Buffer<t_vertex>& vertices)
        {
            m_vertices = vertices;
            invalidateCache();
        }
 
        /**--------------------------------------------------------------------------------------------------
                Cache boundary check.
        
        Author: Tyler Parke
        
        Date: 2017-11-19
        **/
 
        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: 
        /** The vertices. */
        Buffer<t_vertex> m_vertices;
 
        /**--------------------------------------------------------------------------------------------------
        Property: mutable Bounds<2, t_type> m_cache_bounds
        
        Gets the cache bounds.
        
        \returns The m cache bounds.
        **/
 
        mutable Bounds<2, t_type, t_vertex> m_cache_bounds;
 
        /**--------------------------------------------------------------------------------------------------
        Property: mutable t_type m_cache_length
        
        Gets the length of the cache.
        
        \returns The length of the cache.
        **/
 
        mutable t_type m_cache_length;
 
        /**--------------------------------------------------------------------------------------------------
        Property: mutable Buffer<fltp08> m_cache_constant
        
        Gets the cache constant.
        
        \returns The m cache constant.
        **/
 
        mutable Buffer<fltp08> m_cache_constant;
 
        /**--------------------------------------------------------------------------------------------------
        Property: mutable Buffer<fltp08> m_cache_multiple
        
        Gets the cache multiple.
        
        \returns The m cache multiple.
        **/
 
        mutable Buffer<fltp08> m_cache_multiple;
 
        /**--------------------------------------------------------------------------------------------------
        Property: mutable bool m_is_inside_cached
        
        Gets a value indicating whether this object is inside cached.
        
        \returns True if this object m is inside cached, false if not.
        **/
 
        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;
    }
    
}