1

我通过ExpressionsBasedModel使用 ojAlgo 线性/二次求解器来求解绘图库中图形元素的布局，以便它们整齐地适合屏幕边界。具体来说，我想解决比例和平移问题，以便散点图的坐标填满屏幕空间。我通过声明的比例和平移变量来做到这一点，并ExpressionsBasedModel使用这些变量将散点图坐标转换到屏幕上，然后构造转换后的坐标应该投射到屏幕内的线性约束。我还为比例变量添加了一个负成本，以便它们最大化并且散点图覆盖尽可能多的屏幕空间。我的问题是在某些特殊情况下，例如，如果我只有一个点要绘制，这会导致一个无界问题，其中规模趋于无穷大而没有任何约束处于活动状态。如何检测会发生这种情况的比例变量并将它们修复为一些默认值？

为了说明上述问题，我构建了一个玩具绘图库（我正在研究的完整库太大而无法解决这个问题）。为了帮助布局图形元素，我有一个问题类：

class Problem {
    private ArrayList<Variable> _scale_variables = new ArrayList<Variable>();
    private ExpressionsBasedModel _model = new ExpressionsBasedModel();

    Variable freeVariable() {
        return _model.addVariable();
    }

    Variable scaleVariable() {
        Variable x = _model.addVariable();
        x.lower(0.0); // Negative scale not allowed
        _scale_variables.add(x);
        return x;
    }

    Expression expr() {
        return _model.addExpression();
    }

    Result solve() {
        for (Variable scale_var: _scale_variables) {

            // This is may result in unbounded solution for degenerate cases.
            Expression expr = _model.addExpression("Encourage-larger-scale");
            expr.set(scale_var, -1.0);
            expr.weight(1.0);
        }
        return _model.minimise();
    }
}

它包装了一个ExpressionsBasedModel并有一些工具来创建变量。对于我将用来将散点坐标映射到屏幕坐标的转换，我有这个类：

class Transform2d {
    Variable x_scale;
    Variable y_scale;
    Variable x_translation;
    Variable y_translation;

    Transform2d(Problem problem) {
        x_scale = problem.scaleVariable();
        y_scale = problem.scaleVariable();
        x_translation = problem.freeVariable();
        y_translation = problem.freeVariable();
    }

    void respectBounds(double x, double y, double marker_size,
        double width, double height,
        Problem problem) {
        // Respect left and right screen bounds
        {
            Expression expr = problem.expr();
            expr.set(x_scale, x);
            expr.set(x_translation, 1.0);
            expr.lower(marker_size);
            expr.upper(width - marker_size);
        }

        // Respect top and bottom screen bounds
        {
            Expression expr = problem.expr();
            expr.set(y_scale, y);
            expr.set(y_translation, 1.0);
            expr.lower(marker_size);
            expr.upper(height - marker_size);
        }            
    }
}

该方法用于在前面提到respectBounds的类的散点图中添加单个点的约束。Problem要添加散点图的所有点，我有这个功能：

void addScatterPoints(
    double[] xy_pairs,

    // How much space every marker occupies
    double marker_size,

    Transform2d transform_to_screen,

    // Screen size
    double width, double height,

    Problem problem) {

    int data_count = xy_pairs.length/2;
    for (int i = 0; i < data_count; i++) {
        int offset = 2*i;
        double x = xy_pairs[offset + 0];
        double y = xy_pairs[offset + 1];
        transform_to_screen.respectBounds(x, y, marker_size, width, height, problem);
    }
}

首先，让我们看看非退化案例是什么样子的。我指定用于散点图的屏幕大小和标记的大小。我还指定要绘制的数据、构建问题并解决它。这是代码

    Problem problem = new Problem();
    double marker_size = 4;
    double width = 800;
    double height = 600;

    double[] data_to_plot = new double[] {
        1.0, 2.0,
        4.0, 9.3,
        7.0, 4.5};

    Transform2d transform = new Transform2d(problem);
    addScatterPoints(data_to_plot, marker_size, transform, width, height, problem);

    Result result = problem.solve();
    System.out.println("Solution: " + result);

打印出来Solution: OPTIMAL -81.0958904109589 @ { 0, 81.0958904109589, 795.99999999999966, -158.19178082191794 }。

这是退化情况的样子，用相同的 y 坐标绘制两个点：

    Problem problem = new Problem();

    double marker_size = 4;
    double width = 800;
    double height = 600;

    double[] data_to_plot = new double[] {
        1, 1,
        9, 1
    };

    Transform2d transform = new Transform2d(problem);
    addScatterPoints(data_to_plot, marker_size, transform, width, height, problem);

    Result result = problem.solve();
    System.out.println("Solution: " + result);

它显示Solution: UNBOUNDED -596.0 @ { 88.44444444444444, 596, 0, 0 }. 如前所述，我的问题是：如何检测负成本会导致无界解决方案的比例变量并将它们限制为某个默认值，以便我的解决方案不是无界的？

4

0 回答 0