polypartition.h

/*************************************************************************/
/* Copyright (c) 2011-2021 Ivan Fratric and contributors.                */
/*                                                                       */
/* Permission is hereby granted, free of charge, to any person obtaining */
/* a copy of this software and associated documentation files (the       */
/* "Software"), to deal in the Software without restriction, including   */
/* without limitation the rights to use, copy, modify, merge, publish,   */
/* distribute, sublicense, and/or sell copies of the Software, and to    */
/* permit persons to whom the Software is furnished to do so, subject to */
/* the following conditions:                                             */
/*                                                                       */
/* 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.                */
/*************************************************************************/

#ifndef POLYPARTITION_H
#define POLYPARTITION_H

#include "core/math/vector2.h"
#include "core/templates/list.h"
#include "core/templates/rb_set.h"

typedef double tppl_float;

enum TPPLOrientation {
  TPPL_ORIENTATION_CW = -1,
  TPPL_ORIENTATION_NONE = 0,
  TPPL_ORIENTATION_CCW = 1,
};

enum TPPLVertexType {
  TPPL_VERTEXTYPE_REGULAR = 0,
  TPPL_VERTEXTYPE_START = 1,
  TPPL_VERTEXTYPE_END = 2,
  TPPL_VERTEXTYPE_SPLIT = 3,
  TPPL_VERTEXTYPE_MERGE = 4,
};

// 2D point structure.
typedef Vector2 TPPLPoint;

// Polygon implemented as an array of points with a "hole" flag.
class TPPLPoly {
  protected:
  TPPLPoint *points;
  long numpoints;
  bool hole;

  public:
  // Constructors and destructors.
  TPPLPoly();
  ~TPPLPoly();

  TPPLPoly(const TPPLPoly &src);
  TPPLPoly &operator=(const TPPLPoly &src);

  // Getters and setters.
  long GetNumPoints() const {
    return numpoints;
  }

  bool IsHole() const {
    return hole;
  }

  void SetHole(bool p_hole) {
    this->hole = p_hole;
  }

  TPPLPoint &GetPoint(long i) {
    return points[i];
  }

  const TPPLPoint &GetPoint(long i) const {
    return points[i];
  }

  TPPLPoint *GetPoints() {
    return points;
  }

  TPPLPoint &operator[](int i) {
    return points[i];
  }

  const TPPLPoint &operator[](int i) const {
    return points[i];
  }

  // Clears the polygon points.
  void Clear();

  // Inits the polygon with numpoints vertices.
  void Init(long numpoints);

  // Creates a triangle with points p1, p2, and p3.
  void Triangle(TPPLPoint &p1, TPPLPoint &p2, TPPLPoint &p3);

  // Inverts the orfer of vertices.
  void Invert();

  // Returns the orientation of the polygon.
  // Possible values:
  //    TPPL_ORIENTATION_CCW: Polygon vertices are in counter-clockwise order.
  //    TPPL_ORIENTATION_CW: Polygon vertices are in clockwise order.
  //    TPPL_ORIENTATION_NONE: The polygon has no (measurable) area.
  TPPLOrientation GetOrientation() const;

  // Sets the polygon orientation.
  // Possible values:
  //    TPPL_ORIENTATION_CCW: Sets vertices in counter-clockwise order.
  //    TPPL_ORIENTATION_CW: Sets vertices in clockwise order.
  //    TPPL_ORIENTATION_NONE: Reverses the orientation of the vertices if there
  //       is one, otherwise does nothing (if orientation is already NONE).
  void SetOrientation(TPPLOrientation orientation);

  // Checks whether a polygon is valid or not.
  inline bool Valid() const { return this->numpoints >= 3; }
};

#ifdef TPPL_ALLOCATOR
typedef List<TPPLPoly, TPPL_ALLOCATOR(TPPLPoly)> TPPLPolyList;
#else
typedef List<TPPLPoly> TPPLPolyList;
#endif

class TPPLPartition {
  protected:
  struct PartitionVertex {
    bool isActive;
    bool isConvex;
    bool isEar;

    TPPLPoint p;
    tppl_float angle;
    PartitionVertex *previous;
    PartitionVertex *next;

    PartitionVertex();
  };

  struct MonotoneVertex {
    TPPLPoint p;
    long previous;
    long next;
  };

  class VertexSorter {
    MonotoneVertex *vertices;

public:
    VertexSorter(MonotoneVertex *v) :
            vertices(v) {}
    bool operator()(long index1, long index2);
  };

