earcut.hpp
v2.2.4
Un port C ++ de Earcut.js, une bibliothèque de triangulation polygonale rapide et en tête uniquement.
La bibliothèque met en œuvre un algorithme de tranchage d'oreille modifié, optimisé par le hachage de la courbe d'ordre z et étendu pour gérer les trous, les polygones tordus, les dégénérescences et l'auto-intérieur d'une manière qui ne garantit pas l'exactitude de la triangulation, mais tente de toujours produire des résultats acceptables pour des données pratiques comme les formes géographiques.
Il est basé sur des idées de Fist: Triangulation industrielle rapide des polygones par Martin Held et triangulation par coupure de l'oreille par 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);L'oreille peut trianguler un polygone plan simple et plan de tout ordre d'enroulement, y compris les trous. Il renverra même une solution robuste et acceptable pour les poygons non simples. L'oreille fonctionne sur un avion 2D. Si vous avez trois dimensions ou plus, vous pouvez les projeter sur une surface 2D avant la triangulation, ou utiliser une bibliothèque plus appropriée pour la tâche (par exemple CGAL).
Il est également possible d'utiliser votre type de point personnalisé comme entrée. Il existe des accessoires par défaut définis pour std::tuple , std::pair et std::array . Pour un type personnalisé (comme le type IntPoint de Clipper), faites ceci:
// 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 Vous pouvez également utiliser un type de conteneur personnalisé pour votre polygone. Semblable au vecteur std ::, il doit répondre aux exigences du conteneur, en particulier size() , empty() et operator[] .
Dans le cas où vous souhaitez simplement utiliser la bibliothèque de triangulation Earcut; Copiez et incluez le fichier d'en-tête <earcut.hpp> dans votre projet et suivez les étapes documentées dans l'utilisation de la section.
Si vous souhaitez créer les programmes de test, de référence et de visualisation, suivez ces instructions:
Avant de continuer, assurez-vous d'installer les outils et bibliothèques suivants:
Remarque: Sur certains systèmes d'exploitation tels que Windows, des étapes manuelles sont nécessaires pour ajouter CMake et Git à votre variable d'environnement de chemin.
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"Une fois terminé, ouvrez le projet généré avec votre IDE.
Importez le projet à partir de https://github.com/mapbox/earcut.hpp.git et vous devriez être prêt à partir!
Ceci est actuellement basé sur l'oreille 2.2.4.
