PolyLine.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: PolyLine
Included in API: True
Author(s): Tyler Parke
 *-----------------------------------------------------------------------------------------**/
#pragma once
#include <NDEVR/BaseValues.h>
#include <NDEVR/Buffer.h>
#include <NDEVR/Vertex.h>
#include <NDEVR/Bounds.h>
#include <NDEVR/LineSegment.h>
 
/**--------------------------------------------------------------------------------------------------
Namespace: Parke
Namespace that wraps all Logic created by Tyler Parke
 *-----------------------------------------------------------------------------------------------**/
 
namespace NDEVR
{
 
    /**--------------------------------------------------------------------------------------------------
    Class: Polyline
    
    \brief A polyline which stores vertex information for many points along a given path
    
    Author: Tyler Parke
    
    Date: 2017-11-19
     *-----------------------------------------------------------------------------------------------**/
    template<uint01 t_dims, class t_type, class t_vertex = Vertex<t_dims, t_type>>
    class Polyline
    {
    public:
        Polyline(uint04 size = 0)
            : m_vertices(size)
            , m_cache_bounds(Constant<Bounds<t_dims, t_type>>::NaN)
            , m_cache_length(Constant<t_type>::NaN)
        /** . */
        {}
        explicit Polyline(Buffer<t_vertex>& vertices)
            : m_vertices(vertices)
            , m_cache_bounds(Constant<Bounds<t_dims, t_type>>::NaN)
            , m_cache_length(Constant<t_type>::NaN)
        /** . */
        {}
        Polyline(const Polyline& polygon) noexcept
            : m_vertices(polygon.m_vertices)
            , m_cache_bounds(polygon.m_cache_bounds)
            , m_cache_length(polygon.m_cache_length)
        /** . */
        {}
        Polyline(Polyline&& polygon) noexcept
            : m_vertices()
            , m_cache_bounds()
            , m_cache_length()
        {
            std::swap(m_vertices, polygon.m_vertices);
            std::swap(m_cache_bounds, polygon.m_cache_bounds);
            std::swap(m_cache_length, polygon.m_cache_length);
        }
 
        /**--------------------------------------------------------------------------------------------------
        Fn: Bounds<t_dims, t_type, t_vertex> Polyline::bounds() const
        
        Gets the bounds.
        
        Author: Tyler Parke
        
        Date: 2017-11-19
        
        Returns: A Bounds&lt;t_dims,t_type,t_vertex&gt;
         *-----------------------------------------------------------------------------------------------**/
 
        Bounds<t_dims, t_type, t_vertex> bounds() const
        {
            if (isNaN(m_cache_bounds))
            {
                m_cache_bounds = Constant<Bounds<t_dims, 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;
        }
 
        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();
        }
 
        /**--------------------------------------------------------------------------------------------------
        Fn: const t_vertex& Polyline::vertex(uint04 index) const
        
        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];
        }
 
        /**--------------------------------------------------------------------------------------------------
        Fn: LineSegment<t_dims, t_type, t_vertex> Polyline::segment(uint04 index) const
        
        Segments the given index.
        
        Author: Tyler Parke
        
        Date: 2017-11-19
        
        Parameters:
        index -  Zero-based index of the.
        
        Returns: A LineSegment&lt;t_dims,t_type,t_vertex&gt;
         *-----------------------------------------------------------------------------------------------**/
 
        LineSegment<t_dims, t_type, t_vertex> segment(uint04 index) const
        {
            return LineSegment<t_dims, t_type, t_vertex>(vertex(index), vertex(index + 1));
        }
 
        /**--------------------------------------------------------------------------------------------------
        Fn: inline const Buffer<t_vertex>& Polyline::vertices() const
        
        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;
        }
 
        /**--------------------------------------------------------------------------------------------------
        Fn: inline uint04 Polyline::visibleVertexCount() const
        
        Vertex count.
        
        Author: Tyler Parke
        
        Date: 2017-11-19
        
        Returns: An uint04.
         *-----------------------------------------------------------------------------------------------**/
 
        inline uint04 vertexCount() const
        {
            return m_vertices.size();
        }
 
        /**--------------------------------------------------------------------------------------------------
        Fn: inline uint04 Polyline::segmentCount() const
        
        Segment count.
        
        Author: Tyler Parke
        
        Date: 2018-10-29
        
        Returns: An uint04.
         *-----------------------------------------------------------------------------------------------**/
 
        inline uint04 segmentCount() const
        {
            if (m_vertices.size() == 0)
                return 0;
            else
                return m_vertices.size() - 1;
        }
 
