如何找到k个最小包围矩形以包围所有给定点? [英] How can I find k minimum bounding rectangles to enclose all the given points?
问题描述
给定一个参数k作为盒子和n个数据点的数量，我是否还能找到或近似于k个轴对齐的包围矩形，包围所有的点，同时使矩形的面积之和最小?
Given a parameter k for the number of boxes and n data points, is there anyway I can find or approximate k axis-aligned bounding rectangles that enclose all the points while keeping the sum of the area of the rectangles minimum?
推荐答案
一种方法是将其直接写为数学优化问题.
One way is to directly write this as a mathematical optimization problem.
高级优化模型如下所示:
A high-level optimization model can look like as follows:
我们首先定义决策变量:
We first define the decision variables:
r(k,c) = coordinates for k-th box (e.g. c={x,y,w,h})
continuous variable with appropriate bounds
x(i,k) = 1 if point i is assigned to box k
0 otherwise
binary variable
然后2D模型如下所示:
Then the 2D model can look like:
minimize sum(k, r(k,w)*r(k,h)) (sum of areas)
sum(k, x(i,k)) = 1 (assign point to one box)
x(i,k) = 1 ==> point i is inside box k (can be formulated as linear big-M constraints
or indicator constraints )
为了进行测试，我在[0,1] x [0,1]单位框中生成了30个点.
For testing, I generated 30 points in [0,1]x[0,1] unit box.
使用 | k | = 5 框，我们得到:
这可以直接推广到更多维度(绘图变得更加困难).
This can be directly generalized to more dimensions (plotting becomes more difficult).
从本质上讲，这是一个模型，它将分配问题(对于x变量)和位置问题(对于r变量)组合在一起.它可能仅适用于相对较小的数据集.在此示例中，我使用了Gurobi(非凸MIQP)，这是公认的全球最佳解决方案.需要注意的是，即使对于更高维度的问题，我们也可以将其重新构造为非凸的MIQCP(即可以由Gurobi求解).
This is essentially a model that combines an assignment problem (for the x variables) and a location problem (for the r variables). It probably only works for relatively small data sets. For this example, I used Gurobi (non-convex MIQP) and this is the proven globally optimal solution. It is noted that even for higher dimensional problems, we can reformulate things into a non-convex MIQCP (i.e. solvable by Gurobi).
为完整起见，上述模型的数据和结果为:
For completeness, the data and results for the above model were:
---- 52 PARAMETER p data points
x y
i1 0.806 0.173
i2 0.530 0.149
i3 0.648 0.692
i4 0.352 0.020
i5 0.431 0.554
i6 0.641 0.775
i7 0.235 0.781
i8 0.268 0.082
i9 0.973 0.114
i10 0.874 0.667
i11 0.756 0.968
i12 0.199 0.240
i13 0.220 0.261
i14 0.989 0.172
i15 0.066 0.930
i16 0.806 0.832
i17 0.105 0.029
i18 0.229 0.094
i19 0.130 0.903
i20 0.437 0.728
i21 0.248 0.575
i22 0.360 0.516
i23 0.710 0.746
i24 0.704 0.746
i25 0.185 0.936
i26 0.817 0.673
i27 0.463 0.578
i28 0.089 0.657
i29 0.973 0.691
i30 0.894 0.078
---- 52 VARIABLE x.L assignment variables
k1 k2 k3 k4 k5
i1 1.000
i2 1.000
i3 1.000
i4 1.000
i5 1.000
i6 1.000
i7 1.000
i8 1.000
i9 1.000
i10 1.000
i11 1.000
i12 1.000
i13 1.000
i14 1.000
i15 1.000
i16 1.000
i17 1.000
i18 1.000
i19 1.000
i20 1.000
i21 1.000
i22 1.000
i23 1.000
i24 1.000
i25 1.000
i26 1.000
i27 1.000
i28 1.000
i29 1.000
i30 1.000
---- 52 VARIABLE r.L rectangles
x y w h
k1 0.066 0.575 0.181 0.361
k2 0.105 0.020 0.247 0.241
k3 0.360 0.516 0.103 0.211
k4 0.530 0.078 0.459 0.095
k5 0.641 0.667 0.332 0.301
---- 52 VARIABLE z.L = 0.290 objective
这篇关于如何找到k个最小包围矩形以包围所有给定点?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
