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 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>>::Invalid)
            , m_cache_length(Constant<t_type>::Invalid)
        {}
        explicit Polyline(Buffer<t_vertex>& vertices)
            : m_vertices(vertices)
            , m_cache_bounds(Constant<Bounds<t_dims, t_type>>::Invalid)
            , m_cache_length(Constant<t_type>::Invalid)
        {}
        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);
        }
 
        /**--------------------------------------------------------------------------------------------------
                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 (IsInvalid(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();
        }
 
        /**--------------------------------------------------------------------------------------------------
                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];
        }
 
        /**--------------------------------------------------------------------------------------------------
                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));
        }
 
        /**--------------------------------------------------------------------------------------------------
                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();
        }
 
        /**--------------------------------------------------------------------------------------------------
                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;
        }
 
        /**--------------------------------------------------------------------------------------------------
                Sets the vertices.
        
        Author: Tyler Parke
        
        Date: 2017-11-19
        
        Parameters:
        vertices -  The vertices.
        **/
 
        inline void setVertices(const Buffer<t_vertex>& vertices)
        {
            updateVertices(vertices);
        }
 
        /**--------------------------------------------------------------------------------------------------
                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);
        }
 
        /**--------------------------------------------------------------------------------------------------
                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 (IsInvalid(vertex))
            {
                if (index < vertexCount() && IsInvalid(this->vertex(index)))
                    return;//nothing to do
                if (index > 1 && IsInvalid(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();
        }
 
        /**--------------------------------------------------------------------------------------------------
                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();
            }
        }
 
        /**--------------------------------------------------------------------------------------------------
                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();
        }
 
        /**--------------------------------------------------------------------------------------------------
                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();
        }
        /**--------------------------------------------------------------------------------------------------
                Removes the last vertex from the polyline.
 
        Author: Tyler Parke
 
        Date: 2019-01-12
 
        **/
        void removeLastVertex()
        {
            m_vertices.removeLast();
        }
        /**--------------------------------------------------------------------------------------------------
                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--;
                }
            }
        }
        /**--------------------------------------------------------------------------------------------------
                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 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;
        }
 
        /**--------------------------------------------------------------------------------------------------
                Gets the length.
        
        Author: Tyler Parke
        
        Date: 2017-11-19
        
        \returns A t_type.
        **/
        template<class t_precision>
        t_precision length() const
        {
            if (IsInvalid(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(!IsInvalid(segment(i)))
                            m_cache_length += segment(i).template length<t_precision>();
                    }
                }
            }
            return m_cache_length;
        }
        
 
        /**--------------------------------------------------------------------------------------------------
                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>::Invalid;
            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();
        }
 
        /**--------------------------------------------------------------------------------------------------
                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 (!IsInvalid(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 (!IsInvalid(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:
 
        /**--------------------------------------------------------------------------------------------------
                Invalidate cache.
        
        Author: Tyler Parke
        
        Date: 2017-11-19
        **/
 
        inline void invalidateCache() const
        {
            m_cache_length = Constant<t_type>::Invalid;
            m_cache_bounds = Constant<Bounds<t_dims, t_type>>::Invalid;
        }
 
        /**--------------------------------------------------------------------------------------------------
                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;
    };
}