        /**--------------------------------------------------------------------------------------------------
        Fn: inline void Polyline::setVertices(const Buffer<t_vertex>& vertices)
        
        Sets the vertices.
        
        Author: Tyler Parke
        
        Date: 2017-11-19
        
        Parameters:
        vertices -  The vertices.
         *-----------------------------------------------------------------------------------------------**/
 
        inline void setVertices(const Buffer<t_vertex>& vertices)
        {
            updateVertices(vertices);
        }
 
        /**--------------------------------------------------------------------------------------------------
        Fn: void Polyline::add(const t_vertex& vertex)
        
        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();
        }
        void addAndSimplify(const t_vertex& vertex)
        {
            addAndSimplify(vertexCount(), vertex);
        }
 
        /**--------------------------------------------------------------------------------------------------
        Fn: void Polyline::add(uint04 index, const t_vertex& vertex)
        
        Adds index.
        
        Author: Tyler Parke
        
        Date: 2017-11-19
        
        Parameters:
        index -     Zero-based index of the.
        vertex -     The vertex.
         *-----------------------------------------------------------------------------------------------**/
 
        void add(uint04 index, const t_vertex& vertex)
        {
            m_vertices.add(index, vertex);
            invalidateCache();
        }
        void addAndSimplify(uint04 index, const t_vertex& vertex)
        {
            if (isNaN(vertex))
            {
                if (index < vertexCount() && isNaN(this->vertex(index)))
                    return;//nothing to do
                if (index > 1 && isNaN(this->vertex(index - 1)))
                    return;//nothing to do
                m_vertices.add(index, vertex);
                invalidateCache();
            }
            else
            {
                m_vertices.add(index, vertex);
                if (index < vertexCount() - 1)
                {
                    if (segment(index).template isParallel<t_type>(segment(index - 1), 0.00001))
                    {
                        remove(index);
                    }
                }
                if (index > 2)
                {
                    if (segment(index - 1).template isParallel<t_type>(segment(index - 2), 0.00001))
                    {
                        remove(index - 1);
                    }
                }
            }
            invalidateCache();
        }
 
        /**--------------------------------------------------------------------------------------------------
        Fn: void Polyline::replace(uint04 index, const t_vertex& vector)
        
        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& vertex)
        {
            if (m_vertices[index] != vertex)
            {
                m_vertices[index] = vertex;
                invalidateCache();
            }
        }
 
        /**--------------------------------------------------------------------------------------------------
        Fn: void Polyline::removeRows(uint04 index)
        
        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();
        }
 
        /**--------------------------------------------------------------------------------------------------
        Fn: void Polyline::lastVertex()
 
        The last vertex in the polyline
 
        Author: Tyler Parke
 
        Date: 2019-01-12
 
        Returns: The last vertex in the polyline
        *-----------------------------------------------------------------------------------------------**/
        const t_vertex& lastVertex() const
        {
            return m_vertices.last();
        }
        /**--------------------------------------------------------------------------------------------------
        Fn: void Polyline::removeLastVertex()
 
        Removes the last vertex from the polyline.
 
        Author: Tyler Parke
 
        Date: 2019-01-12
 
        *-----------------------------------------------------------------------------------------------**/
        void removeLastVertex()
        {
            m_vertices.removeLast();
        }
        /**--------------------------------------------------------------------------------------------------
        Fn: void Polyline::simplify()
 
        Removes all duplicate adjacent vertices.
 
        Author: Tyler Parke
 
        Date: 2019-01-12
        *-----------------------------------------------------------------------------------------------**/
        void simplify()
        {
            if (vertexCount() <= 1)
                return;
            for (uint04 i = 0; i < vertexCount() - 1; i++)
            {
                if (vertex(i) == vertex(i + 1))
                {
                    remove(i + 1);
                    i--;
                }
                else if (i > 0 && segment(i).template isParallel<t_type>(segment(i - 1), 0.00001))
                {
                    remove(i);
                    i--;
                }
            }
        }
        /**--------------------------------------------------------------------------------------------------
        Fn: void Polyline::clear()
        
        Clears this object to its blank/initial state.
        
        Author: Tyler Parke
        
        Date: 2017-11-19
         *-----------------------------------------------------------------------------------------------**/
 
        void clear()
        {
            m_vertices.clear();
            invalidateCache();
        }
 
