92 #ifndef PSIMPL_GENERIC
93 #define PSIMPL_GENERIC
118 template <
typename T>
131 return array [offset];
135 return array [offset];
191 template <
unsigned DIM,
class InputIterator>
196 for (
unsigned d = 0; d < DIM; ++d) {
214 template <
unsigned DIM,
class InputIterator,
class OutputIterator>
218 OutputIterator result)
220 for (
unsigned d = 0; d < DIM; ++d) {
236 template <
unsigned DIM,
class InputIterator>
237 inline typename std::iterator_traits <InputIterator>::value_type
dot (
241 typename std::iterator_traits <InputIterator>::value_type result = 0;
242 for (
unsigned d = 0; d < DIM; ++d) {
243 result += (*v1) * (*v2);
259 template <
unsigned DIM,
class InputIterator,
class OutputIterator>
264 OutputIterator result)
266 typedef typename std::iterator_traits <InputIterator>::value_type value_type;
268 for (
unsigned d = 0; d < DIM; ++d) {
269 *result = *p1 +
static_cast <value_type
> (fraction * (*p2 - *p1));
284 template <
unsigned DIM,
class InputIterator1,
class InputIterator2>
289 typename std::iterator_traits <InputIterator1>::value_type result = 0;
290 for (
unsigned d = 0; d < DIM; ++d) {
291 result += (*p1 - *p2) * (*p1 - *p2);
306 template <
unsigned DIM,
class InputIterator>
307 inline typename std::iterator_traits <InputIterator>::value_type
line_distance2 (
312 typedef typename std::iterator_traits <InputIterator>::value_type value_type;
317 make_vector <DIM> (l1, l2, v);
318 make_vector <DIM> (l1,
p, w);
320 value_type cv = dot <DIM> (v, v);
321 value_type cw = dot <DIM> (w, v);
324 float fraction = cv == 0 ? 0 :
static_cast <float> (cw) /
static_cast <float> (cv);
326 value_type proj [DIM];
327 interpolate <DIM> (l1, l2, fraction, proj);
329 return point_distance2 <DIM> (
p, proj);
340 template <
unsigned DIM,
class InputIterator>
346 typedef typename std::iterator_traits <InputIterator>::value_type value_type;
351 make_vector <DIM> (s1, s2, v);
352 make_vector <DIM> (s1,
p, w);
354 value_type cw = dot <DIM> (w, v);
357 return point_distance2 <DIM> (
p, s1);
360 value_type cv = dot <DIM> (v, v);
363 return point_distance2 <DIM> (
p, s2);
367 float fraction = cv == 0 ? 0 :
static_cast <float> (cw) /
static_cast <float> (cv);
369 value_type proj [DIM];
370 interpolate <DIM> (s1, s2, fraction, proj);
372 return point_distance2 <DIM> (
p, proj);
383 template <
unsigned DIM,
class InputIterator>
384 inline typename std::iterator_traits <InputIterator>::value_type
ray_distance2 (
389 typedef typename std::iterator_traits <InputIterator>::value_type value_type;
394 make_vector <DIM> (r1, r2, v);
395 make_vector <DIM> (r1,
p, w);
397 value_type cv = dot <DIM> (v, v);
398 value_type cw = dot <DIM> (w, v);
402 return point_distance2 <DIM> (
p, r1);
406 float fraction = cv == 0 ? 0 :
static_cast <float> (cw) /
static_cast <float> (cv);
408 value_type proj [DIM];
409 interpolate <DIM> (r1, r2, fraction, proj);
411 return point_distance2 <DIM> (
p, proj);
421 template <
class InputIterator>
426 typedef typename std::iterator_traits <InputIterator>::value_type value_type;
427 typedef typename std::iterator_traits <InputIterator>::difference_type diff_type;
431 diff_type count = std::distance (
first, last);
437 stats.
max =
static_cast <double> (*std::max_element (
first, last));
438 stats.
sum =
static_cast <double> (std::accumulate (
first, last, init));
439 stats.
mean = stats.
sum / count;
441 stats.
std = std::sqrt (
static_cast <double> (std::inner_product (
first, last,
first, init)) / count);
453 template <
unsigned DIM,
class InputIterator,
class OutputIterator>
456 typedef typename std::iterator_traits <InputIterator>::difference_type
diff_type;
457 typedef typename std::iterator_traits <InputIterator>::value_type
value_type;
458 typedef typename std::iterator_traits <const value_type*>::difference_type
ptr_diff_type;
496 OutputIterator result)
504 if (coordCount % DIM || pointCount < 3 || n < 2) {
505 return std::copy (
first, last, result);
508 unsigned remaining = pointCount - 1;
509 InputIterator key =
first;
515 while (
Forward (key, n, remaining)) {
558 OutputIterator result)
567 if (coordCount % DIM || pointCount < 3 || tol2 == 0) {
568 return std::copy (
first, last, result);
571 InputIterator current =
first;
572 InputIterator next =
first;
578 for (
diff_type index = 1; index < pointCount - 1; ++index) {
579 if (math::point_distance2 <DIM> (current, next) < tol2) {
613 OutputIterator result)
621 return std::copy (
first, last, result);
628 diff_type tempCoordCount = std::distance (tempPoly.
get (),
632 if (coordCount == tempCoordCount) {
633 return std::copy (tempPoly.
get (), tempPoly.
get () + coordCount, result);
644 tempCoordCount = std::distance (tempResult.
get (),
646 tempPoly.
get (), tempPoly.
get () + coordCount, tol, tempResult.
get ()));
649 if (coordCount == tempCoordCount) {
650 return std::copy (tempPoly.
get (), tempPoly.
get () + coordCount, result);
660 tempPoly.
get (), tempPoly.
get () + coordCount, tol, result);
701 OutputIterator result)
710 if (coordCount % DIM || pointCount < 3 || tol2 == 0) {
711 return std::copy (
first, last, result);
714 InputIterator p0 =
first;
723 if (math::segment_distance2 <DIM> (p0, p2, p1) < tol2) {
787 OutputIterator result)
796 if (coordCount % DIM || pointCount < 3 || tol2 == 0) {
797 return std::copy (
first, last, result);
801 InputIterator p0 =
first;
805 InputIterator pi = p1;
806 InputIterator pj = p1;
812 for (
diff_type j = 2; j < pointCount; ++j) {
816 if (math::line_distance2 <DIM> (p0, p1, pj) < tol2) {
877 OutputIterator result)
887 if (coordCount % DIM || pointCount < 3 || min_tol2 == 0 || max_tol2 == 0) {
888 return std::copy (
first, last, result);
892 InputIterator r0 =
first;
893 InputIterator r1 =
first;
894 bool rayDefined =
false;
897 InputIterator pi = r0;
904 for (
diff_type j = 2; j < pointCount; ++j) {
910 if (math::point_distance2 <DIM> (r0, pj) < min_tol2) {
919 if (math::point_distance2 <DIM> (r0, pj) < max_tol2 &&
920 math::ray_distance2 <DIM> (r0, r1, pj) < min_tol2)
983 OutputIterator result)
992 if (coordCount % DIM || pointCount < 3 || look_ahead < 2 || tol2 == 0) {
993 return std::copy (
first, last, result);
996 InputIterator current =
first;
997 InputIterator next =
first;
999 unsigned remaining = pointCount - 1;
1000 unsigned moved =
Forward (next, look_ahead, remaining);
1010 d2 = std::max (d2, math::segment_distance2 <DIM> (current, next,
p));
1019 moved =
Forward (next, look_ahead, remaining);
1071 InputIterator
first,
1074 OutputIterator result)
1081 if (coordCount % DIM || pointCount < 3 || tol == 0) {
1082 return std::copy (
first, last, result);
1099 for (
unsigned d = 0; d < DIM; ++d) {
1100 *result = current [d];
1148 InputIterator
first,
1151 OutputIterator result)
1158 if (coordCount % DIM || pointCount <=
static_cast <diff_type> (count) || count < 2) {
1159 return std::copy (
first, last, result);
1165 coords [c] = *
first;
1177 for (
unsigned d = 0; d < DIM; ++d) {
1178 *result = current [d];
1225 InputIterator original_first,
1226 InputIterator original_last,
1227 InputIterator simplified_first,
1228 InputIterator simplified_last,
1229 OutputIterator result,
1232 diff_type original_coordCount = std::distance (original_first, original_last);
1234 ? original_coordCount / DIM
1237 diff_type simplified_coordCount = std::distance (simplified_first, simplified_last);
1239 ? simplified_coordCount / DIM
1243 if (original_coordCount % DIM || original_pointCount < 2 ||
1244 simplified_coordCount % DIM || simplified_pointCount < 2 ||
1245 original_pointCount < simplified_pointCount ||
1246 !math::equal <DIM> (original_first, simplified_first))
1255 InputIterator simplified_prev = simplified_first;
1256 std::advance (simplified_first, DIM);
1259 while (simplified_first != simplified_last) {
1261 while (original_first != original_last &&
1262 !math::equal <DIM> (original_first, simplified_first))
1264 *result = math::segment_distance2 <DIM> (simplified_prev, simplified_first,
1267 std::advance (original_first, DIM);
1270 simplified_prev = simplified_first;
1271 std::advance (simplified_first, DIM);
1274 if (original_first != original_last) {
1280 *valid = original_first != original_last;
1318 InputIterator original_first,
1319 InputIterator original_last,
1320 InputIterator simplified_first,
1321 InputIterator simplified_last,
1324 diff_type pointCount = std::distance (original_first, original_last) / DIM;
1332 simplified_first, simplified_last,
1333 errors.
get (), valid));
1337 std::ptr_fun <double, double> (std::sqrt));
1353 OutputIterator& result)
1355 for (
unsigned d = 0; d < DIM; ++d) {
1372 OutputIterator& result)
1389 std::advance (it, n *
static_cast <diff_type> (DIM));
1425 unsigned& remaining)
1427 n = std::min (n, remaining);
1443 unsigned& remaining)
1504 unsigned char* keys)
1509 std::fill_n (keys, pointCount, 0);
1511 keys [pointCount - 1] = 1;
1513 typedef std::stack <SubPoly> Stack;
1516 SubPoly subPoly (0, coordCount-DIM);
1517 stack.push (subPoly);
1519 while (!stack.empty ()) {
1520 subPoly = stack.top ();
1525 keys [keyInfo.
index / DIM] = 1;
1545 unsigned char* keys)
1549 std::fill_n (keys, pointCount, 0);
1551 keys [pointCount - 1] = 1;
1552 unsigned keyCount = 2;
1554 if (countTol == 2) {
1558 typedef std::priority_queue <SubPolyAlt> PriorityQueue;
1559 PriorityQueue queue;
1563 queue.push (subPoly);
1565 while (!queue.empty ()) {
1566 subPoly = queue.top ();
1572 if (keyCount == countTol) {
1610 value_type d2 = math::segment_distance2 <DIM> (coords +
first, coords + last,
1612 if (d2 < keyInfo.
dist2) {
1616 keyInfo.
index = current;
1636 template <
unsigned DIM,
class ForwardIterator,
class OutputIterator>
1638 ForwardIterator
first,
1639 ForwardIterator last,
1641 OutputIterator result)
1659 template <
unsigned DIM,
class ForwardIterator,
class OutputIterator>
1661 ForwardIterator
first,
1662 ForwardIterator last,
1663 typename std::iterator_traits <ForwardIterator>::value_type tol,
1664 OutputIterator result)
1683 template <
unsigned DIM,
class ForwardIterator,
class OutputIterator>
1685 ForwardIterator
first,
1686 ForwardIterator last,
1687 typename std::iterator_traits <ForwardIterator>::value_type tol,
1689 OutputIterator result)
1707 template <
unsigned DIM,
class ForwardIterator,
class OutputIterator>
1709 ForwardIterator
first,
1710 ForwardIterator last,
1711 typename std::iterator_traits <ForwardIterator>::value_type tol,
1712 OutputIterator result)
1730 template <
unsigned DIM,
class ForwardIterator,
class OutputIterator>
1732 ForwardIterator
first,
1733 ForwardIterator last,
1734 typename std::iterator_traits <ForwardIterator>::value_type tol,
1735 OutputIterator result)
1754 template <
unsigned DIM,
class ForwardIterator,
class OutputIterator>
1756 ForwardIterator
first,
1757 ForwardIterator last,
1758 typename std::iterator_traits <ForwardIterator>::value_type min_tol,
1759 typename std::iterator_traits <ForwardIterator>::value_type max_tol,
1760 OutputIterator result)
1763 return ps.
Opheim (
first, last, min_tol, max_tol, result);
1779 template <
unsigned DIM,
class B
idirectionalIterator,
class OutputIterator>
1781 BidirectionalIterator
first,
1782 BidirectionalIterator last,
1783 typename std::iterator_traits <BidirectionalIterator>::value_type tol,
1784 unsigned look_ahead,
1785 OutputIterator result)
1788 return ps.
Lang (
first, last, tol, look_ahead, result);
1803 template <
unsigned DIM,
class ForwardIterator,
class OutputIterator>
1805 ForwardIterator
first,
1806 ForwardIterator last,
1807 typename std::iterator_traits <ForwardIterator>::value_type tol,
1808 OutputIterator result)
1826 template <
unsigned DIM,
class ForwardIterator,
class OutputIterator>
1828 ForwardIterator
first,
1829 ForwardIterator last,
1831 OutputIterator result)
1851 template <
unsigned DIM,
class ForwardIterator,
class OutputIterator>
1853 ForwardIterator original_first,
1854 ForwardIterator original_last,
1855 ForwardIterator simplified_first,
1856 ForwardIterator simplified_last,
1857 OutputIterator result,
1861 return ps.
ComputePositionalErrors2 (original_first, original_last, simplified_first, simplified_last, result, valid);
1877 template <
unsigned DIM,
class ForwardIterator>
1879 ForwardIterator original_first,
1880 ForwardIterator original_last,
1881 ForwardIterator simplified_first,
1882 ForwardIterator simplified_last,
1890 #endif // PSIMPL_GENERIC