boostorg / polygon Goto Github PK

View Code? Open in Web Editor NEW

54.0 14.0 71.0 6.19 MB

Boost.org polygon module

Home Page: http://boost.org/libs/polygon

C++ 99.93% HTML 0.04% CMake 0.03%

polygon's People

Contributors

Stargazers

Watchers

Forkers

sanderbog awulkiew marcelraad danieljames fiesh akumta posila vamsik83 fsun2p10 limbolily plopresti crossbuild autodesk-forks danielae jrmwng xltools bazelboost myestro artem-ogre glenfe mike-devel canglangshushu rydotyosh amridris jinhang2008 zhaohui0923 dtzikas donovan680 skandemir dmsteck helixhorned prusa3d ezhangle f3rm4rf3r 0000duck samd2 sdarwin eldiener mborn-adi opensourceeda eadf fieryswampshire longgang fallenwhiter ekra-ltd crypt0r3n3g4d3 murd4m1773n-m4f14 mpnunez jingliang2005 isabella232 aetheriaxai zhangfanyuanhang gilgamsh gtton jellespijker nucarve yvhangfish tjs137 xiaoshuimao khaassorena xavi7988 tinko92 ka-de seanpm2001 sam-caldwell kelleyg2 grafikrobot mogcompany infinityofficialnetwork duanduanfish banchou0531

polygon's Issues

GPC link in analysis.htm is dead

https://github.com/boostorg/polygon/blob/develop/doc/analysis.htm#L141 points to http://www.cs.manchester.ac.uk/~toby/alan/software/ which 404's.

Seems to have moved to http://www.cs.man.ac.uk/~toby/gpc/

1.71.0 polygon operation crashed due to 64bit integer overflow

In 1.71.0, the coordinate_traits specialized for polygon_long_long_type. On 64bit platform, when checking one point is above or below a line for arbitrary formation, it involves 64bit integer multiplication. When input geometry coordinate is really big, this operation can lead to 64bit integer overflow and caused crash.

Infinite loop

A call to construct_voronoi blocks forever in the following code:

int main() {
  using poly_segment = boost::polygon::segment_data<double>;
  std::vector<poly_segment> segments;

  std::ifstream file("bad_voronoi.segments.txt");
  while (!file.fail()) {
    double x1, y1, x2, y2;
    file >> x1 >> y1 >> x2 >> y2;
    segments.push_back({{x1, y1}, {x2, y2}});
  }

  // // Doesn't help:
  // std::vector<poly_segment> split_segments;
  // boost::polygon::intersect_segments(split_segments, segments.begin(), segments.end());
  // segments = std::move(split_segments);

  boost::polygon::voronoi_diagram<double> vd;
  boost::polygon::construct_voronoi(segments.begin(), segments.end(), &vd);
}

bad_voronoi.segments.txt

I've tracked the issue down to the _build() method in voronoi_diagram.hpp, specifically in the loop that remove degenerate vertices:

          do {
            e->vertex0(v);
            e = e->rot_next();
          } while (e != v->incident_edge());

An odd property: removing any segment from bad_voronoi.segments.txt will unbreak the infinite loop. You need all 1912 segments to trigger the fault.

boost::polygon::polygon_set_data::resize does not produce correct results when corner_fill_arc is true

When corner_fill_arc is true resize returns results that are incorrect on long edges. It needs to bias the long edges by exact resizing amount, and round around corners. In current implementation, long edges are not biased exactly. This is due to using a discrete circle in minkowski_offset. Minkowski convolution needs to be done with a continuous circle, if you discretize the circle you make errors in the bias. The results of resize with corner_fill_arc must be similar to boost::geometry::buffer function.

The resize with or without corner_fill_arc must return same results on long edges, only difference needs to be near corners.
If you run the following code you get:
max coordinates without rounding: 110 110
max coordinates with rounding: 109.239 109.239

ALSO: If you create a square that is 1000x1000, the output is empty.
Calling with numbers bigger than 8 does not produce any results: Like
polygon_set1.resize(10.0, true, 9); // output is empty
polygon_set1.resize(10.0, true, 36); // output is empty

void testBoostResize(){
   using polygon = boost::polygon::polygon_with_holes_data<double>;
   using point = boost::polygon::polygon_traits<polygon>::point_type;
   std::vector<point> pts;
   pts.push_back(point(0,0));
   pts.push_back(point(100,0));
   pts.push_back(point(100,100));
   pts.push_back(point(0,100));
   polygon pol;
   boost::polygon::set_points(pol, pts.begin(), pts.end());

   boost::polygon::polygon_set_data<double>  polygon_set2;
   polygon_set2.insert(pol);
   polygon_set2.resize(10.0); // resize without rounding
   vector<polygon> resized2;
   polygon_set2.get(resized2);
   double max_x = -1000;
   double max_y = -1000;
    for (auto it = resized2[0].begin(); it != resized2[0].end(); it++){
        const auto &pt = *it;
        max_x = std::max(max_x, pt.x());
        max_y = std::max(max_y, pt.y());
   }
   cout <<"max coordinates without rounding: "<< max_x <<"  "<< max_y<<endl;


   boost::polygon::polygon_set_data<double>  polygon_set1;
   polygon_set1.insert(pol);
   polygon_set1.resize(10.0, true, 8); // resize with rounding
   vector<polygon> resized1;
   polygon_set1.get(resized1);
   max_x = -1000;
   max_y = -1000;
    for (auto it = resized1[0].begin(); it != resized1[0].end(); it++){
        const auto &pt = *it;
        max_x = std::max(max_x, pt.x());
        max_y = std::max(max_y, pt.y());
   }
   cout <<"max coordinates with rounding: "<< max_x <<"  "<< max_y<<endl;
}

Crash with VS 16.8.6 but working with clang 11/13 and gcc 11

Hi there,

We encountered a weird error running the following code using boost::polygon.

It is compiling and working on:

wandbox.org using clang/gcc
and on macOS using Apple clang 11.0.3.

and compiling but crashing with cl from Visual Studio 16.8.6.

Do you have any idea about what is going on please?

Cheers,
Nicolas

#include <vector>
#include <boost/polygon/polygon.hpp>

int main()
{
	using Polygon = boost::polygon::polygon_data<int>;
	using PolygonPoints = std::vector<typename Polygon::point_type>;
	PolygonPoints polygonPoints{
        { 0, 0 },
        { -37570000, 37568665 },
        { -233490372, -195921616 },
    };
	Polygon const polygon{ std::begin(polygonPoints), std::end(polygonPoints) };
    
	boost::polygon::polygon_set_data<int> polygonSet;
	polygonSet.insert(polygon);

	std::vector<Polygon> trapezoids;
	polygonSet.get_trapezoids(trapezoids);
    
    std::cout << "#trapezoids: " << trapezoids.size() << std::endl;
    
    auto index{ 0 };
    
    for (auto const& trapezoid: trapezoids)
    {
        std::cout << "trapezoid " << index << ":" << std::endl;
        auto pointIndex{ 0 };
        
        for (auto const& coord: trapezoid.coords_)
        {
            std::cout << "point " << pointIndex << ": " << coord.x() << "; " << coord.y() << std::endl;
            ++pointIndex;
        }
        
        ++index;
    }
}

Mistakes in "Voronoi Diagram" docs

Hi Andrii,

I would like to point out some mistakes in the documentation for Voronoi Vertex member function signatures (in file: polygon/doc/voronoi_diagram.htm ):

const point_type& x() const should be const coordinate_type& x() const
const point_type& y() const should be const coordinate_type& y() const

excessive includes in isotropy.hpp

Why are there so many includes in isotropy.hpp that aren't required by this header:

//external
#include <cmath>
#include <cstddef>
#include <cstdlib>
#include <vector>
#include <deque>
#include <map>
#include <set>
#include <list>
//#include <iostream>
#include <algorithm>
#include <limits>
#include <iterator>
#include <string>

I just want the types defined here without getting 55k lines of preprocessed headers.

Reduce capacity of polygon_{;45_;90_}set with shrink_to_fit functionality

First, I'd like to thank you for providing such an awesome library.

But I think the method shrink_to_fit() is missing in order to reduce the capacity of any set.

In your documentation, it is mentioned under the clear() command that one should

Use shrink to fit idiom and assign default constructed polygon set to deallocate.

but there is no way of getting the vector to "shrink_to_fit()" because the value() function is declared as const.
So basically, one has no option to deallocate the memory of a huge polygon_set .

An easy fix would be to add a method as follows:

void shrink_to_fit(){
    data_.shrink_to_fit();
}

Voronoi high-precision coordinate system

Configuration:

Boost Version: 1.77.
GCC Version: 11.1.0, 10.2.0, and 9.3.0.

Problem:

While experimenting with voronoi_advanced_tutorial.cpp higher-precision coordinates (i.e. long double and boost::int64_t) I've noticed that the output diagram edges differs from the default coordinate system (double and int) for this particular case. The default produces the correct output, whereas the high-precision one explodes some values. I am using the tutorial as-is and changing only the voronoi builder inputs. I'm creating 3 polygons (4 segments per polygon).

Full Testcase:

The following output images represent the input segments in black, and the output diagram edges in orange. Figure (a) represent the input segments, Figure (b) shows voronoi output with the default coordinate system, whereas Figure (c) shows the output with the high-precision system.

// From voronoi_advanced_tutorial.cpp:
#include <cmath>
#include <cstdio>
#include <string>
// This will work properly only with GCC compiler.
#include <ieee754.h>
typedef long double fpt80;

#include <boost/polygon/polygon.hpp>
#include <boost/polygon/voronoi.hpp>
using namespace boost::polygon;

struct my_ulp_comparison {
  enum Result {
    LESS = -1,
    EQUAL = 0,
    MORE = 1
  };

  Result operator()(fpt80 a, fpt80 b, unsigned int maxUlps) const {
    if (a == b)
      return EQUAL;
    if (a > b) {
      Result res = operator()(b, a, maxUlps);
      if (res == EQUAL) return res;
      return (res == LESS) ? MORE : LESS;
    }
    ieee854_long_double lhs, rhs;
    lhs.d = a;
    rhs.d = b;
    if (lhs.ieee.negative ^ rhs.ieee.negative)
      return lhs.ieee.negative ? LESS : MORE;
    boost::uint64_t le = lhs.ieee.exponent; le =
        (le << 32) + lhs.ieee.mantissa0;
    boost::uint64_t re = rhs.ieee.exponent; re =
        (re << 32) + rhs.ieee.mantissa0;
    if (lhs.ieee.negative) {
      if (le - 1 > re)
        return LESS;
      le = (le == re) ? 0 : 1;
      le = (le << 32) + lhs.ieee.mantissa1;
      re = rhs.ieee.mantissa1;
      return (re + maxUlps < le) ? LESS : EQUAL;
    } else {
      if (le + 1 < re)
        return LESS;
      le = lhs.ieee.mantissa0;
      re = (le == re) ? 0 : 1;
      re = (re << 32) + rhs.ieee.mantissa1;
      return (le + maxUlps < re) ? LESS : EQUAL;
    }
  }
};

struct my_fpt_converter {
  template <typename T>
  fpt80 operator()(const T& that) const {
    return static_cast<fpt80>(that);
  }

  template <std::size_t N>
  fpt80 operator()(const typename detail::extended_int<N> &that) const {
    fpt80 result = 0.0;
    for (std::size_t i = 1; i <= (std::min)((std::size_t)3, that.size()); ++i) {
      if (i != 1)
        result *= static_cast<fpt80>(0x100000000ULL);
      result += that.chunks()[that.size() - i];
    }
    return (that.count() < 0) ? -result : result;
  }
};

// Voronoi diagram traits.
struct my_voronoi_diagram_traits {
  typedef fpt80 coordinate_type;
  typedef voronoi_cell<coordinate_type> cell_type;
  typedef voronoi_vertex<coordinate_type> vertex_type;
  typedef voronoi_edge<coordinate_type> edge_type;
  class vertex_equality_predicate_type {
  public:
    enum { ULPS = 128 };
    bool operator()(const vertex_type &v1, const vertex_type &v2) const {
      return (ulp_cmp(v1.x(), v2.x(), ULPS) == my_ulp_comparison::EQUAL &&
              ulp_cmp(v1.y(), v2.y(), ULPS) == my_ulp_comparison::EQUAL);
    }
  private:
    my_ulp_comparison ulp_cmp;
  };
};

// Voronoi ctype traits for 48-bit signed integer input coordinates.
struct my_voronoi_ctype_traits {
  typedef boost::int64_t int_type;
  typedef detail::extended_int<3> int_x2_type;
  typedef detail::extended_int<3> uint_x2_type;
  typedef detail::extended_int<128> big_int_type;
  typedef fpt80 fpt_type;
  typedef fpt80 efpt_type;
  typedef my_ulp_comparison ulp_cmp_type;
  typedef my_fpt_converter to_fpt_converter_type;
  typedef my_fpt_converter to_efpt_converter_type;
};

