#pragma region CPL License
/*
Nuclex Native Framework
Copyright (C) 2002-2015 Nuclex Development Labs

This library is free software; you can redistribute it and/or
modify it under the terms of the IBM Common Public License as
published by the IBM Corporation; either version 1.0 of the
License, or (at your option) any later version.

This library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
IBM Common Public License for more details.

You should have received a copy of the IBM Common Public
License along with this library
*/
#pragma endregion // CPL License

#ifndef NUCLEX_GEOMETRY_LINES_GENERATORS_POLYLINE3GENERATOR_H
#define NUCLEX_GEOMETRY_LINES_GENERATORS_POLYLINE3GENERATOR_H

#include "Nuclex/Geometry/Config.h"
#include "Nuclex/Geometry/Lines/PolyLine3.h"
#include "Nuclex/Geometry/Lines/Line3.h"

namespace Nuclex { namespace Geometry { namespace Lines { namespace Generators {

  // ------------------------------------------------------------------------------------------- //

  /// <summary>Primitive generation methods for 3D poly lines</summary>
  template <typename TScalar>
  class PolyLine3Generator {

    #pragma region class DouglasPeuckerSimplifier

    /// <summary>Simplifies poly lines using the Douglas-Peucker algorithm</summary>
    private: class DouglasPeuckerSimplifier {
      
      /// <summary>Initializes a new Douglas-Peucker poly line simplifier</summary>
      /// <param name="polyLine">Poly line of which a simplified version will be built</param>
      public: DouglasPeuckerSimplifier(const PolyLine3<TScalar> &polyLine) :
        polyLine(polyLine) {}

      /// <summary>
      ///   Builds the simplified poly line out of poly line the simplifier was constructed with
      /// </summary>
      /// <param name="maximumError">
      ///   Distance under which a vertex will be collapsed into the line segment it lies on
      /// </param>
      /// <returns>The simplified poly line</returns>
      public: PolyLine3<TScalar> Simplify(TScalar maximumError) const {
        PolyLine3<TScalar> result;
        eliminateOrSplit(
          std::make_pair(0, this->polyLine.Vertices.size() - 1),
          maximumError * maximumError, result
        );
        result.Vertices.push_back(this->polyLine.Vertices.back());
        return result;
      }

      /// <summary>
      ///   Eliminates all points within the span or performs a recursive split on the vertex
      ///   with the largest error
      /// </summary>
      /// <param name="span">Span in which vertices will be analyzed</param>
      /// <param name="squaredMaximumError">
      ///   Distance under which a vertex will be collapsed into the line segment it lies on
      /// </param>
      /// <param name="output">Poly line in which the final vertices will be placed</param>
      private: void eliminateOrSplit(
        const std::pair<std::size_t, std::size_t> &span,
        TScalar squaredMaximumError,
        PolyLine3<TScalar> &output
      ) const {
        const Point3<TScalar> &origin = this->polyLine.Vertices[span.first];
        Line3<TScalar> line(
          origin, Vector3<TScalar>::Normalize(this->polyLine.Vertices[span.second] - origin)
        );

        // If there are interior points, see whether one of the interior points can be
        // simplified into a straight line
        std::size_t firstInteriorIndex = span.first + 1;
        if(firstInteriorIndex < span.second) {
          TScalar largestSquaredError = getSquaredPerpendicularDistance(
            line, this->polyLine.Vertices[firstInteriorIndex]
          );
          std::size_t largestSquaredErrorIndex = firstInteriorIndex;

          for(std::size_t index = firstInteriorIndex + 1; index < span.second; ++index) {
            TScalar squaredError = getSquaredPerpendicularDistance(
              line, this->polyLine.Vertices[index]
            );
            if(squaredError > largestSquaredError) {
              largestSquaredError = squaredError;
              largestSquaredErrorIndex = index;
            }
          }

          // If the point with the largest error exceeds the maximum allowed error,
          // use it as a new output vertex and try to simplify the lines left and right of it
          if(largestSquaredError > squaredMaximumError) {
            eliminateOrSplit(
              std::pair<std::size_t, std::size_t>(span.first, largestSquaredErrorIndex),
              squaredMaximumError,
              output
            );
            eliminateOrSplit(
              std::pair<std::size_t, std::size_t>(largestSquaredErrorIndex, span.second),
              squaredMaximumError,
              output
            );
          } else {
            output.Vertices.push_back(this->polyLine.Vertices[span.first]);
          }
        } else {
          output.Vertices.push_back(this->polyLine.Vertices[span.first]);
        }
      }

      /// <summary>Calculates the squared distance of a point to a line</summary>
      /// <param name="line">Line to which the distance will be calculated</param>
      /// <param name="point">Point whose distance to the line will be calculated</param>
      /// <returns>The squared distance of the point to the line</returns>
      private: static TScalar getSquaredPerpendicularDistance(
        const Line3<TScalar> &line, const Point3<TScalar> &point
      ) {
        Vector3<TScalar> pointOffset = point - line.Origin;
        TScalar dot = Vector3<TScalar>::Dot(pointOffset, line.Direction);

        return Point3<TScalar>::SquaredDistanceBetween(
          point, line.Origin + (line.Direction * dot)
        );
      }

      private: DouglasPeuckerSimplifier(const DouglasPeuckerSimplifier &);
      private: DouglasPeuckerSimplifier &operator =(const DouglasPeuckerSimplifier &);

      /// <summary>Poly line that is being simplified</summary>
      private: const PolyLine3<TScalar> polyLine;

    };

    #pragma endregion // class DouglasPeuckerSimplifier

    /// <summary>Creates a simplified poly line using the Douglas-Peucker algorithm</summary>
    /// <param name="polyLine">Poly line that will be simplified</param>
    /// <param name="maximumError">Maximum error under which vertices can be eliminated</param>
    public: static PolyLine3<TScalar> GetDouglasPeuckerSimplified(
      const PolyLine3<TScalar> &polyLine, TScalar maximumError
    ) {
      return DouglasPeuckerSimplifier(polyLine).Simplify(maximumError);
    }

  };

  // ------------------------------------------------------------------------------------------- //

}}}} // namespace Nuclex::Geometry::Lines::Generators

#endif // NUCLEX_GEOMETRY_LINES_GENERATORS_POLYLINE3GENERATOR_H