earcut.hpp
v2.2.4
Un puerto C ++ de Earcut.js, una biblioteca de triangulación de polígono rápida y solo de encabezado.
La biblioteca implementa un algoritmo modificado de corte en el oído, optimizado por el hash de curva de orden z y extendido para manejar agujeros, polígonos retorcidos, degeneraciones e intermedios de sí mismo de una manera que no garantiza la corrección de la triangulación, pero intenta producir siempre resultados aceptables para datos prácticos como formas geográficas.
Se basa en ideas de Fist: Triangulación rápida de fuerza industrial de polígonos por Martin Hold and Triangulación por el recorte de oídos de 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);Earcut puede triangular un polígono simple y plano de cualquier orden de devanado, incluidos agujeros. Incluso devolverá una solución robusta y aceptable para Poygons no simples. Earcut funciona en un avión 2D. Si tiene tres o más dimensiones, puede proyectarlas en una superficie 2D antes de la triangulación, o usar una biblioteca más adecuada para la tarea (por ejemplo, CGAL).
También es posible usar su tipo de punto personalizado como entrada. Hay accesorios predeterminados definidos para std::tuple , std::pair y std::array . Para un tipo personalizado (como el tipo IntPoint de Clipper), haga esto:
// 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 También puede usar un tipo de contenedor personalizado para su polígono. Similar a std :: vector, debe cumplir con los requisitos del contenedor, en particular size() , empty() y operator[] .
En caso de que solo desee usar la biblioteca de triangulación de Earcut; Copie e incluya el archivo de encabezado <earcut.hpp> en su proyecto y siga los pasos documentados en el uso de la sección.
Si desea construir la prueba, en su lugar, los programas de referencia y visualización, siga estas instrucciones:
Antes de continuar, asegúrese de instalar las siguientes herramientas y bibliotecas:
Nota: En algunos sistemas operativos como Windows, se requieren pasos manuales para agregar CMake y Git a su variable de entorno de ruta.
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"Después de completar, abra el proyecto generado con su IDE.
Importe el proyecto desde https://github.com/mapbox/earcut.hpp.git y ¡debería estar listo para comenzar!
Esto se basa actualmente en Earcut 2.2.4.
