summaryrefslogtreecommitdiff
path: root/src/3rdparty/clip2tri
diff options
context:
space:
mode:
Diffstat (limited to 'src/3rdparty/clip2tri')
-rw-r--r--src/3rdparty/clip2tri/CMakeLists.txt31
-rw-r--r--src/3rdparty/clip2tri/LICENSE21
-rw-r--r--src/3rdparty/clip2tri/clip2tri.cpp406
-rw-r--r--src/3rdparty/clip2tri/clip2tri.h102
-rw-r--r--src/3rdparty/clip2tri/clip2tri.pro22
-rw-r--r--src/3rdparty/clip2tri/qt_attribution.json13
6 files changed, 0 insertions, 595 deletions
diff --git a/src/3rdparty/clip2tri/CMakeLists.txt b/src/3rdparty/clip2tri/CMakeLists.txt
deleted file mode 100644
index 9b5a56b3..00000000
--- a/src/3rdparty/clip2tri/CMakeLists.txt
+++ /dev/null
@@ -1,31 +0,0 @@
-# Generated from clip2tri.pro.
-
-#####################################################################
-## Bundled_Clip2Tri Generic Library:
-#####################################################################
-
-qt_internal_add_3rdparty_library(Bundled_Clip2Tri
- QMAKE_LIB_NAME _clip2tri
- STATIC
- SKIP_AUTOMOC # special case
- EXCEPTIONS
- SOURCES
- clip2tri.cpp clip2tri.h
- INCLUDE_DIRECTORIES
- ../clipper
- ../poly2tri
- LIBRARIES
- Qt::Bundled_Clipper # special case
- Qt::Bundled_Poly2Tri # special case
-)
-qt_disable_warnings(Bundled_Clip2Tri)
-qt_set_symbol_visibility_hidden(Bundled_Clip2Tri)
-
-## Scopes:
-#####################################################################
-
-#### Keys ignored in scope 3:.:.:clip2tri.pro:GCC:
-# QMAKE_CFLAGS_OPTIMIZE_FULL = "-ffast-math"
-
-#### Keys ignored in scope 4:.:.:clip2tri.pro:NOT CLANG AND NOT ICC AND NOT rim_qcc:
-# QMAKE_CXXFLAGS_WARN_ON = "-Wno-error=return-type"
diff --git a/src/3rdparty/clip2tri/LICENSE b/src/3rdparty/clip2tri/LICENSE
deleted file mode 100644
index 9d99b888..00000000
--- a/src/3rdparty/clip2tri/LICENSE
+++ /dev/null
@@ -1,21 +0,0 @@
-The MIT License (MIT)
-
-Copyright (c) 2014 Bitfighter developers
-
-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.
diff --git a/src/3rdparty/clip2tri/clip2tri.cpp b/src/3rdparty/clip2tri/clip2tri.cpp
deleted file mode 100644
index db4911c1..00000000
--- a/src/3rdparty/clip2tri/clip2tri.cpp
+++ /dev/null
@@ -1,406 +0,0 @@
-/*
- * Authors: kaen, raptor, sam686, watusimoto
- *
- * Originally from the bitfighter source code
- *
- * The MIT License (MIT)
- *
- * Copyright (c) 2014 Bitfighter developers
- *
- * 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 "clip2tri.h"
-#include <poly2tri.h>
-
-#include <cstdio>
-
-static const double clipperScaleFactor = 1073741822.0;
-static const double clipperScaleFactorInv = 1.0 / 1073741822.0;
-
-using namespace p2t;
-
-namespace c2t
-{
-
-
-static const F32 CLIPPER_SCALE_FACT = 1000.0f;
-static const F32 CLIPPER_SCALE_FACT_INVERSE = 0.001f;
-
-/////////////////////////////////
-
-Point::Point()
-{
- x = 0;
- y = 0;
-}
-
-Point::Point(const Point& pt)
-{
- x = pt.x;
- y = pt.y;
-}
-
-
-/////////////////////////////////
-
-clip2tri::clip2tri() : openSubject(false)
-{
- // Do nothing!
-}
-
-clip2tri::~clip2tri()
-{
- // Do nothing!
-}
-
-
-void clip2tri::triangulate(const vector<vector<Point> > &inputPolygons, vector<Point> &outputTriangles,
- const vector<Point> &boundingPolygon)
-{
- // Use clipper to clean. This upscales the floating point input
- PolyTree solution;
- mergePolysToPolyTree(inputPolygons, solution);
-
- Path bounds = upscaleClipperPoints(boundingPolygon);
-
- // This will downscale the Clipper output and use poly2tri to triangulate
- triangulateComplex(outputTriangles, bounds, solution);
-}
-
-void clip2tri::addClipPolygon(const Path &path)
-{
- try // prevent any exception to spill into Qt
- {
- clipper.AddPath(path, ptClip, true);
- }
- catch(QtClipperLib::clipperException &e)
- {
- printf("addClipPolygon: %s\n", e.what());
- }
-}
-
-void clip2tri::addSubjectPath(const Path &path, bool closed)
-{
- try // prevent any exception to spill into Qt
- {
- clipper.AddPath(path, ptSubject, closed);
- }
- catch(QtClipperLib::clipperException &e)
- {
- printf("addSubjectPath: %s\n", e.what());
- return;
- }
- if (!closed)
- openSubject = true;
-}
-
-void clip2tri::clearClipper()
-{
- // clear doesn't throw
- clipper.Clear();
- openSubject = false;
-}
-
-static QtClipperLib::ClipType operation(const clip2tri::Operation &op)
-{
- switch (op) {
- case clip2tri::Intersection:
- return QtClipperLib::ctIntersection;
- case clip2tri::Union:
- return QtClipperLib::ctUnion;
- case clip2tri::Difference:
- return QtClipperLib::ctDifference;
- case clip2tri::Xor:
- return QtClipperLib::ctXor;
- }
- return ctIntersection;
-}
-
-static std::string operationName(const clip2tri::Operation &op)
-{
- switch (op) {
- case clip2tri::Intersection:
- return std::string("Intersection");
- case clip2tri::Union:
- return std::string("Union");
- case clip2tri::Difference:
- return std::string("Difference");
- case clip2tri::Xor:
- return std::string("Xor");
- }
- return std::string("Intersection");
-}
-
-Paths clip2tri::execute(const clip2tri::Operation op, const PolyFillType subjFillType, const PolyFillType clipFillType)
-{
- Paths solution;
- try // prevent any exception from spilling into Qt
- {
- if (!openSubject) {
- clipper.Execute(operation(op), solution, subjFillType, clipFillType);
- } else {
- PolyTree res;
- clipper.Execute(operation(op), res, subjFillType, clipFillType);
- PolyNode *n = res.GetFirst();
- if (n) {
- solution.push_back(n->Contour);
- while ((n = n->GetNext()))
- solution.push_back(n->Contour);
- }
- }
- }
- catch(QtClipperLib::clipperException &e)
- {
- printf("executing %s: %s\n", operationName(op).c_str(), e.what());
- }
- return solution;
-}
-
-int clip2tri::pointInPolygon(const IntPoint &pt, const Path &path)
-{
- return PointInPolygon(pt, path);
-}
-
-Path clip2tri::upscaleClipperPoints(const vector<Point> &inputPolygon)
-{
- Path outputPolygon;
- outputPolygon.resize(inputPolygon.size());
-
- for(S32 i = 0; i < inputPolygon.size(); i++)
- outputPolygon[i] = IntPoint(S64(inputPolygon[i].x * CLIPPER_SCALE_FACT), S64(inputPolygon[i].y * CLIPPER_SCALE_FACT));
-
- return outputPolygon;
-}
-
-
-Paths clip2tri::upscaleClipperPoints(const vector<vector<Point> > &inputPolygons)
-{
- Paths outputPolygons;
-
- outputPolygons.resize(inputPolygons.size());
-
- for(S32 i = 0; i < inputPolygons.size(); i++)
- {
- outputPolygons[i].resize(inputPolygons[i].size());
-
- for(S32 j = 0; j < inputPolygons[i].size(); j++)
- outputPolygons[i][j] = IntPoint(S64(inputPolygons[i][j].x * CLIPPER_SCALE_FACT), S64(inputPolygons[i][j].y * CLIPPER_SCALE_FACT));
- }
-
- return outputPolygons;
-}
-
-
-vector<vector<Point> > clip2tri::downscaleClipperPoints(const Paths &inputPolygons)
-{
- vector<vector<Point> > outputPolygons;
-
- outputPolygons.resize(inputPolygons.size());
-
- for(U32 i = 0; i < inputPolygons.size(); i++)
- {
- outputPolygons[i].resize(inputPolygons[i].size());
-
- for(U32 j = 0; j < inputPolygons[i].size(); j++)
- outputPolygons[i][j] = Point(F32(inputPolygons[i][j].X) * CLIPPER_SCALE_FACT_INVERSE, F32(inputPolygons[i][j].Y) * CLIPPER_SCALE_FACT_INVERSE);
- }
-
- return outputPolygons;
-}
-
-
-// Use Clipper to merge inputPolygons, placing the result in a Polytree
-// NOTE: this does NOT downscale the Clipper points. You must do this afterwards
-//
-// Here you add all your non-navigatable objects (e.g. walls, barriers, etc.)
-bool clip2tri::mergePolysToPolyTree(const vector<vector<Point> > &inputPolygons, PolyTree &solution)
-{
- Paths input = upscaleClipperPoints(inputPolygons);
-
- // Fire up clipper and union!
- Clipper clipper;
- clipper.StrictlySimple(true);
-
- try // there is a "throw" in AddPolygon
- {
- clipper.AddPaths(input, ptSubject, true);
- }
- catch(QtClipperLib::clipperException &e)
- {
- printf("mergePolysToPolyTree: %s\n", e.what());
- }
-
- return clipper.Execute(ctUnion, solution, pftNonZero, pftNonZero);
-}
-
-
-// Delete all poly2tri points from a vector and clear the vector
-static void deleteAndClear(vector<p2t::Point*> &vec)
-{
- for(U32 i = 0; i < vec.size(); i++)
- delete vec[i];
-
- vec.clear();
-}
-
-
-// Shrink large polygons by reducing each coordinate by 1 in the
-// general direction of the last point as we wind around
-//
-// This normally wouldn't work in every case, but our upscaled-by-1000 polygons
-// have little chance to create new duplicate points with this method.
-//
-// For information on why this was needed, see:
-//
-// https://code.google.com/p/poly2tri/issues/detail?id=90
-//
-static void edgeShrink(Path &path)
-{
- U32 prev = path.size() - 1;
- for(U32 i = 0; i < path.size(); i++)
- {
- // Adjust coordinate by 1 depending on the direction
- path[i].X - path[prev].X > 0 ? path[i].X-- : path[i].X++;
- path[i].Y - path[prev].Y > 0 ? path[i].Y-- : path[i].Y++;
-
- prev = i;
- }
-}
-
-
-// This uses poly2tri to triangulate. poly2tri isn't very robust so clipper needs to do
-// the cleaning of points before getting here.
-//
-// A tree structure of polygons is required for doing complex polygons-within-polygons.
-// For reference discussion on how this started to be developed, see here:
-//
-// https://code.google.com/p/poly2tri/issues/detail?id=74
-//
-// For assistance with a special case crash, see this utility:
-// http://javascript.poly2tri.googlecode.com/hg/index.html
-//
-// FIXME: what is ignoreFills and ignoreHoles for? kaen?
-bool clip2tri::triangulateComplex(vector<Point> &outputTriangles, const Path &outline,
- const PolyTree &polyTree, bool ignoreFills, bool ignoreHoles)
-{
- // Keep track of memory for all the poly2tri objects we create
- vector<p2t::CDT*> cdtRegistry;
- vector<vector<p2t::Point*> > holesRegistry;
- vector<vector<p2t::Point*> > polylinesRegistry;
-
-
- // Let's be tricky and add our outline to the root node (it should have none), it'll be
- // our first Clipper hole
- PolyNode *rootNode = NULL;
-
- PolyNode tempNode;
- if(polyTree.Total() == 0) // Polytree is empty with no root node, e.g. on an empty level
- rootNode = &tempNode;
- else
- rootNode = polyTree.GetFirst()->Parent;
-
- rootNode->Contour = outline;
-
- // Now traverse our polyline nodes and triangulate them with only their children holes
- PolyNode *currentNode = rootNode;
- while(currentNode != NULL)
- {
- // A Clipper hole is actually what we want to build zones for; they become our bounding
- // polylines. poly2tri holes are therefore the inverse
- if((!ignoreHoles && currentNode->IsHole()) ||
- (!ignoreFills && !currentNode->IsHole()))
- {
- // Build up this polyline in poly2tri's format (downscale Clipper points)
- vector<p2t::Point*> polyline;
- for(U32 j = 0; j < currentNode->Contour.size(); j++)
- polyline.push_back(new p2t::Point(F64(currentNode->Contour[j].X), F64(currentNode->Contour[j].Y)));
-
- polylinesRegistry.push_back(polyline); // Memory
-
- // Set our polyline in poly2tri
- p2t::CDT* cdt = new p2t::CDT(polyline);
- cdtRegistry.push_back(cdt);
-
- for(U32 j = 0; j < currentNode->Childs.size(); j++)
- {
- PolyNode *childNode = currentNode->Childs[j];
-
- // Slightly modify the polygon to guarantee no duplicate points
- edgeShrink(childNode->Contour);
-
- vector<p2t::Point*> hole;
- for(U32 k = 0; k < childNode->Contour.size(); k++)
- hole.push_back(new p2t::Point(F64(childNode->Contour[k].X), F64(childNode->Contour[k].Y)));
-
- holesRegistry.push_back(hole); // Memory
-
- // Add the holes for this polyline
- cdt->AddHole(hole);
- }
-
- cdt->Triangulate();
-
- // Add current output triangles to our total
- vector<p2t::Triangle*> currentOutput = cdt->GetTriangles();
-
- // Copy our data to TNL::Point and to our output Vector
- p2t::Triangle *currentTriangle;
- for(U32 j = 0; j < currentOutput.size(); j++)
- {
- currentTriangle = currentOutput[j];
- outputTriangles.push_back(Point(currentTriangle->GetPoint(0)->x * CLIPPER_SCALE_FACT_INVERSE, currentTriangle->GetPoint(0)->y * CLIPPER_SCALE_FACT_INVERSE));
- outputTriangles.push_back(Point(currentTriangle->GetPoint(1)->x * CLIPPER_SCALE_FACT_INVERSE, currentTriangle->GetPoint(1)->y * CLIPPER_SCALE_FACT_INVERSE));
- outputTriangles.push_back(Point(currentTriangle->GetPoint(2)->x * CLIPPER_SCALE_FACT_INVERSE, currentTriangle->GetPoint(2)->y * CLIPPER_SCALE_FACT_INVERSE));
- }
- }
-
- currentNode = currentNode->GetNext();
- }
-
-
- // Clean up memory used with poly2tri
- //
- // Clean-up workers
- for(S32 i = 0; i < cdtRegistry.size(); i++)
- delete cdtRegistry[i];
-
- // Free the polylines
- for(S32 i = 0; i < polylinesRegistry.size(); i++)
- {
- vector<p2t::Point*> polyline = polylinesRegistry[i];
- deleteAndClear(polyline);
- }
-
- // Free the holes
- for(S32 i = 0; i < holesRegistry.size(); i++)
- {
- vector<p2t::Point*> hole = holesRegistry[i];
- deleteAndClear(hole);
- }
-
- // Make sure we have output data
- if(outputTriangles.size() == 0)
- return false;
-
- return true;
-}
-
-
-} /* namespace c2t */
diff --git a/src/3rdparty/clip2tri/clip2tri.h b/src/3rdparty/clip2tri/clip2tri.h
deleted file mode 100644
index 3848d009..00000000
--- a/src/3rdparty/clip2tri/clip2tri.h
+++ /dev/null
@@ -1,102 +0,0 @@
-/*
- * Authors: kaen, raptor, sam686, watusimoto
- *
- * Originally from the bitfighter source code
- *
- * The MIT License (MIT)
- *
- * Copyright (c) 2014 Bitfighter developers
- *
- * 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 CLIP2TRI_H_
-#define CLIP2TRI_H_
-
-#include <vector>
-#include <clipper.h>
-
-using namespace std;
-using namespace QtClipperLib;
-
-namespace c2t
-{
-
-typedef signed int S32;
-typedef signed long long S64;
-typedef unsigned int U32;
-typedef float F32;
-typedef double F64;
-
-
-struct Point
-{
- F32 x;
- F32 y;
-
- Point();
- Point(const Point &pt);
-
- template<class T, class U>
- Point(T in_x, U in_y) { x = static_cast<F32>(in_x); y = static_cast<F32>(in_y); }
-};
-
-class clip2tri
-{
-private:
- //
- Path upscaleClipperPoints(const vector<Point> &inputPolygon);
-
- // These operate on a vector of polygons
- Paths upscaleClipperPoints(const vector<vector<Point> > &inputPolygons);
- vector<vector<Point> > downscaleClipperPoints(const Paths &inputPolygons);
-
- bool mergePolysToPolyTree(const vector<vector<Point> > &inputPolygons, PolyTree &solution);
-
- bool triangulateComplex(vector<Point> &outputTriangles, const Path &outline,
- const PolyTree &polyTree, bool ignoreFills = true, bool ignoreHoles = false);
-
-public:
- enum Operation { Union, Intersection, Difference, Xor };
- clip2tri();
- virtual ~clip2tri();
-
- void triangulate(const vector<vector<Point> > &inputPolygons, vector<Point> &outputTriangles,
- const vector<Point> &boundingPolygon);
-
- // Clip polygons are intended as closed, even if the first and last vertex aren't the same.
- void addClipPolygon(const Path &path);
- // Closed means the path has to be effectively closed. Meaning path[0] == path[path.size()-1]
- void addSubjectPath(const Path &path, bool closed);
-
- void clearClipper();
-
- Paths execute(const Operation op,
- const PolyFillType subjFillType = pftNonZero,
- const PolyFillType clipFillType = pftNonZero);
-
- static int pointInPolygon(const IntPoint &pt, const Path &path);
-
- Clipper clipper;
- bool openSubject;
-};
-
-} /* namespace c2t */
-
-#endif /* CLIP2TRI_H_ */
diff --git a/src/3rdparty/clip2tri/clip2tri.pro b/src/3rdparty/clip2tri/clip2tri.pro
deleted file mode 100644
index 4059a63a..00000000
--- a/src/3rdparty/clip2tri/clip2tri.pro
+++ /dev/null
@@ -1,22 +0,0 @@
-TARGET = qt_clip2tri
-
-CONFIG += staticlib exceptions warn_off optimize_full
-
-INCLUDEPATH += ../poly2tri
-INCLUDEPATH += ../clipper
-
-load(qt_helper_lib)
-
-# workaround for QTBUG-31586
-contains(QT_CONFIG, c++11): CONFIG += c++11
-
-gcc {
- QMAKE_CFLAGS_OPTIMIZE_FULL += -ffast-math
- !clang:!intel_icc:!rim_qcc: QMAKE_CXXFLAGS_WARN_ON += -Wno-error=return-type
-}
-
-HEADERS += clip2tri.h
-SOURCES += clip2tri.cpp
-
-LIBS_PRIVATE += -L$$MODULE_BASE_OUTDIR/lib -lqt_poly2tri$$qtPlatformTargetSuffix() -lqt_clipper$$qtPlatformTargetSuffix()
-
diff --git a/src/3rdparty/clip2tri/qt_attribution.json b/src/3rdparty/clip2tri/qt_attribution.json
deleted file mode 100644
index a4a1f183..00000000
--- a/src/3rdparty/clip2tri/qt_attribution.json
+++ /dev/null
@@ -1,13 +0,0 @@
-{
- "Id": "clip2tri",
- "Name": "Clip2Tri Polygon Triangulation Library",
- "QDocModule": "qtpositioning",
- "QtUsage": "Used in the QML plugin of Qt Location and in Qt Positioning.",
-
- "Description": "Clip2Tri can be used together with Clipper for robust triangulation.",
- "Homepage": "https://github.com/raptor/clip2tri",
- "LicenseId": "MIT",
- "License": "MIT License",
- "LicenseFile": "LICENSE",
- "Copyright": "Copyright (c) 2014 Bitfighter developers"
-}