earcut.hpp
v2.2.4
Ein C ++-Port of Earcut.js, eine schnelle, nur Header-Polygon-Triangulationsbibliothek.
Die Bibliothek implementiert einen modifizierten Ohrschneidealgorithmus, der durch Z-Order-Kurve-Hashing optimiert und um Löcher, verdrehte Polygone, Degeneritäten und Selbstinterktionen auf eine Weise zu handhaben, die nicht die Korrektheit der Triangulation garantiert , aber Versuche, immer akzeptable Ergebnisse für praktische Daten wie geografische Formen zu erzielen.
Es basiert auf Ideen von Faust: Fast Industrial-Fegth-Triangulation von Polygonen durch Martin-Held und Triangulation nach Ohrausschnitten von David Eberly.
# include < earcut.hpp > // The number type to use for tessellation
using Coord = double ;
// The index type. Defaults to uint32_t, but you can also pass uint16_t if you know that your
// data won't have more than 65536 vertices.
using N = uint32_t ;
// Create array
using Point = std::array<Coord, 2 >;
std::vector<std::vector< Point >> polygon;
// Fill polygon structure with actual data. Any winding order works.
// The first polyline defines the main polygon.
polygon.push_back({{ 100 , 0 }, { 100 , 100 }, { 0 , 100 }, { 0 , 0 }});
// Following polylines define holes.
polygon.push_back({{ 75 , 25 }, { 75 , 75 }, { 25 , 75 }, { 25 , 25 }});
// Run tessellation
// Returns array of indices that refer to the vertices of the input polygon.
// e.g: the index 6 would refer to {25, 75} in this example.
// Three subsequent indices form a triangle. Output triangles are clockwise.
std::vector<N> indices = mapbox::earcut<N>(polygon);Die Ohrstrafe kann ein einfaches, planares Polygon aller Wicklungsreihenfolge einschließlich Löcher triangulieren. Es wird sogar eine robuste, akzeptable Lösung für nicht einfache Poygone zurückgeben. Ohrstrich arbeitet in einem 2D -Flugzeug. Wenn Sie drei oder mehr Abmessungen haben, können Sie sie vor der Triangulation auf eine 2D -Oberfläche projizieren oder eine geeignetere Bibliothek für die Aufgabe (z. B. CGAL) verwenden.
Es ist auch möglich, Ihren benutzerdefinierten Punkttyp als Eingabe zu verwenden. Es gibt Standard -Accessors für std::tuple , std::pair und std::array . Für einen benutzerdefinierten Typ (wie IntPoint -Typ von Clipper) tun Sie Folgendes:
// struct IntPoint {
// int64_t X, Y;
// };
namespace mapbox {
namespace util {
template <>
struct nth < 0 , IntPoint> {
inline static auto get ( const IntPoint &t) {
return t. X ;
};
};
template <>
struct nth < 1 , IntPoint> {
inline static auto get ( const IntPoint &t) {
return t. Y ;
};
};
} // namespace util
} // namespace mapbox Sie können auch einen benutzerdefinierten Container -Typ für Ihr Polygon verwenden. Ähnlich wie bei STD :: Vektor muss es die Anforderungen des Containers, insbesondere size() , empty() und operator[] erfüllen.
Falls Sie nur die Triangulationsbibliothek der Ohrkrampenung verwenden möchten; Kopieren Sie und geben Sie die Header -Datei <earcut.hpp> in Ihr Projekt ein und befolgen Sie die in der Abschnittsnutzung dokumentierten Schritte.
Wenn Sie stattdessen den Test für Test-, Benchmark- und Visualisierungsprogramme erstellen möchten, befolgen Sie die folgenden Anweisungen:
Stellen Sie vor dem weiteren Fortsetzung die folgenden Tools und Bibliotheken installiert:
HINWEIS: Bei einigen Betriebssystemen wie Windows sind manuelle Schritte erforderlich, um CMake und Git Ihrer Pfadumgebungsvariable hinzuzufügen.
git clone --recursive https://github.com/mapbox/earcut.hpp.git
cd earcut.hpp
mkdir build
cd build
cmake ..
make
# ./tests
# ./bench
# ./vizgit clone --recursive https://github.com/mapbox/earcut.hpp.git
cd earcut.hpp
mkdir project
cd project
cmake .. -G " Visual Studio 14 2015 "
:: you can also generate projects for "Visual Studio 12 2013", "XCode", "Eclipse CDT4 - Unix Makefiles"Öffnen Sie nach Abschluss das erzeugte Projekt mit Ihrer IDE.
Importieren Sie das Projekt aus https://github.com/mapbox/earcut.hpp.git und Sie sollten gut gehen!
Dies basiert derzeit auf Earcut 2.2.4.