        /**--------------------------------------------------------------------------------------------------
        Fn: Polyline<t_new_type, t_new_vertex_type> Polyline::as() const
        
        Gets as.
        
        Author: Tyler Parke
        
        Date: 2017-11-19
        
        Returns: A Polyline&lt;t_new_type,t_new_vertex_type&gt;
         *-----------------------------------------------------------------------------------------------**/
        template<uint01 t_new_dims, class t_new_type, class t_new_vertex_type = Vertex<t_new_dims, t_new_type>>
        Polyline<t_dims, t_new_type, t_new_vertex_type> as() const
        {
            Polyline<t_dims, 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<t_dims, t_new_type, t_new_vertex_type>()));
            }
            return poly;
        }
 
        /**--------------------------------------------------------------------------------------------------
        Fn: t_type Polyline::length() const
        
        Gets the length.
        
        Author: Tyler Parke
        
        Date: 2017-11-19
        
        Returns: A t_type.
         *-----------------------------------------------------------------------------------------------**/
        template<class t_precision>
        t_precision length() const
        {
            if (isNaN(m_cache_length))
            {
                if (vertexCount() <= 1)
                {
                    m_cache_length = cast<t_precision>(0);
                }
                else
                {
                    m_cache_length = cast<t_precision>(0);
                    for (uint04 i = 0; i < segmentCount(); i++)
                    {
                        if(!isNaN(segment(i)))
                            m_cache_length += segment(i).template length<t_precision>();
                    }
                }
            }
            return m_cache_length;
        }
        
 
        /**--------------------------------------------------------------------------------------------------
        Fn: constexpr inline t_vertex Polyline::pointAt(t_inter_type value) const
        
        Point at.
        
        Author: Tyler Parke
        
        Date: 2017-11-19
        
        Parameters:
        value -  The value.
        
        Returns: A t_vertex.
         *-----------------------------------------------------------------------------------------------**/
        template<class t_inter_type>
        constexpr inline t_vertex pointAt(t_inter_type value) const
        {
            uint04 index = cast<uint04>(value);
            return segment(index).pointAt(value - cast<t_inter_type>(index));
        }
 
        constexpr inline t_vertex pointAtLength(fltp08 value) const
        {
            if (vertexCount() == 0)
                return Constant<t_vertex>::NaN;
            fltp08 accumulated_distance = 0;
            for (uint04 i = 1; i < vertexCount(); i++)
            {
                fltp08 local_distance = distance<fltp08>(vertex(i - 1), vertex(i));
                if (accumulated_distance + local_distance > value)
                {
                    fltp08 line_percent = clip((value - accumulated_distance) / local_distance, 0.0, 1.0);
                    return (vertex(i - 1).template as<t_dims, fltp08>() * (1.0 - line_percent)
                            + vertex(i).template as<t_dims, fltp08>() * line_percent).template as<t_dims, t_type>();
 
                }
                accumulated_distance += local_distance;
            }
            return lastVertex();
        }
 
        /**--------------------------------------------------------------------------------------------------
        Fn: bool Polyline::operator==(const Polyline& polygon) const
        
        Equality operator.
        
        Author: Tyler Parke
        
        Date: 2017-11-19
        
        Parameters:
        polygon -  The polygon.
        
        Returns: True if the parameters are considered equivalent.
         *-----------------------------------------------------------------------------------------------**/
 
        bool operator==(const Polyline& polygon) const
        {
            return (m_vertices == polygon.m_vertices);
        }
        Polyline& operator=(const Polyline& polygon)
        {
            m_vertices = polygon.m_vertices;
            m_cache_length = polygon.m_cache_length;
            m_cache_bounds = polygon.m_cache_bounds;
            return *this;
        }
        Polyline& operator=(Polyline&& polygon) noexcept
        {
            std::swap(m_vertices, polygon.m_vertices);
            m_cache_length = polygon.m_cache_length;
            m_cache_bounds = polygon.m_cache_bounds;
            return *this;
        }
        Polyline<t_dims, t_type> breakIntoSegmentsByLength(t_type length) const
        {
            Polyline<t_dims, t_type> new_poly;
            if (vertexCount() == 0)
                return new_poly;
 
            t_type remainder_distance(0);
            new_poly.add(vertex(0));//add initial vertex
            for (uint04 i = 0; i < segmentCount(); i++)
            {
                const t_type seg_length = segment(i).template length<t_type>();
                if (seg_length + remainder_distance > length)
                {
                    t_type local_accumulation = length - remainder_distance;
                    lib_assert(local_accumulation > 0.0, "Bad accumulation");
                    auto ray = segment(i).ray().template normalized<fltp08>();
                    do
                    {
                        new_poly.add(segment(i).vertex(A) + ray * local_accumulation);
                        local_accumulation += length;
                    } while (local_accumulation < seg_length);
                    remainder_distance = length + seg_length - local_accumulation;
                }
                else if (!isNaN(seg_length))
                {
                    remainder_distance += seg_length;
                }
            }
            return new_poly;
        }
        Polyline<t_dims, t_type> breakIntoSegmentsByDistance(t_type d) const
        {
            t_type dist_squared = d * d;
            Polyline<t_dims, t_type> new_poly;
            if (vertexCount() == 0)
                return new_poly;
            new_poly.add(vertex(0));
            for (uint04 i = 1; i < vertexCount(); i++)
            {
                if (distanceSquared(new_poly.lastVertex(), vertex(i)) > dist_squared)
                {
                    
                    LineSegment<t_dims, t_type> seg(vertex(i - 1), vertex(i));
                    const Vector<t_dims, t_type> ab = seg.ray();
                    const Vector<t_dims, t_type> ap = new_poly.lastVertex() - seg[A];
                    Vector<t_dims, t_type> normal = ab.template normalized<t_type>();
                    if(ap != 0.0 && !equals(ab, ap, 0.000001) && !equals(ab, -ap, 0.000001))//check if collinear
                    {
                        //project P onto AB
                        //use triangle to solve for point on line d distance away from last vertex
                        t_type sum = (ab * ap).sum();
                        const t_type mag_squared = ab.magnitudeSquared();
                        sum /= mag_squared;
                        const Vector<t_dims, t_type> p0 = seg[A] + (ab * sum);
                        t_type new_distance = sqrt(dist_squared - distanceSquared(p0, new_poly.lastVertex()));
                        new_poly.add(new_distance * normal + p0);
                    }
                    //simplified when back on line
                    while (distanceSquared(new_poly.lastVertex(), vertex(i)) > dist_squared)
                    {
                        new_poly.add(d * normal + new_poly.lastVertex());
                    }
                }
            }
            return new_poly;
        }
 
        Buffer<Polyline<t_dims, t_type>, uint04, ObjectAllocator<false>> breakIntoPolylinesByLength(t_type max_distance) const
        {
            Buffer<Polyline<t_dims, t_type>> new_polys;
            if (vertexCount() == 0)
                return new_polys;
            Polyline<t_dims, t_type> new_poly;
            new_poly.add(vertex(0));
            t_type accumulated_distance = 0;
            for (uint04 i = 1; i < vertexCount(); i++)
            {
                t_type local_distance = distance<t_type>(vertex(i - 1), vertex(i));
                while (accumulated_distance + local_distance > max_distance)
                {
                    auto direction = (vertex(i) - new_poly.lastVertex()).template normalized<t_type>();
                    t_type adjusted_distance = max_distance - accumulated_distance;
 
                    auto final_vertex = adjusted_distance * direction + new_poly.lastVertex();
                    new_poly.add(final_vertex);
                    new_polys.add(new_poly);
 
                    new_poly.clear();
                    new_poly.add(final_vertex);
                    local_distance = local_distance - adjusted_distance;
                    accumulated_distance = 0.0;
 
                }
                new_poly.add(vertex(i));
                accumulated_distance += local_distance;
            }
            new_polys.add(new_poly);
            return new_polys;
        }
 
        Polyline<t_dims, t_type> clipPolyline(const Bounds<t_vertex::NumberOfDimensions(), t_type>& bounds) const
        {
            if (bounds.contains<true>(this->bounds()))
                return *this;
            if (!bounds.intersects(this->bounds()))
                return Polyline();
            Polyline polyline(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 (!isNaN(line))
                {
                    if (polyline.vertexCount() == 0 || polyline.lastVertex() != line.vertex(A))
                        polyline.add(line.vertex(A));
                    polyline.add(line.vertex(B));
                }
            }
            polyline.simplify();
            return polyline;
        }
    private:
 
        /**--------------------------------------------------------------------------------------------------
        Fn: inline void Polyline::invalidateCache() const
        
        Invalidate cache.
        
        Author: Tyler Parke
        
        Date: 2017-11-19
         *-----------------------------------------------------------------------------------------------**/
 
        inline void invalidateCache() const
        {
            m_cache_length = Constant<t_type>::NaN;
            m_cache_bounds = Constant<Bounds<t_dims, t_type>>::NaN;
        }
 
        /**--------------------------------------------------------------------------------------------------
        Fn: void Polyline::updateVertices(const Buffer<t_vertex>& vertices)
        
        Updates the vertices described by given vertices.
        
        Author: Tyler Parke
        
        Date: 2017-11-19
        
        Parameters:
        vertices -  The vertices.
         *-----------------------------------------------------------------------------------------------**/
 
        void updateVertices(const Buffer<t_vertex>& vertices)
        {
            m_vertices = vertices;
            invalidateCache();
        }
    private:
        /** The vertices. */
        Buffer<t_vertex> m_vertices;
 
        /**--------------------------------------------------------------------------------------------------
        Property: mutable Bounds<t_dims, t_type, t_vertex> m_cache_bounds
        
        Gets the cache bounds.
        
        Returns: The m cache bounds.
         *-----------------------------------------------------------------------------------------------**/
 
        mutable Bounds<t_dims, 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;
    };
}