  struct Diagonal {
    long index1;
    long index2;
  };

#ifdef TPPL_ALLOCATOR
  typedef List<Diagonal, TPPL_ALLOCATOR(Diagonal)> DiagonalList;
#else
  typedef List<Diagonal> DiagonalList;
#endif

  // Dynamic programming state for minimum-weight triangulation.
  struct DPState {
    bool visible;
    tppl_float weight;
    long bestvertex;
  };

  // Dynamic programming state for convex partitioning.
  struct DPState2 {
    bool visible;
    long weight;
    DiagonalList pairs;
  };

  // Edge that intersects the scanline.
  struct ScanLineEdge {
    mutable long index;
    TPPLPoint p1;
    TPPLPoint p2;

    // Determines if the edge is to the left of another edge.
    bool operator<(const ScanLineEdge &other) const;

    bool IsConvex(const TPPLPoint &p1, const TPPLPoint &p2, const TPPLPoint &p3) const;
  };

  // Standard helper functions.
  bool IsConvex(TPPLPoint &p1, TPPLPoint &p2, TPPLPoint &p3);
  bool IsReflex(TPPLPoint &p1, TPPLPoint &p2, TPPLPoint &p3);
  bool IsInside(TPPLPoint &p1, TPPLPoint &p2, TPPLPoint &p3, TPPLPoint &p);

  bool InCone(TPPLPoint &p1, TPPLPoint &p2, TPPLPoint &p3, TPPLPoint &p);
  bool InCone(PartitionVertex *v, TPPLPoint &p);

  int Intersects(TPPLPoint &p11, TPPLPoint &p12, TPPLPoint &p21, TPPLPoint &p22);

  TPPLPoint Normalize(const TPPLPoint &p);
  tppl_float Distance(const TPPLPoint &p1, const TPPLPoint &p2);

  // Helper functions for Triangulate_EC.
  void UpdateVertexReflexity(PartitionVertex *v);
  void UpdateVertex(PartitionVertex *v, PartitionVertex *vertices, long numvertices);

  // Helper functions for ConvexPartition_OPT.
  void UpdateState(long a, long b, long w, long i, long j, DPState2 **dpstates);
  void TypeA(long i, long j, long k, PartitionVertex *vertices, DPState2 **dpstates);
  void TypeB(long i, long j, long k, PartitionVertex *vertices, DPState2 **dpstates);

  // Helper functions for MonotonePartition.
  bool Below(TPPLPoint &p1, TPPLPoint &p2);
  void AddDiagonal(MonotoneVertex *vertices, long *numvertices, long index1, long index2,
	  TPPLVertexType *vertextypes, RBSet<ScanLineEdge>::Element **edgeTreeIterators,
	  RBSet<ScanLineEdge> *edgeTree, long *helpers);

  // Triangulates a monotone polygon, used in Triangulate_MONO.
  int TriangulateMonotone(TPPLPoly *inPoly, TPPLPolyList *triangles);

  public:
  // Simple heuristic procedure for removing holes from a list of polygons.
  // It works by creating a diagonal from the right-most hole vertex
  // to some other visible vertex.
  // Time complexity: O(h*(n^2)), h is the # of holes, n is the # of vertices.
  // Space complexity: O(n)
  // params:
  //    inpolys:
  //       A list of polygons that can contain holes.
  //       Vertices of all non-hole polys have to be in counter-clockwise order.
  //       Vertices of all hole polys have to be in clockwise order.
  //    outpolys:
  //       A list of polygons without holes.
  // Returns 1 on success, 0 on failure.
  int RemoveHoles(TPPLPolyList *inpolys, TPPLPolyList *outpolys);

  // Triangulates a polygon by ear clipping.
  // Time complexity: O(n^2), n is the number of vertices.
  // Space complexity: O(n)
  // params:
  //    poly:
  //       An input polygon to be triangulated.
  //       Vertices have to be in counter-clockwise order.
  //    triangles:
  //       A list of triangles (result).
  // Returns 1 on success, 0 on failure.
  int Triangulate_EC(TPPLPoly *poly, TPPLPolyList *triangles);

  // Triangulates a list of polygons that may contain holes by ear clipping
  // algorithm. It first calls RemoveHoles to get rid of the holes, and then
  // calls Triangulate_EC for each resulting polygon.
  // Time complexity: O(h*(n^2)), h is the # of holes, n is the # of vertices.
  // Space complexity: O(n)
  // params:
  //    inpolys:
  //       A list of polygons to be triangulated (can contain holes).
  //       Vertices of all non-hole polys have to be in counter-clockwise order.
  //       Vertices of all hole polys have to be in clockwise order.
  //    triangles:
  //       A list of triangles (result).
  // Returns 1 on success, 0 on failure.
  int Triangulate_EC(TPPLPolyList *inpolys, TPPLPolyList *triangles);

