c++mathboostboost-polygon
Why doesn't i get any intersections of these polygons?
I learn how to use boost::polygon library with custom polygons. I took an example with usage of custom polygons and tried to get intersections of these. I doesn't get any intersection and can't understand why. Also, you can see this constructor
CPoint(boost::polygon::point_data<int> pd)
I can't compile my program without it. Can someone explain, why i need it? What do i do wrong ?
/*
Copyright 2008 Intel Corporation
Use, modification and distribution are subject to the Boost Software License,
Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
http://www.boost.org/LICENSE_1_0.txt).
*/
#include <boost/polygon/polygon.hpp>
#include <cassert>
#include <list>
namespace gtl = boost::polygon;
using namespace boost::polygon::operators;
template <typename Polygon>
void test_polygon()
{
typedef typename gtl::polygon_traits<Polygon>::point_type Point;
Point pts[] = {gtl::construct<Point>(6, 0),
gtl::construct<Point>(0, 6),
gtl::construct<Point>(-6, 0),
gtl::construct<Point>(0, -6),
};
Polygon poly, poly2;
gtl::set_points(poly, pts, pts+5);
Point pts2[] = {gtl::construct<Point>(4, 0),
gtl::construct<Point>(4, 4),
gtl::construct<Point>(0, 4),
gtl::construct<Point>(0, 0),
};
gtl::set_points(poly2, pts2, pts2+5);
std::vector<Polygon> res;
//boost::polygon::polygon_set_data<int> res;
//res += poly;
//assign(res, poly);
res.push_back(poly);
res &= poly2;
std::cout << "size = " << res.size() << std::endl;
assert(!res.empty());
//for(auto it = res[0].begin(); it != res[0].end(); ++it)
// std::cout << "Point(" << it->x << ", " << it->y << ")" << std::endl;
assert(gtl::area(poly) == 100.0f);
}
struct CPoint {
CPoint()=default;
CPoint(boost::polygon::point_data<int> pd) /*---> WHY? What for ? I implemented constructor with traits*/
{
x = pd.x();
y = pd.y();
}
int x;
int y;
};
namespace boost { namespace 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) {
if(orient == HORIZONTAL)
return point.x;
return 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;
}
};
}
}
typedef std::list<CPoint> CPolygon;
namespace boost {
namespace 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 clockwise_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();
t.insert(t.end(), input_begin, input_end);
return t;
}
};
}
}
int main() {
test_polygon<CPolygon>();
return 0;
}
I get size = 0 in the result vector of intersections.
Solution
gtl::set_points(poly, pts, pts + 5);
That's out of bounds, because the array has only 4 elements. Avoid the entire bug category by modernizing:
std::array const pts1{
gtl::construct<Point>(6, 0),
gtl::construct<Point>(0, 6),
gtl::construct<Point>(-6, 0),
gtl::construct<Point>(0, -6),
};
std::array const pts2{
gtl::construct<Point>(4, 0),
gtl::construct<Point>(4, 4),
gtl::construct<Point>(0, 4),
gtl::construct<Point>(0, 0),
};
And then
Polygon poly1;
gtl::set_points(poly1, pts1.begin(), pts1.end());
Polygon poly2;
gtl::set_points(poly2, pts2.begin(), pts2.end());
Next up you have:
static inline winding_direction winding(const CPolygon& t)
{
return clockwise_winding;
}
But your sample data does not conform to that winding. Fixing your input data:
std::array const pts1{
gtl::construct<Point>(0, -6),
gtl::construct<Point>(-6, 0),
gtl::construct<Point>(0, 6),
gtl::construct<Point>(6, 0),
};
std::array const pts2{
gtl::construct<Point>(0, 0),
gtl::construct<Point>(0, 4),
gtl::construct<Point>(4, 4),
gtl::construct<Point>(4, 0),
};
Finally, the result of operators in Boost Polygon is a polygon set view. You can have the library assign that:
std::vector<Polygon> res;
gtl::assign(res, poly1 & poly2);
Or
std::vector<Polygon> res{poly1};
res &= poly2;
Which are both effectively equivalent, though the second might be more efficient?
fmt::print("poly1 {}, area {}\n", poly1, gtl::area(poly1));
fmt::print("poly2 {}, area {}\n", poly2, gtl::area(poly2));
fmt::print("res {}, area {}\n", res, gtl::area(res));
Prints
poly1 [(0, -6), (-6, 0), (0, 6), (6, 0)], area 72
poly2 [(0, 0), (0, 4), (4, 4), (4, 0)], area 16
res [[(4, 2), (2, 4), (0, 4), (0, 0), (4, 0), (4, 2)]], area 0
Fixing The Area
The only thing I see now is the winding on the result set is still wrong.
This is, no doubt, the reason that area(res) fails. We can show by changing the winding to counter-clockwise (and the sample data too of course):
poly1 {(6, 0), (0, 6), (-6, 0), (0, -6)}, area 72
poly2 {(4, 0), (4, 4), (0, 4), (0, 0)}, area 16
res {{(4, 2), (2, 4), (0, 4), (0, 0), (4, 0), (4, 2)}}, area 14
Perhaps you wanted counter-clockwise after all (considering the test data), or perhaps another trait is needed to tell the library the winding for vector<CPolygon> as a polygon set.
Fixing The Constructor Issue
Going up the call-chain in the compiler error when the constructor is removed, we see
polygon_set_mutable_traits<polygon_set_type_1>::set(lvalue, ps.begin(), ps.end());
This seems to confirm the hunch above: You are missing the traits for the polygon set. However, adding some
template <> struct polygon_set_traits<std::vector<CPolygon> > {
using C = std::vector<CPolygon>;
using iterator_type = C::const_iterator;
using coordinate_type = polygon_traits<CPolygon>::coordinate_type;
static iterator_type begin(C const& c) { return c.begin(); }
static iterator_type end(C const& c) { return c.end(); }
static bool clean(C const& c) { return c.empty(); }
};
template <> struct polygon_set_mutable_traits<std::vector<CPolygon> > {
using C = std::vector<CPolygon>;
using iterator_type = C::iterator;
using coordinate_type = polygon_set_traits<C>::coordinate_type;
static iterator_type begin(C& c) { return c.begin(); }
static iterator_type end(C& c) { return c.end(); }
template <typename II>
static inline void set(C& c, II input_begin, II input_end)
{
c.clear();
size_t num_ele = std::distance(input_begin, input_end);
c.reserve(num_ele);
polygon_set_data<coordinate_type> ps;
ps.reserve(num_ele);
ps.insert(input_begin, input_end);
ps.get(c);
}
};
results in the same since ps.get ends up doing a complicated formation on an "arbitrary formation" to get the "fractured" polygon set (ugh, I don't know what all these things mean) and inside an event processor it ends-up just calling your existing polygon_mutable_traits::set_points. I had already simplified your implementation:
template <typename I>
static inline CPolygon& set_points(CPolygon& t, I f, I l)
{
t.assign(f, l);
return t;
}
However, clearly the assumption that decltype(*I) would be CPoint was just an error. Fixing it:
template <> struct polygon_mutable_traits<CPolygon> {
template <typename I>
static inline CPolygon& set_points(CPolygon& p, I f, I l)
{
p.clear();
for (; f != l; ++f)
p.push_back({get(*f, HORIZONTAL), get(*f, VERTICAL)});
return p;
}
};
Now "everything just works"
Complete Demo
Also reverting the test to generic template and ordered before all the types/traits:
#include <boost/polygon/polygon.hpp>
#include <cassert>
#include <fmt/ostream.h>
#include <fmt/ranges.h>
#include <list>
namespace gtl = boost::polygon;
using namespace gtl::operators;
template <typename Polygon> void test_polygon()
{
using Point = typename gtl::polygon_traits<Polygon>::point_type;
std::array const pts1{
gtl::construct<Point>(6, 0),
gtl::construct<Point>(0, 6),
gtl::construct<Point>(-6, 0),
gtl::construct<Point>(0, -6),
};
std::array const pts2{
gtl::construct<Point>(4, 0),
gtl::construct<Point>(4, 4),
gtl::construct<Point>(0, 4),
gtl::construct<Point>(0, 0),
};
Polygon poly1;
gtl::set_points(poly1, pts1.begin(), pts1.end());
Polygon poly2;
gtl::set_points(poly2, pts2.begin(), pts2.end());
#if 1
std::vector<Polygon> res;
gtl::assign(res, poly1 & poly2);
#else
std::vector<Polygon> res{poly1};
res &= poly2;
#endif
fmt::print("poly1 {}, area {}\n", poly1, gtl::area(poly1));
fmt::print("poly2 {}, area {}\n", poly2, gtl::area(poly2));
fmt::print("res {}, area {}\n", res, gtl::area(res));
}
struct CPoint {
int x;
int y;
friend std::ostream& operator<<(std::ostream& os, CPoint const& cp) {
return os << "(" << cp.x << ", " << cp.y << ")";
}
};
namespace boost::polygon {
template <> struct geometry_concept<CPoint> {
using type = point_concept;
};
template <> struct point_traits<CPoint> {
using coordinate_type = int;
static inline coordinate_type get(const CPoint& point,
orientation_2d orient)
{
return orient == HORIZONTAL ? point.x : point.y;
}
};
template <> struct point_mutable_traits<CPoint> {
using coordinate_type = int;
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)
{
return CPoint{x_value, y_value};
}
};
} // namespace boost::polygon
using CPolygon = std::list<CPoint>;
namespace boost::polygon {
template <> struct geometry_concept<CPolygon> {
using type = polygon_concept;
};
template <> struct polygon_traits<CPolygon> {
using iterator_type = CPolygon::const_iterator;
using point_type = CPoint;
using coordinate_type = typename point_traits<point_type>::coordinate_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 counterclockwise_winding;
}
};
template <> struct polygon_mutable_traits<CPolygon> {
template <typename I>
static inline CPolygon& set_points(CPolygon& p, I f, I l)
{
p.clear();
for (; f != l; ++f)
p.push_back({get(*f, HORIZONTAL), get(*f, VERTICAL)});
return p;
}
};
} // namespace boost::polygon
int main()
{
test_polygon<CPolygon>();
}
Prints
poly1 {(6, 0), (0, 6), (-6, 0), (0, -6)}, area 72
poly2 {(4, 0), (4, 4), (0, 4), (0, 0)}, area 16
res {{(4, 2), (2, 4), (0, 4), (0, 0), (4, 0), (4, 2)}}, area 14
Which matches the schematic:
- My C code works fine but crashes right before the end (0xC0000374)
- A good way to pass several arguments into one void pointer argument? (C)
- How to force linkage to older libc `fcntl` instead of `fcntl64`?
- Is there a way to get the OpenSSL X509 certificate name that im sending to peer in C++?
- how to pass parameter as a pointer to an array in c
- TCP Socket - printing all chars of a string that are not \n in C not working
- GTK3 Set GtkButton size
- How to compile my own glibc C standard library from source and use it?
- Ninja Build System + gcc/clang doesn't output diagnostic colors
- C pointers understanding
- Strict aliasing violation in C
- Parser in C doesn't store values in a array
- What is the order of evaluation of printf(..) parameters?
- Compare floating point numbers as integers
- Trap representation
- Difference between sqrt(x) and pow(x,0.5)
- Is it possible to have a 32-bit pointer on x86-64 without undefined behavior?
- Can you explain this 'Hello world' program?
- how can i check file write permissions in C++ code?
- Why does my C program give an error when looping through an array?
- Printing char array with null character in the middle in C
- How do I read the source code for a C library in CLion
- pthread nice value setting for default scheduler in C
- Use a 3d array on a function (array that contains arrays that contain strings)
- frida-server being targeted by port scan?
- Are compound literals always lvalue?
- Why is the beginning of a C file stream called `SEEK_SET`?
- How to Take whitespace in Input in C
- "undefined reference to" errors when linking static C library with C++ code
- Audio timescale-pitch modification - Open source examples?