1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
|
//#ifndef NDEBUG
//#define NFP_DEBUG
//#endif
#include "libnfpglue.hpp"
#include "tools/libnfporb/libnfporb.hpp"
namespace libnest2d {
namespace {
inline bool vsort(const libnfporb::point_t& v1, const libnfporb::point_t& v2)
{
using Coord = libnfporb::coord_t;
Coord x1 = v1.x_, x2 = v2.x_, y1 = v1.y_, y2 = v2.y_;
auto diff = y1 - y2;
#ifdef LIBNFP_USE_RATIONAL
long double diffv = diff.convert_to<long double>();
#else
long double diffv = diff.val();
#endif
if(std::abs(diffv) <=
std::numeric_limits<Coord>::epsilon())
return x1 < x2;
return diff < 0;
}
TCoord<PointImpl> getX(const libnfporb::point_t& p) {
#ifdef LIBNFP_USE_RATIONAL
return p.x_.convert_to<TCoord<PointImpl>>();
#else
return static_cast<TCoord<PointImpl>>(std::round(p.x_.val()));
#endif
}
TCoord<PointImpl> getY(const libnfporb::point_t& p) {
#ifdef LIBNFP_USE_RATIONAL
return p.y_.convert_to<TCoord<PointImpl>>();
#else
return static_cast<TCoord<PointImpl>>(std::round(p.y_.val()));
#endif
}
libnfporb::point_t scale(const libnfporb::point_t& p, long double factor) {
#ifdef LIBNFP_USE_RATIONAL
auto px = p.x_.convert_to<long double>();
auto py = p.y_.convert_to<long double>();
#else
long double px = p.x_.val();
long double py = p.y_.val();
#endif
return libnfporb::point_t(px*factor, py*factor);
}
}
PolygonImpl _nfp(const PolygonImpl &sh, const PolygonImpl &cother)
{
using Vertex = PointImpl;
PolygonImpl ret;
// try {
libnfporb::polygon_t pstat, porb;
boost::geometry::convert(sh, pstat);
boost::geometry::convert(cother, porb);
long double factor = 0.0000001;//libnfporb::NFP_EPSILON;
long double refactor = 1.0/factor;
for(auto& v : pstat.outer()) v = scale(v, factor);
// std::string message;
// boost::geometry::is_valid(pstat, message);
// std::cout << message << std::endl;
for(auto& h : pstat.inners()) for(auto& v : h) v = scale(v, factor);
for(auto& v : porb.outer()) v = scale(v, factor);
// message;
// boost::geometry::is_valid(porb, message);
// std::cout << message << std::endl;
for(auto& h : porb.inners()) for(auto& v : h) v = scale(v, factor);
// this can throw
auto nfp = libnfporb::generateNFP(pstat, porb, true);
auto &ct = ShapeLike::getContour(ret);
ct.reserve(nfp.front().size()+1);
for(auto v : nfp.front()) {
v = scale(v, refactor);
ct.emplace_back(getX(v), getY(v));
}
ct.push_back(ct.front());
std::reverse(ct.begin(), ct.end());
auto &rholes = ShapeLike::holes(ret);
for(size_t hidx = 1; hidx < nfp.size(); ++hidx) {
if(nfp[hidx].size() >= 3) {
rholes.push_back({});
auto& h = rholes.back();
h.reserve(nfp[hidx].size()+1);
for(auto& v : nfp[hidx]) {
v = scale(v, refactor);
h.emplace_back(getX(v), getY(v));
}
h.push_back(h.front());
std::reverse(h.begin(), h.end());
}
}
auto& cmp = vsort;
std::sort(pstat.outer().begin(), pstat.outer().end(), cmp);
std::sort(porb.outer().begin(), porb.outer().end(), cmp);
// leftmost lower vertex of the stationary polygon
auto& touch_sh = scale(pstat.outer().back(), refactor);
// rightmost upper vertex of the orbiting polygon
auto& touch_other = scale(porb.outer().front(), refactor);
// Calculate the difference and move the orbiter to the touch position.
auto dtouch = touch_sh - touch_other;
auto _top_other = scale(porb.outer().back(), refactor) + dtouch;
Vertex top_other(getX(_top_other), getY(_top_other));
// Get the righmost upper vertex of the nfp and move it to the RMU of
// the orbiter because they should coincide.
auto&& top_nfp = Nfp::rightmostUpVertex(ret);
auto dnfp = top_other - top_nfp;
std::for_each(ShapeLike::begin(ret), ShapeLike::end(ret),
[&dnfp](Vertex& v) { v+= dnfp; } );
for(auto& h : ShapeLike::holes(ret))
std::for_each( h.begin(), h.end(),
[&dnfp](Vertex& v) { v += dnfp; } );
// } catch(std::exception& e) {
// std::cout << "Error: " << e.what() << "\nTrying with convex hull..." << std::endl;
// auto ch_stat = ShapeLike::convexHull(sh);
// auto ch_orb = ShapeLike::convexHull(cother);
// ret = Nfp::nfpConvexOnly(ch_stat, ch_orb);
// }
return ret;
}
PolygonImpl Nfp::NfpImpl<PolygonImpl, NfpLevel::CONVEX_ONLY>::operator()(
const PolygonImpl &sh, const ClipperLib::PolygonImpl &cother)
{
return _nfp(sh, cother);//nfpConvexOnly(sh, cother);
}
PolygonImpl Nfp::NfpImpl<PolygonImpl, NfpLevel::ONE_CONVEX>::operator()(
const PolygonImpl &sh, const ClipperLib::PolygonImpl &cother)
{
return _nfp(sh, cother);
}
PolygonImpl Nfp::NfpImpl<PolygonImpl, NfpLevel::BOTH_CONCAVE>::operator()(
const PolygonImpl &sh, const ClipperLib::PolygonImpl &cother)
{
return _nfp(sh, cother);
}
PolygonImpl
Nfp::NfpImpl<PolygonImpl, NfpLevel::ONE_CONVEX_WITH_HOLES>::operator()(
const PolygonImpl &sh, const ClipperLib::PolygonImpl &cother)
{
return _nfp(sh, cother);
}
PolygonImpl
Nfp::NfpImpl<PolygonImpl, NfpLevel::BOTH_CONCAVE_WITH_HOLES>::operator()(
const PolygonImpl &sh, const ClipperLib::PolygonImpl &cother)
{
return _nfp(sh, cother);
}
}
|
