C++实现的轨迹法临界多边形NFP算法框架来解决多边形套料的示例代码

admin

1. 在多边形碰撞检测中，一种常用的且较为高效的算法是分离轴定理（Separating Axis Theorem, SAT）。该算法的基本思想是，如果两个凸多边形在任意一个轴上投影有交集，则它们可能相交；如果存在至少一个轴，两多边形在该轴上的投影没有交集，则可以确定它们不相交。
3. 以下是在C++中使用分离轴定理实现的`doPolygonsIntersect`函数的完整代码：
5. ```cpp
6. #include <iostream>
7. #include <vector>
8. #include <algorithm>
10. // Define a point
11. struct Point {
12.     double x, y;
13. };
15. // Define a polygon using a vector of points
16. using Polygon = std::vector<Point>;
18. // Compute the projection of a polygon onto an axis
19. std::pair<double, double> projectPolygonOnAxis(const Polygon& polygon, const Point& axis) {
20.     double minProj = polygon.front().x * axis.x + polygon.front().y * axis.y;
21.     double maxProj = minProj;
23.     for (const auto& vertex : polygon) {
24.         double proj = vertex.x * axis.x + vertex.y * axis.y;
25.         minProj = std::min(minProj, proj);
26.         maxProj = std::max(maxProj, proj);
27.     }
29.     return {minProj, maxProj};
30. }
32. // Check if two projections overlap
33. bool doProjectionsOverlap(const std::pair<double, double>& proj1, const std::pair<double, double>& proj2) {
34.     return std::max(proj1.first, proj2.first) <= std::min(proj1.second, proj2.second);
35. }
37. // Generate all edge normals for a polygon
38. std::vector<Point> generateEdgeNormals(const Polygon& polygon) {
39.     std::vector<Point> normals;
40.     for (size_t i = 0; i < polygon.size(); ++i) {
41.         Point edge = {polygon[(i + 1) % polygon.size()].x - polygon[i].x,
42.                       polygon[(i + 1) % polygon.size()].y - polygon[i].y};
43.         double length = std::sqrt(edge.x * edge.x + edge.y * edge.y);
44.         Point normal = {-edge.y / length, edge.x / length};
45.         normals.push_back(normal);
46.     }
47.     return normals;
48. }
50. // Check if two polygons intersect using the Separating Axis Theorem
51. bool doPolygonsIntersect(const Polygon& poly1, const Polygon& poly2) {
52.     auto normals1 = generateEdgeNormals(poly1);
53.     auto normals2 = generateEdgeNormals(poly2);
55.     for (const auto& n : normals1) {
56.         auto proj1 = projectPolygonOnAxis(poly1, n);
57.         auto proj2 = projectPolygonOnAxis(poly2, n);
58.         if (!doProjectionsOverlap(proj1, proj2)) {
59.             return false;
60.         }
61.     }
63.     for (const auto& n : normals2) {
64.         auto proj1 = projectPolygonOnAxis(poly1, n);
65.         auto proj2 = projectPolygonOnAxis(poly2, n);
66.         if (!doProjectionsOverlap(proj1, proj2)) {
67.             return false;
68.         }
69.     }
71.     return true;
72. }
74. int main() {
75.     // Example polygons
76.     Polygon poly1 = {{0, 0}, {4, 0}, {4, 4}, {0, 4}};
77.     Polygon poly2 = {{3, 3}, {6, 3}, {6, 6}, {3, 6}};
79.     bool intersect = doPolygonsIntersect(poly1, poly2);
80.     std::cout << "Do the polygons intersect? " << (intersect ? "Yes" : "No") << std::endl;
82.     return 0;
83. }
84. ```
86. 在这个代码中，`projectPolygonOnAxis`函数计算多边形在指定轴上的投影，`doProjectionsOverlap`函数检查两个投影是否重叠，`generateEdgeNormals`函数生成多边形所有边的法线向量。`doPolygonsIntersect`函数首先为每个多边形生成其所有边的法线，然后对每个法线进行投影并检查投影是否重叠。如果在所有法线中都找不到分离轴，则认为两个多边形相交。
88. 请注意，此代码假设输入的多边形是凸的。如果多边形是非凸的，那么你可能需要使用更复杂的算法，例如将非凸多边形分解成凸多边形，然后分别检查每个凸多边形对之间是否相交。

复制代码