File indexing completed on 2024-05-12 03:52:08
0001 /******************************************************************************* 0002 * Author : Angus Johnson * 0003 * Date : 28 January 2023 * 0004 * Website : http://www.angusj.com * 0005 * Copyright : Angus Johnson 2010-2023 * 0006 * Purpose : Minkowski Sum and Difference * 0007 * License : http://www.boost.org/LICENSE_1_0.txt * 0008 *******************************************************************************/ 0009 0010 #ifndef CLIPPER_MINKOWSKI_H 0011 #define CLIPPER_MINKOWSKI_H 0012 0013 #include <cstdlib> 0014 #include <vector> 0015 #include <string> 0016 #include "clipper.core.h" 0017 0018 namespace Clipper2Lib 0019 { 0020 0021 namespace detail 0022 { 0023 inline Paths64 Minkowski(const Path64& pattern, const Path64& path, bool isSum, bool isClosed) 0024 { 0025 size_t delta = isClosed ? 0 : 1; 0026 size_t patLen = pattern.size(), pathLen = path.size(); 0027 if (patLen == 0 || pathLen == 0) return Paths64(); 0028 Paths64 tmp; 0029 tmp.reserve(pathLen); 0030 0031 if (isSum) 0032 { 0033 for (const Point64& p : path) 0034 { 0035 Path64 path2(pattern.size()); 0036 std::transform(pattern.cbegin(), pattern.cend(), 0037 path2.begin(), [p](const Point64& pt2) {return p + pt2; }); 0038 tmp.push_back(path2); 0039 } 0040 } 0041 else 0042 { 0043 for (const Point64& p : path) 0044 { 0045 Path64 path2(pattern.size()); 0046 std::transform(pattern.cbegin(), pattern.cend(), 0047 path2.begin(), [p](const Point64& pt2) {return p - pt2; }); 0048 tmp.push_back(path2); 0049 } 0050 } 0051 0052 Paths64 result; 0053 result.reserve((pathLen - delta) * patLen); 0054 size_t g = isClosed ? pathLen - 1 : 0; 0055 for (size_t h = patLen - 1, i = delta; i < pathLen; ++i) 0056 { 0057 for (size_t j = 0; j < patLen; j++) 0058 { 0059 Path64 quad; 0060 quad.reserve(4); 0061 { 0062 quad.push_back(tmp[g][h]); 0063 quad.push_back(tmp[i][h]); 0064 quad.push_back(tmp[i][j]); 0065 quad.push_back(tmp[g][j]); 0066 }; 0067 if (!IsPositive(quad)) 0068 std::reverse(quad.begin(), quad.end()); 0069 result.push_back(quad); 0070 h = j; 0071 } 0072 g = i; 0073 } 0074 return result; 0075 } 0076 0077 inline Paths64 Union(const Paths64& subjects, FillRule fillrule) 0078 { 0079 Paths64 result; 0080 Clipper64 clipper; 0081 clipper.AddSubject(subjects); 0082 clipper.Execute(ClipType::Union, fillrule, result); 0083 return result; 0084 } 0085 0086 } // namespace internal 0087 0088 inline Paths64 MinkowskiSum(const Path64& pattern, const Path64& path, bool isClosed) 0089 { 0090 return detail::Union(detail::Minkowski(pattern, path, true, isClosed), FillRule::NonZero); 0091 } 0092 0093 inline PathsD MinkowskiSum(const PathD& pattern, const PathD& path, bool isClosed, int decimalPlaces = 2) 0094 { 0095 int error_code = 0; 0096 double scale = pow(10, decimalPlaces); 0097 Path64 pat64 = ScalePath<int64_t, double>(pattern, scale, error_code); 0098 Path64 path64 = ScalePath<int64_t, double>(path, scale, error_code); 0099 Paths64 tmp = detail::Union(detail::Minkowski(pat64, path64, true, isClosed), FillRule::NonZero); 0100 return ScalePaths<double, int64_t>(tmp, 1 / scale, error_code); 0101 } 0102 0103 inline Paths64 MinkowskiDiff(const Path64& pattern, const Path64& path, bool isClosed) 0104 { 0105 return detail::Union(detail::Minkowski(pattern, path, false, isClosed), FillRule::NonZero); 0106 } 0107 0108 inline PathsD MinkowskiDiff(const PathD& pattern, const PathD& path, bool isClosed, int decimalPlaces = 2) 0109 { 0110 int error_code = 0; 0111 double scale = pow(10, decimalPlaces); 0112 Path64 pat64 = ScalePath<int64_t, double>(pattern, scale, error_code); 0113 Path64 path64 = ScalePath<int64_t, double>(path, scale, error_code); 0114 Paths64 tmp = detail::Union(detail::Minkowski(pat64, path64, false, isClosed), FillRule::NonZero); 0115 return ScalePaths<double, int64_t>(tmp, 1 / scale, error_code); 0116 } 0117 0118 } // Clipper2Lib namespace 0119 0120 #endif // CLIPPER_MINKOWSKI_H