Updated to use mapbox hpp skel, made into header only library, added google benchmark, fixed various configuration issues, moved the namespace some
diff --git a/.gitignore b/.gitignore index ff5aa79..7dae8e6 100644 --- a/.gitignore +++ b/.gitignore
@@ -8,8 +8,8 @@ compile_commands.json CTestTestfile.cmake .vscode -build -includes +cmake-build .DS_Store out -node_modules \ No newline at end of file +node_modules +mason_packages
diff --git a/.travis.yml b/.travis.yml index 76aa4d1..1e77f22 100644 --- a/.travis.yml +++ b/.travis.yml
@@ -1,8 +1,81 @@ -language: cpp -dist: trusty -compiler: clang++ -os: linux +language: generic + +matrix: + include: + # clang-tidy/format specific job + - os: linux + sudo: false + env: CLANG_FORMAT CLANG_TIDY + addons: + apt: + sources: [ 'ubuntu-toolchain-r-test' ] + packages: [ 'libstdc++6', 'libstdc++-5-dev' ] + script: + - make tidy + - make format + - os: linux + sudo: false + env: CXX=g++-4.9 + addons: + apt: + sources: [ 'ubuntu-toolchain-r-test' ] + packages: [ 'g++-4.9' ] + - os: linux + sudo: false + env: CXX=g++-5 + addons: + apt: + sources: [ 'ubuntu-toolchain-r-test' ] + packages: [ 'g++-5' ] + - os: linux + sudo: false + env: CXX=clang++ + addons: + apt: + sources: [ 'ubuntu-toolchain-r-test' ] + packages: [ 'libstdc++6', 'libstdc++-5-dev' ] + - os: linux + sudo: required # workaround https://github.com/mapbox/node-cpp-skel/issues/93 + env: CXXFLAGS="-fsanitize=address,undefined,integer -fno-sanitize-recover=all" + addons: + apt: + sources: [ 'ubuntu-toolchain-r-test' ] + packages: [ 'libstdc++6', 'libstdc++-5-dev' ] + # coverage build + - os: linux + sudo: false + env: CXXFLAGS="--coverage" LDFLAGS="--coverage" + addons: + apt: + sources: [ 'ubuntu-toolchain-r-test' ] + packages: [ 'libstdc++6', 'libstdc++-5-dev' ] + script: + - make debug + - make test + # MASON_LLVM_RELEASE comes from the setup.sh script + - mason install llvm-cov ${MASON_LLVM_RELEASE} + - mason link llvm-cov ${MASON_LLVM_RELEASE} + - curl -S -f https://codecov.io/bash -o codecov + - chmod +x codecov + - ./codecov -x "llvm-cov gcov" -Z + +env: + global: + - CMAKE_VERSION="3.8.2" + install: -- cmake -DCMAKE_BUILD_TYPE=Release -- VERBOSE=1 make -script: ./delaunator-test + # set up the environment by installing mason and clang++ + - ./scripts/setup.sh --config local.env + # put mason and clang++ on PATH + - source local.env + - mason install cmake ${CMAKE_VERSION} + - mason link cmake ${CMAKE_VERSION} + - which cmake + +script: + - make release + - make test + - make clean + - make debug + - make test + - make clean
diff --git a/CMakeLists.txt b/CMakeLists.txt index 58e1ae3..45c8ddf 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt
@@ -1,38 +1,62 @@ -cmake_minimum_required(VERSION 3.0.0) +cmake_minimum_required(VERSION 3.8) project(delaunator VERSION 0.1.0) set (CMAKE_CXX_STANDARD 14) -if (NOT EXISTS "${CMAKE_CURRENT_SOURCE_DIR}/includes") - execute_process(COMMAND bash "-c" "(cd ${CMAKE_CURRENT_SOURCE_DIR} && ./fetch-includes.sh)") +set(CMAKE_CXX_STANDARD_REQUIRED on) +set(CMAKE_EXPORT_COMPILE_COMMANDS ON) + +include(${CMAKE_CURRENT_SOURCE_DIR}/cmake/mason.cmake) + +option(WERROR "Add -Werror flag to build (turns warnings into errors)" ON) + +# configure optimization +if (CMAKE_BUILD_TYPE STREQUAL "Debug") + set(OPTIMIZATION_FLAGS "-O0 -DDEBUG") + message("-- Configuring debug build") +else() + set(OPTIMIZATION_FLAGS "-O3 -DNDEBUG") + message("-- Configuring release build") endif() -#delaunator -add_library(delaunator src/delaunator.cpp) -target_include_directories (delaunator PRIVATE "${CMAKE_CURRENT_SOURCE_DIR}/includes/rapidjson/include") -target_include_directories (delaunator PRIVATE "${CMAKE_CURRENT_SOURCE_DIR}/includes/prettyprint") +# Enable extra warnings to adhere to https://github.com/mapbox/cpp/issues/37 +set(DESIRED_WARNINGS "-Wall -Wextra -Wconversion -Wunreachable-code -Wuninitialized -pedantic-errors -Wold-style-cast -Wno-error=unused-variable -Wshadow -Wfloat-equal -Weffc++") +if(CMAKE_CXX_COMPILER_ID STREQUAL "Clang") + set(DESIRED_WARNINGS "${DESIRED_WARNINGS} -Wmost") +endif() -#delaunator -add_library(json-helpers src/json-helpers.cpp) -target_include_directories (json-helpers PRIVATE "${CMAKE_CURRENT_SOURCE_DIR}/includes/rapidjson/include") +# Note: -D_GLIBCXX_USE_CXX11_ABI=0 is needed to support mason packages that are precompiled libs +# Currently we only depend on a header only library, but this will help avoid issues when more libs are added via mason +set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} ${OPTIMIZATION_FLAGS} -D_GLIBCXX_USE_CXX11_ABI=0 ${DESIRED_WARNINGS}") -#delaunator-test -add_executable(delaunator-test src/delaunator-test.cpp) -target_link_libraries(delaunator-test delaunator) -target_include_directories (delaunator-test PRIVATE "${CMAKE_CURRENT_SOURCE_DIR}/includes/catch/single_include/catch2") -target_link_libraries(delaunator-test json-helpers) +if (WERROR) + set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -Werror") +endif() -#benchmark -add_executable(benchmark src/benchmark.cpp) -target_link_libraries(benchmark delaunator) -target_link_libraries(benchmark json-helpers) +# mason_use is a mason function within the mason.cmake file and provides ready-to-go vars, like "STATIC_LIBS" and "INCLUDE_DIRS" +mason_use(catch VERSION 2.4.0 HEADER_ONLY) +include_directories(SYSTEM ${MASON_PACKAGE_catch_INCLUDE_DIRS}) + +mason_use(rapidjson VERSION 1.1.0 HEADER_ONLY) +include_directories(SYSTEM ${MASON_PACKAGE_rapidjson_INCLUDE_DIRS}) + +mason_use(benchmark VERSION 1.2.0) +include_directories(SYSTEM ${MASON_PACKAGE_benchmark_INCLUDE_DIRS}) + +include_directories("${PROJECT_SOURCE_DIR}/include") + +file(GLOB TEST_SOURCES test/*.cpp) +add_executable(unit-tests ${TEST_SOURCES}) + +# libbenchmark.a supports threads and therefore needs pthread support +find_package(Threads REQUIRED) +file(GLOB BENCH_SOURCES bench/*.cpp) +add_executable(bench-tests ${BENCH_SOURCES}) + +file(GLOB TRIANGULATE_SOURCES examples/triangulate/*.cpp) +add_executable(triangulate ${TRIANGULATE_SOURCES}) -#triangulate -add_executable(triangulate src/triangulate.cpp) -target_include_directories (triangulate PRIVATE "${CMAKE_CURRENT_SOURCE_DIR}/includes/rapidjson/include") -target_include_directories (triangulate PRIVATE "${CMAKE_CURRENT_SOURCE_DIR}/includes/prettyprint") -target_link_libraries(triangulate delaunator) -target_link_libraries(triangulate json-helpers) - +# link benchmark static library to the bench-tests binary so the bench tests know where to find the benchmark impl code +target_link_libraries(bench-tests ${MASON_PACKAGE_benchmark_STATIC_LIBS} ${CMAKE_THREAD_LIBS_INIT}) set(CPACK_PROJECT_NAME ${PROJECT_NAME}) set(CPACK_PROJECT_VERSION ${PROJECT_VERSION})
diff --git a/README.md b/README.md index c552418..e5f107e 100644 --- a/README.md +++ b/README.md
@@ -6,6 +6,7 @@ delaunator-cpp is a C++ port from https://github.com/mapbox/delaunator a JavaScript implementation of very fast 2D Delaunay algorithm. [](https://travis-ci.org/delfrrr/delaunator-cpp) +[](https://github.com/mapbox/hpp-skel) ## Features @@ -16,7 +17,7 @@ ## Usage ```CPP -#include "delaunator.h" +#include <delaunator.hpp> #include <cstdio> using namespace std; //... @@ -26,9 +27,9 @@ //triangulation happens here //note moving points to constructor - Delaunator delaunator(move(coords)); + delaunator::Delaunator delaunator(move(coords)); - for(long int i = 0; i < delaunator.triangles.size(); i+=3) { + for(std::size_t i = 0; i < delaunator.triangles.size(); i+=3) { printf( "Triangle points: [[%f, %f], [%f, %f], [%f, %f]]\n", delaunator.coords[2 * delaunator.triangles[i]], //tx0 @@ -42,7 +43,7 @@ } ``` -For full example see `src/triangulate.cpp` +For full example see `examples/triangulate/main.cpp` ## TODO
diff --git a/bench/run.cpp b/bench/run.cpp new file mode 100644 index 0000000..328d7fb --- /dev/null +++ b/bench/run.cpp
@@ -0,0 +1,24 @@ +#include <benchmark/benchmark.h> +#include <string> +#include <delaunator.hpp> +#include "../test/test_utils.hpp" + +static void BM_simple(benchmark::State& state) // NOLINT google-runtime-references +{ + std::string points_str = test_utils::read_file("./test/test-files/osm-nodes-45331-epsg-3857.geojson"); + std::vector<double> coords = test_utils::get_geo_json_points(points_str); + + while (state.KeepRunning()) + { + delaunator::Delaunator delaunator(coords); + } +} + +int main(int argc, char* argv[]) +{ + benchmark::RegisterBenchmark("BM_simple", BM_simple); // NOLINT clang-analyzer-cplusplus.NewDeleteLeaks + benchmark::Initialize(&argc, argv); + benchmark::RunSpecifiedBenchmarks(); + + return 0; +}
diff --git a/cmake/mason.cmake b/cmake/mason.cmake new file mode 100644 index 0000000..31b2312 --- /dev/null +++ b/cmake/mason.cmake
@@ -0,0 +1,231 @@ +string(RANDOM LENGTH 16 MASON_INVOCATION) + +# Directory where Mason packages are located; typically ends with mason_packages +if (NOT MASON_PACKAGE_DIR) + set(MASON_PACKAGE_DIR "${CMAKE_SOURCE_DIR}/mason_packages") +endif() + +# URL prefix of where packages are located. +if (NOT MASON_REPOSITORY) + set(MASON_REPOSITORY "https://mason-binaries.s3.amazonaws.com") +endif() + +# Path to Mason executable +if (NOT MASON_COMMAND) + set(MASON_COMMAND "${CMAKE_SOURCE_DIR}/.mason/mason") +endif() + +# Determine platform +# we call uname -s manually here since +# CMAKE_HOST_SYSTEM_NAME will not be defined before the project() call +execute_process( + COMMAND uname -s + OUTPUT_VARIABLE UNAME_S + OUTPUT_STRIP_TRAILING_WHITESPACE) + +if(NOT MASON_PLATFORM) + if (UNAME_S STREQUAL "Darwin") + set(MASON_PLATFORM "macos") + else() + set(MASON_PLATFORM "linux") + endif() +endif() + + +# Determine platform version string +if(MASON_PLATFORM STREQUAL "ios") + set(MASON_PLATFORM_VERSION "8.0") # Deployment target version +elseif(MASON_PLATFORM STREQUAL "android") + if (ANDROID_ABI STREQUAL "armeabi") + set(MASON_PLATFORM_VERSION "arm-v5-9") + elseif(ANDROID_ABI STREQUAL "arm64-v8a") + set(MASON_PLATFORM_VERSION "arm-v8-21") + elseif(ANDROID_ABI STREQUAL "x86") + set(MASON_PLATFORM_VERSION "x86-9") + elseif(ANDROID_ABI STREQUAL "x86_64") + set(MASON_PLATFORM_VERSION "x86-64-21") + elseif(ANDROID_ABI STREQUAL "mips") + set(MASON_PLATFORM_VERSION "mips-9") + elseif(ANDROID_ABI STREQUAL "mips64") + set(MASON_PLATFORM_VERSION "mips64-21") + else() + set(MASON_PLATFORM_VERSION "arm-v7-9") + endif() +elseif(NOT MASON_PLATFORM_VERSION) + execute_process( + COMMAND uname -m + OUTPUT_VARIABLE MASON_PLATFORM_VERSION + OUTPUT_STRIP_TRAILING_WHITESPACE) +endif() + +if(MASON_PLATFORM STREQUAL "macos") + set(MASON_PLATFORM "osx") +endif() + +set(ENV{MASON_PLATFORM} "${MASON_PLATFORM}") +set(ENV{MASON_PLATFORM_VERSION} "${MASON_PLATFORM_VERSION}") + +include(CMakeParseArguments) + +function(mason_use _PACKAGE) + if(NOT _PACKAGE) + message(FATAL_ERROR "[Mason] No package name given") + endif() + + cmake_parse_arguments("" "HEADER_ONLY" "VERSION" "" ${ARGN}) + + if(_UNPARSED_ARGUMENTS) + message(FATAL_ERROR "[Mason] mason_use() called with unrecognized arguments: ${_UNPARSED_ARGUMENTS}") + endif() + + if(NOT _VERSION) + message(FATAL_ERROR "[Mason] Specifying a version is required") + endif() + + if(MASON_PACKAGE_${_PACKAGE}_INVOCATION STREQUAL "${MASON_INVOCATION}") + # Check that the previous invocation of mason_use didn't select another version of this package + if(NOT MASON_PACKAGE_${_PACKAGE}_VERSION STREQUAL ${_VERSION}) + message(FATAL_ERROR "[Mason] Already using ${_PACKAGE} ${MASON_PACKAGE_${_PACKAGE}_VERSION}. Cannot select version ${_VERSION}.") + endif() + else() + if(_HEADER_ONLY) + set(_PLATFORM_ID "headers") + else() + set(_PLATFORM_ID "${MASON_PLATFORM}-${MASON_PLATFORM_VERSION}") + endif() + + set(_SLUG "${_PLATFORM_ID}/${_PACKAGE}/${_VERSION}") + set(_INSTALL_PATH "${MASON_PACKAGE_DIR}/${_SLUG}") + file(RELATIVE_PATH _INSTALL_PATH_RELATIVE "${CMAKE_CURRENT_SOURCE_DIR}" "${_INSTALL_PATH}") + + if(NOT EXISTS "${_INSTALL_PATH}") + set(_CACHE_PATH "${MASON_PACKAGE_DIR}/.binaries/${_SLUG}.tar.gz") + if (NOT EXISTS "${_CACHE_PATH}") + # Download the package + set(_URL "${MASON_REPOSITORY}/${_SLUG}.tar.gz") + message(STATUS "[Mason] Downloading package ${_URL}...") + + set(_FAILED) + set(_ERROR) + # Note: some CMake versions are compiled without SSL support + get_filename_component(_CACHE_DIR "${_CACHE_PATH}" DIRECTORY) + file(MAKE_DIRECTORY "${_CACHE_DIR}") + execute_process( + COMMAND curl --retry 3 -s -f -S -L "${_URL}" -o "${_CACHE_PATH}.tmp" + RESULT_VARIABLE _FAILED + ERROR_VARIABLE _ERROR) + if(_FAILED) + message(FATAL_ERROR "[Mason] Failed to download ${_URL}: ${_ERROR}") + else() + # We downloaded to a temporary file to prevent half-finished downloads + file(RENAME "${_CACHE_PATH}.tmp" "${_CACHE_PATH}") + endif() + endif() + + # Unpack the package + message(STATUS "[Mason] Unpacking package to ${_INSTALL_PATH_RELATIVE}...") + file(MAKE_DIRECTORY "${_INSTALL_PATH}") + execute_process( + COMMAND ${CMAKE_COMMAND} -E tar xzf "${_CACHE_PATH}" + WORKING_DIRECTORY "${_INSTALL_PATH}") + endif() + + # Create a config file if it doesn't exist in the package + # TODO: remove this once all packages have a mason.ini file + if(NOT EXISTS "${_INSTALL_PATH}/mason.ini") + # Change pkg-config files + file(GLOB_RECURSE _PKGCONFIG_FILES "${_INSTALL_PATH}/*.pc") + foreach(_PKGCONFIG_FILE IN ITEMS ${_PKGCONFIG_FILES}) + file(READ "${_PKGCONFIG_FILE}" _PKGCONFIG_FILE_CONTENT) + string(REGEX REPLACE "(^|\n)prefix=[^\n]*" "\\1prefix=${_INSTALL_PATH}" _PKGCONFIG_FILE_CONTENT "${_PKGCONFIG_FILE_CONTENT}") + file(WRITE "${_PKGCONFIG_FILE}" "${_PKGCONFIG_FILE_CONTENT}") + endforeach() + + if(NOT EXISTS "${MASON_COMMAND}") + message(FATAL_ERROR "[Mason] Could not find Mason command at ${MASON_COMMAND}") + endif() + + set(_FAILED) + set(_ERROR) + execute_process( + COMMAND ${MASON_COMMAND} config ${_PACKAGE} ${_VERSION} + WORKING_DIRECTORY ${CMAKE_SOURCE_DIR} + OUTPUT_FILE "${_INSTALL_PATH}/mason.ini" + RESULT_VARIABLE _FAILED + ERROR_VARIABLE _ERROR) + if(_FAILED) + message(FATAL_ERROR "[Mason] Could not get configuration for package ${_PACKAGE} ${_VERSION}: ${_ERROR}") + endif() + endif() + + set(MASON_PACKAGE_${_PACKAGE}_PREFIX "${_INSTALL_PATH}" CACHE STRING "${_PACKAGE} ${_INSTALL_PATH}" FORCE) + mark_as_advanced(MASON_PACKAGE_${_PACKAGE}_PREFIX) + + # Load the configuration from the ini file + file(STRINGS "${_INSTALL_PATH}/mason.ini" _CONFIG_FILE) + foreach(_LINE IN LISTS _CONFIG_FILE) + string(REGEX MATCH "^([a-z_]+) *= *" _KEY "${_LINE}") + if (_KEY) + string(LENGTH "${_KEY}" _KEY_LENGTH) + string(SUBSTRING "${_LINE}" ${_KEY_LENGTH} -1 _VALUE) + string(REGEX REPLACE ";.*$" "" _VALUE "${_VALUE}") # Trim trailing commas + string(REPLACE "{prefix}" "${_INSTALL_PATH}" _VALUE "${_VALUE}") + string(STRIP "${_VALUE}" _VALUE) + string(REPLACE "=" "" _KEY "${_KEY}") + string(STRIP "${_KEY}" _KEY) + string(TOUPPER "${_KEY}" _KEY) + if(_KEY STREQUAL "INCLUDE_DIRS" OR _KEY STREQUAL "STATIC_LIBS" ) + separate_arguments(_VALUE) + endif() + set(MASON_PACKAGE_${_PACKAGE}_${_KEY} "${_VALUE}" CACHE STRING "${_PACKAGE} ${_KEY}" FORCE) + mark_as_advanced(MASON_PACKAGE_${_PACKAGE}_${_KEY}) + endif() + endforeach() + + # Compare version in the package to catch errors early on + if(NOT _VERSION STREQUAL MASON_PACKAGE_${_PACKAGE}_VERSION) + message(FATAL_ERROR "[Mason] Package at ${_INSTALL_PATH_RELATIVE} has version '${MASON_PACKAGE_${_PACKAGE}_VERSION}', but required '${_VERSION}'") + endif() + + if(NOT _PACKAGE STREQUAL MASON_PACKAGE_${_PACKAGE}_NAME) + message(FATAL_ERROR "[Mason] Package at ${_INSTALL_PATH_RELATIVE} has name '${MASON_PACKAGE_${_PACKAGE}_NAME}', but required '${_NAME}'") + endif() + + if(NOT _HEADER_ONLY) + if(NOT MASON_PLATFORM STREQUAL MASON_PACKAGE_${_PACKAGE}_PLATFORM) + message(FATAL_ERROR "[Mason] Package at ${_INSTALL_PATH_RELATIVE} has platform '${MASON_PACKAGE_${_PACKAGE}_PLATFORM}', but required '${MASON_PLATFORM}'") + endif() + + if(NOT MASON_PLATFORM_VERSION STREQUAL MASON_PACKAGE_${_PACKAGE}_PLATFORM_VERSION) + message(FATAL_ERROR "[Mason] Package at ${_INSTALL_PATH_RELATIVE} has platform version '${MASON_PACKAGE_${_PACKAGE}_PLATFORM_VERSION}', but required '${MASON_PLATFORM_VERSION}'") + endif() + endif() + + # Concatenate the static libs and libraries + set(_LIBRARIES) + list(APPEND _LIBRARIES ${MASON_PACKAGE_${_PACKAGE}_STATIC_LIBS} ${MASON_PACKAGE_${_PACKAGE}_LDFLAGS}) + set(MASON_PACKAGE_${_PACKAGE}_LIBRARIES "${_LIBRARIES}" CACHE STRING "${_PACKAGE} _LIBRARIES" FORCE) + mark_as_advanced(MASON_PACKAGE_${_PACKAGE}_LIBRARIES) + + if(NOT _HEADER_ONLY) + string(REGEX MATCHALL "(^| +)-L *([^ ]+)" MASON_PACKAGE_${_PACKAGE}_LIBRARY_DIRS "${MASON_PACKAGE_${_PACKAGE}_LDFLAGS}") + string(REGEX REPLACE "(^| +)-L *" "\\1" MASON_PACKAGE_${_PACKAGE}_LIBRARY_DIRS "${MASON_PACKAGE_${_PACKAGE}_LIBRARY_DIRS}") + set(MASON_PACKAGE_${_PACKAGE}_LIBRARY_DIRS "${MASON_PACKAGE_${_PACKAGE}_LIBRARY_DIRS}" CACHE STRING "${_PACKAGE} ${MASON_PACKAGE_${_PACKAGE}_LIBRARY_DIRS}" FORCE) + mark_as_advanced(MASON_PACKAGE_${_PACKAGE}_LIBRARY_DIRS) + endif() + + # Store invocation ID to prevent different versions of the same package in one invocation + set(MASON_PACKAGE_${_PACKAGE}_INVOCATION "${MASON_INVOCATION}" CACHE INTERNAL "${_PACKAGE} invocation ID" FORCE) + endif() +endfunction() + +macro(target_add_mason_package _TARGET _VISIBILITY _PACKAGE) + if (NOT MASON_PACKAGE_${_PACKAGE}_INVOCATION) + message(FATAL_ERROR "[Mason] Package ${_PACKAGE} has not been initialized yet") + endif() + + target_include_directories(${_TARGET} ${_VISIBILITY} "${MASON_PACKAGE_${_PACKAGE}_INCLUDE_DIRS}") + target_compile_definitions(${_TARGET} ${_VISIBILITY} "${MASON_PACKAGE_${_PACKAGE}_DEFINITIONS}") + target_compile_options(${_TARGET} ${_VISIBILITY} "${MASON_PACKAGE_${_PACKAGE}_OPTIONS}") + target_link_libraries(${_TARGET} ${_VISIBILITY} "${MASON_PACKAGE_${_PACKAGE}_LIBRARIES}") +endmacro()
diff --git a/examples/triangulate/main.cpp b/examples/triangulate/main.cpp new file mode 100644 index 0000000..e397dc7 --- /dev/null +++ b/examples/triangulate/main.cpp
@@ -0,0 +1,81 @@ +#include "rapidjson/document.h" +#include "rapidjson/prettywriter.h" +#include <delaunator.hpp> +#include "../../test/test_utils.hpp" +#include <cstdio> +#include <fstream> +#include <vector> +#include <initializer_list> +// #include "prettyprint.hpp" +#include <iostream> + +std::string serialize_to_json(delaunator::Delaunator const& delaunator) { + rapidjson::StringBuffer sb; + rapidjson::PrettyWriter<rapidjson::StringBuffer> writer(sb); + writer.StartObject(); + writer.String("type"); writer.String("FeatureCollection"); + writer.String("crs"); + writer.StartObject(); + writer.String("type"); writer.String("name"); + writer.String("properties"); + writer.StartObject(); + writer.String("name"); writer.String("urn:ogc:def:crs:EPSG::900913"); + writer.EndObject(); + writer.EndObject(); + writer.String("features"); + writer.StartArray(); + for(std::size_t i = 0; i < delaunator.triangles.size(); i+=3) { + writer.StartObject(); + writer.String("type"); writer.String("Feature"); + writer.String("properties"); writer.StartObject(); writer.EndObject(); + writer.String("geometry"); + writer.StartObject(); + writer.String("type"); writer.String("Polygon"); + writer.String("coordinates"); + writer.StartArray(); + writer.StartArray(); + writer.StartArray(); + writer.Double(delaunator.coords[2 * delaunator.triangles[i]]); + writer.Double(delaunator.coords[2 * delaunator.triangles[i] + 1]); + writer.EndArray(); + writer.StartArray(); + writer.Double(delaunator.coords[2 * delaunator.triangles[i + 1]]); + writer.Double(delaunator.coords[2 * delaunator.triangles[i + 1] + 1]); + writer.EndArray(); + writer.StartArray(); + writer.Double(delaunator.coords[2 * delaunator.triangles[i + 2]]); + writer.Double(delaunator.coords[2 * delaunator.triangles[i + 2] + 1]); + writer.EndArray(); + writer.StartArray(); + writer.Double(delaunator.coords[2 * delaunator.triangles[i]]); + writer.Double(delaunator.coords[2 * delaunator.triangles[i] + 1]); + writer.EndArray(); + writer.EndArray(); + writer.EndArray(); + writer.EndObject(); + writer.EndObject(); + } + writer.EndArray(); + writer.EndObject(); + return std::string(sb.GetString()); +} + +int main(int, char* argv[]) { + const char* filename = argv[1]; + const char* output = argv[2]; + std::string json = test_utils::read_file(filename); + std::vector<double> coords = test_utils::get_geo_json_points(json); + delaunator::Delaunator delaunator(coords); + const char* out_json = serialize_to_json(delaunator).c_str(); + + if (output) { + printf("Writing to file %s", output); + std::ofstream stream; + stream.open(output); + stream << out_json; + stream.close(); + } else { + std::puts(out_json); + } + return 0; +}
diff --git a/generate-reference-triangles/README.md b/generate-reference-triangles/README.md index 39be18e..42b912a 100644 --- a/generate-reference-triangles/README.md +++ b/generate-reference-triangles/README.md
@@ -5,5 +5,5 @@ ``` npm i -./index.js ../test-files/playgrounds-1356-epsg-3857.geojson ../test-files/playgrounds-1356-triangles.json -``` \ No newline at end of file +./index.js ../test/test-files/playgrounds-1356-epsg-3857.geojson ../test/test-files/playgrounds-1356-triangles.json +```
diff --git a/include/delaunator.hpp b/include/delaunator.hpp new file mode 100644 index 0000000..a0f8121 --- /dev/null +++ b/include/delaunator.hpp
@@ -0,0 +1,516 @@ +#pragma once + +#include <vector> +#include <exception> +#include <memory> +#include <limits> +#include <utility> +#include <cmath> +#include <iostream> + +namespace delaunator { + +inline double dist(const double ax, + const double ay, + const double bx, + const double by) { + const double dx = ax - bx; + const double dy = ay - by; + return dx * dx + dy * dy; +} + +inline double circumradius(const double ax, + const double ay, + const double bx, + const double by, + const double cx, + const double cy) { + const double dx = bx - ax; + const double dy = by - ay; + const double ex = cx - ax; + const double ey = cy - ay; + + const double bl = dx * dx + dy * dy; + const double cl = ex * ex + ey * ey; + const double d = dx * ey - dy * ex; + + const double x = (ey * bl - dy * cl) * 0.5 / d; + const double y = (dx * cl - ex * bl) * 0.5 / d; + + if ((bl > 0.0 || bl < 0.0) && (cl > 0.0 || cl < 0.0) && (d > 0.0 || d < 0.0)) { + return x * x + y * y; + } else { + return std::numeric_limits<double>::max(); + } +} + +inline double area(const double px, + const double py, + const double qx, + const double qy, + const double rx, + const double ry) { + return (qy - py) * (rx - qx) - (qx - px) * (ry - qy); +} + +inline std::pair<double, double> circumcenter(const double ax, + const double ay, + const double bx, + const double by, + const double cx, + const double cy) { + const double dx = bx - ax; + const double dy = by - ay; + const double ex = cx - ax; + const double ey = cy - ay; + + const double bl = dx * dx + dy * dy; + const double cl = ex * ex + ey * ey; + const double d = dx * ey - dy * ex; + + const double x = ax + (ey * bl - dy * cl) * 0.5 / d; + const double y = ay + (dx * cl - ex * bl) * 0.5 / d; + + return std::make_pair(x, y); +} + +inline double compare(std::vector<double> const& coords, + std::size_t i, + std::size_t j, + double cx, + double cy) { + const double d1 = dist(coords[2 * i], coords[2 * i + 1], cx, cy); + const double d2 = dist(coords[2 * j], coords[2 * j + 1], cx, cy); + const double diff1 = d1 - d2; + const double diff2 = coords[2 * i] - coords[2 * j]; + const double diff3 = coords[2 * i + 1] - coords[2 * j + 1]; + + if (diff1 > 0.0 || diff1 < 0.0) { + return diff1; + } else if (diff2 > 0.0 || diff2 < 0.0) { + return diff2; + } else { + return diff3; + } +} + +struct sort_to_center { + + std::vector<double> const& coords; + double cx; + double cy; + + bool operator() (std::size_t i, std::size_t j) { + return compare(coords, i, j, cx, cy) < 0; + } +}; + +inline bool in_circle(double ax, + double ay, + double bx, + double by, + double cx, + double cy, + double px, + double py) { + const double dx = ax - px; + const double dy = ay - py; + const double ex = bx - px; + const double ey = by - py; + const double fx = cx - px; + const double fy = cy - py; + + const double ap = dx * dx + dy * dy; + const double bp = ex * ex + ey * ey; + const double cp = fx * fx + fy * fy; + + return (dx * (ey * cp - bp * fy) - + dy * (ex * cp - bp * fx) + + ap * (ex * fy - ey * fx)) < 0.0; +} + +inline bool check_pts_equal(double x1, double y1, double x2, double y2) { + return std::fabs(x1 - x2) < std::numeric_limits<double>::epsilon() && + std::fabs(y1 - y2) < std::numeric_limits<double>::epsilon(); +} + +constexpr std::size_t INVALID_INDEX = std::numeric_limits<std::size_t>::max(); + +struct DelaunatorPoint { + std::size_t i; + double x; + double y; + std::size_t t; + std::size_t prev; + std::size_t next; + bool removed; +}; + +struct Delaunator { + + std::vector<double> const& coords; + std::vector<std::size_t> triangles; + std::vector<std::size_t> halfedges; + std::vector<std::size_t> m_hash; + std::vector<DelaunatorPoint> m_hull; + double m_center_x; + double m_center_y; + std::size_t m_hash_size; + + Delaunator (std::vector<double> const& in_coords) : + coords(in_coords), + triangles(), + halfedges(), + m_hash(), + m_hull(), + m_center_x(), + m_center_y(), + m_hash_size() + { + std::size_t n = coords.size() >> 1; + + double max_x = std::numeric_limits<double>::min(); + double max_y = std::numeric_limits<double>::min(); + double min_x = std::numeric_limits<double>::max(); + double min_y = std::numeric_limits<double>::max(); + std::vector<std::size_t> ids; + ids.reserve(n); + + for (std::size_t i = 0; i < n; i++) { + const double x = coords[2 * i]; + const double y = coords[2 * i + 1]; + + if (x < min_x) min_x = x; + if (y < min_y) min_y = y; + if (x > max_x) max_x = x; + if (y > max_y) max_y = y; + + ids.push_back(i); + } + const double cx = (min_x + max_x) / 2; + const double cy = (min_y + max_y) / 2; + double min_dist = std::numeric_limits<double>::max(); + + std::size_t i0; + std::size_t i1; + std::size_t i2; + + // pick a seed point close to the centroid + for (std::size_t i = 0; i < n; i++) { + const double d = dist(cx, cy, coords[2 * i], coords[2 * i + 1]); + if (d < min_dist) { + i0 = i; + min_dist = d; + } + } + + min_dist = std::numeric_limits<double>::max(); + + // find the point closest to the seed + for (std::size_t i = 0; i < n; i++) { + if (i == i0) continue; + const double d = dist(coords[2 * i0], coords[2 * i0 + 1], coords[2 * i], coords[2 * i + 1]); + if (d < min_dist && d > 0.0) + { + i1 = i; + min_dist = d; + } + } + + double min_radius = std::numeric_limits<double>::max(); + + // find the third point which forms the smallest circumcircle with the first two + for (std::size_t i = 0; i < n; i++) + { + if (i == i0 || i == i1) continue; + + const double r = circumradius( + coords[2 * i0], coords[2 * i0 + 1], + coords[2 * i1], coords[2 * i1 + 1], + coords[2 * i], coords[2 * i + 1]); + + if (r < min_radius) + { + i2 = i; + min_radius = r; + } + } + + if (!(min_radius < std::numeric_limits<double>::max())) { + throw std::runtime_error("not triangulation");; + } + + bool coord_area = area( + coords[2 * i0], coords[2 * i0 + 1], + coords[2 * i1], coords[2 * i1 + 1], + coords[2 * i2], coords[2 * i2 + 1] + ) < 0.0; + if (coord_area) { + std::swap(i1,i2); + } + + const double i0x = coords[2 * i0]; + const double i0y = coords[2 * i0 + 1]; + const double i1x = coords[2 * i1]; + const double i1y = coords[2 * i1 + 1]; + const double i2x = coords[2 * i2]; + const double i2y = coords[2 * i2 + 1]; + + std::tie(m_center_x, m_center_y) = circumcenter(i0x, i0y, i1x, i1y, i2x, i2y); + + // sort the points by distance from the seed triangle circumcenter + // cerr << ids << endl; + std::sort(ids.begin(), ids.end(), sort_to_center {coords, m_center_x, m_center_y}); + // quicksort(ids, coords, 0, n - 1, m_center_x, m_center_y); + // cerr << ids << endl; + + m_hash_size = static_cast<std::size_t>(std::llround(std::ceil(std::sqrt(n)))); + m_hash.reserve(m_hash_size); + for (std::size_t i = 0; i < m_hash_size; i++) { + m_hash.push_back(INVALID_INDEX); + } + + m_hull.reserve(coords.size()); + + std::size_t e = insert_node(i0); + hash_edge(e); + m_hull[e].t = 0; + + e = insert_node(i1, e); + hash_edge(e); + m_hull[e].t = 1; + + e = insert_node(i2, e); + hash_edge(e); + m_hull[e].t = 2; + + std::size_t max_triangles = n < 3 ? 1 : 2 * n - 5; + triangles.reserve(max_triangles * 3); + halfedges.reserve(max_triangles * 3); + add_triangle(i0, i1, i2, INVALID_INDEX, INVALID_INDEX, INVALID_INDEX); + double xp = std::numeric_limits<double>::quiet_NaN(); + double yp = std::numeric_limits<double>::quiet_NaN(); + for (std::size_t k = 0; k < n; k++) { + const std::size_t i = ids[k]; + const double x = coords[2 * i]; + const double y = coords[2 * i + 1]; + if (check_pts_equal(x, y, xp, yp)) continue; + xp = x; + yp = y; + if ( + check_pts_equal(x, y, i0x, i0y) || + check_pts_equal(x, y, i1x, i1y) || + check_pts_equal(x, y, i2x, i2y) + ) continue; + + const std::size_t start_key = hash_key(x, y); + std::size_t key = start_key; + std::size_t start = INVALID_INDEX; + do { + start = m_hash[key]; + key = (key + 1) % m_hash_size; + } while( + (start == INVALID_INDEX || m_hull[start].removed) && + (key != start_key) + ); + + e = start; + + while( + area( + x, y, + m_hull[e].x, m_hull[e].y, + m_hull[m_hull[e].next].x, m_hull[m_hull[e].next].y + ) >= 0.0 + ) { + e = m_hull[e].next; + + if (e == start) { + throw std::runtime_error("Something is wrong with the input points."); + } + } + + const bool walk_back = e == start; + + // add the first triangle from the point + std::size_t t = add_triangle( + m_hull[e].i, + i, + m_hull[m_hull[e].next].i, + INVALID_INDEX, INVALID_INDEX, m_hull[e].t + ); + + m_hull[e].t = t; // keep track of boundary triangles on the hull + e = insert_node(i, e); + + // recursively flip triangles from the point until they satisfy the Delaunay condition + m_hull[e].t = legalize(t + 2); + if (m_hull[m_hull[m_hull[e].prev].prev].t == halfedges[t + 1]) { + m_hull[m_hull[m_hull[e].prev].prev].t = t + 2; + } + // walk forward through the hull, adding more triangles and flipping recursively + std::size_t q = m_hull[e].next; + while( + area( + x, y, + m_hull[q].x, m_hull[q].y, + m_hull[m_hull[q].next].x, m_hull[m_hull[q].next].y + ) < 0.0 + ) { + t = add_triangle( + m_hull[q].i, i, + m_hull[m_hull[q].next].i, m_hull[m_hull[q].prev].t, + INVALID_INDEX, m_hull[q].t + ); + m_hull[m_hull[q].prev].t = legalize(t + 2); + remove_node(q); + q = m_hull[q].next; + } + if (walk_back) { + // walk backward from the other side, adding more triangles and flipping + q = m_hull[e].prev; + while( + area( + x, y, + m_hull[m_hull[q].prev].x, m_hull[m_hull[q].prev].y, + m_hull[q].x, m_hull[q].y + ) < 0.0 + ) { + t = add_triangle( + m_hull[m_hull[q].prev].i, i, + m_hull[q].i, INVALID_INDEX, + m_hull[q].t, m_hull[m_hull[q].prev].t + ); + legalize(t + 2); + m_hull[m_hull[q].prev].t = t; + remove_node(q); + q = m_hull[q].prev; + } + } + hash_edge(e); + hash_edge(m_hull[e].prev); + } + + } + + std::size_t remove_node(std::size_t node) { + m_hull[m_hull[node].prev].next = m_hull[node].next; + m_hull[m_hull[node].next].prev = m_hull[node].prev; + m_hull[node].removed = true; + return m_hull[node].prev; + } + + std::size_t legalize(std::size_t a) { + std::size_t b = halfedges[a]; + + std::size_t a0 = a - a % 3; + std::size_t b0 = b - b % 3; + + std::size_t al = a0 + (a + 1) % 3; + std::size_t ar = a0 + (a + 2) % 3; + std::size_t bl = b0 + (b + 2) % 3; + + std::size_t p0 = triangles[ar]; + std::size_t pr = triangles[a]; + std::size_t pl = triangles[al]; + std::size_t p1 = triangles[bl]; + + const bool illegal = in_circle( + coords[2 * p0], coords[2 * p0 + 1], + coords[2 * pr], coords[2 * pr + 1], + coords[2 * pl], coords[2 * pl + 1], + coords[2 * p1], coords[2 * p1 + 1] + ); + + if (illegal) { + triangles[a] = p1; + triangles[b] = p0; + link(a, halfedges[bl]); + link(b, halfedges[ar]); + link(ar, bl); + + std::size_t br = b0 + (b + 1) % 3; + + legalize(a); + return legalize(br); + } + return ar; + } + + std::size_t insert_node(std::size_t i) { + std::size_t node = m_hull.size(); + DelaunatorPoint p = { + i, + coords[2 * i], + coords[2 * i + 1], + 0, + node, + node, + false + }; + m_hull.push_back(p); + return node; + } + + std::size_t insert_node(std::size_t i, std::size_t prev) { + std::size_t node = insert_node(i); + m_hull[node].next = m_hull[prev].next; + m_hull[node].prev = prev; + m_hull[m_hull[node].next].prev = node; + m_hull[prev].next = node; + return node; + } + + std::size_t hash_key(double x, double y) { + const double dx = x - m_center_x; + const double dy = y - m_center_y; + // use pseudo-angle: a measure that monotonically increases + // with real angle, but doesn't require expensive trigonometry + const double p = 1 - dx / (std::abs(dx) + std::abs(dy)); + return static_cast<std::size_t>(std::llround(std::floor((2 + (dy < 0 ? -p : p)) / 4 * m_hash_size))); + } + + void hash_edge(std::size_t e) { + m_hash[hash_key(m_hull[e].x, m_hull[e].y)] = e; + } + + std::size_t add_triangle(std::size_t i0, + std::size_t i1, + std::size_t i2, + std::size_t a, + std::size_t b, + std::size_t c) { + std::size_t t = triangles.size(); + triangles.push_back(i0); + triangles.push_back(i1); + triangles.push_back(i2); + link(t, a); + link(t + 1, b); + link(t + 2, c); + return t; + } + + void link(std::size_t a, std::size_t b) { + std::size_t s = halfedges.size(); + if (a == s) { + halfedges.push_back(b); + } else if (a < s) { + halfedges[a] = b; + } else { + throw std::runtime_error("Cannot link edge"); + } + if (b != INVALID_INDEX) { + std::size_t s2 = halfedges.size(); + if (b == s2) { + halfedges.push_back(a); + } else if (b < s2) { + halfedges[b] = a; + } else { + throw std::runtime_error("Cannot link edge"); + } + } + } + +}; + +} // end namespace delaunator
diff --git a/scripts/clang-tidy.sh b/scripts/clang-tidy.sh new file mode 100755 index 0000000..b3a76ad --- /dev/null +++ b/scripts/clang-tidy.sh
@@ -0,0 +1,38 @@ +#!/usr/bin/env bash + +set -eu +set -o pipefail + +# https://clang.llvm.org/extra/clang-tidy/ + +# to speed up re-runs, only re-create environment if needed +if [[ ! -f local.env ]]; then + # automatically setup environment + ./scripts/setup.sh --config local.env +fi + +# source the environment +source local.env + +PATH_TO_CLANG_TIDY_SCRIPT="$(pwd)/mason_packages/.link/share/run-clang-tidy.py" + +# to speed up re-runs, only install clang-tidy if needed +if [[ ! -f PATH_TO_CLANG_TIDY_SCRIPT ]]; then + # The MASON_LLVM_RELEASE variable comes from `local.env` + mason install clang-tidy ${MASON_LLVM_RELEASE} + # We link the tools to make it easy to know ${PATH_TO_CLANG_TIDY_SCRIPT} + mason link clang-tidy ${MASON_LLVM_RELEASE} +fi + +# build the compile_commands.json file if it does not exist +if [[ ! -f cmake-build/compile_commands.json ]]; then + # the build automatically puts the compile commands in the ./build directory + make + +fi + +# change into the build directory so that clang-tidy can find the files +# at the right paths (since this is where the actual build happens) +cd cmake-build +${PATH_TO_CLANG_TIDY_SCRIPT} -fix +
diff --git a/scripts/coverage.sh b/scripts/coverage.sh new file mode 100755 index 0000000..2cfc9c9 --- /dev/null +++ b/scripts/coverage.sh
@@ -0,0 +1,29 @@ +#!/usr/bin/env bash + +set -eu +set -o pipefail + +# http://clang.llvm.org/docs/UsersManual.html#profiling-with-instrumentation +# https://www.bignerdranch.com/blog/weve-got-you-covered/ + +# automatically setup environment + +./scripts/setup.sh --config local.env +source local.env + +make clean +export CXXFLAGS="-fprofile-instr-generate -fcoverage-mapping" +export LDFLAGS="-fprofile-instr-generate" +mason install llvm-cov ${MASON_LLVM_RELEASE} +mason link llvm-cov ${MASON_LLVM_RELEASE} +make debug +rm -f *profraw +rm -f *gcov +rm -f *profdata +LLVM_PROFILE_FILE="code-%p.profraw" make test +CXX_MODULE="./cmake-build/unit-tests" +llvm-profdata merge -output=code.profdata code-*.profraw +llvm-cov report ${CXX_MODULE} -instr-profile=code.profdata -use-color +llvm-cov show ${CXX_MODULE} -instr-profile=code.profdata src/*.cpp -filename-equivalence -use-color +llvm-cov show ${CXX_MODULE} -instr-profile=code.profdata src/*.cpp -filename-equivalence -use-color --format html > /tmp/coverage.html +echo "open /tmp/coverage.html for HTML version of this report"
diff --git a/scripts/format.sh b/scripts/format.sh new file mode 100755 index 0000000..e2e5165 --- /dev/null +++ b/scripts/format.sh
@@ -0,0 +1,36 @@ +#!/usr/bin/env bash + +set -eu +set -o pipefail + +: ' + +Runs clang-format on the code in include/ + +Return `1` if there are files to be formatted, and automatically formats them. + +Returns `0` if everything looks properly formatted. + +' + # Set up the environment by installing mason and clang++ +./scripts/setup.sh --config local.env +source local.env + +# Add clang-format as a dep +mason install clang-format ${MASON_LLVM_RELEASE} +mason link clang-format ${MASON_LLVM_RELEASE} + +# Run clang-format on all cpp and hpp files in the /src directory +find include/ bench/ test/ -type f -name '*.hpp' -or -name '*.cpp' \ + | xargs -I{} clang-format -i -style=file {} + +# Print list of modified files +dirty=$(git ls-files --modified include/ bench/ test/) + +if [[ $dirty ]]; then + echo "The following files have been modified:" + echo $dirty + exit 1 +else + exit 0 +fi \ No newline at end of file
diff --git a/scripts/setup.sh b/scripts/setup.sh new file mode 100755 index 0000000..42ce1ba --- /dev/null +++ b/scripts/setup.sh
@@ -0,0 +1,132 @@ +#!/usr/bin/env bash + +set -eu +set -o pipefail + +export MASON_RELEASE="${_MASON_RELEASE:-v0.18.0}" +export MASON_LLVM_RELEASE="${_MASON_LLVM_RELEASE:-5.0.1}" + +PLATFORM=$(uname | tr A-Z a-z) +if [[ ${PLATFORM} == 'darwin' ]]; then + PLATFORM="osx" +fi + +MASON_URL="https://s3.amazonaws.com/mason-binaries/${PLATFORM}-$(uname -m)" + +llvm_toolchain_dir="$(pwd)/.toolchain" + +function run() { + local config=${1} + # unbreak bash shell due to rvm bug on osx: https://github.com/direnv/direnv/issues/210#issuecomment-203383459 + # this impacts any usage of scripts that are source'd (like this one) + if [[ "${TRAVIS_OS_NAME:-}" == "osx" ]]; then + echo 'shell_session_update() { :; }' > ~/.direnvrc + fi + + # + # COMPILER TOOLCHAIN + # + + # We install clang++ without the mason client for a couple reasons: + # 1) decoupling makes it viable to use a custom branch of mason that might + # modify the upstream s3 bucket in a such a way that does not give + # it access to build tools like clang++ + # 2) Allows us to short-circuit and use a global clang++ install if it + # is available to save space for local builds. + GLOBAL_CLANG="${HOME}/.mason/mason_packages/${PLATFORM}-$(uname -m)/clang++/${MASON_LLVM_RELEASE}" + GLOBAL_LLVM="${HOME}/.mason/mason_packages/${PLATFORM}-$(uname -m)/llvm/${MASON_LLVM_RELEASE}" + if [[ -d ${GLOBAL_LLVM} ]]; then + echo "Detected '${GLOBAL_LLVM}/bin/clang++', using it" + local llvm_toolchain_dir=${GLOBAL_LLVM} + elif [[ -d ${GLOBAL_CLANG} ]]; then + echo "Detected '${GLOBAL_CLANG}/bin/clang++', using it" + local llvm_toolchain_dir=${GLOBAL_CLANG} + elif [[ -d ${GLOBAL_CLANG} ]]; then + echo "Detected '${GLOBAL_CLANG}/bin/clang++', using it" + local llvm_toolchain_dir=${GLOBAL_CLANG} + elif [[ ! -d ${llvm_toolchain_dir} ]]; then + BINARY="${MASON_URL}/clang++/${MASON_LLVM_RELEASE}.tar.gz" + echo "Downloading ${BINARY}" + mkdir -p ${llvm_toolchain_dir} + curl -sSfL ${BINARY} | tar --gunzip --extract --strip-components=1 --directory=${llvm_toolchain_dir} + fi + + # + # MASON + # + + function setup_mason() { + local install_dir=${1} + local mason_release=${2} + mkdir -p ${install_dir} + curl -sSfL https://github.com/mapbox/mason/archive/${mason_release}.tar.gz | tar --gunzip --extract --strip-components=1 --directory=${install_dir} + } + + setup_mason $(pwd)/.mason ${MASON_RELEASE} + + # + # ENV SETTINGS + # + + echo "export PATH=${llvm_toolchain_dir}/bin:$(pwd)/.mason:$(pwd)/mason_packages/.link/bin:"'${PATH}' > ${config} + echo "export CXX=${CXX:-${llvm_toolchain_dir}/bin/clang++}" >> ${config} + echo "export MASON_RELEASE=${MASON_RELEASE}" >> ${config} + echo "export MASON_LLVM_RELEASE=${MASON_LLVM_RELEASE}" >> ${config} + # https://github.com/google/sanitizers/wiki/AddressSanitizerAsDso + RT_BASE=${llvm_toolchain_dir}/lib/clang/${MASON_LLVM_RELEASE}/lib/$(uname | tr A-Z a-z)/libclang_rt + if [[ $(uname -s) == 'Darwin' ]]; then + RT_PRELOAD=${RT_BASE}.asan_osx_dynamic.dylib + else + RT_PRELOAD=${RT_BASE}.asan-x86_64.so + fi + echo "export MASON_LLVM_RT_PRELOAD=${RT_PRELOAD}" >> ${config} + SUPPRESSION_FILE="/tmp/leak_suppressions.txt" + # Add suppressions as needed + #echo "leak:__strdup" > ${SUPPRESSION_FILE} + echo "export ASAN_SYMBOLIZER_PATH=${llvm_toolchain_dir}/bin/llvm-symbolizer" >> ${config} + echo "export MSAN_SYMBOLIZER_PATH=${llvm_toolchain_dir}/bin/llvm-symbolizer" >> ${config} + echo "export UBSAN_OPTIONS=print_stacktrace=1" >> ${config} + if [[ -f ${SUPPRESSION_FILE} ]]; then + echo "export LSAN_OPTIONS=suppressions=${SUPPRESSION_FILE}" >> ${config} + fi + echo "export ASAN_OPTIONS=symbolize=1:abort_on_error=1:detect_container_overflow=1:check_initialization_order=1:detect_stack_use_after_return=1" >> ${config} + echo 'export MASON_SANITIZE="-fsanitize=address,undefined -fno-sanitize=vptr,function"' >> ${config} + echo 'export MASON_SANITIZE_CXXFLAGS="${MASON_SANITIZE} -fno-sanitize=vptr,function -fsanitize-address-use-after-scope -fno-omit-frame-pointer -fno-common"' >> ${config} + echo 'export MASON_SANITIZE_LDFLAGS="${MASON_SANITIZE}"' >> ${config} + + exit 0 +} + +function usage() { + >&2 echo "Usage" + >&2 echo "" + >&2 echo "$ ./scripts/setup.sh --config local.env" + >&2 echo "$ source local.env" + >&2 echo "" + exit 1 +} + +if [[ ! ${1:-} ]]; then + usage +fi + +# https://stackoverflow.com/questions/192249/how-do-i-parse-command-line-arguments-in-bash +for i in "$@" +do +case $i in + --config) + if [[ ! ${2:-} ]]; then + usage + fi + shift + run $@ + ;; + -h | --help) + usage + shift + ;; + *) + usage + ;; +esac +done
diff --git a/src/benchmark.cpp b/src/benchmark.cpp deleted file mode 100644 index c4b80af..0000000 --- a/src/benchmark.cpp +++ /dev/null
@@ -1,24 +0,0 @@ - -#include <chrono> -#include "delaunator.h" -#include "json-helpers.h" -#include <string> -#include <vector> - -using namespace std; -int main(int, char* argv[]) { - string points_str = json_helpers::read_file("./test-files/osm-nodes-45331-epsg-3857.geojson"); - const vector<double> coords = json_helpers::get_geo_json_points(points_str); - - auto t_start = chrono::high_resolution_clock::now(); - Delaunator delaunator(move(coords)); - auto t_end = chrono::high_resolution_clock::now(); - - auto milliseconds = chrono::duration_cast<chrono::milliseconds>(t_end - t_start).count(); - - printf("coords=%lu \n", delaunator.coords.size() / 2); - printf("milliseconds=%lld \n", milliseconds); - printf("triangles=%lu \n", delaunator.triangles.size()); - - return 0; -} \ No newline at end of file
diff --git a/src/delaunator-test.cpp b/src/delaunator-test.cpp deleted file mode 100644 index 06d4ce0..0000000 --- a/src/delaunator-test.cpp +++ /dev/null
@@ -1,46 +0,0 @@ -#define CATCH_CONFIG_MAIN -#include "delaunator.h" -#include "catch.hpp" -#include "json-helpers.h" -#include <string> -#include <vector> - -using namespace std; - -namespace { - void validate(const vector<double> &coords) { - Delaunator d(coords); - - SECTION("validate halfedges") { - for(size_t i = 0; i < d.halfedges.size(); i++) { - const auto i2 = d.halfedges[i]; - REQUIRE(static_cast<bool>((i2 == -1) || (d.halfedges[i2] == i))); - } - } - - } -} - -TEST_CASE("triangles match JS version ouput", "[Delaunator]") { - string points_str = json_helpers::read_file("./test-files/playgrounds-1356-epsg-3857.geojson"); - string triangles_str = json_helpers::read_file("./test-files/playgrounds-1356-triangles.json"); - const vector<double> coords = json_helpers::get_geo_json_points(points_str); - const vector<double> triangles = json_helpers::get_array_points(triangles_str); - Delaunator delaunator(move(coords)); - - SECTION("length of triangles is the same") { - REQUIRE(delaunator.triangles.size() == triangles.size()); - } - - SECTION("values are the same") { - for(size_t i = 0; i < triangles.size(); i++) - { - REQUIRE(delaunator.triangles[i] == triangles[i]); - } - } -} - -TEST_CASE("produces correct triangulation", "[Delaunator]") { - const vector<double> coords = {168, 180, 168, 178, 168, 179, 168, 181, 168, 183, 167, 183, 167, 184, 165, 184, 162, 186, 164, 188, 161, 188, 160, 191, 158, 193, 156, 193, 152, 195, 152, 198, 150, 198, 147, 198, 148, 205, 150, 210, 148, 210, 148, 208, 145, 206, 142, 206, 140, 206, 138, 206, 135, 206, 135, 209, 131, 209, 131, 211, 127, 211, 124, 210, 120, 207, 120, 204, 120, 202, 124, 201, 123, 201, 125, 198, 125, 194, 127, 194, 127, 191, 130, 191, 132, 189, 134, 189, 134, 186, 136, 184, 134, 182, 134, 179, 134, 176, 136, 174, 139, 174, 141, 177, 142, 176, 144, 176, 147, 178, 148, 176, 151, 178, 154, 178, 153, 175, 152, 174, 152, 170, 152, 168, 150, 166, 148, 166, 147, 165, 145, 162, 146, 160, 146, 157, 146, 155, 144, 155, 142, 152, 140, 150, 138, 150, 138, 148, 140, 145, 140, 142, 140, 138, 139, 138, 137, 138, 135, 138, 133, 135, 132, 132, 129, 132, 128, 132, 124, 132, 124, 130, 123, 130, 118, 126, 116, 124, 112, 122, 109, 122, 105, 122, 102, 124, 100, 124, 97, 124, 95, 126, 92, 127, 89, 127, 88, 130, 85, 132, 80, 134, 72, 134, 69, 134, 65, 138, 64, 138, 58, 137, 56, 133, 52, 133, 51, 133, 48, 133, 44, 133, 41, 131, 38, 130, 35, 130, 32, 127, 30, 127, 27, 127, 24, 127, 24, 126, 23, 124, 20, 122, 17, 122, 16, 118, 15, 116, 15, 110, 18, 108, 20, 102, 24, 97, 28, 102, 28, 98, 26, 97, 28, 94, 27, 85, 29, 79, 32, 76, 39, 70, 44, 66, 48, 65, 53, 61, 53, 58, 51, 54, 54, 54, 52, 48, 51, 43, 48, 42, 49, 38, 48, 34, 51, 30, 53, 33, 58, 30, 61, 30, 60, 27, 64, 26, 68, 24, 74, 24, 80, 24, 85, 26, 92, 26, 96, 29, 103, 32, 109, 33, 112, 37, 116, 37, 120, 37, 124, 35, 126, 35, 128, 38, 132, 38, 134, 41, 138, 38, 140, 36, 142, 40, 144, 43, 145, 41, 149, 41, 155, 41, 159, 41, 161, 46, 165, 46, 164, 42, 164, 39, 164, 34, 167, 30, 173, 24, 178, 24, 184, 24, 189, 26, 195, 21, 195, 20, 199, 20, 203, 20, 207, 17, 211, 17, 216, 17, 218, 16, 222, 22, 225, 27, 228, 31, 226, 34, 224, 34, 226, 39, 228, 43, 230, 46, 236, 46, 242, 46, 243, 50, 245, 50, 247, 54, 247, 56, 248, 60, 248, 65, 253, 66, 255, 64, 260, 64, 264, 67, 268, 71, 272, 66, 275, 66, 281, 61, 285, 66, 286, 70, 292, 74, 294, 74, 296, 74, 296, 71, 301, 74, 307, 74, 311, 78, 315, 74, 315, 77, 319, 77, 322, 82, 328, 82, 331, 81, 331, 84, 333, 86, 333, 90, 330, 95, 326, 98, 328, 99, 332, 98, 333, 101, 331, 104, 329, 104, 327, 106, 329, 111, 332, 116, 333, 119, 333, 122, 332, 126, 332, 130, 327, 130, 321, 130, 317, 130, 315, 134, 312, 134, 308, 138, 306, 138, 306, 144, 306, 149, 306, 152, 301, 152, 297, 154, 295, 154, 292, 154, 292, 158, 288, 158, 283, 162, 281, 164, 279, 163, 276, 163, 273, 166, 272, 169, 268, 168, 265, 170, 260, 172, 256, 176, 252, 176, 248, 181, 246, 182, 246, 189, 246, 194, 248, 197, 250, 198, 252, 200, 252, 203, 254, 205, 260, 205, 264, 202, 267, 202, 269, 202, 272, 199, 280, 199, 278, 202, 278, 207, 278, 211, 276, 211, 272, 213, 268, 213, 265, 213, 264, 211, 262, 210, 260, 210, 257, 212, 257, 214, 255, 217, 253, 217, 253, 221, 249, 220, 247, 220, 243, 222, 240, 223, 239, 226, 234, 231, 229, 231, 224, 231, 219, 227, 220, 227, 222, 224, 222, 222, 222, 219, 224, 217, 222, 214, 220, 212, 217, 210, 215, 210, 211, 209, 208, 206, 202, 209, 202, 205, 206, 202, 211, 198, 216, 195, 220, 192, 224, 192, 221, 186, 218, 186, 214, 185, 208, 185, 204, 186, 200, 186, 193, 183, 190, 182, 188, 182, 190, 178, 186, 178, 184, 174, 182, 171, 178, 171, 173, 174, 169, 174, 169, 175, 169, 179, 167, 182, 164, 186, 160, 192, 155, 195, 152, 198, 150, 198, 148, 198, 148, 202, 151, 208, 148, 210, 146, 208, 144, 205, 140, 205, 137, 208, 132, 208, 132, 210, 127, 210, 124, 210, 120, 206, 120, 202, 123, 202, 124, 201, 124, 198, 128, 195, 131, 191, 133, 187, 135, 183, 130, 203, 129, 208, 123, 203, 129, 203, 129, 198, 133, 198, 136, 200, 142, 200, 143, 199, 143, 197, 137, 196, 136, 194, 133, 194, 136, 186, 136, 182, 141, 186, 144, 186, 150, 186, 150, 190, 155, 190, 159, 188, 156, 182, 151, 182, 144, 182, 164, 176, 161, 177, 157, 177, 166, 176, 168, 165, 175, 167, 180, 167, 188, 159, 195, 164, 195, 162, 187, 162, 178, 163, 173, 166, 168, 170, 156, 170, 157, 165, 164, 165, 164, 161, 170, 159, 167, 158, 159, 154, 149, 151, 145, 145, 145, 138, 152, 138, 152, 146, 159, 146, 165, 153, 176, 153, 180, 153, 187, 153, 194, 153, 202, 153, 202, 158, 197, 158, 193, 158, 193, 142, 180, 142, 171, 142, 163, 135, 176, 135, 186, 139, 201, 139, 206, 139, 205, 147, 205, 160, 198, 160, 206, 174, 205, 178, 196, 178, 196, 182, 202, 182, 206, 181, 209, 181, 215, 181, 222, 181, 230, 177, 238, 175, 241, 175, 237, 175, 237, 168, 237, 161, 232, 156, 231, 162, 225, 166, 217, 169, 210, 173, 224, 173, 227, 173, 235, 175, 237, 178, 228, 192, 222, 199, 216, 199, 211, 204, 205, 206, 219, 207, 222, 211, 229, 214, 236, 214, 244, 211, 247, 211, 268, 206, 277, 201, 279, 201, 281, 202, 278, 202, 242, 178, 236, 170, 236, 162, 255, 162, 251, 156, 240, 156, 253, 152, 261, 152, 277, 157, 268, 151, 255, 143, 260, 142, 267, 145, 271, 149, 273, 154, 258, 146, 257, 131, 256, 134, 248, 137, 260, 137, 260, 134, 271, 137, 276, 138, 276, 144, 289, 144, 285, 150, 294, 150, 298, 149, 301, 145, 292, 145, 282, 134, 276, 134, 283, 127, 282, 116, 277, 113, 283, 113, 288, 106, 296, 106, 297, 113, 297, 118, 298, 118, 310, 122, 310, 128, 300, 130, 300, 140, 292, 129, 292, 114, 283, 122, 289, 122, 299, 122, 299, 134, 294, 134, 288, 124, 314, 121, 311, 113, 308, 110, 304, 96, 299, 90, 299, 82, 305, 87, 309, 94, 311, 101, 312, 102, 314, 107, 320, 112, 320, 115, 326, 116, 323, 109, 321, 102, 321, 94, 321, 90, 328, 90, 328, 88, 316, 88, 316, 84, 307, 84, 290, 77, 289, 88, 289, 97, 278, 97, 268, 106, 268, 110, 261, 105, 255, 103, 244, 103, 252, 100, 252, 91, 252, 82, 242, 78, 252, 78, 259, 78, 264, 87, 267, 92, 272, 91, 272, 83, 264, 83, 260, 79, 276, 79, 283, 84, 283, 94, 289, 94, 284, 86, 272, 77, 253, 110, 248, 110, 239, 110, 234, 114, 222, 125, 219, 127, 219, 131, 219, 138, 219, 141, 224, 139, 224, 135, 225, 130, 232, 136, 240, 138, 237, 131, 237, 118, 248, 120, 256, 122, 262, 127, 255, 118, 245, 110, 207, 129, 199, 134, 195, 134, 188, 130, 180, 130, 165, 129, 156, 129, 165, 128, 173, 125, 185, 126, 193, 126, 201, 124, 204, 123, 208, 116, 214, 114, 207, 114, 196, 114, 183, 121, 183, 111, 189, 117, 196, 112, 172, 126, 164, 126, 159, 114, 174, 106, 186, 106, 192, 105, 184, 105, 184, 96, 173, 96, 163, 111, 159, 110, 152, 110, 168, 110, 171, 106, 183, 98, 193, 101, 219, 96, 225, 97, 225, 104, 232, 92, 240, 92, 237, 86, 229, 86, 216, 88, 214, 79, 203, 79, 203, 75, 212, 75, 221, 75, 229, 80, 230, 89, 217, 88, 217, 77, 228, 77, 228, 69, 235, 71, 240, 71, 244, 66, 236, 54, 236, 62, 232, 68, 229, 61, 216, 61, 212, 58, 212, 47, 212, 39, 214, 28, 215, 48, 225, 55, 236, 55, 202, 65, 202, 54, 202, 44, 202, 24, 198, 32, 199, 38, 192, 38, 185, 38, 174, 42, 174, 48, 178, 51, 184, 51, 194, 55, 191, 68, 182, 68, 174, 69, 167, 67, 153, 59, 153, 49, 147, 49, 152, 58, 152, 74, 154, 83, 161, 83, 165, 88, 153, 97, 153, 89, 152, 82, 168, 88, 168, 101, 156, 102, 156, 119, 173, 110, 184, 110, 177, 106, 160, 106, 145, 125, 137, 122, 131, 120, 124, 120, 122, 118, 113, 118, 114, 111, 129, 111, 140, 110, 143, 106, 137, 102, 127, 102, 119, 98, 126, 93, 139, 93, 139, 99, 141, 95, 128, 89, 118, 74, 128, 76, 135, 76, 141, 83, 141, 71, 137, 61, 137, 50, 129, 50, 118, 50, 109, 52, 112, 61, 123, 60, 134, 60, 129, 76, 121, 67, 124, 76, 123, 76, 111, 74, 128, 73, 109, 83, 109, 94, 105, 103, 102, 118, 92, 113, 98, 105, 99, 93, 94, 93, 94, 81, 99, 81, 100, 73, 100, 89, 100, 60, 100, 55, 105, 37, 101, 34, 93, 37, 90, 37, 90, 49, 99, 49, 88, 68, 80, 68, 78, 64, 88, 62, 86, 77, 76, 89, 71, 91, 71, 106, 78, 106, 82, 118, 84, 110, 71, 104, 76, 103, 76, 91, 78, 83, 85, 89, 83, 103, 83, 119, 76, 130, 62, 130, 68, 127, 74, 126, 83, 123, 62, 123, 56, 123, 59, 129, 59, 120, 49, 110, 46, 106, 56, 100, 62, 94, 62, 109, 72, 112, 67, 112, 57, 112, 61, 122, 60, 102, 52, 125, 44, 121, 36, 114, 32, 110, 20, 110, 22, 118, 35, 118, 44, 124, 32, 119, 22, 111, 44, 96, 36, 106, 36, 94, 32, 94, 35, 83, 44, 91, 52, 91, 52, 80, 59, 80, 62, 76, 62, 70, 47, 78, 55, 75, 64, 71, 64, 60, 58, 53, 58, 43, 65, 43, 65, 60, 76, 52, 73, 38, 76, 36, 93, 48, 89, 39, 99, 40, 98, 50, 94, 63, 117, 63, 131, 67, 131, 74, 142, 78, 140, 61, 124, 58, 124, 48, 136, 55, 236, 200, 228, 200, 226, 192, 232, 198, 238, 210, 248, 210, 236, 220, 230, 223, 230, 213, 175, 32, 172, 32, 171, 38, 184, 30}; - validate(coords); -}
diff --git a/src/delaunator.cpp b/src/delaunator.cpp deleted file mode 100644 index 73b9d6f..0000000 --- a/src/delaunator.cpp +++ /dev/null
@@ -1,485 +0,0 @@ - -#include "delaunator.h" -#include <algorithm> -#include <cstdio> -#include <limits> -#include <tuple> -#include <stdexcept> -#include <cmath> -// #include "prettyprint.hpp" -#include <iostream> - -using namespace std; - -namespace { - const double max_double = numeric_limits<double>::max(); - double dist( - const double &ax, - const double &ay, - const double &bx, - const double &by - ) { - const double dx = ax - bx; - const double dy = ay - by; - return dx * dx + dy * dy; - } - double circumradius( - const double &ax, - const double &ay, - const double &bx, - const double &by, - const double &cx, - const double &cy - ) { - const double dx = bx - ax; - const double dy = by - ay; - const double ex = cx - ax; - const double ey = cy - ay; - - const double bl = dx * dx + dy * dy; - const double cl = ex * ex + ey * ey; - const double d = dx * ey - dy * ex; - - const double x = (ey * bl - dy * cl) * 0.5 / d; - const double y = (dx * cl - ex * bl) * 0.5 / d; - - if (bl && cl && d) { - return x * x + y * y; - } else { - return max_double; - } - } - - double area( - const double px, - const double py, - const double qx, - const double qy, - const double rx, - const double ry - ) { - return (qy - py) * (rx - qx) - (qx - px) * (ry - qy); - } - - tuple<double, double> circumcenter( - const double &ax, - const double &ay, - const double &bx, - const double &by, - const double &cx, - const double &cy - ) { - const double dx = bx - ax; - const double dy = by - ay; - const double ex = cx - ax; - const double ey = cy - ay; - - const double bl = dx * dx + dy * dy; - const double cl = ex * ex + ey * ey; - const double d = dx * ey - dy * ex; - - const double x = ax + (ey * bl - dy * cl) * 0.5 / d; - const double y = ay + (dx * cl - ex * bl) * 0.5 / d; - - return make_tuple(x, y); - } - double compare( - const vector<double> &coords, - unsigned long int i, - unsigned long int j, - double cx, - double cy - ) { - const double d1 = dist(coords[2 * i], coords[2 * i + 1], cx, cy); - const double d2 = dist(coords[2 * j], coords[2 * j + 1], cx, cy); - const double diff1 = d1 - d2; - const double diff2 = coords[2 * i] - coords[2 * j]; - const double diff3 = coords[2 * i + 1] - coords[2 * j + 1]; - - if (diff1) { - return diff1; - } else if(diff2) { - return diff2; - } else { - return diff3; - } - } - struct sort_to_center { - double cx; - double cy; - vector<double> &coords; - bool operator() (long int i, long int j) { - return compare(coords, i, j, cx, cy) < 0; - } - }; - - bool in_circle( - double ax, double ay, - double bx, double by, - double cx, double cy, - double px, double py - ) { - const double dx = ax - px; - const double dy = ay - py; - const double ex = bx - px; - const double ey = by - py; - const double fx = cx - px; - const double fy = cy - py; - - const double ap = dx * dx + dy * dy; - const double bp = ex * ex + ey * ey; - const double cp = fx * fx + fy * fy; - - return (dx * (ey * cp - bp * fy) - - dy * (ex * cp - bp * fx) + - ap * (ex * fy - ey * fx)) < 0; - } -} - -Delaunator::Delaunator(vector<double> in_coords) { - coords = move(in_coords); - const long int n = coords.size() >> 1; - double max_x = -1 * max_double; - double max_y = -1 * max_double; - double min_x = max_double; - double min_y = max_double; - vector<long int> ids; - ids.reserve(n); - for (long int i = 0; i < n; i++) { - const double x = coords[2 * i]; - const double y = coords[2 * i + 1]; - // printf("%f %f", x, y); - - if (x < min_x) min_x = x; - if (y < min_y) min_y = y; - if (x > max_x) max_x = x; - if (y > max_y) max_y = y; - // ids[i] = i; - ids.push_back(i); - } - const double cx = (min_x + max_x) / 2; - const double cy = (min_y + max_y) / 2; - double min_dist = max_double; - unsigned long int i0; - unsigned long int i1; - unsigned long int i2; - - // pick a seed point close to the centroid - for (unsigned long int i = 0; i < n; i++) { - const double d = dist(cx, cy, coords[2 * i], coords[2 * i + 1]); - if (d < min_dist) { - i0 = i; - min_dist = d; - } - } - - min_dist = max_double; - - // find the point closest to the seed - for (unsigned long int i = 0; i < n; i++) { - if (i == i0) continue; - const double d = dist(coords[2 * i0], coords[2 * i0 + 1], coords[2 * i], coords[2 * i + 1]); - if (d < min_dist && d > 0) - { - i1 = i; - min_dist = d; - } - } - - double min_radius = max_double; - - // find the third point which forms the smallest circumcircle with the first two - for (unsigned long int i = 0; i < n; i++) - { - if (i == i0 || i == i1) continue; - - const double r = circumradius( - coords[2 * i0], coords[2 * i0 + 1], - coords[2 * i1], coords[2 * i1 + 1], - coords[2 * i], coords[2 * i + 1]); - - if (r < min_radius) - { - i2 = i; - min_radius = r; - } - } - - if (min_radius == max_double) { - throw runtime_error("not triangulation");; - } - - if ( - area( - coords[2 * i0], coords[2 * i0 + 1], - coords[2 * i1], coords[2 * i1 + 1], - coords[2 * i2], coords[2 * i2 + 1] - ) < 0 - ) { - const double tmp = i1; - i1 = i2; - i2 = tmp; - } - - const double i0x = coords[2 * i0]; - const double i0y = coords[2 * i0 + 1]; - const double i1x = coords[2 * i1]; - const double i1y = coords[2 * i1 + 1]; - const double i2x = coords[2 * i2]; - const double i2y = coords[2 * i2 + 1]; - - tie(m_center_x, m_center_y) = circumcenter(i0x, i0y, i1x, i1y, i2x, i2y); - - // sort the points by distance from the seed triangle circumcenter - // cerr << ids << endl; - const sort_to_center s = { - .cx = m_center_x, - .cy = m_center_y, - .coords = coords - }; - sort(ids.begin(), ids.end(), s); - // quicksort(ids, coords, 0, n - 1, m_center_x, m_center_y); - // cerr << ids << endl; - - m_hash_size = ceil(sqrt(n)); - m_hash.reserve(m_hash_size); - for (int i = 0; i < m_hash_size; i++) m_hash.push_back(-1); - - m_hull.reserve(coords.size()); - - long int e = insert_node(i0); - hash_edge(e); - m_hull[e].t = 0; - - e = insert_node(i1, e); - hash_edge(e); - m_hull[e].t = 1; - - e = insert_node(i2, e); - hash_edge(e); - m_hull[e].t = 2; - - const long int max_triangles = 2 * n - 5; - triangles.reserve(max_triangles * 3); - halfedges.reserve(max_triangles * 3); - add_triangle(i0, i1, i2, -1, -1, -1); - double xp = NAN; - double yp = NAN; - for (long int k = 0; k < n; k++) { - const long int i = ids[k]; - const double x = coords[2 * i]; - const double y = coords[2 * i + 1]; - if (x == xp && y == yp) continue; - xp = x; - yp = y; - if ( - (x == i0x && y == i0y) || - (x == i1x && y == i1y) || - (x == i2x && y == i2y) - ) continue; - - const long int start_key = hash_key(x, y); - long int key = start_key; - long int start = -1; - do { - start = m_hash[key]; - key = (key + 1) % m_hash_size; - } while( - (start < 0 || m_hull[start].removed) && - (key != start_key) - ); - - e = start; - - while( - area( - x, y, - m_hull[e].x, m_hull[e].y, - m_hull[m_hull[e].next].x, m_hull[m_hull[e].next].y - ) >= 0 - ) { - e = m_hull[e].next; - - if (e == start) { - throw runtime_error("Something is wrong with the input points."); - } - } - - const bool walk_back = e == start; - - // add the first triangle from the point - long int t = add_triangle( - m_hull[e].i, - i, - m_hull[m_hull[e].next].i, - -1, -1, m_hull[e].t - ); - - m_hull[e].t = t; // keep track of boundary triangles on the hull - e = insert_node(i, e); - - // recursively flip triangles from the point until they satisfy the Delaunay condition - m_hull[e].t = legalize(t + 2); - if (m_hull[m_hull[m_hull[e].prev].prev].t == halfedges[t + 1]) { - m_hull[m_hull[m_hull[e].prev].prev].t = t + 2; - } - // walk forward through the hull, adding more triangles and flipping recursively - long int q = m_hull[e].next; - while( - area( - x, y, - m_hull[q].x, m_hull[q].y, - m_hull[m_hull[q].next].x, m_hull[m_hull[q].next].y - ) < 0 - ) { - t = add_triangle( - m_hull[q].i, i, - m_hull[m_hull[q].next].i, m_hull[m_hull[q].prev].t, - -1, m_hull[q].t - ); - m_hull[m_hull[q].prev].t = legalize(t + 2); - remove_node(q); - q = m_hull[q].next; - } - if (walk_back) { - // walk backward from the other side, adding more triangles and flipping - q = m_hull[e].prev; - while( - area( - x, y, - m_hull[m_hull[q].prev].x, m_hull[m_hull[q].prev].y, - m_hull[q].x, m_hull[q].y - ) < 0 - ) { - t = add_triangle( - m_hull[m_hull[q].prev].i, i, - m_hull[q].i, -1, - m_hull[q].t, m_hull[m_hull[q].prev].t - ); - legalize(t + 2); - m_hull[m_hull[q].prev].t = t; - remove_node(q); - q = m_hull[q].prev; - } - } - hash_edge(e); - hash_edge(m_hull[e].prev); - } - -}; - -long int Delaunator::remove_node(long int node) { - m_hull[m_hull[node].prev].next = m_hull[node].next; - m_hull[m_hull[node].next].prev = m_hull[node].prev; - m_hull[node].removed = true; - return m_hull[node].prev; -} - -long int Delaunator::legalize(long int a) { - long int halfedges_size = halfedges.size(); - const long int b = halfedges[a]; - - const long int a0 = a - a % 3; - const long int b0 = b - b % 3; - - const long int al = a0 + (a + 1) % 3; - const long int ar = a0 + (a + 2) % 3; - const long int bl = b0 + (b + 2) % 3; - - const long int p0 = triangles[ar]; - const long int pr = triangles[a]; - const long int pl = triangles[al]; - const long int p1 = triangles[bl]; - - const bool illegal = in_circle( - coords[2 * p0], coords[2 * p0 + 1], - coords[2 * pr], coords[2 * pr + 1], - coords[2 * pl], coords[2 * pl + 1], - coords[2 * p1], coords[2 * p1 + 1] - ); - - if (illegal) { - triangles[a] = p1; - triangles[b] = p0; - link(a, halfedges[bl]); - link(b, halfedges[ar]); - link(ar, bl); - - const long int br = b0 + (b + 1) % 3; - - legalize(a); - return legalize(br); - } - return ar; -} - -long int Delaunator::insert_node(long int i, long int prev) { - const long int node = insert_node(i); - m_hull[node].next = m_hull[prev].next; - m_hull[node].prev = prev; - m_hull[m_hull[node].next].prev = node; - m_hull[prev].next = node; - return node; -}; - -long int Delaunator::insert_node(long int i) { - long int node = m_hull.size(); - DelaunatorPoint p = { - .i = i, - .x = coords[2 * i], - .y = coords[2 * i + 1], - .prev = node, - .next = node, - .removed = false - }; - m_hull.push_back(move(p)); - return node; -} - -long int Delaunator::hash_key(double x, double y) { - const double dx = x - m_center_x; - const double dy = y - m_center_y; - // use pseudo-angle: a measure that monotonically increases - // with real angle, but doesn't require expensive trigonometry - const double p = 1 - dx / (abs(dx) + abs(dy)); - return floor((2 + (dy < 0 ? -p : p)) / 4 * m_hash_size); -} - -void Delaunator::hash_edge(long int e){ - m_hash[hash_key(m_hull[e].x, m_hull[e].y)] = e; -} - -long int Delaunator::add_triangle( - long int i0, long int i1, long int i2, - long int a, long int b, long int c -) { - const long int t = triangles.size(); - triangles.push_back(i0); - triangles.push_back(i1); - triangles.push_back(i2); - link(t, a); - link(t + 1, b); - link(t + 2, c); - return t; -} - -void Delaunator::link(long int a, long int b) { - long int s = halfedges.size(); - if (a == s) { - halfedges.push_back(b); - } else if (a < s) { - halfedges[a] = b; - } else { - throw runtime_error("Cannot link edge"); - } - if (b != -1) { - long int s = halfedges.size(); - if (b == s) { - halfedges.push_back(a); - } else if (b < s) { - halfedges[b] = a; - } else { - throw runtime_error("Cannot link edge"); - } - } -}; \ No newline at end of file
diff --git a/src/delaunator.h b/src/delaunator.h deleted file mode 100644 index a95b871..0000000 --- a/src/delaunator.h +++ /dev/null
@@ -1,40 +0,0 @@ -#pragma once -#include <vector> -#include <exception> -#include <deque> -#include <memory> - -struct DelaunatorPoint { - long int i; - double x; - double y; - long int t; - long int prev; - long int next; - bool removed; -}; - -class Delaunator{ - public: - Delaunator(std::vector<double> in_coords); - std::vector<unsigned long int> triangles; - std::vector<long int> halfedges; - std::vector<double> coords; - private: - double m_center_x; - double m_center_y; - long int m_hash_size; - std::vector<int> m_hash; - std::vector<DelaunatorPoint> m_hull; - long int insert_node(long int i); - long int insert_node(long int i, long int prev); - long int hash_key(double x, double y); - void hash_edge(long int e); - long int add_triangle( - long int i0, long int i1, long int i2, - long int a, long int b, long int c - ); - void link(long int a, long int b); - long int legalize(long int a); - long int remove_node(long int node); -};
diff --git a/src/json-helpers.cpp b/src/json-helpers.cpp deleted file mode 100644 index 1d65259..0000000 --- a/src/json-helpers.cpp +++ /dev/null
@@ -1,56 +0,0 @@ - -#include "json-helpers.h" -#include <fstream> -#include <stdexcept> -#include "rapidjson/document.h" - -using namespace std; - -string json_helpers::read_file(const char* filename) { - ifstream input_file(filename); - if(input_file.good()) { - string json_str( - (istreambuf_iterator<char>(input_file)), - istreambuf_iterator<char>() - ); - return json_str; - } else { - printf("Error reading file %s", filename); - throw runtime_error("Error reading file"); - } -} - -vector<double> json_helpers::get_geo_json_points(const string& json) { - rapidjson::Document document; - if(document.Parse(json.c_str()).HasParseError()) { - throw runtime_error("Cannot parse JSON"); - } - const rapidjson::Value& features = document["features"]; - vector<double> coords; - // vector<double> y_vector; - for(rapidjson::SizeType i = 0; i < features.Size(); i++) { - const rapidjson::Value& coordinates = features[i]["geometry"]["coordinates"]; - const double x = coordinates[0].GetDouble(); - const double y = coordinates[1].GetDouble(); - coords.push_back(x); - coords.push_back(y); - } - return coords; -} - -vector<double> json_helpers::get_array_points(const string& json) { - vector<double> points; - rapidjson::Document document; - if(document.Parse(json.c_str()).HasParseError()) { - throw runtime_error("Cannot parse JSON"); - } - if(!document.IsArray()) { - throw runtime_error("It's not JSON Array"); - } - points.reserve(static_cast<int>(document.Size())); - for(rapidjson::SizeType i = 0; i < document.Size(); i++) { - points.push_back(document[i].GetDouble()); - } - return points; - -}
diff --git a/src/json-helpers.h b/src/json-helpers.h deleted file mode 100644 index e48f3c9..0000000 --- a/src/json-helpers.h +++ /dev/null
@@ -1,10 +0,0 @@ -#pragma once - -#include <string> -#include <vector> - -namespace json_helpers { - std::string read_file(const char* filename); - std::vector<double> get_geo_json_points(const std::string& json); - std::vector<double> get_array_points(const std::string& json); -}
diff --git a/src/triangulate.cpp b/src/triangulate.cpp deleted file mode 100644 index abe1fde..0000000 --- a/src/triangulate.cpp +++ /dev/null
@@ -1,86 +0,0 @@ -#include "rapidjson/document.h" -#include "rapidjson/prettywriter.h" -#include "delaunator.h" -#include "json-helpers.h" -#include <cstdio> -#include <fstream> -#include <vector> -#include <initializer_list> -// #include "prettyprint.hpp" -#include <iostream> -using namespace std; - -namespace { - - const string serialize_to_json(Delaunator &delaunator) { - rapidjson::StringBuffer sb; - rapidjson::PrettyWriter<rapidjson::StringBuffer> writer(sb); - writer.StartObject(); - writer.String("type"); writer.String("FeatureCollection"); - writer.String("crs"); - writer.StartObject(); - writer.String("type"); writer.String("name"); - writer.String("properties"); - writer.StartObject(); - writer.String("name"); writer.String("urn:ogc:def:crs:EPSG::900913"); - writer.EndObject(); - writer.EndObject(); - writer.String("features"); - writer.StartArray(); - for(long int i = 0; i < delaunator.triangles.size(); i+=3) { - writer.StartObject(); - writer.String("type"); writer.String("Feature"); - writer.String("properties"); writer.StartObject(); writer.EndObject(); - writer.String("geometry"); - writer.StartObject(); - writer.String("type"); writer.String("Polygon"); - writer.String("coordinates"); - writer.StartArray(); - writer.StartArray(); - writer.StartArray(); - writer.Uint(delaunator.coords[2 * delaunator.triangles[i]]); - writer.Uint(delaunator.coords[2 * delaunator.triangles[i] + 1]); - writer.EndArray(); - writer.StartArray(); - writer.Uint(delaunator.coords[2 * delaunator.triangles[i + 1]]); - writer.Uint(delaunator.coords[2 * delaunator.triangles[i + 1] + 1]); - writer.EndArray(); - writer.StartArray(); - writer.Uint(delaunator.coords[2 * delaunator.triangles[i + 2]]); - writer.Uint(delaunator.coords[2 * delaunator.triangles[i + 2] + 1]); - writer.EndArray(); - writer.StartArray(); - writer.Uint(delaunator.coords[2 * delaunator.triangles[i]]); - writer.Uint(delaunator.coords[2 * delaunator.triangles[i] + 1]); - writer.EndArray(); - writer.EndArray(); - writer.EndArray(); - writer.EndObject(); - writer.EndObject(); - } - writer.EndArray(); - writer.EndObject(); - return string(sb.GetString()); - } -} - - -int main(int, char* argv[]) { - const char* filename = argv[1]; - const char* output = argv[2]; - string json = json_helpers::read_file(filename); - const vector<double> coords = json_helpers::get_geo_json_points(json); - Delaunator delaunator(move(coords)); - const char* out_json = serialize_to_json(delaunator).c_str(); - - if (output) { - printf("Writing to file %s", output); - ofstream stream; - stream.open(output); - stream << out_json; - stream.close(); - } else { - puts(out_json); - } - return 0; -}
diff --git a/test-files/map-25p-epsg-3857.geojson b/test/test-files/map-25p-epsg-3857.geojson similarity index 100% rename from test-files/map-25p-epsg-3857.geojson rename to test/test-files/map-25p-epsg-3857.geojson
diff --git a/test-files/osm-nodes-45331-epsg-3857.geojson b/test/test-files/osm-nodes-45331-epsg-3857.geojson similarity index 100% rename from test-files/osm-nodes-45331-epsg-3857.geojson rename to test/test-files/osm-nodes-45331-epsg-3857.geojson
diff --git a/test-files/osm-nodes-45331-triangles.json b/test/test-files/osm-nodes-45331-triangles.json similarity index 100% rename from test-files/osm-nodes-45331-triangles.json rename to test/test-files/osm-nodes-45331-triangles.json
diff --git a/test-files/playgrounds-1356-epsg-3857.geojson b/test/test-files/playgrounds-1356-epsg-3857.geojson similarity index 100% rename from test-files/playgrounds-1356-epsg-3857.geojson rename to test/test-files/playgrounds-1356-epsg-3857.geojson
diff --git a/test-files/playgrounds-1356-triangles.json b/test/test-files/playgrounds-1356-triangles.json similarity index 100% rename from test-files/playgrounds-1356-triangles.json rename to test/test-files/playgrounds-1356-triangles.json
diff --git a/test/test_json_validate.cpp b/test/test_json_validate.cpp new file mode 100644 index 0000000..740088e --- /dev/null +++ b/test/test_json_validate.cpp
@@ -0,0 +1,34 @@ +#include <delaunator.hpp> +#include <catch.hpp> +#include "test_utils.hpp" + +TEST_CASE("triangles match JS version ouput", "[Delaunator]") { + std::string points_str = test_utils::read_file("./test/test-files/playgrounds-1356-epsg-3857.geojson"); + std::string triangles_str = test_utils::read_file("./test/test-files/playgrounds-1356-triangles.json"); + std::vector<double> coords = test_utils::get_geo_json_points(points_str); + std::vector<double> triangles = test_utils::get_array_points(triangles_str); + delaunator::Delaunator delaunator(coords); + + SECTION("length of triangles is the same") { + REQUIRE(delaunator.triangles.size() == triangles.size()); + } + + SECTION("values are the same") { + for(size_t i = 0; i < triangles.size(); i++) + { + REQUIRE(delaunator.triangles[i] == Approx(triangles[i])); + } + } +} + +TEST_CASE("produces correct triangulation", "[Delaunator]") { + std::vector<double> coords = {168, 180, 168, 178, 168, 179, 168, 181, 168, 183, 167, 183, 167, 184, 165, 184, 162, 186, 164, 188, 161, 188, 160, 191, 158, 193, 156, 193, 152, 195, 152, 198, 150, 198, 147, 198, 148, 205, 150, 210, 148, 210, 148, 208, 145, 206, 142, 206, 140, 206, 138, 206, 135, 206, 135, 209, 131, 209, 131, 211, 127, 211, 124, 210, 120, 207, 120, 204, 120, 202, 124, 201, 123, 201, 125, 198, 125, 194, 127, 194, 127, 191, 130, 191, 132, 189, 134, 189, 134, 186, 136, 184, 134, 182, 134, 179, 134, 176, 136, 174, 139, 174, 141, 177, 142, 176, 144, 176, 147, 178, 148, 176, 151, 178, 154, 178, 153, 175, 152, 174, 152, 170, 152, 168, 150, 166, 148, 166, 147, 165, 145, 162, 146, 160, 146, 157, 146, 155, 144, 155, 142, 152, 140, 150, 138, 150, 138, 148, 140, 145, 140, 142, 140, 138, 139, 138, 137, 138, 135, 138, 133, 135, 132, 132, 129, 132, 128, 132, 124, 132, 124, 130, 123, 130, 118, 126, 116, 124, 112, 122, 109, 122, 105, 122, 102, 124, 100, 124, 97, 124, 95, 126, 92, 127, 89, 127, 88, 130, 85, 132, 80, 134, 72, 134, 69, 134, 65, 138, 64, 138, 58, 137, 56, 133, 52, 133, 51, 133, 48, 133, 44, 133, 41, 131, 38, 130, 35, 130, 32, 127, 30, 127, 27, 127, 24, 127, 24, 126, 23, 124, 20, 122, 17, 122, 16, 118, 15, 116, 15, 110, 18, 108, 20, 102, 24, 97, 28, 102, 28, 98, 26, 97, 28, 94, 27, 85, 29, 79, 32, 76, 39, 70, 44, 66, 48, 65, 53, 61, 53, 58, 51, 54, 54, 54, 52, 48, 51, 43, 48, 42, 49, 38, 48, 34, 51, 30, 53, 33, 58, 30, 61, 30, 60, 27, 64, 26, 68, 24, 74, 24, 80, 24, 85, 26, 92, 26, 96, 29, 103, 32, 109, 33, 112, 37, 116, 37, 120, 37, 124, 35, 126, 35, 128, 38, 132, 38, 134, 41, 138, 38, 140, 36, 142, 40, 144, 43, 145, 41, 149, 41, 155, 41, 159, 41, 161, 46, 165, 46, 164, 42, 164, 39, 164, 34, 167, 30, 173, 24, 178, 24, 184, 24, 189, 26, 195, 21, 195, 20, 199, 20, 203, 20, 207, 17, 211, 17, 216, 17, 218, 16, 222, 22, 225, 27, 228, 31, 226, 34, 224, 34, 226, 39, 228, 43, 230, 46, 236, 46, 242, 46, 243, 50, 245, 50, 247, 54, 247, 56, 248, 60, 248, 65, 253, 66, 255, 64, 260, 64, 264, 67, 268, 71, 272, 66, 275, 66, 281, 61, 285, 66, 286, 70, 292, 74, 294, 74, 296, 74, 296, 71, 301, 74, 307, 74, 311, 78, 315, 74, 315, 77, 319, 77, 322, 82, 328, 82, 331, 81, 331, 84, 333, 86, 333, 90, 330, 95, 326, 98, 328, 99, 332, 98, 333, 101, 331, 104, 329, 104, 327, 106, 329, 111, 332, 116, 333, 119, 333, 122, 332, 126, 332, 130, 327, 130, 321, 130, 317, 130, 315, 134, 312, 134, 308, 138, 306, 138, 306, 144, 306, 149, 306, 152, 301, 152, 297, 154, 295, 154, 292, 154, 292, 158, 288, 158, 283, 162, 281, 164, 279, 163, 276, 163, 273, 166, 272, 169, 268, 168, 265, 170, 260, 172, 256, 176, 252, 176, 248, 181, 246, 182, 246, 189, 246, 194, 248, 197, 250, 198, 252, 200, 252, 203, 254, 205, 260, 205, 264, 202, 267, 202, 269, 202, 272, 199, 280, 199, 278, 202, 278, 207, 278, 211, 276, 211, 272, 213, 268, 213, 265, 213, 264, 211, 262, 210, 260, 210, 257, 212, 257, 214, 255, 217, 253, 217, 253, 221, 249, 220, 247, 220, 243, 222, 240, 223, 239, 226, 234, 231, 229, 231, 224, 231, 219, 227, 220, 227, 222, 224, 222, 222, 222, 219, 224, 217, 222, 214, 220, 212, 217, 210, 215, 210, 211, 209, 208, 206, 202, 209, 202, 205, 206, 202, 211, 198, 216, 195, 220, 192, 224, 192, 221, 186, 218, 186, 214, 185, 208, 185, 204, 186, 200, 186, 193, 183, 190, 182, 188, 182, 190, 178, 186, 178, 184, 174, 182, 171, 178, 171, 173, 174, 169, 174, 169, 175, 169, 179, 167, 182, 164, 186, 160, 192, 155, 195, 152, 198, 150, 198, 148, 198, 148, 202, 151, 208, 148, 210, 146, 208, 144, 205, 140, 205, 137, 208, 132, 208, 132, 210, 127, 210, 124, 210, 120, 206, 120, 202, 123, 202, 124, 201, 124, 198, 128, 195, 131, 191, 133, 187, 135, 183, 130, 203, 129, 208, 123, 203, 129, 203, 129, 198, 133, 198, 136, 200, 142, 200, 143, 199, 143, 197, 137, 196, 136, 194, 133, 194, 136, 186, 136, 182, 141, 186, 144, 186, 150, 186, 150, 190, 155, 190, 159, 188, 156, 182, 151, 182, 144, 182, 164, 176, 161, 177, 157, 177, 166, 176, 168, 165, 175, 167, 180, 167, 188, 159, 195, 164, 195, 162, 187, 162, 178, 163, 173, 166, 168, 170, 156, 170, 157, 165, 164, 165, 164, 161, 170, 159, 167, 158, 159, 154, 149, 151, 145, 145, 145, 138, 152, 138, 152, 146, 159, 146, 165, 153, 176, 153, 180, 153, 187, 153, 194, 153, 202, 153, 202, 158, 197, 158, 193, 158, 193, 142, 180, 142, 171, 142, 163, 135, 176, 135, 186, 139, 201, 139, 206, 139, 205, 147, 205, 160, 198, 160, 206, 174, 205, 178, 196, 178, 196, 182, 202, 182, 206, 181, 209, 181, 215, 181, 222, 181, 230, 177, 238, 175, 241, 175, 237, 175, 237, 168, 237, 161, 232, 156, 231, 162, 225, 166, 217, 169, 210, 173, 224, 173, 227, 173, 235, 175, 237, 178, 228, 192, 222, 199, 216, 199, 211, 204, 205, 206, 219, 207, 222, 211, 229, 214, 236, 214, 244, 211, 247, 211, 268, 206, 277, 201, 279, 201, 281, 202, 278, 202, 242, 178, 236, 170, 236, 162, 255, 162, 251, 156, 240, 156, 253, 152, 261, 152, 277, 157, 268, 151, 255, 143, 260, 142, 267, 145, 271, 149, 273, 154, 258, 146, 257, 131, 256, 134, 248, 137, 260, 137, 260, 134, 271, 137, 276, 138, 276, 144, 289, 144, 285, 150, 294, 150, 298, 149, 301, 145, 292, 145, 282, 134, 276, 134, 283, 127, 282, 116, 277, 113, 283, 113, 288, 106, 296, 106, 297, 113, 297, 118, 298, 118, 310, 122, 310, 128, 300, 130, 300, 140, 292, 129, 292, 114, 283, 122, 289, 122, 299, 122, 299, 134, 294, 134, 288, 124, 314, 121, 311, 113, 308, 110, 304, 96, 299, 90, 299, 82, 305, 87, 309, 94, 311, 101, 312, 102, 314, 107, 320, 112, 320, 115, 326, 116, 323, 109, 321, 102, 321, 94, 321, 90, 328, 90, 328, 88, 316, 88, 316, 84, 307, 84, 290, 77, 289, 88, 289, 97, 278, 97, 268, 106, 268, 110, 261, 105, 255, 103, 244, 103, 252, 100, 252, 91, 252, 82, 242, 78, 252, 78, 259, 78, 264, 87, 267, 92, 272, 91, 272, 83, 264, 83, 260, 79, 276, 79, 283, 84, 283, 94, 289, 94, 284, 86, 272, 77, 253, 110, 248, 110, 239, 110, 234, 114, 222, 125, 219, 127, 219, 131, 219, 138, 219, 141, 224, 139, 224, 135, 225, 130, 232, 136, 240, 138, 237, 131, 237, 118, 248, 120, 256, 122, 262, 127, 255, 118, 245, 110, 207, 129, 199, 134, 195, 134, 188, 130, 180, 130, 165, 129, 156, 129, 165, 128, 173, 125, 185, 126, 193, 126, 201, 124, 204, 123, 208, 116, 214, 114, 207, 114, 196, 114, 183, 121, 183, 111, 189, 117, 196, 112, 172, 126, 164, 126, 159, 114, 174, 106, 186, 106, 192, 105, 184, 105, 184, 96, 173, 96, 163, 111, 159, 110, 152, 110, 168, 110, 171, 106, 183, 98, 193, 101, 219, 96, 225, 97, 225, 104, 232, 92, 240, 92, 237, 86, 229, 86, 216, 88, 214, 79, 203, 79, 203, 75, 212, 75, 221, 75, 229, 80, 230, 89, 217, 88, 217, 77, 228, 77, 228, 69, 235, 71, 240, 71, 244, 66, 236, 54, 236, 62, 232, 68, 229, 61, 216, 61, 212, 58, 212, 47, 212, 39, 214, 28, 215, 48, 225, 55, 236, 55, 202, 65, 202, 54, 202, 44, 202, 24, 198, 32, 199, 38, 192, 38, 185, 38, 174, 42, 174, 48, 178, 51, 184, 51, 194, 55, 191, 68, 182, 68, 174, 69, 167, 67, 153, 59, 153, 49, 147, 49, 152, 58, 152, 74, 154, 83, 161, 83, 165, 88, 153, 97, 153, 89, 152, 82, 168, 88, 168, 101, 156, 102, 156, 119, 173, 110, 184, 110, 177, 106, 160, 106, 145, 125, 137, 122, 131, 120, 124, 120, 122, 118, 113, 118, 114, 111, 129, 111, 140, 110, 143, 106, 137, 102, 127, 102, 119, 98, 126, 93, 139, 93, 139, 99, 141, 95, 128, 89, 118, 74, 128, 76, 135, 76, 141, 83, 141, 71, 137, 61, 137, 50, 129, 50, 118, 50, 109, 52, 112, 61, 123, 60, 134, 60, 129, 76, 121, 67, 124, 76, 123, 76, 111, 74, 128, 73, 109, 83, 109, 94, 105, 103, 102, 118, 92, 113, 98, 105, 99, 93, 94, 93, 94, 81, 99, 81, 100, 73, 100, 89, 100, 60, 100, 55, 105, 37, 101, 34, 93, 37, 90, 37, 90, 49, 99, 49, 88, 68, 80, 68, 78, 64, 88, 62, 86, 77, 76, 89, 71, 91, 71, 106, 78, 106, 82, 118, 84, 110, 71, 104, 76, 103, 76, 91, 78, 83, 85, 89, 83, 103, 83, 119, 76, 130, 62, 130, 68, 127, 74, 126, 83, 123, 62, 123, 56, 123, 59, 129, 59, 120, 49, 110, 46, 106, 56, 100, 62, 94, 62, 109, 72, 112, 67, 112, 57, 112, 61, 122, 60, 102, 52, 125, 44, 121, 36, 114, 32, 110, 20, 110, 22, 118, 35, 118, 44, 124, 32, 119, 22, 111, 44, 96, 36, 106, 36, 94, 32, 94, 35, 83, 44, 91, 52, 91, 52, 80, 59, 80, 62, 76, 62, 70, 47, 78, 55, 75, 64, 71, 64, 60, 58, 53, 58, 43, 65, 43, 65, 60, 76, 52, 73, 38, 76, 36, 93, 48, 89, 39, 99, 40, 98, 50, 94, 63, 117, 63, 131, 67, 131, 74, 142, 78, 140, 61, 124, 58, 124, 48, 136, 55, 236, 200, 228, 200, 226, 192, 232, 198, 238, 210, 248, 210, 236, 220, 230, 223, 230, 213, 175, 32, 172, 32, 171, 38, 184, 30}; + delaunator::Delaunator d(coords); + + SECTION("validate halfedges") { + for(size_t i = 0; i < d.halfedges.size(); i++) { + const auto i2 = d.halfedges[i]; + REQUIRE(static_cast<bool>((i2 == delaunator::INVALID_INDEX) || (d.halfedges[i2] == i))); + } + } +}
diff --git a/test/test_main.cpp b/test/test_main.cpp new file mode 100644 index 0000000..b3143fb --- /dev/null +++ b/test/test_main.cpp
@@ -0,0 +1,2 @@ +#define CATCH_CONFIG_MAIN +#include <catch.hpp>
diff --git a/test/test_utils.hpp b/test/test_utils.hpp new file mode 100644 index 0000000..2ad7e82 --- /dev/null +++ b/test/test_utils.hpp
@@ -0,0 +1,56 @@ +#include <fstream> +#include <stdexcept> +#include "rapidjson/document.h" + +namespace test_utils { + +std::string read_file(const char* filename) { + std::ifstream input_file(filename); + if(input_file.good()) { + std::string json_str( + (std::istreambuf_iterator<char>(input_file)), + std::istreambuf_iterator<char>() + ); + return json_str; + } else { + printf("Error reading file %s", filename); + throw std::runtime_error("Error reading file"); + } +} + +std::vector<double> get_geo_json_points(std::string const& json) { + rapidjson::Document document; + if(document.Parse(json.c_str()).HasParseError()) { + throw std::runtime_error("Cannot parse JSON"); + } + const rapidjson::Value& features = document["features"]; + std::vector<double> coords; + // vector<double> y_vector; + for(rapidjson::SizeType i = 0; i < features.Size(); i++) { + const rapidjson::Value& coordinates = features[i]["geometry"]["coordinates"]; + const double x = coordinates[0].GetDouble(); + const double y = coordinates[1].GetDouble(); + coords.push_back(x); + coords.push_back(y); + } + return coords; +} + +std::vector<double> get_array_points(std::string const& json) { + std::vector<double> points; + rapidjson::Document document; + if(document.Parse(json.c_str()).HasParseError()) { + throw std::runtime_error("Cannot parse JSON"); + } + if(!document.IsArray()) { + throw std::runtime_error("It's not JSON Array"); + } + points.reserve(static_cast<std::size_t>(document.Size())); + for(rapidjson::SizeType i = 0; i < document.Size(); i++) { + points.push_back(document[i].GetDouble()); + } + return points; + +} + +} // end ns test_utils