earcut.hpp
v2.2.4
Порт C ++ earCut.js, быстрая библиотека полигона только для заголовка.
Библиотека реализует модифицированный алгоритм нарезов уха, оптимизированный с помощью хеширования кривой Z-порядка и продленного для обработки отверстий, скрученных полигонов, дегенерации и самостоятельных переключений таким образом, чтобы не гарантировать правильность триангуляции, но пытается всегда давать приемлемые результаты для практических данных, таких как географические формы.
Он основан на идеях от кулака: быстрого промышленного триангуляции многоугольников Мартином и триангуляцией по вырезанию ушей Дэвидом Эберли.
# 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);Ушная прикола может триангулировать простой, плоский многоугольник любого обмотки, включая отверстия. Это даже вернет надежное, приемлемое решение для непреодолимых пойгонов. Ушная прикола работает на 2D -самолете. Если у вас есть три или более измерений, вы можете проецировать их на 2D -поверхность перед триангуляцией или использовать более подходящую библиотеку для этой задачи (например, CGAL).
Также возможно использовать пользовательский тип точки в качестве входного ввода. Есть аксессов по умолчанию, определяемые для std::tuple , std::pair и std::array . Для пользовательского типа (например, типа IntPoint от Clipper), сделайте это:
// 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 Вы также можете использовать пользовательский тип контейнера для вашего многоугольника. Подобно std :: vector, он должен соответствовать требованиям контейнера, в определенном size() , empty() и operator[] .
В случае, если вы просто хотите использовать библиотеку траангуляции для ушной приколы; Скопируйте и включите файл заголовка <earcut.hpp> в вашем проекте и следуйте шагам, зарегистрированным в использовании раздела.
Если вы хотите создать программы теста, теста и визуализации вместо этого, следуйте этим инструкциям:
Прежде чем продолжить, убедитесь, что установили следующие инструменты и библиотеки:
Примечание. В некоторых операционных системах, таких как Windows, необходимы ручные шаги, чтобы добавить Cmake и GIT в переменную среды вашего пути.
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"После завершения откройте сгенерированный проект с вашим IDE.
Импортируйте проект с https://github.com/mapbox/earcut.hpp.git, и вы должны быть хороши!
В настоящее время это основано на ушной приколе 2.2.4.
