aewallin / openvoronoi Goto Github PK

2D voronoi diagram for point and line-segment sites using incremental topology-oriented algorithm. C++ with python bindings. Licensed under LGPL2.1.

Home Page: http://www.anderswallin.net/cam/

License: GNU Lesser General Public License v2.1

C++ 46.81% Python 47.48% Shell 0.07% CMake 5.64%

openvoronoi's Introduction

OpenVoronoi

Updates: 2018-07 (change to LGLP), 2015-02-12.

The OpenVoronoi project aims to produce an algorithm for calculating the 2D voronoi-diagram for point, line-segment, and circular-arc sites. Currently point-sites and line-segment sites work. Arc-sites are being worked on. The incremental topology-oriented (Sugihara-Iri and/or Held) algorithm is used (see References).

The core algorithm is in C++ with python bindings using Boost Python. There are many python examples that use VTK for visualization. As of 2018 VTK 6 is used for visualizations. Some tests use a random polygon generator (https://github.com/aewallin/randompolygon) and a font-geometry generator based on FreeType (https://github.com/aewallin/truetype-tracer)

OpenVoronoi is written by Anders Wallin (anders.e.e.wallin "at" gmail.com) and initially released under GPLv3. In July 2018, license was changed to LGPL2.1 (see COPYING) with permission and cooperation of all contributors (Issue #35).

In February 2015 Rogach published a Java port called jopenvoronoi (https://github.com/Rogach/jopenvoronoi)

Voronoi diagrams are used for many purposes in computational geometry, but the motivation for OpenVoronoi has mainly been 2D offset-generation (see offset.hpp) for cnc mill toolpath calcuations. An experimental approximate medial-axis filter (medial_axis.hpp) has been added.

The OpenVoronoi project is at https://github.com/aewallin/openvoronoi

Launchpad PPA (not updated regularly) https://launchpad.net/~anders-e-e-wallin/+archive/cam

Build, Test, and Code-coverage dashboard: http://my.cdash.org/index.php?project=OpenVoronoi (not updated regularly! ToDo: set up continuous build/test server + website)

The mailing-list for OpenVoronoi is at https://groups.google.com/forum/?hl=en#!forum/opencamlib

There is a gallery of voronoi diagrams produced with OpenVoronoi at https://picasaweb.google.com/106188605401091280402/OpenVoronoiExamples

Required Dependencies:

cmake
libqd-dev http://crd.lbl.gov/~dhbailey/mpdist/
Boost graph library
graphviz (visualization for graph algorithms)

Optional Dependencies:

git (required only for the version-string)
python (if python bindings are built/used)
Boost python (if python bindings are built)
doxygen (for building documentation)
asymptote (to build white-paper figures)
lyx (to build white-paper)
libvtk (many python-scripts use VTK for visualization)
python-vtk (VTK python bindings)
truetype-tracer https://github.com/aewallin/truetype-tracer (some tests)
randompolygon https://github.com/aewallin/randompolygon (some tests)

Build/Install instructions

From PPA:

sudo add-apt-repository ppa:anders-e-e-wallin/cam
sudo apt-get update
sudo apt-get install openvoronoi

From source:

$ git clone git://github.com/aewallin/openvoronoi.git
$ cd openvoronoi
$ mkdir bld
$ cd bld
$ cmake ../src
$ make
$ sudo make install

Documentation

Doxygen documentation can be built with "make doc" A white-paper on the algorithm and solvers in LyX format is located in /doc. It has its own CMakeLists.txt file which builds a PDF file.

Tests

Both c++ and python tests are found in src/test/. These are run with CTest. In the build-directory either "make test" or "ctest" will run all tests. You can run only tests that have e.g. "ttt" in the test-name with "ctest -R ttt" Currently the tests do not produce any output (png or svg output could be an option?)

Organization

doc/ has documentation in lyx format, with figures in asymptote format.

Build a PDF with the CMakeLists.txt in this directory.
cpp_examples/ has c++ examples (more needed)
python_examples/ has Python examples. Many use VTK and VTK's python bindingd for visualization.
src/ has the source for the main algorithm
src/solvers has vd-vertex solver code
src/py has python wrapping code
src/common has common classes not specific to voronoi diagrams
src/utility input and output from OpenVoronoi to/from various formats

Contributing

See the TODO file. Fork the github repo, create a feature branch, commit yor changes, test. Make a short description of your changes and create a pull request. Follow the coding-style of the existing code. One fix/feature per pull request. Contributed code must comply with the LGPL. Provide short doxygen-formatted documentation in the code.

Other voronoi-diagram codes

CGAL, http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Voronoi_diagram_2/Chapter_main.html
LEDA, http://www.algorithmic-solutions.info/leda_guide/geo_algs/voronoi.html
Boost.Polygon.Voronoi, http://www.boost.org/doc/libs/1_52_0/libs/polygon/doc/voronoi_main.htm
VRONI/Martin Held. This code is commercial and not available, as far as we know. http://www.cosy.sbg.ac.at/~held/projects/vroni/vroni.html
Voro++, BSD-licensed code for 3D voronoi cell computation. May not be useful for 2D toolpath generation? http://math.lbl.gov/voro++/
Triangle http://www.cs.cmu.edu/~quake/triangle.html Really a mesh-generator for e.g. finite-element analysis. A constrained Delaunay triangulation could be used to generate a Voronoi diagram for point and line inputs.

Boost.Polygon.Voronoi was a Google Summer of Code project in 2010. Integer input coordinates. Exact geometric predicates through geometric filtering. Uses Fortune's sweepline algorithm. Boostcon video: "Sweep-Line Algorithm for Voronoi Diagrams of Points, Line Segments and Medial Axis of Polygons in the Plane" http://blip.tv/boostcon/sweep-line-algorithm-for-voronoi-diagrams-of-points-line-segments-and-medial-axis-of-polygons-in-the-plane-5368229

Patel (see References) seems to have independently implemented the VRONI/Held algorithm, bu we don't know where this code is or under what license it is.

References

Sugihara and Iri, (1992) "construction of the voronoi diagram for one million generators in single-precision arithmetic" http://dx.doi.org/10.1109/5.163412

Imai (1996) "A Topology-Oriented Algorithm for the Voronoi Diagram of Polygons" http://www.cccg.ca/proceedings/1996/cccg1996_0019.pdf

Sugihara, Iri, Inagaki, Imai, (2000) "topology oriented implementation - an approach to robust geometric algorithms" http://dx.doi.org/10.1007/s004530010002

Held, (1991) "On the Computational Geometry of Pocket Machining" Lecture notes in computer science, vol 500 http://www.amazon.com/Computational-Geometry-Machining-Lecture-Computer/dp/3540541039/

Held, (2001) "VRONI: an engineering approach to the reliable and efficient computation of Voronoi diagrams of points and line segments" http://dx.doi.org/10.1016/S0925-7721(01)00003-7

Martin Held, Stefan Huber, (2009) "Topology-oriented incremental computation of Voronoi diagrams of circular arcs and straight-line segments", Computer-Aided Design, Volume 41, Issue 5, May 2009, Pages 327-338 http://dx.doi.org/10.1016/j.cad.2008.08.004

Nirav B. Patel (2005), "Voronoi diagrams, robust and efficient implementation", Binghamton University, State University of New York, 2005, MSc thesis. (this thesis is not accompanied by code, or much implementation detail)

Kim D-S, (1998), "Polygon offsetting using a Voronoi diagram and two stacks" Computer Aided Design, Vol. 30, No. 14, pp 1069-1076 http://dx.doi.org/10.1016/S0010-4485(98)00063-3

Chen, Fu "An optimal approach to multiple tool selection and their numerical control path generation for aggressive rough machining of pockets with free-form boundaries" Computer Aided Design 43 (2011) 651-663 http://dx.doi.org/10.1016/j.cad.2011.01.020

todo: Burnikel-papers?

References, HSM or Trochoidal paths:

Martin Held, Christian Spielberger (2009). "A smooth spiral tool path for high speed machining of 2D pockets", Computer-Aided Design, Volume 41, Issue 7, July 2009, Pages 539-550 http://dx.doi.org/10.1016/j.cad.2009.04.002 See also www.cosy.sbg.ac.at/~cspiel/projects/hsm/isvd08.pdf and www.cosy.sbg.ac.at/~held/teaching/seminar/seminar_2010-11/hsm.pdf

Gershon Elber, Elaine Cohen, Sam Drake, "MATHSM: medial axis trasform toward high speed machining of pockets", Computer Aided Design 37 (2004) 241-250 http://dx.doi.org/10.1016/j.cad.2004.05.008

Rauch et al. (2009) "Improving trochoidal tool paths generation and implementation using process constraints modelling" http://dx.doi.org/10.1016/j.ijmachtools.2008.12.006 This paper has formulas for maximum depth of cut for circular and trochoidal clearing paths

Ibaraki (2010) "On the removal of critical cutting regions by trochoidal grooving" http://dx.doi.org/10.1016/j.precisioneng.2010.01.007

openvoronoi's People

Contributors

Stargazers

Watchers

openvoronoi's Issues

Failure on n-gons with even n

I feel it's due to parallel edges in such n-gons, but not completely sure.
Made simple test generator: http://pastebin.com/ULwQdgSw
git rev-parse --short HEAD
6c9c25f
Output before failure with n=100
add line 49 : 370 377
add line 50 : 377 384
add line 51 : 384 390
WARNING empty solution set!!
WARNING in_region_filter() results in empty solution set!!
WARNING t_filter() results in empty solution set!!
solution edge: (-1.39563e-05, -0.000444096)1 - (5.52635e-17, -8.75288e-18)1
solution edge: 3206[1]{1} -[2]- 3208[1]{0}
s1= LineSite: (-0.898224, 0.0565115) - (-0.9, 1.10218e-16)(k=-1)
s2= LineSite: (0.898224, -0.0565115) - (0.9, 0)(k=-1)
s3= LineSite: (-0.898224, -0.0565115) - (-0.9, 1.10218e-16)
Running solvers again:
LLLPARASolver.
s1 : -0.999507 0.0314108 -0.899556 -1
s2 : 0.999507 -0.0314108 -0.899556 -1
s3 : 0.999507 0.0314108 0.899556 1
bisector: -0.999507 0.0314108 5.55112e-17
Solution: t=0.899556 (-0.9, -28.6385) k3=1
LLLPARASolver.
s1 : -0.999507 0.0314108 -0.899556 -1
s2 : 0.999507 -0.0314108 -0.899556 -1
s3 : 0.999507 0.0314108 0.899556 1
bisector: -0.999507 0.0314108 5.55112e-17
Solution: t=0.899556 (-2.77693e-17, -2.6509e-15) k3=-1
No solutions found by solvers!
VertexPositioner::desperate_solution()
edge: (-1.39563e-05, -0.000444096) - (5.52635e-17, -8.75288e-18)
dist(): 0.899556 - 0.899556
WARNING: Returning desperate solution:
(0.0305228, 0.971251) t=0.899556 k3=-1 e_err=0.97173
s1_err= 0.404023
s2_err= 0.404023
s3_err= 0.445509
solution_on_edge() ERROR err= 0.97173
solution edge: 3206[1]{1} -[2]- 3208[1]{0}
edge: 3206(t=0.899556) - 3208(t=0.899556)
edge: (-1.39563e-05, -0.000444096) - (5.52635e-17, -8.75288e-18)
solution: (0.0305228, 0.971251) t=0.899556
python: /home/shadowjack/projects/openvoronoi/src/vertex_positioner.cpp:98: ovd::solvers::Solution ovd::VertexPositioner::position(ovd::HEEdge, ovd::Site*): Assertion `solution_on_edge(sl)' failed.
Aborted

warnings about misleading indentation

The build gives a lot of warnings about misleading indentation (-Wmisleading-indentation) for code like:
if (step==current_step) return false; current_step++;

That should be fixed or silenced. (Maybe create a macro for that recurring code?)

Python 3 support

Hi, I've more or less completed the work of packaging OpenVoronoi for Debian in preparation for the relicensing. It's possible to automatically provide both Python 2 & 3 packages, but it looks like Python 3 is not supported. I crossed my fingers and tried it after replacing all the print s with print()s, but it looks like it'll be slightly more effort than that. Have you given any thought to adding Python 3 support?

Boost Python not found by cmake in MacOS

I'm trying to compile in MacOS with python bindings, but cmake is not founding boost-python. But I have install it for python 2.7 and 3 using brew.

Here is what I get:

--  Your compiler is = /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/c++
--  Your linker is = /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/ld
--  CMAKE_BUILD_TYPE  = Release
--  CMAKE_CXX_FLAGS_RELEASE = -O3 -DNDEBUG
--  CMAKE_CXX_FLAGS = -O3 -DNDEBUG
-- Your system is: Darwin
-- Python includes: /usr/include/python2.7
-- Boost version: 1.68.0
-- Boost_LIB_VERSION: 1_68
-- Boost_INCLUDE_DIRS are: /usr/local/include
-- boost_LIBRARY_DIRS is: /usr/local/lib
-- Boost_LIBRARIES is: 
CMake Error at /usr/local/Cellar/cmake/3.13.4/share/cmake/Modules/FindBoost.cmake:2100 (message):
  Unable to find the requested Boost libraries.

  Boost version: 1.68.0

  Boost include path: /usr/local/include

  Could not find the following Boost libraries:

          boost_python

  No Boost libraries were found.  You may need to set BOOST_LIBRARYDIR to the
  directory containing Boost libraries or BOOST_ROOT to the location of
  Boost.
Call Stack (most recent call first):
  CMakeLists.txt:134 (find_package)


-- Boost_PYTHON_LIBRARY is: 
CMake Error at Findqd.cmake:39 (MESSAGE):
  Could not find QD
Call Stack (most recent call first):
  CMakeLists.txt:140 (find_package)


-- Configuring incomplete, errors occurred!
See also "/Users/patriciogv/Desktop/openvoronoi/build/CMakeFiles/CMakeOutput.log".

Any thoughts? Thanks

make coveralls test-coverage work

Currently travis is not interacting with coveralls in the right way, since coveralls shows zero coverage.
Maybe the tests are not run with a debug-build?

avoid dependencies for tests

We now depend on a random-polygon-generator and on a font-geometry-source library for a lot of tests.
This is fine for development, but maybe not ideal for deployment and automated testing.

It would be better to use the geometry-sources to generate "hardcopy" text-files with the desired test-geometry and store that in each test-directory. A good descriptive text-format is needed (YAML/INI-format or similar?)

assertion failure in VoronoiDiagram::add_edge

I found another sequence of inputs that results in error:

    ovd::Point p1(0.15907424869091413, -0.22755592000227737);
    ovd::Point p2(-0.158774429631718, -0.22755592000227737);
    ovd::Point p3(-0.158774429631718, 0.5000000000000007);
    ovd::Point p6(0.44085019690616595, -0.4999999999999993);
    ovd::Point p7(0.44085019690616595, 0.4999999999999993);

    int v1 = vd->insert_point_site(p1);
    int v2 = vd->insert_point_site(p2);
    int v3 = vd->insert_point_site(p3);
    int v6 = vd->insert_point_site(p6);
    int v7 = vd->insert_point_site(p7);

    vd->insert_line_site(v1, v2);
    vd->insert_line_site(v2, v3);
    vd->insert_line_site(v6, v7);

Usage of Voronoi library

Hello, my name is Lena and I am trying to work with algorithm Event-chain and I need Voroni diagram to do it to find nearest neighbors (or 5 nearest neighbors). But I can not use your library because I work in Visual Studio 2019 and it asks for new and new files/libraries which I can not find here. Maybe you could help me to realize your library I really need it! In which program you realized your library? And maybe you know how else I can realize algorithm of find nearest neighbor. Regards.

Consider changing to more permissive license

The GPL3 license with strong copyleft provisions is too restrictive to allow linking and packaging with applications like FreeCAD that are LGPL.

If openvoronoi was re-licensed LGPL2.1, inclusion in other applications would be easier and interest in using the library would increase.

I'm willing to help with any re-licensing effort and FreeCAD community will help with debian packaging if re-licensed so we can use it.

Unable to compile on Arch Linux

I'm getting the following errors once I try to make. I have both boost and boost-libs installed. Any ideas?

~/Downloads/openvoronoi-master/bld $ make
[ 26%] Built target libopenvoronoi
[ 52%] Built target openvoronoi_static
[ 57%] Built target openvoronoi
[ 59%] Linking CXX executable cpptest_medial_axis
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PySequence_GetSlice'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyExc_ValueError'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyString_Size'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyBool_Type'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyObject_GetAttr'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyDict_GetItemString'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyNumber_And'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyExc_IndexError'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyUnicodeUCS4_FromEncodedObject'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyEval_GetGlobals'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `_PyEval_SliceIndex'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyTuple_Type'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyNumber_InPlaceSubtract'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyList_Type'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyObject_GetAttrString'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyFile_FromString'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyModule_Type'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyMem_Free'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyType_IsSubtype'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyStaticMethod_Type'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyErr_WarnEx'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyTuple_New'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyObject_SetAttr'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyObject_IsInstance'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyErr_NoMemory'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `_Py_NoneStruct'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyExc_AttributeError'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyNumber_Add'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyList_Append'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyType_Type'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyExc_ReferenceError'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyString_Type'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyArg_ParseTupleAndKeywords'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyStaticMethod_New'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyNumber_InPlaceMultiply'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyInt_Type'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyTuple_Size'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyErr_SetObject'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `_PyObject_New'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyDict_Keys'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyType_GenericAlloc'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyErr_Format'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyObject_CallFunction'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyList_Reverse'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyString_FromString'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PySequence_DelSlice'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyCFunction_Type'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyExc_OverflowError'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyMem_Malloc'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyErr_ExceptionMatches'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyComplex_ImagAsDouble'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyCFunction_NewEx'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyList_New'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyImport_ImportModule'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyUnicodeUCS4_AsWideChar'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyProperty_Type'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyNumber_InPlaceOr'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyUnicode_Type'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyObject_DelItem'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyString_FromStringAndSize'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyErr_Clear'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `Py_InitModule4_64'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyRun_StringFlags'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyDict_GetItem'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyWeakref_NewRef'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyNumber_Multiply'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyNumber_Lshift'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyDict_New'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyErr_SetString'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyDict_Update'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PySlice_New'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyString_FromFormat'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyRun_FileExFlags'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyObject_SetItem'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyNumber_Divide'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyObject_SetAttrString'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyLong_AsUnsignedLongLong'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyExc_RuntimeError'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyNumber_Xor'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PySequence_SetSlice'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyNumber_InPlaceDivide'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyInt_AsLong'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `_Py_NotImplementedStruct'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyNumber_Rshift'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyBaseObject_Type'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyExc_StopIteration'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyObject_GetItem'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyExc_TypeError'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyDict_Values'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyType_Ready'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyObject_Size'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyMethod_Type'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyMethod_New'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyObject_ClearWeakRefs'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyLong_AsLongLong'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyEval_CallFunction'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyNumber_Remainder'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyErr_NewException'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyObject_CallMethod'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyNumber_Or'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyObject_IsTrue'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyList_Sort'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyLong_AsUnsignedLong'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyNumber_InPlaceRemainder'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyDict_Type'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyString_InternFromString'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyErr_Occurred'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyDict_Copy'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyLong_Type'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyNumber_InPlaceAnd'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyNumber_InPlaceXor'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `_PyType_Lookup'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyDict_Size'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyNumber_InPlaceRshift'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyFloat_Type'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyIter_Next'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyCallable_Check'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyClass_Type'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyComplex_RealAsDouble'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyLong_FromUnsignedLong'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyList_Insert'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyString_AsString'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyObject_RichCompare'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyDict_Items'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyInt_FromLong'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyTuple_GetItem'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyNumber_Subtract'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyFile_AsFile'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyComplex_Type'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyDict_Clear'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyNumber_InPlaceLshift'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyBool_FromLong'
/usr/bin/ld: /usr/lib/gcc/x86_64-pc-linux-gnu/8.2.1/../../../../lib/libboost_python.so: undefined reference to `PyNumber_InPlaceAdd'
collect2: error: ld returned 1 exit status
make[2]: *** [cpptest_medial_axis/CMakeFiles/cpptest_medial_axis.dir/build.make:87: cpptest_medial_axis/cpptest_medial_axis] Error 1
make[1]: *** [CMakeFiles/Makefile2:1258: cpptest_medial_axis/CMakeFiles/cpptest_medial_axis.dir/all] Error 2
make: *** [Makefile:163: all] Error 2

won't build on Mac OS X

I get a build error.

Cmake runs without issue (well, it gave me warnings about missing libraries, I installed them, then it ran with out issue).

Then, upon running "make", the static library builds find and the dynamic passes clang an invalid combination of parameters:

[ 95%] Built target openvoronoi_static
Scanning dependencies of target openvoronoi
[100%] Building CXX object CMakeFiles/openvoronoi.dir/py/open_voronoi_py.o
Linking CXX shared module openvoronoi.so
clang: error: invalid argument '-current_version 12.2.284' only allowed with '-dynamiclib'
make[2]: *** [openvoronoi.12.02.284.so] Error 1
make[1]: *** [CMakeFiles/openvoronoi.dir/all] Error 2
make: *** [all] Error 2

I am not a cmake expert, so I don't know how to edit/re-run with the updated option added - instructions on how to do that would be very helpful, as well as a patch!

My system details are:

Mac OS X 10.8.3, clang:

Apple LLVM version 4.2 (clang-425.0.24) (based on LLVM 3.2svn)
Target: x86_64-apple-darwin12.3.0
Thread model: posix

System python (2.7.3, framework.)

The following tests FAILED: 51 - cpptest_ttt_glyph_small_35 (Failed)

Test: cpptest_ttt_glyph_small_35 fails.
This is because of a special case where LLLSolver does not return a sensible solution ad we fallback on a desperate solution instead (which probably has the wrong k3 sign)

This test can also be run with the example code:
openvoronoi/cpp_examples/ttt_glyph/bld$ ./ovd_tst --c 35

OpenVoronoi is missing a robust desperate solver which could always be used as a last resort when a faster special purpose solver is not able to do the job. To do.

This test did not fail on my Ubuntu 12.04 install but started failing on 12.10, so the numerical instability varies with compiler/boost/libqd (not sure which!).

Assertion `check_dist(edge, sl, s3)' failed

The following code results in error:

    ovd::VoronoiDiagram* vd = new ovd::VoronoiDiagram(1,100);

    ovd::Point p1(0.41164403323558574,-0.6789386939364543);
    ovd::Point p2(0.17427452375132169,-0.6522148409835533);
    ovd::Point p3(0.15951277675921582,-0.6538785084950686);
    ovd::Point p4(0.3890141779152667,-0.6928288255549844);
    ovd::Point p5(0.3860913593953006,-0.6919949537598736);
    ovd::Point p6(0.42532972342719244,-0.6914003202947938);
    ovd::Point p7(-0.16212113598677202,-0.6733320323817963);

    int v1 = vd->insert_point_site(p1);
    int v2 = vd->insert_point_site(p2);
    vd->insert_point_site(p3);
    int v4 = vd->insert_point_site(p4);
    int v5 = vd->insert_point_site(p5);
    int v6 = vd->insert_point_site(p6);
    int v7 = vd->insert_point_site(p7);

    vd->insert_line_site(v4, v5);
    vd->insert_line_site(v1, v2);
    vd->insert_line_site(v6, v7);

Here's the output.

Here's the view on the segment being added, after vertex marking was done, but no new vertices were added:

Here's the view below that line, displaying the problematic edge:

Failure happens when vertex is positioned on (0.102,-1.687)-(0.098,-1.714) edge (red circles mark IN vertices).
Problem is, there is no solution lying on that edge (no point equidistant to the shortest segment, lone pointsite and newly added linesite). Maybe the problem is in the way vertices were marked?

change "print get_python_lib()" to "print(get_python_lib())" in CMakeLists.txt

I had to change "print get_python_lib()" to "print(get_python_lib())" in CMakeLists.txt so that cmake would complete.

(I am trying to use openvoronoi to construct land ownership borders according to jordabalken 1 kap. 5 §, see [https://www.riksdagen.se/sv/dokument-lagar/dokument/svensk-forfattningssamling/jordabalk-1970994_sfs-1970-994#K1].)

boost/python included despite BUILD_PYTHON_MODULE=OFF

As per subject.

All of the Boost Python related bits of CMakeLists.txt are skipped when BUILD_PYTHON_MODULE is set to OFF, but offset_sorter.hpp seems to unconditionally include boost/python.hpp (see here).

Later on, there is another issue with boost::python::list offset_list_py().

Making the #include and function definition conditional on BUILD_PYTHON_LIB seems to fix this, but I'm unsure as to the consequences of just disabling things.

provide info on build-type

The debug or coverage build types are very very slow to run - so there should be some way of diagnosing this. Either include the build-type in the current version-string, or provide two functions, a separate version string (just the major version) and a more detailed build_info() with git-commit ID and build-type (possibly other compiler options also?)

Please throw exception instead of dying

It's very inconvenient when algorithm kilsl program instead of reporting failure.

boost/timer.hpp BOOST_HEADER_DEPRECATED

compiling gives a few of these warnings:

/usr/include/boost/timer.hpp:21:1: note: #pragma message: This header is deprecated. Use the facilities in <boost/timer/timer.hpp> instead.
21 | BOOST_HEADER_DEPRECATED( "the facilities in <boost/timer/timer.hpp>" )

support for polyline sites

It seems like polyline sites are almost supported. I attach the example SVG generated by the polygon example, where all 6 line-segment sites are yellow: polygon.svg.txt
What is missing is merging polygons around line-segment sites that belong to the same polyline (by removing the edges that have been generated between those polygons).

See this modification of the polygon example:
lake-owners.svg.txt

I classified the 6 line-segments into two polylines; 2 of them are still yellow and the 4 others are now blue. I removed all the edges that were created between line-segment sites of the same colour.

What I just did manually in the SVG is what the program could do to support poly-line sites.

Think of the example SVG as a drawing of a lake with different shore owners, where the program has calculated the property boundary through the lake. (Or an island with different shore owners, where the program has calculated the property boundaries through the surrounding water.)

insert_point_site fail

I try to build the cpp example on win10 with vs2019. build ok, but even insert first point site made program crash.
In medial axis example, it failed at line 27:
int id0 = vd->insert_point_site(p0);

Is that openvoronoi is not support windows? Or I use the wrong version of boost ?

void ovd::VoronoiDiagram::add_edges(ovd::HEFace, ovd::HEFace, ovd::HEFace, std::pair<void, void>): Assertion `(new_count % 2) == 0' failed. Aborted (core dumped)

When I am trying to use the cpp_examples medial_axis, I found the error:

void ovd::VoronoiDiagram::add_edges(ovd::HEFace, ovd::HEFace, ovd::HEFace, std::pair<void*, void*>): Assertion `(new_count % 2) == 0' failed.

With the code:

    ovd::Point p0(3.25,1.15);
    ovd::Point p1(1.1,1.15);
    ovd::Point p2(-0.275,1.15);
    ovd::Point p3(-1.25,0.475);
    ovd::Point p4(-0.95,-1.1);
    ovd::Point p5(1.1,-1.15);

    int id0 = vd->insert_point_site(p0);
    int id1 = vd->insert_point_site(p1);
    int id2 = vd->insert_point_site(p2);
    int id3 = vd->insert_point_site(p3);
    int id4 = vd->insert_point_site(p4);
    int id5 = vd->insert_point_site(p5);

    vd->insert_line_site(id0, id1);
    vd->insert_line_site(id1, id2);
    vd->insert_line_site(id2, id3);
    vd->insert_line_site(id3, id4);
    vd->insert_line_site(id4, id5);
    vd->insert_line_site(id5, id0);
    vd->check();

However, when I remove Point p1 and remake, it works without errors.
With the code:

    ovd::Point p0(3.25,1.15);
    // ovd::Point p1(1.1,1.15);
    ovd::Point p2(-0.275,1.15);
    ovd::Point p3(-1.25,0.475);
    ovd::Point p4(-0.95,-1.1);
    ovd::Point p5(1.1,-1.15);

    int id0 = vd->insert_point_site(p0);
    // int id1 = vd->insert_point_site(p1);
    int id2 = vd->insert_point_site(p2);
    int id3 = vd->insert_point_site(p3);
    int id4 = vd->insert_point_site(p4);
    int id5 = vd->insert_point_site(p5);

    vd->insert_line_site(id0, id2);
    // vd->insert_line_site(id1, id2);
    vd->insert_line_site(id2, id3);
    vd->insert_line_site(id3, id4);
    vd->insert_line_site(id4, id5);
    vd->insert_line_site(id5, id0);
    vd->check();

I think the different points caused the problems. But I did not find why it happens.
Thanks.

import openvoronoi as ovd ImportError: libboost_python-py27.so.1.49.0

recently on Ubuntu 13.10 all my python scripts have stopped working and I get:
import openvoronoi as ovd
ImportError: libboost_python-py27.so.1.49.0: cannot open shared object file: No such file or directory

I should have only Boost 1.53.0 libraries installed on this machine, and I have rebuilt and reinstalled openvoronoi many times.

Any ideas??

Offset bug

There is a bug in Offset which causes erratic behaviour if the offset-distance is chosen so that it exactly matches the offset-distance of a LINELINE or PARA_LINELINE edge (these edges cannot sensibly be parametrized with the t-value). The correct behavior is probably not to output an offset loop at all for this t-value.

Idea: Use openvoronoi as alternative toolpath in F-Engrave

Hi Anders,
In the works of refactoring F-Engrave I got the idea to add openvoronoi as an alternative toolpath strategy. After having consulted Scorch, the author, I renamed F-Engrave to OOF-Engrave.

Both openvoronoi as f-engrave are under GPLv3 so I expect using the first in the latter is no problem. My question is whether this assumption is true.

Encrypted Input File

I want to use this code for my m.tech project but the input file is encrypted and not able to decrypt it. I want to give user input. Can you please help me with this.

Error in building "open_voronoi_py"

I have the following error on my local machine (Ubuntu 22.04) and by forking and triggering the workflow.

Error:

Run cmake --build /home/runner/work/openvoronoi/openvoronoi/build --config Release
[  2%] Building CXX object CMakeFiles/libopenvoronoi.dir/voronoidiagram.cpp.o
[  4%] Building CXX object CMakeFiles/libopenvoronoi.dir/vertex.cpp.o
[  7%] Building CXX object CMakeFiles/libopenvoronoi.dir/edge.cpp.o
[  9%] Building CXX object CMakeFiles/libopenvoronoi.dir/checker.cpp.o
[ [1](https://github.com/huberemanuel/openvoronoi/actions/runs/4390203857/jobs/7688482103#step:7:1)1%] Building CXX object CMakeFiles/libopenvoronoi.dir/common/point.cpp.o
[ 14%] Building CXX object CMakeFiles/libopenvoronoi.dir/vertex_positioner.cpp.o
[ 1[6](https://github.com/huberemanuel/openvoronoi/actions/runs/4390203857/jobs/7688482103#step:7:7)%] Building CXX object CMakeFiles/libopenvoronoi.dir/common/numeric.cpp.o
[ 19%] Building CXX object CMakeFiles/libopenvoronoi.dir/medial_axis_pocket.cpp.o
[ 21%] Building CXX object CMakeFiles/libopenvoronoi.dir/medial_axis_walk.cpp.o
[ 23%] Building CXX object CMakeFiles/libopenvoronoi.dir/offset.cpp.o
[ 26%] Linking CXX shared library libopenvoronoi.so
[ 26%] Built target libopenvoronoi
[ 28%] Building CXX object CMakeFiles/openvoronoi_static.dir/voronoidiagram.cpp.o
[ 30%] Building CXX object CMakeFiles/openvoronoi_static.dir/vertex.cpp.o
[ 33%] Building CXX object CMakeFiles/openvoronoi_static.dir/edge.cpp.o
[ 35%] Building CXX object CMakeFiles/openvoronoi_static.dir/checker.cpp.o
[ 38%] Building CXX object CMakeFiles/openvoronoi_static.dir/common/point.cpp.o
[ 40%] Building CXX object CMakeFiles/openvoronoi_static.dir/vertex_positioner.cpp.o
[ 42%] Building CXX object CMakeFiles/openvoronoi_static.dir/common/numeric.cpp.o
[ 45%] Building CXX object CMakeFiles/openvoronoi_static.dir/medial_axis_pocket.cpp.o
[ 4[7](https://github.com/huberemanuel/openvoronoi/actions/runs/4390203857/jobs/7688482103#step:7:8)%] Building CXX object CMakeFiles/openvoronoi_static.dir/medial_axis_walk.cpp.o
[ 50%] Building CXX object CMakeFiles/openvoronoi_static.dir/offset.cpp.o
[ 52%] Linking CXX static library libopenvoronoi_static.a
[ 52%] Built target openvoronoi_static
[ 54%] Building CXX object CMakeFiles/openvoronoi.dir/py/open_voronoi_py.cpp.o
In file included from /usr/include/boost/smart_ptr/detail/sp_thread_sleep.hpp:22,
                 from /usr/include/boost/smart_ptr/detail/yield_k.hpp:23,
                 from /usr/include/boost/smart_ptr/detail/spinlock_gcc_atomic.hpp:14,
                 from /usr/include/boost/smart_ptr/detail/spinlock.hpp:42,
                 from /usr/include/boost/smart_ptr/detail/spinlock_pool.hpp:25,
                 from /usr/include/boost/smart_ptr/shared_ptr.hpp:29,
                 from /usr/include/boost/shared_ptr.hpp:17,
                 from /usr/include/boost/python/converter/shared_ptr_to_python.hpp:12,
                 from /usr/include/boost/python/converter/arg_to_python.hpp:15,
                 from /usr/include/boost/python/call.hpp:15,
                 from /usr/include/boost/python/object_core.hpp:14,
                 from /usr/include/boost/python/args.hpp:22,
                 from /usr/include/boost/python.hpp:11,
                 from /home/runner/work/openvoronoi/openvoronoi/src/py/open_voronoi_py.cpp:21:
/usr/include/boost/bind.hpp:36:1: note: ‘#pragma message: The practice of declaring the Bind placeholders (_1, _2, ...) in the global namespace is deprecated. Please use <boost/bind/bind.hpp> + using namespace boost::placeholders, or define BOOST_BIND_GLOBAL_PLACEHOLDERS to retain the current behavior.’
   36 | BOOST_PRAGMA_MESSAGE(
      | ^~~~~~~~~~~~~~~~~~~~
/usr/include/boost/detail/iterator.hpp:13:1: note: ‘#pragma message: This header is deprecated. Use <iterator> instead.’
   13 | BOOST_HEADER_DEPRECATED("<iterator>")
      | ^~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/set:60,
                 from /home/runner/work/openvoronoi/openvoronoi/src/voronoidiagram.hpp:23,
                 from /home/runner/work/openvoronoi/openvoronoi/src/py/voronoidiagram_py.hpp:23,
                 from /home/runner/work/openvoronoi/openvoronoi/src/py/open_voronoi_py.cpp:23:
/usr/include/c++/11/bits/stl_tree.h: In instantiation of ‘static const _Key& std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_S_key(std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Const_Link_type) [with _Key = ovd::OffsetLoop; _Val = ovd::OffsetLoop; _KeyOfValue = std::_Identity<ovd::OffsetLoop>; _Compare = ovd::OffsetLoopCompare; _Alloc = std::allocator<ovd::OffsetLoop>; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Const_Link_type = const std::_Rb_tree_node<ovd::OffsetLoop>*]’:
/usr/include/c++/11/bits/stl_tree.h:2102:44:   required from ‘std::pair<std::_Rb_tree_node_base*, std::_Rb_tree_node_base*> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_get_insert_equal_pos(const key_type&) [with _Key = ovd::OffsetLoop; _Val = ovd::OffsetLoop; _KeyOfValue = std::_Identity<ovd::OffsetLoop>; _Compare = ovd::OffsetLoopCompare; _Alloc = std::allocator<ovd::OffsetLoop>; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::key_type = ovd::OffsetLoop]’
/usr/include/c++/11/bits/stl_tree.h:2151:4:   required from ‘std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_insert_equal(_Arg&&) [with _Arg = const ovd::OffsetLoop&; _Key = ovd::OffsetLoop; _Val = ovd::OffsetLoop; _KeyOfValue = std::_Identity<ovd::OffsetLoop>; _Compare = ovd::OffsetLoopCompare; _Alloc = std::allocator<ovd::OffsetLoop>; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator = std::_Rb_tree<ovd::OffsetLoop, ovd::OffsetLoop, std::_Identity<ovd::OffsetLoop>, ovd::OffsetLoopCompare, std::allocator<ovd::OffsetLoop> >::iterator]’
/usr/include/c++/11/bits/stl_multiset.h:503:36:   required from ‘std::multiset<_Key, _Compare, _Alloc>::iterator std::multiset<_Key, _Compare, _Alloc>::insert(const value_type&) [with _Key = ovd::OffsetLoop; _Compare = ovd::OffsetLoopCompare; _Alloc = std::allocator<ovd::OffsetLoop>; std::multiset<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<ovd::OffsetLoop, ovd::OffsetLoop, std::_Identity<ovd::OffsetLoop>, ovd::OffsetLoopCompare, std::allocator<ovd::OffsetLoop> >::const_iterator; std::multiset<_Key, _Compare, _Alloc>::value_type = ovd::OffsetLoop]’
/home/runner/work/openvoronoi/openvoronoi/src/offset_sorter.hpp:124:41:   required from here
/usr/include/c++/11/bits/stl_tree.h:770:15: error: static assertion failed: comparison object must be invocable as const
  770 |               is_invocable_v<const _Compare&, const _Key&, const _Key&>,
      |               ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/11/bits/stl_tree.h:770:15: note: ‘std::is_invocable_v<const ovd::OffsetLoopCompare&, const ovd::OffsetLoop&, const ovd::OffsetLoop&>’ evaluates to false
gmake[2]: *** [CMakeFiles/openvoronoi.dir/build.make:76: CMakeFiles/openvoronoi.dir/py/open_voronoi_py.cpp.o] Error 1
gmake[1]: *** [CMakeFiles/Makefile2:43[8](https://github.com/huberemanuel/openvoronoi/actions/runs/4390203857/jobs/7688482103#step:7:9): CMakeFiles/openvoronoi.dir/all] Error 2
gmake: *** [Makefile:[16](https://github.com/huberemanuel/openvoronoi/actions/runs/4390203857/jobs/7688482103#step:7:17)6: all] Error 2
Error: Process completed with exit code 2.

only supports VTK version 5, VTK 6 incompatible?

Apparently VTK version 6 has some incompatibilities with VTK version 5.

A note should be added that openvoronoi visualization scripts only work with VTK version 5.
or the scripts rewritten so they work on the latest VTK release.

multi-OS build on Travis-CI

Modify travis.yml so that we build & test on Linux, Max OSX, and Windows.

find_separator_target() FATAL ERROR

The following sequence of points gives errors:

-0.2567719874411157,-0.4983049800651602
0.12205285479992212,-0.640371712930281
-0.25972854724944455,-0.5143879072702902
-0.34168692840153536,-0.6418861147966213
-0.5288215108461576,0.18480346369654843
-0.35263585687204546,-0.50735692278175
-0.4821854389417177,0.46463421861462373

Here's the code and output: https://gist.github.com/Rogach/29cf52b69f40cc941fc6

The image of the polygon:

The polygon looks relatively harmless, and I have no idea what the problem may be.

The error is relatively rare with smaller random polygons, but happens often with bigger polygons -it took ~300 random polygons with 4096 points to generate this error, ~30000 with 1024 points, and several million to find a case with 32 points - which I then simplified to the one in above image. (I used my own random polygon generator, not the one used in tests, so it may not happen in your tests)

Improve Travis CI build & test

I started a bit on Travis CI automated build and testing
https://travis-ci.org/aewallin/openvoronoi
it does not build yet - because of a problem with the git version-string.

we would want:

different compilers (gcc, clang, etc) and possibly platforms
c++ library and python-module builds
automated tests (could/should this be a separate build-process on travis?)

About the possibility of extending the library to ArcSite

Hello,Mr.Wallin,There are three questions I want to share with you.The first one,I've read the codes about construction voronoi diagram of point site and line site in detail;a little bug about construction voronoi diagram of line site with test data:
ovd::Point p0(-1.0, 0.0);
ovd::Point p1(-1.0, 2.0);

ovd::Point p2(0.0, 2.0);
ovd::Point p3(0.0, 1.0);

ovd::Point p4(1.0, 1.0);
ovd::Point p5(1.0, 0.0);

//insert point site
int id0 = vd->insert_point_site(p0);
int id1 = vd->insert_point_site(p1);
int id2 = vd->insert_point_site(p2);
int id3 = vd->insert_point_site(p3);
int id4 = vd->insert_point_site(p4);
int id5 = vd->insert_point_site(p5);

vd->insert_line_site(id0, id1);
vd->insert_line_site(id1, id2);
vd->insert_line_site(id2, id3);
vd->insert_line_site(id3, id4);
vd->insert_line_site(id4, id5);
vd->insert_line_site(id5, id0);

we construct voronoi diagram successfully ,however ,when we change the direction of line site" vd->insert_line_site(id5, id0)" to" vd->insert_line_site(id0, id5)";failed, the reason for which is when we change the direction of line site,the offset direction for is unchanged ,which leads to the solution lies the other side of line site,thus add edge unsuccessfully.

The second one,I can't understand the logic of construction of separator of line site ,,specially about the API process_null_edge(),can you give some details about that.

The last one,I've read your blog about about if extension of Arc site is possible; the first difficulty is about Arc predicates,which you've given the math expression about in_region(p),apex_point(p),I've checked that,it's right;the second is about edge-parametrizations for the new type of voronoi-edges that will occur when we have arc-sites (arc/point, arc/line, and arc/arc) written in your blog,then calculate voronoi vertex position is necessary,which is mentioned in the thesis"Topology-oriented incremental computation of Voronoi diagrams of circular arcs
and straight-line segments",or a more detailed version Msc of Stefan Huber"Computation of Voronoi Diagrams of
Circular Arcs and Straight Lines",and split vertex is added to avoid loop in delete tree,I don't know if the construction of separator of arc site is as same as the line site.

Performance vs Boost Voronoi

Hi aewallin, loving the work you are doing on openvoronoi.

I was wondering whether you have some more recent numbers on the performance of this library compared to Boost Voronoi. I have found one of your blog posts regarding this, but it is from 2012 and I suppose a lot of things might have changed since then.

If you don't have any concrete numbers then perhaps you have a rough estimate on how the performance of this library has changed since then? Boost Voronoi hasn't been updated since then so that remains as a stable baseline :p

QD dependencies (Windows)

Trying to build the lib with MS VS and got Could not find QD message.

README says

Required Dependencies:
...
 - libqd-dev             http://crd.lbl.gov/~dhbailey/mpdist/

Is libqd-dev are https://www.davidhbailey.com/dhbsoftware/ QD lib ? Does it have a Windows version?

autodetect available libraries for tests

many of the tests depend on external libraries that generate input-geometry, such as:

truetypetracer (depends on Freetype)
randompolygon (which in turn depends on CGAL)

ideally the tests should be configured and run only if the user has the required libraries installed.
without the libraries we would just run the tests that we can.

2014 February: 5 tests failed out of 157

these should be investigated and fixed.
arcs are very experimental.
the truetype tracer failing tests are probably numerical instabilities.

97% tests passed, 5 tests failed out of 157
Total Test time (real) = 68.50 sec
The following tests FAILED:
5 - cpptest_arc (Failed)
7 - cpptest_arc_d (Failed)
8 - cpptest_arc_r (Failed)
23 - cpptest_ttt_glyph_big_7 (SEGFAULT)
51 - cpptest_ttt_glyph_small_35 (Failed)

Problems with several linesites outgoing from the same pointsite

Simple testcase:

    ovd::Point p1(0.0, 0.0);
    ovd::Point p2(-0.5, 0);
    ovd::Point p3(0.5, 0);
    ovd::Point p4(0, 0.5);

    int v1 = vd->insert_point_site(p1);
    int v2 = vd->insert_point_site(p2);
    int v3 = vd->insert_point_site(p3);
    int v4 = vd->insert_point_site(p4);

    vd->insert_line_site(v1, v2);
    vd->insert_line_site(v1, v3);
    vd->insert_line_site(v1, v4);

Output:

voronoidiagram.cpp:1563: void ovd::VoronoiDiagram::add_edges(ovd::HEFace, ovd::HEFace, ovd::HEFace, std::pair<void*, void*>): Assertion `(new_count % 2) == 0' failed.

Almost any set of coordinates resembling these also fails, but with another problem:

    ovd::Point p1(0.002, 0.030);
    ovd::Point p2(-0.473, 0.099);
    ovd::Point p3(0.571, 0.008);
    ovd::Point p4(0.100, 0.524);

    int v1 = vd->insert_point_site(p1);
    int v2 = vd->insert_point_site(p2);
    int v3 = vd->insert_point_site(p3);
    int v4 = vd->insert_point_site(p4);

    vd->insert_line_site(v1, v2);
    vd->insert_line_site(v1, v3);
    vd->insert_line_site(v1, v4);

gives:

voronoidiagram.cpp:1216: void* ovd::VoronoiDiagram::find_seed_vertex(ovd::HEFace, ovd::Site*): Assertion `minPred < 0' failed.