27 skyline_.push_back(SkylineSegment{0, 0, this->
width()});
33 return area_so_far_ / ((float)this->
width() * this->
height());
37 struct SkylineSegment {
43 std::vector<SkylineSegment> skyline_;
51 bool rectangleFits(
int skylineIndex,
int width,
int height,
int*
y)
const;
54 void addSkylineLevel(
int skylineIndex,
int x,
int y,
int width,
int height);
58 if ((
unsigned)
width > (
unsigned)this->
width() ||
59 (
unsigned)height > (
unsigned)this->
height()) {
64 int bestWidth = this->
width() + 1;
66 int bestY = this->
height() + 1;
68 for (
int i = 0; i < (
int)skyline_.size(); ++i) {
72 if (
y < bestY || (
y == bestY && skyline_[i].width_ < bestWidth)) {
74 bestWidth = skyline_[i].width_;
75 bestX = skyline_[i].x_;
82 if (-1 != bestIndex) {
83 this->addSkylineLevel(bestIndex, bestX, bestY,
width,
height);
96bool SkylineRectanglePacker::rectangleFits(
int skylineIndex,
100 int x = skyline_[skylineIndex].x_;
105 int widthLeft =
width;
106 int i = skylineIndex;
107 int y = skyline_[skylineIndex].y_;
108 while (widthLeft > 0 && i < (
int)skyline_.size()) {
109 y = std::max(
y, skyline_[i].y_);
113 widthLeft -= skyline_[i].width_;
121void SkylineRectanglePacker::addSkylineLevel(
int skylineIndex,
126 SkylineSegment newSegment;
129 newSegment.width_ =
width;
130 skyline_.insert(std::next(skyline_.begin(), skylineIndex), newSegment);
132 FML_DCHECK(newSegment.x_ + newSegment.width_ <= this->width());
136 for (
int i = skylineIndex + 1; i < (
int)skyline_.size(); ++i) {
138 FML_DCHECK(skyline_[i - 1].x_ <= skyline_[i].x_);
140 if (skyline_[i].x_ < skyline_[i - 1].x_ + skyline_[i - 1].width_) {
141 int shrink = skyline_[i - 1].x_ + skyline_[i - 1].width_ - skyline_[i].x_;
143 skyline_[i].x_ += shrink;
144 skyline_[i].width_ -= shrink;
146 if (skyline_[i].width_ <= 0) {
148 skyline_.erase(std::next(skyline_.begin(), i));
160 for (
int i = 0; i < ((
int)skyline_.size()) - 1; ++i) {
161 if (skyline_[i].y_ == skyline_[i + 1].y_) {
162 skyline_[i].width_ += skyline_[i + 1].width_;
163 skyline_.erase(std::next(skyline_.begin(), i));
171 return std::make_unique<SkylineRectanglePacker>(
width,
height);
Type::kYUV Type::kRGBA() int(0.7 *637)
Packs rectangles into a specified area without rotating them.
static std::unique_ptr< RectanglePacker > Factory(int width, int height)
Return an empty packer with area specified by width and height.
float percentFull() const final
Returns how much area has been filled with rectangles.
void reset() final
Empty out all previously added rectangles.
~SkylineRectanglePacker() final
bool addRect(int w, int h, IPoint16 *loc) final
Attempt to add a rect without moving already placed rectangles.
SkylineRectanglePacker(int w, int h)
#define FML_DCHECK(condition)