godot/thirdparty/misc/polypartition.cpp

/*************************************************************************/
/* 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.                */
/*************************************************************************/

#include "polypartition.h"

#include <math.h>
#include <string.h>
#include <algorithm>

TPPLPoly::TPPLPoly() { … }

TPPLPoly::~TPPLPoly() { … }

void TPPLPoly::Clear() { … }

void TPPLPoly::Init(long numpoints) { … }

void TPPLPoly::Triangle(TPPLPoint &p1, TPPLPoint &p2, TPPLPoint &p3) { … }

TPPLPoly::TPPLPoly(const TPPLPoly &src) : … { … }

TPPLPoly &TPPLPoly::operator=(const TPPLPoly &src) { … }

TPPLOrientation TPPLPoly::GetOrientation() const { … }

void TPPLPoly::SetOrientation(TPPLOrientation orientation) { … }

void TPPLPoly::Invert() { … }

TPPLPartition::PartitionVertex::PartitionVertex() : … { … }

TPPLPoint TPPLPartition::Normalize(const TPPLPoint &p) { … }

tppl_float TPPLPartition::Distance(const TPPLPoint &p1, const TPPLPoint &p2) { … }

// Checks if two lines intersect.
int TPPLPartition::Intersects(TPPLPoint &p11, TPPLPoint &p12, TPPLPoint &p21, TPPLPoint &p22) { … }

// Removes holes from inpolys by merging them with non-holes.
int TPPLPartition::RemoveHoles(TPPLPolyList *inpolys, TPPLPolyList *outpolys) { … }

bool TPPLPartition::IsConvex(TPPLPoint &p1, TPPLPoint &p2, TPPLPoint &p3) { … }

bool TPPLPartition::IsReflex(TPPLPoint &p1, TPPLPoint &p2, TPPLPoint &p3) { … }

bool TPPLPartition::IsInside(TPPLPoint &p1, TPPLPoint &p2, TPPLPoint &p3, TPPLPoint &p) { … }

bool TPPLPartition::InCone(TPPLPoint &p1, TPPLPoint &p2, TPPLPoint &p3, TPPLPoint &p) { … }

bool TPPLPartition::InCone(PartitionVertex *v, TPPLPoint &p) { … }

void TPPLPartition::UpdateVertexReflexity(PartitionVertex *v) { … }

void TPPLPartition::UpdateVertex(PartitionVertex *v, PartitionVertex *vertices, long numvertices) { … }

// Triangulation by ear removal.
int TPPLPartition::Triangulate_EC(TPPLPoly *poly, TPPLPolyList *triangles) { … }

int TPPLPartition::Triangulate_EC(TPPLPolyList *inpolys, TPPLPolyList *triangles) { … }

int TPPLPartition::ConvexPartition_HM(TPPLPoly *poly, TPPLPolyList *parts) { … }

int TPPLPartition::ConvexPartition_HM(TPPLPolyList *inpolys, TPPLPolyList *parts) { … }

// Minimum-weight polygon triangulation by dynamic programming.
// Time complexity: O(n^3)
// Space complexity: O(n^2)
int TPPLPartition::Triangulate_OPT(TPPLPoly *poly, TPPLPolyList *triangles) { … }

void TPPLPartition::UpdateState(long a, long b, long w, long i, long j, DPState2 **dpstates) { … }

void TPPLPartition::TypeA(long i, long j, long k, PartitionVertex *vertices, DPState2 **dpstates) { … }

void TPPLPartition::TypeB(long i, long j, long k, PartitionVertex *vertices, DPState2 **dpstates) { … }

int TPPLPartition::ConvexPartition_OPT(TPPLPoly *poly, TPPLPolyList *parts) { … }

// 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)
// The algorithm used here is outlined in the book
// "Computational Geometry: Algorithms and Applications"
// by Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars.
int TPPLPartition::MonotonePartition(TPPLPolyList *inpolys, TPPLPolyList *monotonePolys) { … }

// Adds a diagonal to the doubly-connected list of vertices.
void TPPLPartition::AddDiagonal(MonotoneVertex *vertices, long *numvertices, long index1, long index2,
	TPPLVertexType *vertextypes, RBSet<ScanLineEdge>::Element **edgeTreeIterators,
	RBSet<ScanLineEdge> *edgeTree, long *helpers) { … }

bool TPPLPartition::Below(TPPLPoint &p1, TPPLPoint &p2) { … }

// Sorts in the falling order of y values, if y is equal, x is used instead.
bool TPPLPartition::VertexSorter::operator()(long index1, long index2) { … }

bool TPPLPartition::ScanLineEdge::IsConvex(const TPPLPoint &p1, const TPPLPoint &p2, const TPPLPoint &p3) const { … }

bool TPPLPartition::ScanLineEdge::operator<(const ScanLineEdge &other) const { … }

// Triangulates monotone polygon.
// Time complexity: O(n)
// Space complexity: O(n)
int TPPLPartition::TriangulateMonotone(TPPLPoly *inPoly, TPPLPolyList *triangles) { … }

int TPPLPartition::Triangulate_MONO(TPPLPolyList *inpolys, TPPLPolyList *triangles) { … }

int TPPLPartition::Triangulate_MONO(TPPLPoly *poly, TPPLPolyList *triangles) { … }