algorithm - 平铺视频视图的算法

Question

我正在制作一个带有视频聊天的应用程序，并且需要在缩放/团队等屏幕中布局参与者，完全填充一个矩形。我将旋转锁定为横向，所以我预计大多数视频的宽高比约为 16/9，但这可以裁剪，所以它只是目标。

因此，给定 n 个图块和一个 x 乘以 y 的矩形，返回一个包含位置和大小的 n 个矩形的列表，它们将一起完全填充外部矩形。

希望有人知道一种算法，它可以做到这一点，同时尽可能地保持纵横比！

（我尝试制作一个简单的算法，只是逐步添加一列或一行，这取决于哪一个将使图块纵横比匹配最接近 16/9，直到有足够的子图块，然后“加入”未使用的图块，但它来了更复杂，不如我希望的那么好......）

        public static List<Tile> GetTilePartitionResult(
            double width, double height, 
            int partitions, double preferredAspectRatio = 16d/9d)
        {
            var columns = 1;
            var rows = 1;
            var lastAddedRow = false;

            while (columns * rows < partitions)
            {
                // Find out if we should add a row or a column
                var rowAddedAspect = GetAspectRatio(width, height, rows + 1, columns);
                var columnAddedAspect = GetAspectRatio(width, height, rows, columns + 1);

                var rowAddedDiffFromIdeal = Math.Abs(preferredAspectRatio - rowAddedAspect);
                var columnAddedDiffFromIdeal = Math.Abs(preferredAspectRatio - columnAddedAspect);

                if (rowAddedDiffFromIdeal < columnAddedDiffFromIdeal)
                {
                    rows++;
                    lastAddedRow = true;
                }
                else
                {
                    columns++;
                    lastAddedRow = false;
                }
            }
            
            // Since after adding the "last" divider we might have an excess number of cells
            // So trim the "other" dimension until there is just enough tiles
            if (lastAddedRow)
            {
                while (((columns - 1) * rows) >= partitions) columns--;
            }
            else
            {
                while (((rows - 1) * columns) >= partitions) rows--;
            }

            // Assume we have the optimal grid/column setup, now distribute 
            // the tiles over this grid
            var tileHeight = height / rows;
            var tileWidth = width / columns;
            var tiles = new List<Tile>();
            for (var row = 0; row < rows; row++)
            {
                for (var column = 0; column < columns; column++)
                {
                    var newTile = new Tile
                    {
                        Height = tileHeight,
                        Width = tileWidth,
                        XOffSet = column * tileWidth,
                        YOffSet = row * tileHeight,
                        GridX = column,
                        GridY = row
                    };
                    tiles.Add(newTile);
                    
                    // Was this the last tile:
                    if (tiles.Count == partitions)
                    {
                        // Yes -> check if there is free space on this column
                        var extraColumns = columns - 1 - column;
                        if (extraColumns > 0)
                        {
                            // this extra space can be used in 2 ways,
                            // either expand current tile with, or expand
                            // height of previous row columns(the cells that are "above" the empty space)
                            // We decide which is best by choosing the resulting aspect ratio which
                            // most closely matches desired aspect ratio
                            var newWidthIfExpandingHorizontally = newTile.Width + (extraColumns * tileWidth);
                            var newHeightIfExpandingVertically = height * 2;
                            var aspectRatioIfExpandingHorizontally =
                                GetAspectRatio(newWidthIfExpandingHorizontally, height, 1, 1);
                            var aspectRationIfExpandingVertically =
                                GetAspectRatio(width, newHeightIfExpandingVertically, 1, 1);
                            if (Math.Abs(aspectRatioIfExpandingHorizontally - preferredAspectRatio) <
                                Math.Abs(aspectRationIfExpandingVertically - preferredAspectRatio))
                            {
                                // TODO: Should consider widening multiple "right" places tiles
                                // and move some down if extra cells > 1 .... Next time...
                                newTile.Width = newWidthIfExpandingHorizontally;
                            }
                            else
                            {
                                // Find all tiles in previous row above empty space and change height:
                                var tilesToExpand = tiles.Where(t => t.GridY == row - 1 && t.GridX > column);
                                foreach (var tile in tilesToExpand)
                                {
                                    tile.Height = newHeightIfExpandingVertically;
                                }
                            }
                        }
                        // Nothing else to do on this column(we filled it...)
                        break;
                    }
                }
            }

            return tiles;
        }

PS我的代码是用C#编写的，但这确实是一个通用算法问题......

标签： algorithm