// Tescase: The output from the high-precision coordinate system differs from the output with the default coordinate system.
#define HIGH_PRECISION_MODE

#ifdef HIGH_PRECISION_MODE
using output_coordinate_t = fpt80;
using input_coordinate_t = boost::int64_t;
using VD = voronoi_diagram<output_coordinate_t, my_voronoi_diagram_traits>;
using VB = voronoi_builder<input_coordinate_t, my_voronoi_ctype_traits>;
#else
using output_coordinate_t = double;
using input_coordinate_t = int;
using VD = voronoi_diagram<output_coordinate_t>;
using VB = voronoi_builder<input_coordinate_t>;
#endif

using point_t = point_data<input_coordinate_t>;
using segment_t = segment_data<input_coordinate_t>;

static std::ostream &operator<<(std::ostream &os, const VD::vertex_type &pt) {
  return os << "[" << pt.x() << "," << pt.y() << "]";
}

int main() {
  VB vb;
  // Creates segments from a sequence of points (circular).
  auto add_segment_to_vb = [&](const std::vector<point_t> &vec) {
    for (std::size_t i = 0; i < vec.size(); i++) {
      auto p0 = vec[i];
      auto p1 = vec[(i + 1) % vec.size()];
      vb.insert_segment(p0.x(), p0.y(), p1.x(), p1.y());
    }
  };

  add_segment_to_vb(std::vector<point_t>{{0, 0}, {0, 200}, {200, 200}, {200, 0}}); // major rectangle
  add_segment_to_vb(std::vector<point_t>{{20, 20}, {80, 20}, {80, 180}, {20, 180}}); // left inner rectangle
  add_segment_to_vb(std::vector<point_t>{{120, 20}, {180, 20}, {180, 180}, {120, 180}}); // right inner rectangle

  VD vd;
  vb.construct(&vd);

  for (const auto& edge : vd.edges()) {
    if (edge.is_primary() && edge.is_finite())
      std::cout << *edge.vertex0() << " -> " << *edge.vertex1() << std::endl;
  }
  return 0;
}

I've reduce the test case to three and two segments that show different outputs when changing the coordinate system. The "most severe" is with all segments.

Three Segments Testcase

The snippet below show the input segments to voronoi builder. Figure (d) depicts the output from the default coordinate system, whereas Figure (e) from the high-precision.

vb.insert_segment(200, 0, 200, 200);
vb.insert_segment(200, 200, 0, 200);
vb.insert_segment(180, 180, 120, 180);

Two Segments Testcase

Similarly, the snippet shows the input segments, Figure (f) the output from the default system, and Figure (g) from the high-precision.

vb.insert_segment(200, 0, 200, 200);
vb.insert_segment(180, 180, 120, 180);

Remarks

I can't figure out what's the problem and the int_type to ftp_type conversion from the tutorial seems correct. Could you assist investigating possible causes that are causing this behavior?

Signed integer overflow in scan_arbitrary.hpp

Undefined behaviour sanitizer on Linux with Clang complains about this:

When "Unit" is int, a call to validate_scan in Line 148 causes a "std::numeric_limits::min -1" in line 174

atr_ missing from member initialization list

In boost/polygon/transform.hpp, the axis_transformation class has several constructors. atr_ is in the member initializer list for some, but not all. This is causing compiler warnings when I compile with the -Weffc++ flag. It could probably be initialized as atr_(NULL_TRANSFORM) everywhere.

Voronoi C++20 warnings

Compiling the most simple Voronoi code, at Visual Studio 2022 (V143), with C++20, gives a lot warnings.
Most warnings are about using operator '+' or '>' between float and enum.
I'll be glad if this was solved somehow. I would be happy to do a PR, but I need some guidance, because not all warnings lead to the source.

Heres the minimalistic code snippet:

#include <boost/polygon/voronoi.hpp>
#include <boost/geometry/geometries/adapted/boost_polygon.hpp>

using boost::polygon::voronoi_diagram;
typedef voronoi_diagram<double> VD;
typedef boost::polygon::point_data<int64_t> Point;
void stub() {
	VD vd;

	std::vector<Point> points;
	construct_voronoi(points.cbegin(), points.cend(), &vd);
}

Heres the warnings:

Build started...
1>------ Build started: Project: BoostWarnings, Configuration: Release x64 ------
1>stub.cpp
1>C:\Users\User\source\repos\Sandbox\vcpkg\installed\x64-windows\include\boost\polygon\voronoi.hpp(38,38): warning C4244: 'argument': conversion from '__int64' to 'const int', possible loss of data
1>C:\Users\User\source\repos\Sandbox\vcpkg\installed\x64-windows\include\boost\polygon\voronoi.hpp(51): message : see reference to function template instantiation 'unsigned __int64 boost::polygon::insert<boost::polygon::point_data<int64_t>,VB>(const Point &,VB *)' being compiled
1>        with
1>        [
1>            VB=boost::polygon::default_voronoi_builder,
1>            Point=boost::polygon::point_data<int64_t>
1>        ]
1>C:\Users\User\source\repos\Sandbox\vcpkg\installed\x64-windows\include\boost\polygon\voronoi.hpp(101): message : see reference to function template instantiation 'void boost::polygon::insert<PointIterator,boost::polygon::default_voronoi_builder>(const PointIterator,const PointIterator,VB *)' being compiled
1>        with
1>        [
1>            PointIterator=std::_Vector_const_iterator<std::_Vector_val<std::_Simple_types<Point>>>,
1>            VB=boost::polygon::default_voronoi_builder
1>        ]
1>C:\Users\User\source\repos\MagnusEngine\MagnusLib\stub.cpp(11): message : see reference to function template instantiation 'void boost::polygon::construct_voronoi<std::_Vector_const_iterator<std::_Vector_val<std::_Simple_types<_Ty>>>,VD>(const PointIterator,const PointIterator,VD *)' being compiled
1>        with
1>        [
1>            _Ty=Point,
1>            PointIterator=std::_Vector_const_iterator<std::_Vector_val<std::_Simple_types<Point>>>,
1>            VD=VD
1>        ]
1>C:\Users\User\source\repos\Sandbox\vcpkg\installed\x64-windows\include\boost\polygon\voronoi.hpp(38,28): warning C4244: 'argument': conversion from '__int64' to 'const int', possible loss of data
1>C:\Users\User\source\repos\Sandbox\vcpkg\installed\x64-windows\include\boost\polygon\detail\voronoi_predicates.hpp(1417,42): warning C5055: operator '>': deprecated between enumerations and floating-point types
1>C:\Users\User\source\repos\Sandbox\vcpkg\installed\x64-windows\include\boost\polygon\detail\voronoi_predicates.hpp(1332): message : while compiling class template member function 'void boost::polygon::detail::voronoi_predicates<CTT>::lazy_circle_formation_functor<Site,Circle>::sss(const boost::polygon::detail::site_event<int> &,const boost::polygon::detail::site_event<int> &,const boost::polygon::detail::site_event<int> &,boost::polygon::detail::circle_event<double> &)'
1>        with
1>        [
1>            CTT=boost::polygon::detail::voronoi_ctype_traits<boost::polygon::detail::int32>,
1>            Site=boost::polygon::detail::site_event<int>,
1>            Circle=boost::polygon::detail::circle_event<double>
1>        ]
1>C:\Users\User\source\repos\Sandbox\vcpkg\installed\x64-windows\include\boost\polygon\detail\voronoi_predicates.hpp(1498): message : see reference to function template instantiation 'void boost::polygon::detail::voronoi_predicates<CTT>::lazy_circle_formation_functor<Site,Circle>::sss(const boost::polygon::detail::site_event<int> &,const boost::polygon::detail::site_event<int> &,const boost::polygon::detail::site_event<int> &,boost::polygon::detail::circle_event<double> &)' being compiled
1>        with
1>        [
1>            CTT=boost::polygon::detail::voronoi_ctype_traits<boost::polygon::detail::int32>,
1>            Site=boost::polygon::detail::site_event<int>,
1>            Circle=boost::polygon::detail::circle_event<double>
1>        ]
1>C:\Users\User\source\repos\Sandbox\vcpkg\installed\x64-windows\include\boost\polygon\detail\voronoi_predicates.hpp(1526): message : see reference to class template instantiation 'boost::polygon::detail::voronoi_predicates<CTT>::lazy_circle_formation_functor<Site,Circle>' being compiled
1>        with
1>        [
1>            CTT=boost::polygon::detail::voronoi_ctype_traits<boost::polygon::detail::int32>,
1>            Site=boost::polygon::detail::site_event<int>,
1>            Circle=boost::polygon::detail::circle_event<double>
1>        ]
1>C:\Users\User\source\repos\Sandbox\vcpkg\installed\x64-windows\include\boost\polygon\voronoi_builder.hpp(509): message : see reference to class template instantiation 'boost::polygon::detail::voronoi_predicates<CTT>::circle_formation_predicate<boost::polygon::detail::site_event<int>,boost::polygon::detail::circle_event<double>,boost::polygon::detail::voronoi_predicates<CTT>::circle_existence_predicate<Site>,boost::polygon::detail::voronoi_predicates<CTT>::lazy_circle_formation_functor<Site,Circle>>' being compiled
1>        with
1>        [
1>            CTT=boost::polygon::detail::voronoi_ctype_traits<boost::polygon::detail::int32>,
1>            Site=boost::polygon::detail::site_event<int>,
1>            Circle=boost::polygon::detail::circle_event<double>
1>        ]
1>C:\Users\User\source\repos\Sandbox\vcpkg\installed\x64-windows\include\boost\polygon\voronoi.hpp(102): message : see reference to class template instantiation 'boost::polygon::voronoi_builder<boost::polygon::detail::int32,boost::polygon::detail::voronoi_ctype_traits<boost::polygon::detail::int32>,boost::polygon::detail::voronoi_predicates<CTT>>' being compiled
1>        with
1>        [
1>            CTT=boost::polygon::detail::voronoi_ctype_traits<boost::polygon::detail::int32>
1>        ]
1>C:\Users\User\source\repos\Sandbox\vcpkg\installed\x64-windows\include\boost\polygon\detail\voronoi_predicates.hpp(1418,42): warning C5055: operator '>': deprecated between enumerations and floating-point types
1>C:\Users\User\source\repos\Sandbox\vcpkg\installed\x64-windows\include\boost\polygon\detail\voronoi_predicates.hpp(1419,50): warning C5055: operator '>': deprecated between enumerations and floating-point types
1>C:\Users\User\source\repos\Sandbox\vcpkg\installed\x64-windows\include\boost\polygon\detail\voronoi_predicates.hpp(1214,41): warning C5055: operator '>': deprecated between enumerations and floating-point types
1>C:\Users\User\source\repos\Sandbox\vcpkg\installed\x64-windows\include\boost\polygon\detail\voronoi_predicates.hpp(1138): message : while compiling class template member function 'void boost::polygon::detail::voronoi_predicates<CTT>::lazy_circle_formation_functor<Site,Circle>::pss(const boost::polygon::detail::site_event<int> &,const boost::polygon::detail::site_event<int> &,const boost::polygon::detail::site_event<int> &,int,boost::polygon::detail::circle_event<double> &)'
1>        with
1>        [
1>            CTT=boost::polygon::detail::voronoi_ctype_traits<boost::polygon::detail::int32>,
1>            Site=boost::polygon::detail::site_event<int>,
1>            Circle=boost::polygon::detail::circle_event<double>
1>        ]
1>C:\Users\User\source\repos\Sandbox\vcpkg\installed\x64-windows\include\boost\polygon\detail\voronoi_predicates.hpp(1472): message : see reference to function template instantiation 'void boost::polygon::detail::voronoi_predicates<CTT>::lazy_circle_formation_functor<Site,Circle>::pss(const boost::polygon::detail::site_event<int> &,const boost::polygon::detail::site_event<int> &,const boost::polygon::detail::site_event<int> &,int,boost::polygon::detail::circle_event<double> &)' being compiled
1>        with
1>        [
1>            CTT=boost::polygon::detail::voronoi_ctype_traits<boost::polygon::detail::int32>,
1>            Site=boost::polygon::detail::site_event<int>,
1>            Circle=boost::polygon::detail::circle_event<double>
1>        ]
1>C:\Users\User\source\repos\Sandbox\vcpkg\installed\x64-windows\include\boost\polygon\detail\voronoi_predicates.hpp(1215,41): warning C5055: operator '>': deprecated between enumerations and floating-point types
1>C:\Users\User\source\repos\Sandbox\vcpkg\installed\x64-windows\include\boost\polygon\detail\voronoi_predicates.hpp(1216,49): warning C5055: operator '>': deprecated between enumerations and floating-point types
1>C:\Users\User\source\repos\Sandbox\vcpkg\installed\x64-windows\include\boost\polygon\detail\voronoi_predicates.hpp(1316,41): warning C5055: operator '>': deprecated between enumerations and floating-point types
1>C:\Users\User\source\repos\Sandbox\vcpkg\installed\x64-windows\include\boost\polygon\detail\voronoi_predicates.hpp(1317,41): warning C5055: operator '>': deprecated between enumerations and floating-point types
1>C:\Users\User\source\repos\Sandbox\vcpkg\installed\x64-windows\include\boost\polygon\detail\voronoi_predicates.hpp(1318,49): warning C5055: operator '>': deprecated between enumerations and floating-point types
1>C:\Users\User\source\repos\Sandbox\vcpkg\installed\x64-windows\include\boost\polygon\detail\voronoi_predicates.hpp(1124,44): warning C5055: operator '>': deprecated between enumerations and floating-point types
1>C:\Users\User\source\repos\Sandbox\vcpkg\installed\x64-windows\include\boost\polygon\detail\voronoi_predicates.hpp(1051): message : while compiling class template member function 'void boost::polygon::detail::voronoi_predicates<CTT>::lazy_circle_formation_functor<Site,Circle>::pps(const boost::polygon::detail::site_event<int> &,const boost::polygon::detail::site_event<int> &,const boost::polygon::detail::site_event<int> &,int,boost::polygon::detail::circle_event<double> &)'
1>        with
1>        [
1>            CTT=boost::polygon::detail::voronoi_ctype_traits<boost::polygon::detail::int32>,
1>            Site=boost::polygon::detail::site_event<int>,
1>            Circle=boost::polygon::detail::circle_event<double>
1>        ]
1>C:\Users\User\source\repos\Sandbox\vcpkg\installed\x64-windows\include\boost\polygon\detail\voronoi_predicates.hpp(1460): message : see reference to function template instantiation 'void boost::polygon::detail::voronoi_predicates<CTT>::lazy_circle_formation_functor<Site,Circle>::pps(const boost::polygon::detail::site_event<int> &,const boost::polygon::detail::site_event<int> &,const boost::polygon::detail::site_event<int> &,int,boost::polygon::detail::circle_event<double> &)' being compiled
1>        with
1>        [
1>            CTT=boost::polygon::detail::voronoi_ctype_traits<boost::polygon::detail::int32>,
1>            Site=boost::polygon::detail::site_event<int>,
1>            Circle=boost::polygon::detail::circle_event<double>
1>        ]
1>C:\Users\User\source\repos\Sandbox\vcpkg\installed\x64-windows\include\boost\polygon\detail\voronoi_predicates.hpp(1125,44): warning C5055: operator '>': deprecated between enumerations and floating-point types
1>C:\Users\User\source\repos\Sandbox\vcpkg\installed\x64-windows\include\boost\polygon\detail\voronoi_predicates.hpp(1126,52): warning C5055: operator '>': deprecated between enumerations and floating-point types
1>C:\Users\User\source\repos\Sandbox\vcpkg\installed\x64-windows\include\boost\polygon\detail\voronoi_predicates.hpp(1037,44): warning C5055: operator '>': deprecated between enumerations and floating-point types
1>C:\Users\User\source\repos\Sandbox\vcpkg\installed\x64-windows\include\boost\polygon\detail\voronoi_predicates.hpp(998): message : while compiling class template member function 'void boost::polygon::detail::voronoi_predicates<CTT>::lazy_circle_formation_functor<Site,Circle>::ppp(const boost::polygon::detail::site_event<int> &,const boost::polygon::detail::site_event<int> &,const boost::polygon::detail::site_event<int> &,boost::polygon::detail::circle_event<double> &)'
1>        with
1>        [
1>            CTT=boost::polygon::detail::voronoi_ctype_traits<boost::polygon::detail::int32>,
1>            Site=boost::polygon::detail::site_event<int>,
1>            Circle=boost::polygon::detail::circle_event<double>
1>        ]
1>C:\Users\User\source\repos\Sandbox\vcpkg\installed\x64-windows\include\boost\polygon\detail\voronoi_predicates.hpp(1455): message : see reference to function template instantiation 'void boost::polygon::detail::voronoi_predicates<CTT>::lazy_circle_formation_functor<Site,Circle>::ppp(const boost::polygon::detail::site_event<int> &,const boost::polygon::detail::site_event<int> &,const boost::polygon::detail::site_event<int> &,boost::polygon::detail::circle_event<double> &)' being compiled
1>        with
1>        [
1>            CTT=boost::polygon::detail::voronoi_ctype_traits<boost::polygon::detail::int32>,
1>            Site=boost::polygon::detail::site_event<int>,
1>            Circle=boost::polygon::detail::circle_event<double>
1>        ]
1>C:\Users\User\source\repos\Sandbox\vcpkg\installed\x64-windows\include\boost\polygon\detail\voronoi_predicates.hpp(1038,44): warning C5055: operator '>': deprecated between enumerations and floating-point types
1>C:\Users\User\source\repos\Sandbox\vcpkg\installed\x64-windows\include\boost\polygon\detail\voronoi_predicates.hpp(1039,52): warning C5055: operator '>': deprecated between enumerations and floating-point types
1>Done building project "BoostWarnings.vcxproj".
========== Build: 1 succeeded, 0 failed, 0 up-to-date, 0 skipped ==========

