将任意三角形装入有限大小的盒子中？

Question

我需要尽可能紧密地将三角形装进一个盒子中，这是3D优化的一部分（我正在将使用alpha通道的不同纹理段填充到单个不同的纹理中，用于深度排序，以便纹理不会在每个新三角形时切换）

是否有一种算法可以实现这一点？三角形本身可以变得灵活（可以通过变形成为直角，从而有效地将其作为箱子填充算法），但如果可能的话，我想避免这样做，因为它会扭曲底层的纹理艺术。

- Anne Quinn

---

有趣的问题。 三角形的反射和任意旋转是否被允许？ - j_random_hacker

嗯，有32种（而不是16种）方法可以将2个三角形A和B组合在一起，避免扩展A的边界框中的任意1条边：B相对于A的4个90度旋转，以及每个旋转的以下8个“布局”：A与B的{左侧，右侧}对齐其{顶部，底部}最靠近的点；A {上方，下方} B，使它们的{左侧，右侧}最靠近的点对齐。但是，我认为仅考虑这些是不够的 - 可能通过将B放置在某些“中间”位置来获得更小的整体边界框... :( - j_random_hacker

很抱歉，我没有一个“完整”的答案要给出，但请忽略关闭投票 - 这些天几乎每个问题都会累积这些投票，也许是因为它们只能被投“赞成”。在我看来，这是一个非常有趣的问题，最好保持开放状态 :) - j_random_hacker

我很确定这个问题是NP完全的。快速搜索后，我发现了一个5页的论文，描述了一种将三角形装入正方形容器的启发式算法，但我不认为你能找到一个完美的多项式时间解决方案。 - daxvena

仅为澄清，此处的“box”是三维（长方体）还是二维（正方形/矩形）？我习惯于在2D中看到启发式算法，将三角形或四边形打包到纹理坐标UV空间中，但没有一个在3D中运行的算法。 - user4842163

Answer 1

"tight as reasonable" -> 比无为好

这些代码片段提供了一种简单的解决方案，可以将形状（包括三角形）逐层填充到矩形中。

public abstract class Shape {
    protected Point offset = new Point();
    public abstract int getHeight();
    public abstract int getWidth();
}

public class Triangle extends Shape {
    // all points are relative to offset (from Shape)
    Point top = new Point(); // top.y is always 0, left.y >= 0 right.y >= 0 
    Point left = new Point(); // left.x < right.x
    Point right = new Point();

    public int getHeight() {
        return left.y >= right.y ? left.y : right.y;
    }

    public int getWidth() {
        int xmin = left.x <= top.x ? left.x : top.x;
        int xmax = right.x >= top.x ? right.x : top.x;
        return xmax - xmin;
    }
}

public class StuffRectangle extends Shape {
    private Point ww = new Point();

    private ArrayList<Shape> maintained = new ArrayList<Shape>();
    private int insx;
    private int insy;
    private int maxy;

    public int getHeight() {
        return ww.y;
    }

    public int getWidth() {
        return ww.x;
    }

    public void clear() {
        insx = 0;
        insy = 0;
        maxy = 0;
        maintained.clear();
    }

    /**
     * Fill the rectangle band by band.
     * 
     * The inserted shapes are removed from the provided shape collection.
     * 
     * @param shapes
     *            the shapes to insert
     * @return the count of inserted shapes.
     */
    public int stuff(Collection<Shape> shapes) {
        int inserted = 0;

        for (;;) {
            int insertedInPass = 0;
            for (Iterator<Shape> i = shapes.iterator(); i.hasNext();) {
                Shape shape = i.next();

                // does the shape fit into current band?
                int sx = shape.getWidth();
                if (insx + sx > getWidth())
                    continue;
                int sy = shape.getHeight();
                if (insy + sy > getHeight())
                    continue;

                // does fit
                ++insertedInPass;

                // remove from shapes
                i.remove();

                // add to maintained and adjust offset
                maintained.add(shape);
                shape.offset.x = insx;
                shape.offset.y = insy;

                insx += sx;
                if (sy > maxy)
                    maxy = sy;

            }
            inserted += insertedInPass;
            if (shapes.isEmpty())
                break;
            // nothing fits current band - try a new band
            if (insertedInPass == 0) {
                // already a new band - does not fit at all
                if (insx == 0)
                    break;

                // start new band
                insx = 0;
                insy += maxy;
                maxy = 0;
                continue;
            }
        }

        return inserted;
    }
}

- bebbo