C++2d矩形2d最小面积二叉树装箱,箱子知道长宽,矩形数据为double型,包含ID,长宽,矩形允许旋转 90度,并且返回矩形的摆放位置,代码
时间: 2023-10-16 14:06:17 浏览: 91
以下是C++实现矩形最小面积二叉树装箱的代码,其中包含矩形ID,长宽,是否旋转以及矩形的放置位置和朝向。
```c++
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
struct Rect {
int id;
double width;
double height;
bool rotated;
double x;
double y;
double angle;
bool operator<(const Rect& other) const {
return width > other.width;
}
};
struct Node {
Node* left;
Node* right;
Rect rect;
double x;
double y;
Node(Rect r) : rect(r), left(nullptr), right(nullptr), x(0), y(0) {}
~Node() {
if (left) delete left;
if (right) delete right;
}
};
Node* insert(Node* node, Rect rect, double width, double height) {
if (!node) {
node = new Node(rect);
node->x = 0;
node->y = 0;
node->rect.x = node->x;
node->rect.y = node->y;
return node;
}
if (node->left && node->right) {
Node* new_node = insert(node->left, rect, width, height);
if (new_node) {
return new_node;
}
return insert(node->right, rect, width, height);
} else {
double w = node->rect.width + rect.width;
double h = max(node->rect.height, rect.height);
if (w <= width && h <= height) {
Node* new_node = nullptr;
if (!node->left) {
new_node = new Node(rect);
new_node->x = node->rect.width;
new_node->y = 0;
new_node->rect.x = node->x + new_node->x;
new_node->rect.y = node->y + new_node->y;
node->left = new_node;
} else {
new_node = new Node(rect);
new_node->x = 0;
new_node->y = node->rect.height;
new_node->rect.x = node->x + new_node->x;
new_node->rect.y = node->y + new_node->y;
node->right = new_node;
}
return new_node;
}
}
return nullptr;
}
void print_tree(Node* node) {
if (!node) return;
cout << "Rect ID: " << node->rect.id << " Width: " << node->rect.width << " Height: " << node->rect.height << " X: " << node->x << " Y: " << node->y;
if (node->rect.rotated) cout << " Angle: " << node->rect.angle;
cout << endl;
print_tree(node->left);
print_tree(node->right);
}
double pack(vector<Rect>& rects, double width, double height) {
sort(rects.begin(), rects.end());
Node* root = nullptr;
for (auto& rect : rects) {
Node* node = insert(root, rect, width, height);
if (!node) {
root = insert(root, rect, height, width);
rect.rotated = true;
swap(rect.width, rect.height);
}
}
print_tree(root);
delete root;
return 0;
}
int main() {
vector<Rect> rects{
{ 1, 20, 10 },
{ 2, 10, 40 },
{ 3, 30, 5 },
{ 4, 5, 30 },
{ 5, 15, 15 },
{ 6, 10, 10 },
{ 7, 20, 20 },
{ 8, 15, 5 },
{ 9, 5, 15 },
{ 10, 10, 5 }
};
double width = 50;
double height = 50;
pack(rects, width, height);
return 0;
}
```
这里使用了最简单的二叉树装箱算法,将每个矩形从大到小排序,然后尝试将它们插入到已有的节点中。如果节点有两个子节点,则先尝试将矩形插入到左子节点中,如果不行则尝试右子节点。如果节点只有一个子节点或没有子节点,则尝试将矩形插入到该节点中。如果插入成功,则将新的矩形节点返回,否则返回nullptr。如果无法放入,则尝试在高度方向上旋转矩形并再次尝试放置。
在每个节点中,存储了矩形以及该节点的坐标,如果矩形被旋转,则还存储了旋转角度。在装箱结束后,打印出每个矩形的摆放位置和朝向。
阅读全文