  // Creates an optimal polygon triangulation in terms of minimal edge length.
  // Time complexity: O(n^3), n is the number of vertices
  // Space complexity: O(n^2)
  // params:
  //    poly:
  //       An input polygon to be triangulated.
  //       Vertices have to be in counter-clockwise order.
  //    triangles:
  //       A list of triangles (result).
  // Returns 1 on success, 0 on failure.
  int Triangulate_OPT(TPPLPoly *poly, TPPLPolyList *triangles);

  // Triangulates a polygon by first partitioning it into monotone polygons.
  // Time complexity: O(n*log(n)), n is the number of vertices.
  // Space complexity: O(n)
  // params:
  //    poly:
  //       An input polygon to be triangulated.
  //       Vertices have to be in counter-clockwise order.
  //    triangles:
  //       A list of triangles (result).
  // Returns 1 on success, 0 on failure.
  int Triangulate_MONO(TPPLPoly *poly, TPPLPolyList *triangles);

  // Triangulates a list of polygons by first
  // partitioning them into monotone polygons.
  // Time complexity: O(n*log(n)), n is the number of vertices.
  // Space complexity: O(n)
  // params:
  //    inpolys:
  //       A list of polygons to be triangulated (can contain holes).
  //       Vertices of all non-hole polys have to be in counter-clockwise order.
  //       Vertices of all hole polys have to be in clockwise order.
  //    triangles:
  //       A list of triangles (result).
  // Returns 1 on success, 0 on failure.
  int Triangulate_MONO(TPPLPolyList *inpolys, TPPLPolyList *triangles);

  // Creates a monotone partition of a list of polygons that
  // can contain holes. Triangulates a set of polygons by
  // first partitioning them into monotone polygons.
  // Time complexity: O(n*log(n)), n is the number of vertices.
  // Space complexity: O(n)
  // params:
  //    inpolys:
  //       A list of polygons to be triangulated (can contain holes).
  //       Vertices of all non-hole polys have to be in counter-clockwise order.
  //       Vertices of all hole polys have to be in clockwise order.
  //    monotonePolys:
  //       A list of monotone polygons (result).
  // Returns 1 on success, 0 on failure.
  int MonotonePartition(TPPLPolyList *inpolys, TPPLPolyList *monotonePolys);

  // Partitions a polygon into convex polygons by using the
  // Hertel-Mehlhorn algorithm. The algorithm gives at most four times
  // the number of parts as the optimal algorithm, however, in practice
  // it works much better than that and often gives optimal partition.
  // It uses triangulation obtained by ear clipping as intermediate result.
  // Time complexity O(n^2), n is the number of vertices.
  // Space complexity: O(n)
  // params:
  //    poly:
  //       An input polygon to be partitioned.
  //       Vertices have to be in counter-clockwise order.
  //    parts:
  //       Resulting list of convex polygons.
  // Returns 1 on success, 0 on failure.
  int ConvexPartition_HM(TPPLPoly *poly, TPPLPolyList *parts);

  // Partitions a list of polygons into convex parts by using the
  // Hertel-Mehlhorn algorithm. The algorithm gives at most four times
  // the number of parts as the optimal algorithm, however, in practice
  // it works much better than that and often gives optimal partition.
  // It uses triangulation obtained by ear clipping as intermediate result.
  // Time complexity O(n^2), n is the number of vertices.
  // Space complexity: O(n)
  // params:
  //    inpolys:
  //       An input list of polygons to be partitioned. Vertices of
  //       all non-hole polys have to be in counter-clockwise order.
  //       Vertices of all hole polys have to be in clockwise order.
  //    parts:
  //       Resulting list of convex polygons.
  // Returns 1 on success, 0 on failure.
  int ConvexPartition_HM(TPPLPolyList *inpolys, TPPLPolyList *parts);

  // Optimal convex partitioning (in terms of number of resulting
  // convex polygons) using the Keil-Snoeyink algorithm.
  // For reference, see M. Keil, J. Snoeyink, "On the time bound for
  // convex decomposition of simple polygons", 1998.
  // Time complexity O(n^3), n is the number of vertices.
  // Space complexity: O(n^3)
  // params:
  //    poly:
  //       An input polygon to be partitioned.
  //       Vertices have to be in counter-clockwise order.
  //    parts:
  //       Resulting list of convex polygons.
  // Returns 1 on success, 0 on failure.
  int ConvexPartition_OPT(TPPLPoly *poly, TPPLPolyList *parts);
};

#endif