#include <boost/polygon/segment_utils.hpp> gives errors

This header doesn't seem to be valid on its own, it only works if included after <boost/polygon/polygon.hpp> has been included.

Either this should be documented very prominently (it doesn't seem to be) or the header should be self-sufficient and include <boost/polygon/polygon.hpp> itself, or give a clear #error explaining that the other header needs to be included first.

sorry, wrong project. Please delete the issue.

voronoi generator could create empty cells

The voronoi builder calls voronoi_diagram::_build()
to remove degenerate edges and vertices. Once this is done, Voronoi cells are sometimes left, which reference no edge. These invalid cells should be removed as well by the same method.

missing edges in Voronoi diagram

This is a follow-up on https://svn.boost.org/trac10/ticket/12707
where a smallest possible polygon has been distilled:

    {       0, 10000000},
    {  700000,        1}, // it has to be 1, higher number, zero or -1 work.
    {  700000,  9000000},
    { 9100000,  9000000},
    { 9100000,        0},
    {10000000, 10000000}

I have rounded the coordinates to nice numbers for easier debugging.

Error in voronoi_diagram.hpp with recent Microsoft compiler

The current MS Visual Studio (v16.6.0) compiler reports an error in voronoi_diagram.hpp:

boost/polygon/voronoi_diagram.hpp(266,17): error C7626: unnamed class used in typedef name cannot declare members other than non-static data members, member enumerations, or member classe

See https://docs.microsoft.com/en-us/cpp/overview/cpp-conformance-improvements?view=vs-2019#unnamed-classes-in-typedef-declarations

As suggested in the link above, giving an arbitrary name to the struct would eliminate the error.

boost::polygon::detail::resize creates invalid polygons on expansion

I have a regular polygon that is expanded via functions in boost::polygon / boost::polygon::polygon_set_data resize().

Expanding a polygon should result in a new outline (yellow) which nowhere touches the original polygon (green) and which nowhere comes closer to the original polygon outline than the expansion size:

Unfortunately this is not the result I get with boost::polygon. Here the new ouline cuts the original one:

In other words: the result is damaged and wrong even to its own specification. This happens with Boost 1.77.

[voronoi] The diagram has an infinite segment that origin point inside in closed polygon.

Boost version 1.75.0.
Created a voronoi diagram for a given closed polygon. The diagram has an infinite segment(ray) that origin point inside in polygon. As far as I understand, such cases should not be for closed polygons and second point of this segment must on the perimeter. Also in this case, two segments of the diagram intersect.
Source polygon:
Perimeter.txt
Diagram (Blue segments are polygon. Black segments are primary. Green segments are secondary.):

Infinity segment (Blue segments are polygon. Infinite segment(ray) is red. Black segments are primary segments inside polygon and not touching perimeter.):

Segments intersect (Blue segments are polygon. Black segments are primary. Green segments are secondary.):

boost::polygon::detail::resize() gives wrong result when expanding a shape

I have some polygons which are expanded by using function boost::polygon::detail::resize(). What I would expect to get is a result where the new outline of the shape is bigger than the old one and ecause of that never touches the new one:

https://i.ibb.co/BqDKGtd/clip-ok.png

Here the green oultine is the original while the yellow one is the expected result.

But what I get when I use the related boost function via a call to

boost::polygon::polygon_set_data<int> result;
result.resize();

is something like that:

https://i.ibb.co/ftPNTCV/clip-boost.png

As one can see, the expanded shape follows the original one way too much and therefore results in a new shape, which overlaps the old one at some points.

sorry, wrong project. Please delete the issue.

polygon/detail/voronoi_ctypes.h does not include <algorithm> but uses std::min ?

Hi,
Running the Boost 1.69 polygon test on VxWorks 7, four voronoi-related tests fail to compile due to the use of std::min in voronoi_ctypes.hpp, which does not include the

<algorithm>

header.

Adding

#include <algorithm>

after the

#include <vector>

line appears to fix the problem.
This is using the Dinkum-derived C++ libraries for VxWorks, and building with clang 7.0.0.1.

I'm guessing that in other environments

<algorithm>

is getting included somehow, but is
there a reason that voronoi_ctypes.hpp should not include it directly?

Use-after-free on 64-bit coordinates

#include <boost/polygon/polygon.hpp>
#include <iterator>
#include <cstdint>

namespace bp = boost::polygon;

typedef int64_t Coord;
typedef bp::point_data<Coord> Vec2;
typedef bp::polygon_data<Coord> Polygon;
typedef bp::polygon_set_data<Coord> PolySet;

int main()
{
    const Vec2 pts[] = {
        Vec2(0,0),
        Vec2(-219215130788,1374389535),
        Vec2(-195163313930,204784040673), // BAD
        //Vec2(-195163313929,204784040673), // OK
    };

    Polygon poly;
    set_points(poly, std::cbegin(pts), std::cend(pts));
    PolySet pset;
    pset.insert(poly);
    std::vector<Polygon> c;
    pset.get_trapezoids(c);
}

Compile with -fsantitize=address to see the use-after-free error, although my glibc complains even without it.

Note that these coordinates are all less than 40 bits.

The suggestions in #36 (use gmp_override.hpp) and #39 (update 64-bit coordinate_traits) do not help.

What does help is changing the last line of evalAtXforYlazy() to return roundl(evalAtXforYret). I do not understand the code well enough to say whether this is a good idea in general.

voronoi_diagram provides no non-const acccessors to cells, edges and vertices

voronoi_diagram provides const methods cells(), edges() and vertices(). Having no way to access non-const variants of these members makes impossible to set color of cells, edges or vertices without resorting to const_cast.

Please either provide non-const accessors.

I understand that it may not be a good idea to give non-const access to these voronoi_diagram elements. Alternatively, possibly a better solution would be to add set_color() methods to voronoi_diagram to possibly encapsulate the const_cast.

transformation::operator+= is broken

The concatentation operator of the transformation object is broken. Simple test code:

#include <iostream>

#include <boost/polygon/polygon.hpp>

namespace bp = boost::polygon;

int main() {
    bp::transformation<int> xform1(bp::axis_transformation::ATR::NULL_TRANSFORM);
    bp::transformation<int> xform2(bp::axis_transformation::ATR::ROTATE_LEFT);

    bp::point_data<int> shift;
    xform1.get_translation(shift);

    std::cout << "before: " << shift.x() << ", " << shift.y() << std::endl;
    xform1 += xform2;
    xform1.get_translation(shift);
    std::cout << "after: " << shift.x() << ", " << shift.y() << std::endl;
}

The output for me is:

before: 0, 0
after: 32529, 852967680

Which is wrong, as the "after" values should be (0, 0) as well. If you look at the implementation in transform.hpp, it's seriously messed up:

  // concatenate this with that
  const transformation& operator+=(const transformation& tr) {
    coordinate_type x, y;
    transformation<coordinate_type> inv = inverse();
    inv.transform(x, y);
    p_.set(HORIZONTAL, p_.get(HORIZONTAL) + x);
    p_.set(VERTICAL, p_.get(VERTICAL) + y);
    // concatenate axis transforms
    atr_ += tr.atr_;
    return *this;
  }

variables x and y are uninitialized, leading to garbage values.
the formula makes no sense; the translation of the tr object is not even used.

This seems like such an essential function to be screwed up. Did it just happened that this operator is not used anywhere else in the project?

segfault in polygon_set_data<int>::get

The following program crashes with a segmentation fault inside the get() call. I've tested against 1.65, 1.72, and current master. I'm pretty sure that this usage falls inside the API contract, but perhaps I'm missing something?

#include <boost/polygon/polygon.hpp>

int main(int argc, char **argv) {
    const boost::polygon::point_data<int> triangles[][3] = {
        {{-7273739,1362950}, {-7273144,1362356}, {-3077455,-2833333}},
        {{-490017,-3840545}, {-2888380,-1442182}, {-6168936,1838374}},
        {{-3078718,-2832071}, {-3078274,-2832514}, {-2288161,-2042401}},
    };

    boost::polygon::polygon_set_data<int> polygon_set;
    polygon_set.insert(boost::polygon::polygon_data<int>(std::begin(triangles[0]), std::end(triangles[0])));
    polygon_set.insert(boost::polygon::polygon_data<int>(std::begin(triangles[1]), std::end(triangles[1])));
    polygon_set.insert(boost::polygon::polygon_data<int>(std::begin(triangles[2]), std::end(triangles[2])));

    std::vector<boost::polygon::polygon_with_holes_data<int>> output;
    polygon_set.get(output);
}

Aboated at boost::polygon::polygon_set_data<long long>::get()

Executing this code aborted in version 1.66.0.
I confirmed that aborted in version 1.79.0.
Aborted when run in debug mode.

#include <stdio.h>
#include <stdlib.h>
#include <vector>

#include <boost/polygon/polygon.hpp>

namespace gtl = boost::polygon;
int main(int argc, char* argv[])
{
	gtl::polygon_set_data<long long>* polyset = new gtl::polygon_set_data<long long>;

	{
		gtl::polygon_data<long long>* ppoly = new gtl::polygon_data<long long>;
		std::vector<gtl::polygon_traits<gtl::polygon_data<long long>>::point_type> vpoint;
		vpoint.reserve(4);
		vpoint.push_back(gtl::polygon_traits<gtl::polygon_data<long long>>::point_type(346862000, 438294000));
		vpoint.push_back(gtl::polygon_traits<gtl::polygon_data<long long>>::point_type(346533000, 438337000));
		vpoint.push_back(gtl::polygon_traits<gtl::polygon_data<long long>>::point_type(353343000, 490071000));
		vpoint.push_back(gtl::polygon_traits<gtl::polygon_data<long long>>::point_type(353673000, 490027000));
		set_points(*ppoly, vpoint.begin(), vpoint.end());
		(*polyset).insert(*ppoly);
		delete ppoly;
	}


	{
		gtl::polygon_data<long long>* ppoly = new gtl::polygon_data<long long>;
		std::vector<gtl::polygon_traits<gtl::polygon_data<long long>>::point_type> vpoint;
		vpoint.reserve(4);
		vpoint.push_back(gtl::polygon_traits<gtl::polygon_data<long long>>::point_type(353626000, 489671000));
		vpoint.push_back(gtl::polygon_traits<gtl::polygon_data<long long>>::point_type(353176000, 489730000));
		vpoint.push_back(gtl::polygon_traits<gtl::polygon_data<long long>>::point_type(353223000, 490087000));
		vpoint.push_back(gtl::polygon_traits<gtl::polygon_data<long long>>::point_type(353673000, 490027000));
		set_points(*ppoly, vpoint.begin(), vpoint.end());
		(*polyset).insert(*ppoly);
		delete ppoly;
	}

	{
		gtl::polygon_data<long long>* ppoly = new gtl::polygon_data<long long>;
		std::vector<gtl::polygon_traits<gtl::polygon_data<long long>>::point_type> vpoint;
		vpoint.reserve(4);
		vpoint.push_back(gtl::polygon_traits<gtl::polygon_data<long long>>::point_type(354911000, 489643000));
		vpoint.push_back(gtl::polygon_traits<gtl::polygon_data<long long>>::point_type(354791000, 489659000));
		vpoint.push_back(gtl::polygon_traits<gtl::polygon_data<long long>>::point_type(354838000, 490016000));
		vpoint.push_back(gtl::polygon_traits<gtl::polygon_data<long long>>::point_type(354958000, 490000000));
		set_points(*ppoly, vpoint.begin(), vpoint.end());
		(*polyset).insert(*ppoly);
		delete ppoly;
	}

	{
		gtl::polygon_data<long long>* ppoly = new gtl::polygon_data<long long>;
		std::vector<gtl::polygon_traits<gtl::polygon_data<long long>>::point_type> vpoint;
		vpoint.reserve(4);
		vpoint.push_back(gtl::polygon_traits<gtl::polygon_data<long long>>::point_type(353296000, 489714000));
		vpoint.push_back(gtl::polygon_traits<gtl::polygon_data<long long>>::point_type(353176000, 489730000));
		vpoint.push_back(gtl::polygon_traits<gtl::polygon_data<long long>>::point_type(353223000, 490087000));
		vpoint.push_back(gtl::polygon_traits<gtl::polygon_data<long long>>::point_type(353343000, 490071000));
		set_points(*ppoly, vpoint.begin(), vpoint.end());
		(*polyset).insert(*ppoly);
		delete ppoly;
	}

	std::vector<gtl::polygon_data<long long>> result;
	polyset->get(result);

	delete 	polyset;


	return 0;
}

This is the call stack and The value of the variable when aborting.

The call stack

 	msvcp140d.dll!00007ffb3f51f7e6()	不明
>	boosttest.exe!std::_Debug_lt_pred<boost::polygon::scanline_base<__int64>::less_half_edge & __ptr64,std::pair<boost::polygon::point_data<__int64>,boost::polygon::point_data<__int64> > const & __ptr64,std::pair<boost::polygon::point_data<__int64>,boost::polygon::point_data<__int64> > const & __ptr64>(boost::polygon::scanline_base<__int64>::less_half_edge & _Pred, const std::pair<boost::polygon::point_data<__int64>,boost::polygon::point_data<__int64> > & _Left, const std::pair<boost::polygon::point_data<__int64>,boost::polygon::point_data<__int64> > & _Right, const wchar_t * _File, unsigned int _Line) 行 1064	C++
 	boosttest.exe!std::_Tree<std::_Tmap_traits<std::pair<boost::polygon::point_data<__int64>,boost::polygon::point_data<__int64> >,std::vector<std::pair<int,int>,std::allocator<std::pair<int,int> > >,boost::polygon::scanline_base<__int64>::less_half_edge,std::allocator<std::pair<std::pair<boost::polygon::point_data<__int64>,boost::polygon::point_data<__int64> > const ,std::vector<std::pair<int,int>,std::allocator<std::pair<int,int> > > > >,0> >::_Insert_nohint<std::pair<std::pair<boost::polygon::point_data<__int64>,boost::polygon::point_data<__int64> > const ,std::vector<std::pair<int,int>,std::allocator<std::pair<int,int> > > > & __ptr64,std::_Tree_node<std::pair<std::pair<boost::polygon::point_data<__int64>,boost::polygon::point_data<__int64> > const ,std::vector<std::pair<int,int>,std::allocator<std::pair<int,int> > > >,void * __ptr64> * __ptr64>(bool _Leftish, std::pair<std::pair<boost::polygon::point_data<__int64>,boost::polygon::point_data<__int64> > const ,std::vector<std::pair<int,int>,std::allocator<std::pair<int,int> > > > & _Val, std::_Tree_node<std::pair<std::pair<boost::polygon::point_data<__int64>,boost::polygon::point_data<__int64> > const ,std::vector<std::pair<int,int>,std::allocator<std::pair<int,int> > > >,void *> * _Newnode) 行 1742	C++
 	boosttest.exe!std::_Tree<std::_Tmap_traits<std::pair<boost::polygon::point_data<__int64>,boost::polygon::point_data<__int64> >,std::vector<std::pair<int,int>,std::allocator<std::pair<int,int> > >,boost::polygon::scanline_base<__int64>::less_half_edge,std::allocator<std::pair<std::pair<boost::polygon::point_data<__int64>,boost::polygon::point_data<__int64> > const ,std::vector<std::pair<int,int>,std::allocator<std::pair<int,int> > > > >,0> >::emplace<std::pair<std::pair<boost::polygon::point_data<__int64>,boost::polygon::point_data<__int64> >,std::vector<std::pair<int,int>,std::allocator<std::pair<int,int> > > > & __ptr64>(std::pair<std::pair<boost::polygon::point_data<__int64>,boost::polygon::point_data<__int64> >,std::vector<std::pair<int,int>,std::allocator<std::pair<int,int> > > > & <_Val_0>) 行 962	C++
 	boosttest.exe!std::map<std::pair<boost::polygon::point_data<__int64>,boost::polygon::point_data<__int64> >,std::vector<std::pair<int,int>,std::allocator<std::pair<int,int> > >,boost::polygon::scanline_base<__int64>::less_half_edge,std::allocator<std::pair<std::pair<boost::polygon::point_data<__int64>,boost::polygon::point_data<__int64> > const ,std::vector<std::pair<int,int>,std::allocator<std::pair<int,int> > > > > >::insert<std::pair<std::pair<boost::polygon::point_data<__int64>,boost::polygon::point_data<__int64> >,std::vector<std::pair<int,int>,std::allocator<std::pair<int,int> > > > & __ptr64,void>(std::pair<std::pair<boost::polygon::point_data<__int64>,boost::polygon::point_data<__int64> >,std::vector<std::pair<int,int>,std::allocator<std::pair<int,int> > > > & _Val) 行 212	C++
 	boosttest.exe!boost::polygon::scanline<__int64,int,std::vector<int,std::allocator<int> > >::insert_new_edges_into_scanline() 行 1202	C++
 	boosttest.exe!boost::polygon::scanline<__int64,int,std::vector<int,std::allocator<int> > >::scan<boost::polygon::polygon_set_data<__int64>,boost::polygon::arbitrary_boolean_op<__int64>::boolean_output_functor<boost::polygon::polygon_set_data<__int64>,std::vector<int,std::allocator<int> >,0>,std::_Vector_iterator<std::_Vector_val<std::_Simple_types<std::pair<std::pair<boost::polygon::point_data<__int64>,boost::polygon::point_data<__int64> >,std::pair<int,int> > > > > >(boost::polygon::polygon_set_data<__int64> & result, boost::polygon::arbitrary_boolean_op<__int64>::boolean_output_functor<boost::polygon::polygon_set_data<__int64>,std::vector<int,std::allocator<int> >,0> rf, std::_Vector_iterator<std::_Vector_val<std::_Simple_types<std::pair<std::pair<boost::polygon::point_data<__int64>,boost::polygon::point_data<__int64> >,std::pair<int,int> > > > > begin, std::_Vector_iterator<std::_Vector_val<std::_Simple_types<std::pair<std::pair<boost::polygon::point_data<__int64>,boost::polygon::point_data<__int64> >,std::pair<int,int> > > > > end) 行 1222	C++
 	boosttest.exe!boost::polygon::arbitrary_boolean_op<__int64>::execute<boost::polygon::polygon_set_data<__int64>,std::_Vector_const_iterator<std::_Vector_val<std::_Simple_types<std::pair<std::pair<boost::polygon::point_data<__int64>,boost::polygon::point_data<__int64> >,int> > > >,std::_Vector_const_iterator<std::_Vector_val<std::_Simple_types<std::pair<std::pair<boost::polygon::point_data<__int64>,boost::polygon::point_data<__int64> >,int> > > > >(boost::polygon::polygon_set_data<__int64> & result, std::_Vector_const_iterator<std::_Vector_val<std::_Simple_types<std::pair<std::pair<boost::polygon::point_data<__int64>,boost::polygon::point_data<__int64> >,int> > > > b1, std::_Vector_const_iterator<std::_Vector_val<std::_Simple_types<std::pair<std::pair<boost::polygon::point_data<__int64>,boost::polygon::point_data<__int64> >,int> > > > e1, std::_Vector_const_iterator<std::_Vector_val<std::_Simple_types<std::pair<std::pair<boost::polygon::point_data<__int64>,boost::polygon::point_data<__int64> >,int> > > > b2, std::_Vector_const_iterator<std::_Vector_val<std::_Simple_types<std::pair<std::pair<boost::polygon::point_data<__int64>,boost::polygon::point_data<__int64> >,int> > > > e2, int op) 行 2627	C++
 	boosttest.exe!boost::polygon::polygon_set_data<__int64>::clean() 行 37	C++
 	boosttest.exe!boost::polygon::polygon_set_data<__int64>::get_fracture<std::vector<boost::polygon::polygon_data<__int64>,std::allocator<boost::polygon::polygon_data<__int64> > >,boost::polygon::polygon_concept>(std::vector<boost::polygon::polygon_data<__int64>,std::allocator<boost::polygon::polygon_data<__int64> > > & container, bool fracture_holes, boost::polygon::polygon_concept __formal) 行 793	C++
 	boosttest.exe!boost::polygon::polygon_set_data<__int64>::get_dispatch<std::vector<boost::polygon::polygon_data<__int64>,std::allocator<boost::polygon::polygon_data<__int64> > > >(std::vector<boost::polygon::polygon_data<__int64>,std::allocator<boost::polygon::polygon_data<__int64> > > & output, boost::polygon::polygon_concept tag) 行 785	C++
 	boosttest.exe!boost::polygon::polygon_set_data<__int64>::get<std::vector<boost::polygon::polygon_data<__int64>,std::allocator<boost::polygon::polygon_data<__int64> > > >(std::vector<boost::polygon::polygon_data<__int64>,std::allocator<boost::polygon::polygon_data<__int64> > > & output) 行 237	C++
 	boosttest.exe!main(int argc, char * * argv) 行 70	C++

The value of the variable

-		_Left	({coords_=0x000001ece6044590 {354838000, 490016000} }, {coords_=0x000001ece60445a0 {354958000, 490000000} })	const std::pair<boost::polygon::point_data<__int64>,boost::polygon::point_data<__int64> > &
+		first	{coords_=0x000001ece6044590 {354838000, 490016000} }	boost::polygon::point_data<__int64>
+		second	{coords_=0x000001ece60445a0 {354958000, 490000000} }	boost::polygon::point_data<__int64>
+		[未加工ビュー]	{first={coords_=0x000001ece6044590 {354838000, 490016000} } second={coords_=0x000001ece60445a0 {354958000, ...} } }	const std::pair<boost::polygon::point_data<__int64>,boost::polygon::point_data<__int64> >
		_Line	1744	unsigned int
-		_Pred	{x_=0x0000008e9d53d428 {354838000} justBefore_=0x0000008e9d53d438 {0} pack_=0x0000008e9d53d440 {evalAtXforYret=...} }	boost::polygon::scanline_base<__int64>::less_half_edge &
+		x_	0x0000008e9d53d428 {354838000}	__int64 *
+		justBefore_	0x0000008e9d53d438 {0}	int *
+		pack_	0x0000008e9d53d440 {evalAtXforYret=0.0000000000000000 evalAtXforYxIn=0.0000000000000000 evalAtXforYx1=...}	boost::polygon::scanline_base<__int64>::evalAtXforYPack *
-		_Right	({coords_=0x000001ece6035b30 {353296040, 489714261} }, {coords_=0x000001ece6035b40 {353343000, 490071000} })	const std::pair<boost::polygon::point_data<__int64>,boost::polygon::point_data<__int64> > &
+		first	{coords_=0x000001ece6035b30 {353296040, 489714261} }	boost::polygon::point_data<__int64>
+		second	{coords_=0x000001ece6035b40 {353343000, 490071000} }	boost::polygon::point_data<__int64>
+		[未加工ビュー]	{first={coords_=0x000001ece6035b30 {353296040, 489714261} } second={coords_=0x000001ece6035b40 {353343000, ...} } }	const std::pair<boost::polygon::point_data<__int64>,boost::polygon::point_data<__int64> >

Please investigate the cause of the abort.

polygon_set_data<T>::resize() with holes when holes position is not known?

Hi,

I have a set of polygon data which consist of several arrays of coordinates which form the polygons. I resize them with polygon_set_data::resize() using boost::polygon::polygon_with_holes_data. Unfortunately there is a problem:

boost::polygon::polygon_with_holes_data expects a clear data structure: an outline polygon in one part of the structure and the polygons in a different one. But my input coordinate arrays do not make such definitions, they are just sets of polygons where it is known they belong together. So as an example: let's say I have two arrays of polygon data, one describes a triangle and one a rectangle. For these two shapes there is no clear definition which is the total outline and which is the hole. This definition is made implicitly by the size of these shapes and their location: so when the triangle is smaller than the rectangle and located completely within the rectangle, the triangle is the hole.

So my question is: is there a way to resize() polygons without that clear outline/holes structure? Means when outline and hole are swapped or mixed? Or are there any functions in boost::polygon which give the possibility to sort my input data by outline and holes?

Thanks!

Boost minkowski on mac and windows

Hi,

I never had mac computer or ran mac operating system.

But I need to compike boost minkowski example https://www.boost.org/doc/libs/1_65_1/boost/polygon/detail/minkowski.hpp that must run on both operating systems.

Currently I installed boost on windows a d compiled this example using .bat file which works.
But I have no understading how to do the same for mac.

Make `polygon_90_set_view::value()` public

Is there a reason why polygon_90_set_view::value() is not public, in contrast with similar value() methods on polygon_45_set_view and boost::polygon_set_view?

Making it a public method would make it possible to write more generic client code. Suppose for example I have two polygon sets of a certain (unknown) type, A and B. Then, the following code instantiates a polygon set of the correct type, but only in case the set view resulting from the union operation is not a boost::polygon_90_set_view.

auto result{(A | B).value()};

As far as I can see, there is no fundamental reason why polygon_90_set_view::value() can not be made publicly visible.

Basic tutorial example

Not sure whether this is the right place to note that the Boost website contains outdated info.

The basic tutorial contained a bug, which has been solved in a6718a0:
See also https://github.com/boostorg/polygon/blob/develop/example/voronoi_basic_tutorial.cpp

However, the boost tutorial page still lists the old buggy tutorial.

polygon::intersect(rectA, rectB, consider_touch) doesn't actually pass consider_touch to the intersection-check

function is:
boost::polygon::intersect(T1& a, const T2& b, bool consider_touch = true)

docs on the function:
https://www.boost.org/doc/libs/1_64_0/libs/polygon/doc/gtl_rectangle_concept.htm

bug where the bool isn't passed to the actual intersection-check is:

polygon/include/boost/polygon/rectangle_concept.hpp

Line 645 in 8ba35b5

if(intersects(rectangle, b)) {

fix:
change
if(intersects(rectangle, b)) {
to:
if(intersects(rectangle, b, consider_touch)) {

boost::polygon::area returns 0 area

Hi,

I am trying to the area of small rectangular polygon. For some reason boost::polygon::area return 0. Code sample is below

#include <boost/polygon/polygon.hpp>
#include <boost/polygon/rectangle_data.hpp>
#include <boost/polygon/polygon_set_data.hpp>
#include <boost/polygon/polygon_data.hpp>
#include <boost/version.hpp>
#include <boost/format.hpp>

template<typename T>
auto make_rect(T x1, T y1, T x2, T y2) {
    auto r = boost::polygon::rectangle_data(x1, y1, x2, y2);
    boost::polygon::polygon_data<T> p;
    boost::polygon::assign(p, r);
    return p;
}

int main(int argc, char **argv) {
    std::cout << BOOST_LIB_VERSION << std::endl;
    boost::polygon::polygon_set_data<double> poly, poly1;
    poly.insert(make_rect(0.003065, 0.0007, 0.0034, 0.0009525));
    std::cout << boost::format("%e") % boost::polygon::area(poly) << std::endl;
}

The result of the above code is:

1_78
0.000000e+00

Is this a bug or I am missing a #define?

Not knowing how useful this is:
I did a little bit of debugging, stepping side by side through "good" and "bad" test cases. First, "clean"-inig the polygon produces different results. Seems like cleaning is done by running a boolean op with nothing, and then this code inside boost/polygon/detail/scan_arbitrary.hpp:


    //iterator over range of vertex property elements and call result functor
    //passing edge to be output, the merged data on both sides and the result
    template <typename result_type, typename result_functor, typename iT>
    void scan(result_type& result, result_functor rf, iT begin, iT end) {
      while(begin != end) {
        x_ = (*begin).first.first.get(HORIZONTAL); //update scanline stop location
        //print_scanline();
        --x_;   // <<---- NOTE THIS
        remove_retired_edges_from_scanline();
        ++x_; // <<-- NOTE THIS
        begin = handle_input_events(result, rf, begin, end);
        remove_retired_edges_from_scanline();
        //print_scanline();
        insert_new_edges_into_scanline();
      }
      //print_scanline();
      x_ = (std::numeric_limits<Unit>::max)();
      remove_retired_edges_from_scanline();
    }

Is the code assuming that the sequence --x_ followed by ++x_ will produce x_? In the case x_ = 0.003065 the final result is 0.0030649999999999844

The result of polygon_90_set_data::get with argument vthreshold is incorrect

The code is as follows:

#include "boost/polygon/gtl.hpp"
#include <vector>
#include <iostream>

using namespace std;

int main(int argc, char** argv)
{
    gtl::point_data<int> point[] = {{53, 17}, {53, 68}, {33, 68}, {33, 17}};
    gtl::polygon_90_data<int> p90;
    p90.set(point, point + 5);
    gtl::rectangle_data<int> r1 = {10, 20, 30, 40};
    gtl::rectangle_data<int> r2 = {10, 25, 35, 45};
    gtl::rectangle_data<int> r3 = {10, 55, 43, 62};
    gtl::polygon_90_set_data<int> ps1(gtl::VERTICAL), ps2(gtl::VERTICAL);
    ps1.insert(r1);
    ps1.insert(r3);
    ps2.insert(r2);
    ps2.insert(p90);

    gtl::polygon_90_set_data<int> ps3 = ps1 | ps2;    
    vector<gtl::polygon_90_data<int>> p90s;
    ps3.get(p90s, 8);
    for (auto& p : p90s) {
        for (auto& x : p) {
          cout << "(" << x.x() << " " << x.y() << ")";
        }
        cout << endl;
    }

    return 0;
}

The result is:

(17 33)(25 33)(25 30)(20 30)(20 10)(45 10)(17 10)
(53 17)(33 17)(33 55)(10 55)(10 62)(33 62)(33 68)(53 68)

The input 17(point{53,17}) is the vertical coordinate, and the output 17(point{17,33}) is the horizontal coordinate.

detail/voronoi_robust_fpt.hpp

Доброе время суток.

Коллеги из соседнего отдела нашли особенность, там деление на 0 происходит.

182 строка

  robust_fpt operator-(const robust_fpt& that) const {
    floating_point_type fpv = this->fpv_ - that.fpv_;
    relative_error_type re;
    if ((!is_neg(this->fpv_) && !is_pos(that.fpv_)) ||
        (!is_pos(this->fpv_) && !is_neg(that.fpv_))) {
      re = (std::max)(this->re_, that.re_) + ROUNDING_ERROR;
    } else {
      floating_point_type temp =
        0;          //
      if (fpv != 0) // этот случай в библиотеке не обработан
        temp =      //
        (this->fpv_ * this->re_ + that.fpv_ * that.re_) / fpv;
      if (is_neg(temp))
        temp = -temp;
      re = temp + ROUNDING_ERROR;
    }
    return robust_fpt(fpv, re);
  }

Сможете посмотреть и поправить?

What is `circle_event.lower_x`?

I'm trying to understand the algorithm (btw if there is a formal description -- will be glad to read it) and want to understand what is circle_event.lower_x field, I understand that circle_event class represents circle built during sweeping the plane and from docstring I can see that

lower_x_ - leftmost x-coordinate;

For example, if we have a circle

does this point has coordinates (lower_x, center_y) or am I missing something?

If lower_x is the lefmost should it be always to the left of the center_x?

polygon_data_set::insert creates unwanted polygon point

I want to represent a donut shape with boost::polygon, such as the figure below, with the following points:

10 polygon : (0, 0), (10, 0), (10, 10), (8, 10), (8, 2), (2, 2), (2, 8), (8, 8), (8, 10), (0, 10),

Once I include the polygon into a polygon set data, however, it creates an additional unwanted point (8,8) from (8,10)->(8,2). Even boost::polygon::simplify leaves this point. Is that the expected behavior?

12 insert : (10, 10), (8, 10), (8, 8), (8, 2), (2, 2), (2, 8), (8, 8), (8, 10), (0, 10), (0, 0), (10, 0), (10, 10),
12 simplf : (10, 10), (8, 10), (8, 8), (8, 2), (2, 2), (2, 8), (8, 8), (8, 10), (0, 10), (0, 0), (10, 0), (10, 10),

#include <iostream>

#include <boost/geometry.hpp>
#include <boost/geometry/geometries/linestring.hpp>
#include <boost/geometry/geometries/point_xy.hpp>
#include <boost/polygon/polygon.hpp>

#include <boost/assign.hpp>

using namespace boost::assign;
namespace gtl = boost::polygon;
using namespace boost::polygon::operators;

//--------------------------------------------------------------------------------
// CPoint
//--------------------------------------------------------------------------------
struct CPoint {
  //CPoint() : x(0), y(0) {}
  //CPoint(int a, int b) : x(a), y(b) {}

  int x;
  int y;
};

namespace boost::polygon {
template <>
struct geometry_concept<CPoint> { typedef point_concept type; };
template <>
struct point_traits<CPoint> {
  typedef int coordinate_type;

  static inline coordinate_type get(const CPoint& point, orientation_2d orient) {
    return ((orient == HORIZONTAL) ? point.x : point.y);
  }
};

template <>
struct point_mutable_traits<CPoint> {
  typedef int coordinate_type;

  static inline void set(CPoint& point, orientation_2d orient, int value) {
    if(orient == HORIZONTAL)
      point.x = value;
    else
      point.y = value;
  }
  static inline CPoint construct(int x_value, int y_value) {
    CPoint retval;
    retval.x = x_value;
    retval.y = y_value;
    return retval;
  }
};
}

//--------------------------------------------------------------------------------
// CPolygon
//--------------------------------------------------------------------------------
typedef std::list<CPoint> CPolygon;

namespace boost::polygon {
template <>
struct geometry_concept<CPolygon>{ typedef polygon_concept type; };

template <>
struct polygon_traits<CPolygon> {
  typedef int coordinate_type;
  typedef CPolygon::const_iterator iterator_type;
  typedef CPoint point_type;

  static inline iterator_type begin_points(const CPolygon& t) { return t.begin(); }
  static inline iterator_type end_points(const CPolygon& t) { return t.end(); }
  static inline std::size_t size(const CPolygon& t) { return t.size(); }
  static inline winding_direction winding(const CPolygon& t) { return unknown_winding; }
};

template <>
struct polygon_mutable_traits<CPolygon> {
  template <typename iT>
  static inline CPolygon& set_points(CPolygon& t, iT input_begin, iT input_end) {
    t.clear();
    while(input_begin != input_end) {
      t.push_back(CPoint());
      gtl::assign(t.back(), *input_begin);
      ++input_begin;
    }
    return t;
  }
};
}

std::ostream &operator<<(std::ostream &os, const CPoint &p) {
  return os << "(" << p.x << ", " << p.y << ")";
}

std::ostream &operator<<(std::ostream &os, const CPolygon &p) {
  for (const auto point : p)
    os << point << ", ";
  return os;
}


int main()
{
  CPolygon donut{
    CPoint{0, 0}, CPoint{10,0}, CPoint{10, 10},
    CPoint{8, 10}, CPoint{8, 2},
    CPoint{2, 2}, CPoint{2, 8}, CPoint{8, 8},
   CPoint{8,10}, CPoint{0,10} }; 

  std::cout << donut.size() << "  donut : " << donut << std::endl;

  boost::polygon::polygon_set_data<int> ps;
  std::vector<CPolygon> polygons;
  ps.insert(donut);
  ps.get(polygons);
  for (const auto &pl : polygons)
    std::cout << pl.size() << " insert : " << pl << std::endl;

  polygons.clear();
  boost::polygon::simplify(ps, 1e-3);
  ps.get(polygons);
  for (const auto &pl : polygons)
    std::cout << pl.size() << " simplf : " << pl << std::endl;

	return 0;
}

Inserting 64-bit rectangle into 64-bit polygon set doesn't work

Godbolt live link

The following program inserts a 64-bit rectangle into a 64-bit polygon set. Then it does the same thing again, but using a polygon instead of a rectangle to represent the shape. It prints out whether each polygon set is empty following the insertion of the figure.

Expected output:

pset1 empty == 0
pset2 empty == 0

Actual output:

pset1 empty == 1
pset2 empty == 0

In other words, inserting the figure as a rectangle drops it.

Note that the figure is not dropped (and you get the expected output) if you change the values of the coordinates to fit in 32 bits.

#include <boost/polygon/polygon.hpp>

#include <iostream>
#include <cstdint>
#include <vector>

namespace bp = boost::polygon;

typedef int64_t Coord;
typedef bp::point_data<Coord> Point;
typedef bp::polygon_data<Coord> Poly;
typedef bp::rectangle_data<Coord> Rect;
typedef bp::polygon_set_data<Coord> PolySet;

int
main()
{
    const int64_t xl = 1214688665600;
    const int64_t xh = 1226223002624;
    const int64_t yl = 1524039680000;
    const int64_t yh = 1527821107200;

    Rect r(xl, yl, xh, yh);
    PolySet pset1;
    pset1.insert(r);
    std::cout << "pset1 empty == " << bp::empty(pset1) << "\n";

    std::vector<Point> points;
    points.push_back(Point(xl,yl));
    points.push_back(Point(xl,yh));
    points.push_back(Point(xh,yh));
    points.push_back(Point(xh,yl));
    Poly poly;
    poly.set(points.begin(), points.end());
    PolySet pset2;
    pset2.insert(poly);
    std::cout << "pset2 empty == " << bp::empty(pset2) << "\n";
}

List of non BOOST-prefixed macros

The following macros are missing a BOOST_ prefix, which is against Boost library guidelines:

./boost/polygon/gtl.hpp:#ifndef GTL_GTL_HPP
./boost/polygon/gtl.hpp:#define GTL_GTL_HPP

[voronoi] issue with pss()

1.76.0 produces this voronoi output:

1

0
3
673 903 -985 -362
-238 248 -179 453
-136 323 -90 419

herepss([-985,-362],[-179,453,-238,248],[673,903,-985,-362]) finds a CE @[-2674.2,1851.9];

2

0
3
519 -635 342 -158
-440 707 661 -976
269 -113 507 -171

here pss([519,-635],[519,-635,342,-158],[269,-113,507,-171]) finds a CE @ [788.2,-535.1]

3

0
3
597 -23 533 65
716 302 455 245
-716 412 999 356

here pss([-716,412],[-716,412,999,356],[533,65,597,-23]) finds a CE @ [-784.19,-1676.38]

4

in example ”primary_29.txt" pss([-1,1], [0,1,0,0], [0,0,-1,1]) finds a CE @ [-0.59,1.41]

In these examples pss() solves for CE solutions where the (infinite line) segments tangents the CE, but the segment falls short of reaching that tangent point.

bug in robust_sqrt_expr::eval2()

The robust_sqrt_expr::eval2() is called with very long input arguments in these following two cases:

boost::polygon::voronoi_builder<...>::activate_circle_event(...)
-> cfp::circle_existence_predicate<...>::operator()(...)
	-> lazy_cff::pss(...)
		-> mp_cff::pss(...) 
			-> rsqrexpr::eval4(eint*, eint*)
				-> rsqrexpr::eval3(eint*, eint*)
					-> rsqrexpr::eval2(eint*, eint*)
			-> efpt mp_cff::sqrt_expr_evaluator_pss4<eint, efpt>(eint*, eint*)
				-> efpt mp_cff::sqrt_expr_evaluator_pss3<eint, efpt>(eint*, eint*)
					-> rsqrexpr::eval2(eint*, eint*)

where

using dtl = boost:polygon::voronoi::detail;
using eint = dtl::extended_int<33ul>;
using efpt = dtl::extended_exponent_fpt<double, dtl::extened_exponent_fpt_traits<double> >;
using rsqrexpr = dtl::robust_sqrt_expr<eint, dtl::extended_exponent_fpt<double, dtl::extened_exponent_fpt_traits<double> >, dtl::type_converter_efpt>;
using lazy_cff = dtl::voronoi_predicates<dtl::voronoi_ctype_traits<int> >::lazy_circle_formation_functor<dtl::site_event<int>, dtl::circle_event<double> >;
using mp_cff = dtl::voronoi_predicates<dtl::voronoi_ctype_traits<int> >::mp_circle_formation_functor<dtl::site_event<int>, dtl::circle_event<double> >;
using cfp = dtl::voronoi_predicates<dtl::voronoi_ctype_traits<int> >::circle_formation_predicate<dtl::site_event<int>, dtl::circle_event<double>, dtl::voronoi_predicates<dtl::voronoi_ctype_traits<int> >;

for brevity.

The eval2() does the following operation on input arguments A, B:
return convert(A[0].sqr() * B[0] - A[1].sqr() * B[1]) / (a - b);

Here neither the square operation nor the A[].sqr()*B[] fit the multi precision fixed point type in many cases. There is a trick inside extended_int::mul() method, which right shifts the result to fit the multi precision fixed point type, but it was not implemented correctly:

The expression A[0].sqr() * B[0] - A[1].sqr() * B[1] mixes apples with oranges. Each side of the subtract operator may have been right shifted by a different exponent, therefore subtracting such two expressions does not make sense.
The returned "float with exponent" type does not have the implicit right shift operation performed by extended_int::mul() accounted for.

I would be happy to hear that I am wrong, but as of now I would bet my shoes that this code path is not correct. I have placed asserts and back trace print-outs inside the extended_int::mul() function to check for these events where the implicit right shift happens. I would only consider such operation safe, if a result of such operation was used for further multiplication followed by a signum test *(a predicate evaluation), which is certainly not the case here.

I am not quite sure how to solve this. One solution is to convert the inputs of eval2() to yet wider int types. Another option is to craft eval2() to account for the right shifts inside mul(), to craft the subtract operator to account for the additional exponents of its operands etc. I may try something, though I would be thankful to @asydorchuk for his opinion. Maybe I am wrong after all and everything works correctly :-)

voronoi warning: conversion from '__int64' to 'const int' at insert(const Segment& segment, VB* vb)

My datatype is int64, and for some reason Boost is converting it to int.
struct Point { int64 X, Y; }

polygon\voronoi.hpp(68,8): warning C4244: 'argument': conversion from '__int64' to 'const int', possible loss of data

template <typename Segment, typename VB>
typename enable_if<
  typename gtl_if<
    typename is_segment_concept<
      typename geometry_concept<Segment>::type
    >::type
  >::type,
  std::size_t
>::type insert(const Segment& segment, VB* vb) {
  return vb->insert_segment(
      x(low(segment)), y(low(segment)), // this is where the warning comes from
      x(high(segment)), y(high(segment)));
}

Maybe I'm doing something wrong, please advise, and maybe it is similar to this.

popCoordinate in funtion pushPoint is confusing

polygon/include/boost/polygon/detail/polygon_formation.hpp

Lines 964 to 975 in 8ba35b5

    
           template <typename Unit> 
        
           inline PolyLine<Unit>& PolyLine<Unit>::pushPoint(const point_data<Unit>& point) { 
        
              if(numSegments()){ 
        
                point_data<Unit> endPt = getEndPoint(); 
        
                //vertical is true, horizontal is false 
        
                if((tailOrient().to_int() ? point.get(VERTICAL) == endPt.get(VERTICAL) : point.get(HORIZONTAL) == endPt.get(HORIZONTAL))) { 
        
                  //we were pushing a colinear segment 
        
                  return popCoordinate(); 
        
                } 
        
              } 
        
             return pushCoordinate(tailOrient().to_int() ? point.get(VERTICAL) : point.get(HORIZONTAL)); 
        
           }

When collinear, this function returns the result after popCoordinate, which may lose a coordinate, and push nothing.

Intersection of polygons with double coordinate type doesn't work

https://godbolt.org/z/v7exo37sP - this is an example of intersection custom polygons with a double data type.
https://godbolt.org/z/9n8We6eqb - example with your polygons

You can see that if i change coordinate type to double i can't get any intersections

An exception "cannot dereference end map/set iterator" in polygon_arbitrary_formation.hpp

While using Polygon Set Data Object void get(output_container& output) to get fractures of a complex polygon, line#1754 in polygon_arbitrary_formation.hpp caused the exception. The exception happened since line#1687 in polygon_arbitrary_formation.hpp. In line#1687, it increases value of "iter" to get out "while" loop . After the while loop, value of "iter" is null which is used in line#1754 to cause the exception happened.

PolyLinePolygonWithHolesData::iteratorHoles is not LegacyIterator

The class template PolyLinePolygonWithHolesData's member type iteratorHoles is not a legal LegacyIterator since there is no specialization of std::iterator_traits for it.

This leads to the surprising behavior that code won't compile when the iterator is used with the standard library's algorithms, say std::transform, and the concept is correctly enforced (for example by compiling with __GLIBCXX_DEBUG).

(There might be other iterators for which this is true as well?)

Boost library polygon failed to build due to c2065 c2146 c2659 c2440 c2563 c2568

Environment:
VS 2017 + Windows Server 2016

Issue description:
We build and run test for Boost. And we found voronoi_builder_test.cpp failed to build due to error c2065: 'T': undeclared identifier
c2146: syntax error: missing ';' before identifier 'x'
c2659'=': function as left operand
c2440: '': cannot convert from 'initializer list' to 'boost::polygon::point_data' c2563: mismatch in formal parameter list
c2568: '*': unable to resolve function overload
Could you pleaes take a look? Thanks in advance.
log_x86_test_75.log

Error info:
msvc.link ..\out\x86rel\boost\bin.v2\libs\polygon\test\polygon_rectangle_formation_test.test\msvc-14.1\release\threading-multi\polygon_rectangle_formation_test.exe
compile-c-c++ ..\out\x86rel\boost\bin.v2\libs\polygon\test\voronoi_builder_test.test\msvc-14.1\release\threading-multi\voronoi_builder_test.obj
voronoi_builder_test.cpp
libs\polygon\test\voronoi_builder_test.cpp(361): error C2065: 'T': undeclared identifier
libs\polygon\test\voronoi_builder_test.cpp(361): error C2146: syntax error: missing ';' before identifier 'x'
libs\polygon\test\voronoi_builder_test.cpp(361): error C2659: '=': function as left operand
libs\polygon\test\voronoi_builder_test.cpp(362): error C2065: 'T': undeclared identifier
libs\polygon\test\voronoi_builder_test.cpp(362): error C2146: syntax error: missing ';' before identifier 'y'
libs\polygon\test\voronoi_builder_test.cpp(362): error C2659: '=': function as left operand
libs\polygon\test\voronoi_builder_test.cpp(363): error C2440: '': cannot convert from 'initializer list' to 'boost::polygon::point_data'
libs\polygon\test\voronoi_builder_test.cpp(363): note: No constructor could take the source type, or constructor overload resolution was ambiguous
libs\polygon\test\voronoi_builder_test.cpp(364): error C2563: mismatch in formal parameter list
libs\polygon\test\voronoi_builder_test.cpp(364): error C2568: '*': unable to resolve function overload
libs\polygon\test\voronoi_builder_test.cpp(364): note: could be 'enable_if<gtl_and<boost::polygon::y_p_sx,is_mutable_point_concept<geometry_concept::type>::type>::type,void>::type boost::polygon::x(PointType &,point_mutable_traits::coordinate_type)'
libs\polygon\test\voronoi_builder_test.cpp(364): note: or 'enable_if<gtl_and<boost::polygon::y_p_x,is_point_concept<geometry_concept::type>::type>::type,point_coordinate_type::type>::type boost::polygon::x(const PointType &)'
libs\polygon\test\voronoi_builder_test.cpp(580): error C2065: 'T': undeclared identifier
libs\polygon\test\voronoi_builder_test.cpp(580): error C2146: syntax error: missing ';' before identifier 'x1'
libs\polygon\test\voronoi_builder_test.cpp(580): error C2065: 'x1': undeclared identifier
libs\polygon\test\voronoi_builder_test.cpp(580): error C2659: '=': function as left operand
libs\polygon\test\voronoi_builder_test.cpp(580): error C2065: 'x2': undeclared identifier
libs\polygon\test\voronoi_builder_test.cpp(580): error C2065: 'y2': undeclared identifier
libs\polygon\test\voronoi_builder_test.cpp(581): error C2065: 'x1': undeclared identifier
libs\polygon\test\voronoi_builder_test.cpp(581): error C2065: 'x2': undeclared identifier
libs\polygon\test\voronoi_builder_test.cpp(581): error C2065: 'y2': undeclared identifier
libs\polygon\test\voronoi_builder_test.cpp(582): error C2065: 'x1': undeclared identifier
libs\polygon\test\voronoi_builder_test.cpp(583): error C2659: '=': function as left operand
libs\polygon\test\voronoi_builder_test.cpp(584): error C2065: 'x2': undeclared identifier
libs\polygon\test\voronoi_builder_test.cpp(585): error C2065: 'y2': undeclared identifier
libs\polygon\test\voronoi_builder_test.cpp(587): error C2065: 'x1': undeclared identifier
libs\polygon\test\voronoi_builder_test.cpp(588): error C2065: 'x2': undeclared identifier
libs\polygon\test\voronoi_builder_test.cpp(588): error C2065: 'y2': undeclared identifier
libs\polygon\test\voronoi_builder_test.cpp(618): error C2065: 'T': undeclared identifier
libs\polygon\test\voronoi_builder_test.cpp(618): error C2146: syntax error: missing ';' before identifier 'x1'
libs\polygon\test\voronoi_builder_test.cpp(618): error C2065: 'x1': undeclared identifier
libs\polygon\test\voronoi_builder_test.cpp(619): error C2065: 'T': undeclared identifier
libs\polygon\test\voronoi_builder_test.cpp(619): error C2146: syntax error: missing ';' before identifier 'y1'
libs\polygon\test\voronoi_builder_test.cpp(619): error C2659: '=': function as left operand
libs\polygon\test\voronoi_builder_test.cpp(620): error C2065: 'T': undeclared identifier
libs\polygon\test\voronoi_builder_test.cpp(620): error C2146: syntax error: missing ';' before identifier 'dx'
libs\polygon\test\voronoi_builder_test.cpp(620): error C2065: 'dx': undeclared identifier
libs\polygon\test\voronoi_builder_test.cpp(620): error C2065: 'dy': undeclared identifier
libs\polygon\test\voronoi_builder_test.cpp(621): error C2065: 'dx': undeclared identifier
libs\polygon\test\voronoi_builder_test.cpp(621): error C2065: 'dy': undeclared identifier
libs\polygon\test\voronoi_builder_test.cpp(622): error C2065: 'dx': undeclared identifier
libs\polygon\test\voronoi_builder_test.cpp(623): error C2065: 'dy': undeclared identifier
libs\polygon\test\voronoi_builder_test.cpp(625): error C2065: 'T': undeclared identifier
libs\polygon\test\voronoi_builder_test.cpp(625): error C2146: syntax error: missing ';' before identifier 'x2'
libs\polygon\test\voronoi_builder_test.cpp(625): error C2065: 'x2': undeclared identifier
libs\polygon\test\voronoi_builder_test.cpp(625): error C2065: 'x1': undeclared identifier
libs\polygon\test\voronoi_builder_test.cpp(625): error C2065: 'dx': undeclared identifier
libs\polygon\test\voronoi_builder_test.cpp(626): error C2065: 'T': undeclared identifier
libs\polygon\test\voronoi_builder_test.cpp(626): error C2146: syntax error: missing ';' before identifier 'y2'
libs\polygon\test\voronoi_builder_test.cpp(626): error C2065: 'y2': undeclared identifier
libs\polygon\test\voronoi_builder_test.cpp(626): error C2065: 'dy': undeclared identifier
libs\polygon\test\voronoi_builder_test.cpp(627): error C2065: 'x1': undeclared identifier
libs\polygon\test\voronoi_builder_test.cpp(628): error C2065: 'x2': undeclared identifier
libs\polygon\test\voronoi_builder_test.cpp(628): error C2065: 'y2': undeclared identifier
libs\polygon\test\voronoi_builder_test.cpp(634): error C2065: 'T': undeclared identifier
libs\polygon\test\voronoi_builder_test.cpp(634): error C2146: syntax error: missing ';' before identifier 'x1'
libs\polygon\test\voronoi_builder_test.cpp(634): error C2065: 'x1': undeclared identifier
libs\polygon\test\voronoi_builder_test.cpp(635): error C2065: 'T': undeclared identifier
libs\polygon\test\voronoi_builder_test.cpp(635): error C2146: syntax error: missing ';' before identifier 'y1'
libs\polygon\test\voronoi_builder_test.cpp(635): error C2659: '=': function as left operand
libs\polygon\test\voronoi_builder_test.cpp(636): error C2065: 'T': undeclared identifier
libs\polygon\test\voronoi_builder_test.cpp(636): error C2146: syntax error: missing ';' before identifier 'x2'
libs\polygon\test\voronoi_builder_test.cpp(636): error C2065: 'x2': undeclared identifier
libs\polygon\test\voronoi_builder_test.cpp(637): error C2065: 'T': undeclared identifier
libs\polygon\test\voronoi_builder_test.cpp(637): error C2146: syntax error: missing ';' before identifier 'y2'
libs\polygon\test\voronoi_builder_test.cpp(637): error C2065: 'y2': undeclared identifier
libs\polygon\test\voronoi_builder_test.cpp(638): error C2065: 'x1': undeclared identifier
libs\polygon\test\voronoi_builder_test.cpp(639): error C2065: 'x2': undeclared identifier
libs\polygon\test\voronoi_builder_test.cpp(639): error C2065: 'y2': undeclared identifier

Voronoi diagram broken

I've been stress-testing the Voronoi diagram builder and I have concluded that the library doesn't produce stable results when the input data gets a little complex.

My test cases consists of random polygons without self-overlap.

Here's one arbitrary case which shows severe problems:

Input segments in black, voronoi edges in red, voronoi parabolas in blue (with low discretization), infinite edges not drawn.

Here's the segments which produce the erroneous case above:
boost_voronoi_problem.txt

WINDOWS COMPILATION: point_data.hpp(63): error C2672: 'assign': no matching overloaded function found

Goal is to, in Windows, compile a Python extension to the Boost Polygon library, which is already compiling and working fine in Linux. The Linux makefile I was given used -std=c++0x which I read means C++11 standard, which is only supported in MS VC++ 2019 and up, so that is the compiler I used (aka MSVC 14.2).

downloaded latest Boost release: 1.77.0
- unzip to c:\boost_1_77_0
open x64 Native Tools Command Prompt for VS 2019
cd c:\boost_1_77_0
bootstrap.bat
b2 -j4 toolset=msvc-14.2 address-model=64 architecture=x86 link=shared threading=multi runtime-link=shared --build-type=minimal stage --stagedir=stage/x64 --with-python
cd c:\myPyPackage\cpp
compile Python extension:
cl /EHsc /std:c11 /MD /W4 -O2 /I"c:\boost_1_77_0" /I"c:\python36\include" boost_polygon_python.cpp c:\boost_1_77_0\stage\x64\lib\boost_python36-vc142-mt-x64-1_77.lib c:\python36\libs\python36.lib
- https://docs.microsoft.com/en-us/cpp/build/reference/md-mt-ld-use-run-time-library?view=msvc-160

output:

Microsoft (R) C/C++ Optimizing Compiler Version 19.29.30136 for x64
Copyright (C) Microsoft Corporation.  All rights reserved.

boost_polygon_python.cpp
c:\boost_1_77_0\boost/python/converter/builtin_converters.hpp(170): warning C4244: 'argument': conversion from 'const long double' to 'double', possible loss of data
c:\boost_1_77_0\boost/python/converter/builtin_converters.hpp(174): warning C4244: 'argument': conversion from '_Ty' to 'double', possible loss of data
        with
        [
            _Ty=long double
        ]
c:\boost_1_77_0\boost\polygon\polygon_90_set_data.hpp(801): warning C4267: 'argument': conversion from 'size_t' to 'int', possible loss of data
c:\boost_1_77_0\boost\polygon\polygon_90_set_data.hpp(789): note: while compiling class template member function 'boost::polygon::polygon_90_set_data<int> &boost::polygon::polygon_90_set_data<int>::interact(const boost::polygon::polygon_90_set_data<int> &)'
boost_polygon_python.cpp(275): note: see reference to function template instantiation 'boost::polygon::polygon_90_set_data<int> &boost::polygon::polygon_90_set_data<int>::interact(const boost::polygon::polygon_90_set_data<int> &)' being compiled
boost_polygon_python.cpp(186): note: see reference to class template instantiation 'boost::polygon::polygon_90_set_data<int>' being compiled
c:\boost_1_77_0\boost/python/object_call.hpp(18): warning C4459: declaration of 'self' hides global declaration
c:\boost_1_77_0\boost/python/self.hpp(24): note: see declaration of 'boost::python::self_ns::self'
boost_polygon_python.cpp(143): note: see reference to function template instantiation 'boost::python::api::object boost::python::api::object_operators<boost::python::api::object>::operator ()<int,int>(const A0 &,const A1 &) const' being compiled
        with
        [
            A0=int,
            A1=int
        ]
boost_polygon_python.cpp(142): note: see reference to function template instantiation 'boost::python::api::object boost::python::api::object_operators<boost::python::api::object>::operator ()<int,int>(const A0 &,const A1 &) const' being compiled
        with
        [
            A0=int,
            A1=int
        ]
c:\boost_1_77_0\boost\polygon\point_data.hpp(63): error C2672: 'assign': no matching overloaded function found
c:\boost_1_77_0\boost\polygon\point_data.hpp(57): note: see reference to function template instantiation 'boost::polygon::point_data<int> &boost::polygon::point_data<int>::operator =<PointType>(const PointType &)' being compiled
        with
        [
            PointType=boost::python::extract<boost::polygon::Point>
        ]
c:\boost_1_77_0\boost\polygon\point_data.hpp(57): note: see reference to function template instantiation 'boost::polygon::point_data<int> &boost::polygon::point_data<int>::operator =<PointType>(const PointType &)' being compiled
        with
        [
            PointType=boost::python::extract<boost::polygon::Point>
        ]
boost_polygon_python.cpp(81): note: see reference to function template instantiation 'boost::polygon::point_data<int>::point_data<boost::python::extract<boost::polygon::Point>>(const PointType &)' being compiled
        with
        [
            PointType=boost::python::extract<boost::polygon::Point>
        ]
boost_polygon_python.cpp(81): note: see reference to function template instantiation 'boost::polygon::point_data<int>::point_data<boost::python::extract<boost::polygon::Point>>(const PointType &)' being compiled
        with
        [
            PointType=boost::python::extract<boost::polygon::Point>
        ]
c:\boost_1_77_0\boost\polygon\point_data.hpp(63): error C2893: Failed to specialize function template 'enable_if<gtl_and_3<boost::polygon::y_pt_assign,is_mutable_point_concept<geometry_concept<T>::type>::type,is_point_concept<geometry_concept<PointType2>::type>::type>::type,PointType1>::type &boost::polygon::assign(PointType1 &,const PointType2 &)'
c:\boost_1_77_0\boost\polygon\point_concept.hpp(167): note: see declaration of 'boost::polygon::assign'
c:\boost_1_77_0\boost\polygon\point_data.hpp(63): note: With the following template arguments:
c:\boost_1_77_0\boost\polygon\point_data.hpp(63): note: 'PointType1=boost::polygon::point_data<int>'
c:\boost_1_77_0\boost\polygon\point_data.hpp(63): note: 'PointType2=PointType'

and here's the Python extension source:

#define BOOST_ALL_DYN_LINK
#define BOOST_THREAD_USE_DLL
#define BOOST_DYN_LINK
#define BOOST_PYTHON_SHARED_LIB
#define BOOST_POLYGON_MSVC
#include <boost/python.hpp>
#include <boost/polygon/polygon.hpp>
using namespace boost::python;
using namespace boost::polygon::operators;

#include <algorithm>
#include <vector>

namespace boost {
   namespace polygon {
      typedef point_data<int> Point;
      typedef rectangle_data<int> Rectangle;
      typedef polygon_90_set_data<int> PolygonSet;
   }
}

/*
 * Extractors (Extract C++ objects from Python objects)
 */
namespace boost {
   namespace python {

      template <>
      struct extract<boost::polygon::Point> {
         typedef boost::polygon::Point result_type;

         extract(boost::python::object const& obj) : obj_(obj) {}

         result_type operator()() const {
            return get_point();
         }

         operator result_type() const {
            return get_point();
         }

         bool check() const {
            boost::python::object point_class =
               boost::python::import("myPyPackage.geometry.point").attr("Point");
            return ::PyObject_IsInstance(obj_.ptr(), point_class.ptr());
         }

      private:
         result_type get_point() const {
            int x = extract<int>(obj_.attr("xcoord"));
            int y = extract<int>(obj_.attr("ycoord"));
            return boost::polygon::Point(x, y);
         }

      private:
         boost::python::object obj_;
      };

      template <>
      struct extract<boost::polygon::Rectangle> {
         typedef boost::polygon::Rectangle result_type;

         extract(boost::python::object const& obj) : obj_(obj) {}

         result_type operator()() const {
            return get_rectangle();
         }

         operator result_type() const {
            return get_rectangle();
         }

         bool check() const {
            boost::python::object rectangle_class =
               boost::python::import("myPyPackage.geometry.rectangle").attr("Rectangle");
            return ::PyObject_IsInstance(obj_.ptr(), rectangle_class.ptr());
         }

      private:
         result_type get_rectangle() const {
           boost::polygon::Point lower_left = extract<boost::polygon::Point>(obj_.attr("lower_left"));
           boost::polygon::Point upper_right = extract<boost::polygon::Point>(obj_.attr("upper_right"));
            return boost::polygon::Rectangle(lower_left.x(), lower_left.y(),
                                             upper_right.x(), upper_right.y());
         }

      private:
         boost::python::object obj_;
      };

      template <>
      struct extract<std::vector<boost::polygon::Rectangle>> {
         typedef std::vector<boost::polygon::Rectangle> result_type;

         extract(boost::python::object const& obj) : obj_(obj) {}

         result_type operator()() const {
            return get_polygons();
         }

         operator result_type() const {
            return get_polygons();
         }

         bool check() const {
            boost::python::extract<boost::python::list> list_extract(obj_);
            return list_extract.check();
         }

      private:
         result_type get_polygons() const {
            boost::python::extract<boost::python::list> list_extract(obj_);
            if (!list_extract.check()) {
               throw std::runtime_error("Expecting a python list of polygons/rectangles");
            }

            std::vector<boost::polygon::Rectangle> polygons;

            boost::python::list polygon_list = list_extract();
            for (size_t i=0; i<(size_t)boost::python::len(polygon_list); ++i) {
               boost::python::object py_polygon = polygon_list[i];
               boost::python::extract<boost::polygon::Rectangle> extract_polygon(py_polygon);
               if (!extract_polygon.check()) {
                  throw std::runtime_error("Expecting only rectangle in the list");
               }
               boost::polygon::Rectangle value = extract_polygon();
               polygons.push_back(std::move(value));
            }
            return std::move(polygons);
         }

      private:
         boost::python::object obj_;
      };

   }}

struct Boost_Rectangle_To_Python_Rectangle {
   static PyObject* convert(boost::polygon::Rectangle const& rectangle) {
      boost::python::object point_class =
         boost::python::import("myPyPackage.geometry.point").attr("Point");
      boost::python::object pt1 = point_class(rectangle.get(boost::polygon::HORIZONTAL).low(),
                                              rectangle.get(boost::polygon::VERTICAL).low());
      boost::python::object pt2 = point_class(rectangle.get(boost::polygon::HORIZONTAL).high(),
                                              rectangle.get(boost::polygon::VERTICAL).high());
      boost::python::object rectangle_class =
         boost::python::import("myPyPackage.geometry.rectangle").attr("Rectangle");
      return boost::python::incref(rectangle_class(pt1, pt2).ptr());
   }
};

struct ManhattanPolygons {
   ManhattanPolygons();

   ManhattanPolygons(ManhattanPolygons const& other);

   ManhattanPolygons& operator=(ManhattanPolygons const& rhs);

   void insert(boost::python::object py_polygon);

   void clear();

   boost::python::list get_rectangles();

   boost::python::object extent() const;

   ManhattanPolygons intersect(ManhattanPolygons const& other) const;

   ManhattanPolygons join(ManhattanPolygons const& other) const;

   ManhattanPolygons difference(ManhattanPolygons const& other) const;

   ManhattanPolygons symmetric_difference(ManhattanPolygons const& other) const;

   ManhattanPolygons resize(int value) const;

   ManhattanPolygons interact(ManhattanPolygons const& other) const;

   ManhattanPolygons scale(double factor) const;

   std::shared_ptr<boost::polygon::PolygonSet> pPolygons_;
};

ManhattanPolygons::ManhattanPolygons()
   : pPolygons_() {
   pPolygons_.reset(new boost::polygon::PolygonSet);
}

ManhattanPolygons::ManhattanPolygons(ManhattanPolygons const& other)
   : pPolygons_() {
   pPolygons_.reset(new boost::polygon::PolygonSet);
   *pPolygons_ = *(other.pPolygons_);
}

ManhattanPolygons& ManhattanPolygons::operator=(ManhattanPolygons const& rhs) {
   if (this != &rhs) {
      *pPolygons_ = *(rhs.pPolygons_);
   }
   return *this;
}

void ManhattanPolygons::insert(boost::python::object py_polygon) {
   boost::python::extract<std::vector<boost::polygon::Rectangle>> polygons_extract(py_polygon);
   if (polygons_extract.check()) {
      std::vector<boost::polygon::Rectangle> polygons = polygons_extract();
      for (auto it=polygons.cbegin(); it!=polygons.cend(); ++it) {
         pPolygons_->insert(*it);
      }
      return;
   }
   boost::python::extract<boost::polygon::Rectangle> polygon_extract(py_polygon);
   if (!polygon_extract.check()) {
      throw std::runtime_error("Expecting a python rectangle or a list of python rectangles");
   }
   boost::polygon::Rectangle polygon = polygon_extract();
   pPolygons_->insert(polygon);
}

void ManhattanPolygons::clear() {
   pPolygons_->clear();
}

boost::python::list ManhattanPolygons::get_rectangles() {
   boost::python::list list_of_rectangles;
   std::vector<boost::polygon::Rectangle> result;
   pPolygons_->get_rectangles(result);
   for (auto itr=result.begin(); itr!=result.end(); ++itr) {
      boost::python::object python_rectangle(*itr);
      list_of_rectangles.append(python_rectangle);
   }
   return list_of_rectangles;
}

boost::python::object ManhattanPolygons::extent() const {
   boost::polygon::Rectangle rectangle;
   if (pPolygons_->extents(rectangle)) {
      boost::python::object py_rectangle(rectangle);
      return py_rectangle;
   }
   return boost::python::object();
}

ManhattanPolygons ManhattanPolygons::intersect(ManhattanPolygons const& other) const {
   ManhattanPolygons result(*this);
   *(result.pPolygons_) &= *(other.pPolygons_);
   return std::move(result);
}

ManhattanPolygons ManhattanPolygons::join(ManhattanPolygons const& other) const {
   ManhattanPolygons result(*this);
   *(result.pPolygons_) += *(other.pPolygons_);
   return std::move(result);
}

ManhattanPolygons ManhattanPolygons::difference(ManhattanPolygons const& other) const {
   ManhattanPolygons result(*this);
   *(result.pPolygons_) -= *(other.pPolygons_);
   return std::move(result);
}

ManhattanPolygons ManhattanPolygons::symmetric_difference(ManhattanPolygons const& other) const {
   ManhattanPolygons result(*this);
   *(result.pPolygons_) ^= *(other.pPolygons_);
   return std::move(result);
}

ManhattanPolygons ManhattanPolygons::resize(int value) const {
   ManhattanPolygons result(*this);
   result.pPolygons_->resize(value, value, value, value);
   return std::move(result);
}

ManhattanPolygons ManhattanPolygons::interact(ManhattanPolygons const& other) const {
   ManhattanPolygons result(*this);
   result.pPolygons_->interact(*(other.pPolygons_));
   return std::move(result);
}

ManhattanPolygons ManhattanPolygons::scale(double factor) const {
   ManhattanPolygons result(*this);
   result.pPolygons_->scale(factor);
   return std::move(result);
}

BOOST_PYTHON_MODULE(boost_polygon_python) {
   boost::python::to_python_converter<boost::polygon::Rectangle,
                                      Boost_Rectangle_To_Python_Rectangle>();

   class_<ManhattanPolygons>("PolygonSet")
      .def("insert", &ManhattanPolygons::insert)
      .def("clear", &ManhattanPolygons::clear)
      .def("get_rectangles", &ManhattanPolygons::get_rectangles)
      .def("intersect", &ManhattanPolygons::intersect)
      .def("join", &ManhattanPolygons::join)
      .def("difference", &ManhattanPolygons::difference)
      .def("symmetric_difference", &ManhattanPolygons::symmetric_difference)
      .def("resize", &ManhattanPolygons::resize)
      .def("interact", &ManhattanPolygons::interact)
      .def("scale", &ManhattanPolygons::scale)
      ;
}

polygon_*_set_data::get() does not behave according to the documentation

According to the documentation for the get() method on both polygon_45_set_data and polygon_90_set_data, output polygons should always have counter-clockwise winding, and no duplicated start and end point:

Polygons will be output with counterclockwise winding, hole polygons will be output with clockwise winding. The last vertex of an output polygon is not the duplicate of the first, and the number of points is equal to the number of edges.

The following code demonstrates an issue with get(), where in case of polygon_45_set_data::get, the start- and end vertex is duplicated, and in case of polygon_90_set_data::get, the winding is incorrect:

#include <boost/polygon/polygon.hpp>
#include <boost/polygon/polygon_90_set_data.hpp>

namespace bp = boost::polygon;

int main()
{
  using Polygon45 = bp::polygon_45_data<int>;
  using Polygon90 = bp::polygon_90_data<int>;
  using Point = bp::point_data<int>;
  using Polygon45Set = bp::polygon_45_set_data<int>;
  using Polygon90Set = bp::polygon_90_set_data<int>;

  using namespace boost::polygon::operators;

  {
    Polygon90 A;
    {
      std::vector<Point> points{{0, 0}, {1, 0}, {1, 1}, {0, 1}};
      bp::set_points(A, points.begin(), points.end());
    }

    Polygon90 B;
    {
      std::vector<Point> points{{2, 0}, {3, 0}, {3, 1}, {2, 1}};
      bp::set_points(B, points.begin(), points.end());
    }

    std::vector<Polygon90> result;
    Polygon90Set(A - B).get<std::vector<Polygon90>>(result);

    std::cout << "Non counter-clockwise winding:\n";
    for (const auto& polygon : result)
    {
      for (const Point& p : polygon)
      {
        std::cout << '(' << std::to_string(p.x()) << ", " << std::to_string(p.y()) << ")\n";
      }
    }
  }

  {
    Polygon45 A;
    {
      std::vector<Point> points{{0, 0}, {1, 0}, {1, 1}};
      bp::set_points(A, points.begin(), points.end());
    }

    Polygon45 B;
    {
      std::vector<Point> points{{2, 0}, {3, 0}, {3, 1}};
      bp::set_points(B, points.begin(), points.end());
    }

    std::vector<Polygon45> result;
    Polygon45Set(A - B).get<std::vector<Polygon45>>(result);

    std::cout << "Duplicated start- and end vertex:\n";
    for (const auto& polygon : result)
    {
      for (const Point& p : polygon)
      {
        std::cout << '(' << std::to_string(p.x()) << ", " << std::to_string(p.y()) << ")\n";
      }
    }
  }

  return 0;
}

Output:

Non counter-clockwise winding:
(1, 0)
(0, 0)
(0, 1)
(1, 1)
Duplicated start- and end vertex:
(1, 1)
(0, 0)
(1, 0)
(1, 1)

Is this in fact an issue in the code (not the documentation)?

	template <typename Unit>
	inline PolyLine<Unit>& PolyLine<Unit>::pushPoint(const point_data<Unit>& point) {
	if(numSegments()){
	point_data<Unit> endPt = getEndPoint();
	//vertical is true, horizontal is false
	if((tailOrient().to_int() ? point.get(VERTICAL) == endPt.get(VERTICAL) : point.get(HORIZONTAL) == endPt.get(HORIZONTAL))) {
	//we were pushing a colinear segment
	return popCoordinate();
	}
	}
	return pushCoordinate(tailOrient().to_int() ? point.get(VERTICAL) : point.get(HORIZONTAL));
	}