Merge pull request #6 from delfrrr/layout-updates
Use mapbox hpp skel
diff --git a/.clang-format b/.clang-format
new file mode 100644
index 0000000..cb9f91c
--- /dev/null
+++ b/.clang-format
@@ -0,0 +1,19 @@
+Standard: Cpp11
+IndentWidth: 4
+AccessModifierOffset: -4
+UseTab: Never
+BinPackParameters: false
+BinPackArguments: false
+AllowShortIfStatementsOnASingleLine: true
+AllowShortLoopsOnASingleLine: false
+AllowShortBlocksOnASingleLine: true
+AllowShortFunctionsOnASingleLine: false
+AllowAllParametersOfDeclarationOnNextLine: true
+ConstructorInitializerAllOnOneLineOrOnePerLine: true
+AlwaysBreakTemplateDeclarations: true
+NamespaceIndentation: None
+PointerBindsToType: true
+SpacesInParentheses: false
+BreakBeforeBraces: Attach
+ColumnLimit: 0
+Cpp11BracedListStyle: false
diff --git a/.gitignore b/.gitignore
index ff5aa79..7dde577 100644
--- a/.gitignore
+++ b/.gitignore
@@ -2,14 +2,16 @@
CMakeFiles
CMakeScripts
Testing
-Makefile
cmake_install.cmake
install_manifest.txt
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
+.toolchain
+.mason
+local.env
\ No newline at end of file
diff --git a/.travis.yml b/.travis.yml
index 76aa4d1..e1a5b82 100644
--- a/.travis.yml
+++ b/.travis.yml
@@ -1,8 +1,56 @@
-language: cpp
-dist: trusty
-compiler: clang++
-os: linux
+language: generic
+
+matrix:
+ include:
+ # clang-format specific job
+ - os: linux
+ sudo: false
+ env: CLANG_FORMAT
+ addons:
+ apt:
+ sources: [ 'ubuntu-toolchain-r-test' ]
+ packages: [ 'libstdc++6', 'libstdc++-5-dev' ]
+ script:
+ - make format
+ - 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' ]
+ # disabled before fixing https://github.com/delfrrr/delaunator-cpp/issues/5
+ # - 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' ]
+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..72a83c2 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -1,38 +1,63 @@
-cmake_minimum_required(VERSION 3.0.0)
-project(delaunator VERSION 0.1.0)
+cmake_minimum_required(VERSION 3.8)
+project(delaunator VERSION 0.2.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})
+
+#examples
+add_executable(triangulate-geojson examples/triangulate_geojson.cpp)
+add_executable(basic examples/basic.cpp)
-#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/Makefile b/Makefile
new file mode 100644
index 0000000..5abaceb
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,43 @@
+
+# Whether to turn compiler warnings into errors
+export WERROR ?= true
+export BUILD_DIR ?= cmake-build
+
+default: release
+
+release:
+ mkdir -p ./$(BUILD_DIR) && cd ./$(BUILD_DIR) && cmake ../ -DCMAKE_BUILD_TYPE=Release -DWERROR=$(WERROR) && VERBOSE=1 cmake --build .
+
+debug:
+ mkdir -p ./$(BUILD_DIR) && cd ./$(BUILD_DIR) && cmake ../ -DCMAKE_BUILD_TYPE=Debug -DWERROR=$(WERROR) && VERBOSE=1 cmake --build .
+
+test:
+ @if [ -f ./$(BUILD_DIR)/unit-tests ]; then ./$(BUILD_DIR)/unit-tests; else echo "Please run 'make release' or 'make debug' first" && exit 1; fi
+
+bench:
+ @if [ -f ./$(BUILD_DIR)/bench-tests ]; then ./$(BUILD_DIR)/bench-tests; else echo "Please run 'make release' or 'make debug' first" && exit 1; fi
+
+tidy:
+ @echo "not implmented"
+
+coverage:
+ @echo "not implmented"
+
+clean:
+ rm -rf ./$(BUILD_DIR)
+ # remove remains from running 'make coverage'
+ rm -f *.profraw
+ rm -f *.profdata
+ @echo "run 'make distclean' to also clear mason_packages, .mason, and .toolchain directories"
+
+distclean: clean
+ rm -rf mason_packages
+ # remove remains from running './scripts/setup.sh'
+ rm -rf .mason
+ rm -rf .toolchain
+ rm -f local.env
+
+format:
+ ./scripts/format.sh
+
+.PHONY: test bench
\ No newline at end of file
diff --git a/README.md b/README.md
index c552418..d45a370 100644
--- a/README.md
+++ b/README.md
@@ -6,45 +6,41 @@
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
* Probably the fastest C++ open source 2D Delaunay implementation
-* Roughly 3 times faster then JS version.
+* Roughly 6 times faster then JS version (more improvements are coming).
* Example showing triangulation of GeoJson points
## Usage
+`examples/basic.cpp`
+
```CPP
-#include "delaunator.h"
-#include <cstdio>
-using namespace std;
-//...
-int main(int, char* argv[]) {
- //...
- const vector<double> coords = {/* x0, y0, x1, y1, ... */};
+#include <delaunator.hpp>
+#include <cstdio>
+
+int main() {
+ /* x0, y0, x1, y1, ... */
+ std::vector<double> coords = {-1, 1, 1, 1, 1, -1, -1, -1};
//triangulation happens here
- //note moving points to constructor
- Delaunator delaunator(move(coords));
+ delaunator::Delaunator d(coords);
- for(long int i = 0; i < delaunator.triangles.size(); i+=3) {
+ for(std::size_t i = 0; i < d.triangles.size(); i+=3) {
printf(
"Triangle points: [[%f, %f], [%f, %f], [%f, %f]]\n",
- delaunator.coords[2 * delaunator.triangles[i]], //tx0
- delaunator.coords[2 * delaunator.triangles[i] + 1], //ty0
- delaunator.coords[2 * delaunator.triangles[i + 1]], //tx1
- delaunator.coords[2 * delaunator.triangles[i + 1] + 1], //ty1
- delaunator.coords[2 * delaunator.triangles[i + 2]], //tx2
- delaunator.coords[2 * delaunator.triangles[i + 2] + 1], //ty2
- )
+ d.coords[2 * d.triangles[i]], //tx0
+ d.coords[2 * d.triangles[i] + 1], //ty0
+ d.coords[2 * d.triangles[i + 1]], //tx1
+ d.coords[2 * d.triangles[i + 1] + 1],//ty1
+ d.coords[2 * d.triangles[i + 2]], //tx2
+ d.coords[2 * d.triangles[i + 2] + 1] //ty2
+ );
}
}
```
-For full example see `src/triangulate.cpp`
-
-## TODO
-
-* Benchmarks
-* Unit tests
+[See more examples here](./examples)
diff --git a/bench/run.cpp b/bench/run.cpp
new file mode 100644
index 0000000..06ee8f1
--- /dev/null
+++ b/bench/run.cpp
@@ -0,0 +1,19 @@
+#include "../examples/utils.hpp"
+#include <benchmark/benchmark.h>
+#include <delaunator.hpp>
+#include <string>
+
+namespace {
+void BM_45K_geojson_nodes(benchmark::State& state) {
+ std::string points_str = utils::read_file("./test/test-files/osm-nodes-45331-epsg-3857.geojson");
+ std::vector<double> coords = utils::get_geo_json_points(points_str);
+
+ while (state.KeepRunning()) {
+ delaunator::Delaunator delaunator(coords);
+ }
+}
+} // namespace
+
+BENCHMARK(BM_45K_geojson_nodes)->Unit(benchmark::kMillisecond);
+
+BENCHMARK_MAIN()
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/basic.cpp b/examples/basic.cpp
new file mode 100644
index 0000000..276ceb2
--- /dev/null
+++ b/examples/basic.cpp
@@ -0,0 +1,22 @@
+#include <delaunator.hpp>
+#include <cstdio>
+
+int main() {
+ /* x0, y0, x1, y1, ... */
+ std::vector<double> coords = {-1, 1, 1, 1, 1, -1, -1, -1};
+
+ //triangulation happens here
+ delaunator::Delaunator d(coords);
+
+ for(std::size_t i = 0; i < d.triangles.size(); i+=3) {
+ printf(
+ "Triangle points: [[%f, %f], [%f, %f], [%f, %f]]\n",
+ d.coords[2 * d.triangles[i]], //tx0
+ d.coords[2 * d.triangles[i] + 1], //ty0
+ d.coords[2 * d.triangles[i + 1]], //tx1
+ d.coords[2 * d.triangles[i + 1] + 1],//ty1
+ d.coords[2 * d.triangles[i + 2]], //tx2
+ d.coords[2 * d.triangles[i + 2] + 1] //ty2
+ );
+ }
+}
diff --git a/examples/triangulate_geojson.cpp b/examples/triangulate_geojson.cpp
new file mode 100644
index 0000000..4c24850
--- /dev/null
+++ b/examples/triangulate_geojson.cpp
@@ -0,0 +1,80 @@
+#include "rapidjson/document.h"
+#include "rapidjson/prettywriter.h"
+#include <delaunator.hpp>
+#include "./utils.hpp"
+#include <cstdio>
+#include <fstream>
+#include <vector>
+#include <initializer_list>
+#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 = utils::read_file(filename);
+ std::vector<double> coords = 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/examples/utils.hpp b/examples/utils.hpp
new file mode 100644
index 0000000..fd8c622
--- /dev/null
+++ b/examples/utils.hpp
@@ -0,0 +1,60 @@
+#pragma once
+
+#include <fstream>
+#include <stdexcept>
+#include <string>
+#include <vector>
+#include "rapidjson/document.h"
+
+namespace 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 utils
diff --git a/fetch-includes.sh b/fetch-includes.sh
deleted file mode 100755
index 46f7adc..0000000
--- a/fetch-includes.sh
+++ /dev/null
@@ -1,8 +0,0 @@
-#!/usr/bin/env bash
-
-mkdir -p ./includes
-rm -rf ./includes/*
-
-git clone --branch v1.1.0 --depth=1 https://github.com/Tencent/rapidjson.git ./includes/rapidjson
-git clone --branch master --depth=1 https://github.com/louisdx/cxx-prettyprint.git ./includes/prettyprint
-git clone --branch master --depth=1 https://github.com/catchorg/Catch2.git ./includes/catch
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/generate-reference-triangles/index.js b/generate-reference-triangles/index.js
index 11724f9..9356209 100755
--- a/generate-reference-triangles/index.js
+++ b/generate-reference-triangles/index.js
@@ -26,6 +26,9 @@
console.log('miliseconds =', end - start);
console.log('triangles =', delaunator.triangles.length);
-const trianglesAr = Array.from(delaunator.triangles);
-writeFileSync(outputFile, JSON.stringify(trianglesAr));
+if (outputFile) {
+ console.log('Saving to', outputFile)
+ const trianglesAr = Array.from(delaunator.triangles);
+ writeFileSync(outputFile, JSON.stringify(trianglesAr));
+}
diff --git a/include/delaunator.hpp b/include/delaunator.hpp
new file mode 100644
index 0000000..0a38442
--- /dev/null
+++ b/include/delaunator.hpp
@@ -0,0 +1,513 @@
+#pragma once
+
+#include <algorithm>
+#include <cmath>
+#include <exception>
+#include <iostream>
+#include <limits>
+#include <memory>
+#include <utility>
+#include <vector>
+
+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;
+};
+
+class Delaunator {
+
+public:
+ std::vector<double> const& coords;
+ std::vector<std::size_t> triangles;
+ std::vector<std::size_t> halfedges;
+
+ Delaunator(std::vector<double> const& in_coords);
+
+private:
+ 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;
+
+ std::size_t remove_node(std::size_t node);
+ std::size_t legalize(std::size_t a);
+ std::size_t insert_node(std::size_t i);
+ std::size_t insert_node(std::size_t i, std::size_t prev);
+ std::size_t hash_key(double x, double y);
+ void hash_edge(std::size_t 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);
+ void link(std::size_t a, std::size_t b);
+};
+
+Delaunator::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 = INVALID_INDEX;
+ std::size_t i1 = INVALID_INDEX;
+ std::size_t i2 = INVALID_INDEX;
+
+ // 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 Delaunator::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 Delaunator::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 Delaunator::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 Delaunator::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 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.0 - dx / (std::abs(dx) + std::abs(dy));
+ return static_cast<std::size_t>(std::llround(std::floor(
+ (2.0 + (dy < 0.0 ? -p : p)) / 4.0 * static_cast<double>(m_hash_size) //TODO:is this conversion save?
+ )));
+}
+
+void Delaunator::hash_edge(std::size_t e) {
+ m_hash[hash_key(m_hull[e].x, m_hull[e].y)] = e;
+}
+
+std::size_t Delaunator::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 Delaunator::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");
+ }
+ }
+}
+
+} //namespace delaunator
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/delaunator.test.cpp b/test/delaunator.test.cpp
new file mode 100644
index 0000000..4138bbd
--- /dev/null
+++ b/test/delaunator.test.cpp
@@ -0,0 +1,42 @@
+#include "../examples/utils.hpp"
+#include <catch.hpp>
+#include <delaunator.hpp>
+
+namespace {
+void validate(const std::vector<double>& coords) {
+ delaunator::Delaunator d(coords);
+
+ SECTION("validate halfedges") {
+ for (std::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)));
+ }
+ }
+}
+} // namespace
+
+TEST_CASE("triangles match JS version ouput", "[Delaunator]") {
+ std::string points_str = utils::read_file("./test/test-files/playgrounds-1356-epsg-3857.geojson");
+ std::string triangles_str = utils::read_file("./test/test-files/playgrounds-1356-triangles.json");
+ std::vector<double> coords = utils::get_geo_json_points(points_str);
+ std::vector<double> triangles = 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 (std::size_t i = 0; i < triangles.size(); i++) {
+ REQUIRE(delaunator.triangles[i] == Approx(triangles[i]));
+ }
+ }
+}
+
+TEST_CASE("produces correct triangulation", "[Delaunator]") {
+ // clang-format off
+ 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};
+ // clang-format on
+ validate(coords);
+}
diff --git a/test/main.test.cpp b/test/main.test.cpp
new file mode 100644
index 0000000..b3143fb
--- /dev/null
+++ b/test/main.test.cpp
@@ -0,0 +1,2 @@
+#define CATCH_CONFIG_MAIN
+#include <catch.hpp>
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
