PolyLine.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: 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
{

    template<uint01 t_dims, class t_type, class t_vertex = Vertex<t_dims, t_type>>
    class Polyline
    {
    public:
        typedef AlocatingAlignedBuffer<Polyline<t_dims, t_type, t_vertex>, 32> PolyLineBuffer;
        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);
        }

 
        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();
        }

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

 
        LineSegment<t_dims, t_type, t_vertex> segment(uint04 index) const
        {
            return LineSegment<t_dims, t_type, t_vertex>(vertex(index), vertex(index + 1));
        }

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

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

 
        inline uint04 segmentCount() const
        {
            if (m_vertices.size() == 0)
                return 0;
            else
                return m_vertices.size() - 1;
        }

 
        inline void setVertices(const Buffer<t_vertex>& vertices)
        {
            updateVertices(vertices);
        }

 
        void add(const t_vertex& vertex)
        {
            m_vertices.add(vertex);
            invalidateCache();
        }
        void addAndSimplify(const t_vertex& vertex)
        {
            addAndSimplify(vertexCount(), 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();
        }

 
        void replace(uint04 index, const t_vertex& vertex)
        {
            if (m_vertices[index] != vertex)
            {
                m_vertices[index] = vertex;
                invalidateCache();
            }
        }

 
        void remove(uint04 index)
        {
            m_vertices.removeIndex(index);
            invalidateCache();
        }

        const t_vertex& lastVertex() const
        {
            return m_vertices.last();
        }

        void removeLastVertex()
        {
            m_vertices.removeLast();
        }

        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--;
                }
            }
        }

 
        void clear()
        {
            m_vertices.clear();
            invalidateCache();
        }

        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;
        }

        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(IsValid(segment(i)))
                            m_cache_length += segment(i).template length<t_precision>();
                    }
                }
            }
            return m_cache_length;
        }
        

        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();
        }

 
        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 (IsValid(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;
        }
 
        PolyLineBuffer breakIntoPolylinesByLength(t_type max_distance) const
        {
            PolyLineBuffer 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 (IsValid(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:

 
        inline void invalidateCache() const
        {
            m_cache_length = Constant<t_type>::Invalid;
            m_cache_bounds = Constant<Bounds<t_dims, t_type>>::Invalid;
        }

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

 
        mutable Bounds<t_dims, t_type, t_vertex> m_cache_bounds;

 
        mutable t_type m_cache_length;
    };
}