我包含了一个代码片段，希望它能很好地总结一切，并以一种“填空”的状态表示。
如果在更大的背景下查看问题有助于理解问题的根源，那么我最终要做的是在手机日历上显示每日查看时间表，这可能类似于手机日历的工作方式。当事件开始在时间上重叠时，在这里用垂直 y 轴表示，我希望能够优化这些事件的宽度和位置，而不是重叠它们，也不会隐藏超出我必须隐藏的内容——但是当有太多的时候许多能够表明事物是隐藏的。
尽管样本是在 javascript 中，但我并没有在寻找任何基于 CSS/HTML 的解决方案——DOM 结构或多或少是固定不变的，只是在寻找一种算法，如果它是在 C++、TurboPascal、Assembly、Java 中，无论什么都不重要。在我的示例预期结果中，场景越复杂，结果更像是粗略估计，它在演示中以及在呈现我的预期结果时也会出现 - 我什至没有真正在脑海中进行数学运算的好方法一旦事情开始变得奇怪。
目标是填写函数 optimizeLeftAndRightXStartPointsForNormalizedRectangleAreaWithoutOverlapping = (rectangles,minimumArea,minimumWidth,xMin,xMax)=>{}
// Let's say I have an array like this of rectangles where they have set y coordinates
// Some constraints on how this array comes out: it will besorted by the yTop property as shown below, but with no secondary sort criteria.
// The rectangles difference between yBottom and yTop is always at least 15, in other words this array won't contain any rectangles less than 15 in height
const rectanglesYcoordinatesOnlyExample1 = [
{"rectangle_id":"b22d","yTop":0,"yBottom":60},
{"rectangle_id":"8938","yTop":60,"yBottom":120},
{"rectangle_id":"e78a","yTop":60,"yBottom":120},
{"rectangle_id":"81ed","yTop":207,"yBottom":222},
{"rectangle_id":"b446","yTop":207,"yBottom":222},
{"rectangle_id":"ebd3","yTop":207,"yBottom":222},
{"rectangle_id":"2caf","yTop":208,"yBottom":223},
{"rectangle_id":"e623","yTop":227,"yBottom":242},
{"rectangle_id":"e6a3","yTop":270,"yBottom":320},
{"rectangle_id":"e613","yTop":272,"yBottom":460},
{"rectangle_id":"c2d1","yTop":272,"yBottom":290},
{"rectangle_id":"e64d","yTop":274,"yBottom":300},
{"rectangle_id":"b653","yTop":276,"yBottom":310},
{"rectangle_id":"e323","yTop":276,"yBottom":310},
{"rectangle_id":"fca3","yTop":300,"yBottom":315}
]
// I want to get a result sort of like this, explanations provided, although I'm not sure if my internal calculations in my head are 100% on the further I go.
// And I want to a run a function like so:
// optimizeLeftAndRightXStartPointsForNormalizedRectangleAreaWithoutOverlapping(rectanglesYcoordinatesOnlyExample1,(33.3 * 15),10,0,100);
// I will make this call later but I need to hoist my expected results here to enable the mocking to work for now at the point of the function definiton for my example. (see below)
// like so I'd get a result something like this, but I start becoming less certain of what the correct result should be the more I go into fringe stuff.
const expectedResultMoreOrLessForExample1 = [
{"rectangle_id":"b22d","leftX":0,"rightX":100,"yTop":0,"yBottom":60},
{"rectangle_id":"8938","leftX":0,"rightX":50,"yTop":60,"yBottom":120},
{"rectangle_id":"e78a","leftX":50,"rightX":100,"yTop":60,"yBottom":120},
{"rectangle_id":"81ed","leftX":0,"rightX":33.3,"yTop":207,"yBottom":222}, // Three rectangles side by side with minimum Area ["81ed","b446","ebd3"] from this point
{"rectangle_id":"b446","leftX":33.3,"rightX":66.6,"yTop":207,"yBottom":222},
{"rectangle_id":"ebd3","isMax":true,"leftX":66.7,"rightX":100,"yTop":207,"yBottom":222}, // has isMax property because there would be an overlap if it tried the next result, and it can't take area away from the other rectangles
// This rectangle gets thrown out because it would be there are 3 other rectangles in that area each with the minimum area (33.3 * 15);
// {"rectangle_id":"2caf","yTop":208,"yBottom":223}, This one gets thrown out from the result the time being because there are too many rectangles in one area of vertical space.
{"rectangle_id":"e623","yTop":227,"yBottom":242,"leftX":0,"rightX":100},
{"rectangle_id":"e6a3","leftX":0,"rightX":25,"yTop":270,"yBottom":320},
{"rectangle_id":"e613","leftX":25,"rightX":35,"yTop":272,"yBottom":460},
{"rectangle_id":"c2d1","leftX":71.28,"rightX":100,"yTop":272,"yBottom":290}, // fill the remaining space since optimizing to max area would take 99%
{"rectangle_id":"e64d","leftX":35,"rightX":61.28,"yTop":274,"yBottom":300},
{"rectangle_id":"b653","yTop":276,"yBottom":940,"leftX":61.28,rightX:71.28},
{"rectangle_id":"fca3","leftX":35,"rightX":61.28,"yTop":300,"yBottom":315}
]
// the function name is really long to reflect what it is what I want to do. Don't normally make functions this intense
const optimizeLeftAndRightXStartPointsForNormalizedRectangleAreaWithoutOverlapping = (rectangles,minimumArea,minimumWidth,xMin,xMax)=>{
// TODO : fill in the optimization function.
// Code I'm looking for would be swapped in here if you wanted to make changes to demo it do it here
if(rectangles === rectanglesYcoordinatesOnlyExample1 && minimumArea === (33.3 * 15) && minimumWidth === 10 && xMin === 0 && xMax === 100){ // Just handling the example
return expectedResultMoreOrLessForExample1;
} else {
console.log('I only know how to handle example 1, as computed by a human, poorly. fill in the function and replace the block with working stuff');
return [];
}
}
const displayResults = (completedRectangleList) => {
const rectangleColors = ['cyan','magenta','green','yellow','orange']
completedRectangleList.forEach((rectangle,index) =>{
let newRectangle = document.createElement('div');
newRectangle.style.position = 'absolute';
newRectangle.style.height = rectangle.yBottom - rectangle.yTop + 'px';
newRectangle.style.top = rectangle.yTop + 'px';
newRectangle.style.left = parseInt(rectangle.leftX)+'%';
newRectangle.style.width = rectangle.rightX - rectangle.leftX + "%";
newRectangle.style.backgroundColor = rectangleColors[index % rectangleColors.length];
newRectangle.innerHTML = rectangle.rectangle_id;
if(rectangle.isMax){
newRectangle.innerHTML += '- more hidden';
}
document.body.appendChild(newRectangle);
})
}
// I am calling this function with minimum Area of 33.3 * 15, because it represents 3 min height rectangles taking up a third of the minX,maxX values, which are 0 & 100, representing a percentage value ultimately
let resultForExample1 = optimizeLeftAndRightXStartPointsForNormalizedRectangleAreaWithoutOverlapping(rectanglesYcoordinatesOnlyExample1,(33.3 * 15),10,0,100);
displayResults(resultForExample1);就我所尝试的而言，我开始做一些事情，然后我想到一些边缘案例，然后事情变得有点困惑。即使在我脑子里计算出来的预期结果中我也觉得我自己人性化的计算有点偏差，所以在评估这个问题的时候看我的expectedResult再看它的渲染，还是有点偏差。希望 optimizeLeftAndRightXStartPointsForNormalizedRectangleAreaWithoutOverlapping() 背后的意图和含义或多或少是清楚的。
我仍在研究可能的方法，但与此同时寻求人群的智慧，直到找到我为止。我很好奇解决方案，但我还没有找到正确的轨道。
最佳答案
此答案中的算法尝试在固定宽度的边界框内排列矩形。该算法的输入是指定了 topY 和 bottomY 的矩形数组。该算法计算每个矩形的 leftX 和 rightX。矩形的大小和位置是为了避免重叠。例如，下图显示了算法排列的 7 个矩形。在区域 1 中，最大重叠为 2，因此矩形绘制为半宽。区域 2 没有重叠，因此矩形是全宽的。并且区域 3 有重叠 3，因此矩形是边界框宽度的三分之一。
算法分为三个主要步骤:
- 根据输入数组中的信息填充
eventQueue。 每个矩形产生两个事件:一个带有topY的EVENT_START，以及 带有bottomY的EVENT_STOP。eventQueue是一个优先级 队列，其中优先级基于定义的三个值 事件(按所示顺序评估):y:较低的y值优先。type:EVENT_STOP 优先于 EVENT_START。rectID:较低的rectID值优先。
- 搜索区域的结尾，同时:
- 将事件存储到
regionQueue中。regionQueue是一个简单的 FIFO，它允许对事件进行第二次处理， 在确定该区域的范围之后。 - 跟踪
maxOverlap(受函数参数限制)。maxOverlap决定所有的宽度 区域内的矩形。
- 将事件存储到
- 清空
regionQueue，同时计算每个队列的 X 值 区域中的矩形。这部分算法使用了一个数组 称为usedColumns。该数组中的每个条目都是-1(表示该列未在使用中)或一个rectID(表示 哪个矩形正在使用该列)。弹出EVENT_START时 从regionQueue中，一列被分配给矩形。什么时候EVENT_STOP从regionQueue弹出，该列返回到未使用 (-1) 状态。
算法的输入是一个矩形数组。这些矩形的 topY 和 bottomY 值必须由调用者填充。 leftX 和 rightX 值必须初始化为 -1。如果算法结束时 X 值仍为 -1，则无法为矩形分配位置，因为超过了 overlapLimit。所有其他矩形都有完整的坐标集，可以绘制了。
typedef struct
{
int topY; // input parameter, filled in by the caller
int bottomY; // input parameter, filled in by the caller
int leftX; // output parameter, must be initially -1
int rightX; // output parameter, must be initially -1
}
stRect;
typedef struct
{
int y; // this is the 'topY' or 'bottomY' of a rectangle
int type; // either EVENT_START or EVENT_STOP
int rectID; // the index into the input array for this rectangle
}
stEvent;
enum { EVENT_START, EVENT_STOP };
void arrangeRectangles(stRect *rectArray, int length, int overlapLimit, int containerWidth)
{
stQueue *eventQueue = queueCreate();
stQueue *regionQueue = queueCreate();
// fill the event queue with START and STOP events for each rectangle
for (int i = 0; i < length; i++)
{
stEvent startEvent = {rectArray[i].topY, EVENT_START, i};
queueAdd(eventQueue, &startEvent);
stEvent stopEvent = {rectArray[i].bottomY, EVENT_STOP, i};
queueAdd(eventQueue, &stopEvent);
}
while (queueIsNotEmpty(eventQueue))
{
// search for the end of a region, while keeping track of the overlap in that region
int overlap = 0;
int maxOverlap = 0;
stEvent event;
while (queuePop(eventQueue, &event)) // take from the event queue
{
queueAdd(regionQueue, &event); // save in the region queue
if (event.type == EVENT_START)
overlap++;
else
overlap--;
if (overlap == 0) // reached the end of a region
break;
if (overlap > maxOverlap)
maxOverlap = overlap;
}
// limit the overlap as specified by the function parameter
if (maxOverlap > overlapLimit)
maxOverlap = overlapLimit;
// compute the width to be used for rectangles in this region
int width = containerWidth / maxOverlap;
// create and initialize an array to keep track of which columns are in use
int usedColumns[maxOverlap];
for (int i = 0; i < maxOverlap; i++)
usedColumns[i] = -1;
// process the region, computing left and right X values for each rectangle
while (queuePop(regionQueue, &event))
{
if (event.type == EVENT_START)
{
// find an available column for this rectangle, and assign the X values
for (int column = 0; column < maxOverlap; column++)
if (usedColumns[column] < 0)
{
usedColumns[column] = event.rectID;
rectArray[event.rectID].leftX = column * width;
rectArray[event.rectID].rightX = (column+1) * width;
break;
}
}
else
{
// free the column that's being used for this rectangle
for (int i = 0; i < maxOverlap; i++)
if (usedColumns[i] == event.rectID)
{
usedColumns[i] = -1;
break;
}
}
}
}
queueDestroy(eventQueue);
queueDestroy(regionQueue);
}
void example(void)
{
stRect inputArray[] = {
{ 0,150,-1,-1},
{ 30,180,-1,-1},
{180,360,-1,-1},
{360,450,-1,-1},
{420,540,-1,-1},
{450,570,-1,-1},
{480,540,-1,-1}
};
int length = sizeof(inputArray) / sizeof(inputArray[0]);
arrangeRectangles(inputArray, length, 3, 100);
}
注意:我不保证此代码的有效性。彻底的审查和测试留给读者作为练习。
@chairmanmow慷慨地将算法转换为 javascript 以节省其他人寻找 javascript 解决方案的时间。这是翻译:
const topZero = 0;
const parent = i => ((i + 1) >>> 1) - 1;
const left = i => (i << 1) + 1;
const right = i => (i + 1) << 1;
class PriorityQueue {
constructor(comparator = (a, b) => a > b) {
this._heap = [];
this._comparator = comparator;
}
size() {
return this._heap.length;
}
isEmpty() {
return this.size() == 0;
}
peek() {
return this._heap[topZero];
}
push(...values) {
values.forEach(value => {
this._heap.push(value);
this._siftUp();
});
return this.size();
}
pop() {
const poppedValue = this.peek();
const bottom = this.size() - 1;
if (bottom > topZero) {
this._swap(topZero, bottom);
}
this._heap.pop();
this._siftDown();
return poppedValue;
}
replace(value) {
const replacedValue = this.peek();
this._heap[topZero] = value;
this._siftDown();
return replacedValue;
}
_greater(i, j) {
return this._comparator(this._heap[i], this._heap[j]);
}
_swap(i, j) {
[this._heap[i], this._heap[j]] = [this._heap[j], this._heap[i]];
}
_siftUp() {
let node = this.size() - 1;
while (node > topZero && this._greater(node, parent(node))) {
this._swap(node, parent(node));
node = parent(node);
}
}
_siftDown() {
let node = topZero;
while (
(left(node) < this.size() && this._greater(left(node), node)) ||
(right(node) < this.size() && this._greater(right(node), node))
) {
let maxChild = (right(node) < this.size() && this._greater(right(node), left(node))) ? right(node) : left(node);
this._swap(node, maxChild);
node = maxChild;
}
}
}
const rectangles = [{
rectID: "b22d",
"yTop": 0,
"yBottom": 60,
"leftX": -1,
"rightX": -1
},
{
rectID: "8938",
"yTop": 60,
"yBottom": 120,
"leftX": -1,
"rightX": -1
},
{
rectID: "e78a",
"yTop": 60,
"yBottom": 120,
"leftX": -1,
"rightX": -1
},
{
rectID: "81ed",
"yTop": 207,
"yBottom": 222,
"leftX": -1,
"rightX": -1
},
{
rectID: "b446",
"yTop": 207,
"yBottom": 222,
"leftX": -1,
"rightX": -1
},
{
rectID: "ebd3",
"yTop": 207,
"yBottom": 222,
"leftX": -1,
"rightX": -1
},
{
rectID: "2caf",
"yTop": 208,
"yBottom": 223,
"leftX": -1,
"rightX": -1
},
{
rectID: "e623",
"yTop": 227,
"yBottom": 242,
"leftX": -1,
"rightX": -1
},
{
rectID: "e6a3",
"yTop": 270,
"yBottom": 320,
"leftX": -1,
"rightX": -1
},
{
rectID: "e613",
"yTop": 272,
"yBottom": 460,
"leftX": -1,
"rightX": -1
},
{
rectID: "c2d1",
"yTop": 272,
"yBottom": 290,
"leftX": -1,
"rightX": -1
},
{
rectID: "e64d",
"yTop": 274,
"yBottom": 300,
"leftX": -1,
"rightX": -1
},
{
rectID: "b653",
"yTop": 276,
"yBottom": 310,
"leftX": -1,
"rightX": -1
},
{
rectID: "e323",
"yTop": 276,
"yBottom": 310,
"leftX": -1,
"rightX": -1
},
{
rectID: "fca3",
"yTop": 300,
"yBottom": 315,
"leftX": -1,
"rightX": -1
}
];
let eventQueue = new PriorityQueue((a, b) => {
if (a.y !== b.y) return a.y < b.y;
if (a.type !== b.type) return a.type > b.type;
return a.rectID > b.rectID;
})
let regionQueue = []; // FIFO
const EVENT_START = 0;
const EVENT_STOP = 1;
const queueAdd = (queue, toAdd, type, priority) => {
return queue.push(toAdd);
}
const queuePop = (queue) => {
return queue.pop();
}
const queueDestroy = (queue) => {
return queue = [];
}
const optimizeLeftAndRightXStartPointsForNormalizedRectangleAreaWithoutOverlapping = (rectArray, length, overlapLimit, containerWidth) => {
// fill the event queue with START and STOP events for each rectangle
for (let i = 0; i < length; i++) {
let startEvent = {
y: rectArray[i].yTop,
type: EVENT_START,
index: i
};
eventQueue.push(startEvent);
let stopEvent = {
y: rectArray[i].yBottom,
type: EVENT_STOP,
index: i
};
eventQueue.push(stopEvent);
}
while (eventQueue.size()) { // queueIsNotEmpty(eventQueue)
// search for the end of a region, while keeping track of the overlap in that region
let overlap = 0;
let maxOverlap = 0;
let event;
while (event = eventQueue.pop()) { // take from the event queue
queueAdd(regionQueue, event); // save in the region queue
if (event.type === 0) {
overlap++;
} else {
overlap--;
}
if (overlap === 0) { // reached the end of a region
break;
}
// if we have a new maximum for the overlap, update 'maxOverlap'
if (overlap > maxOverlap) {
maxOverlap = overlap;
}
}
// limit the overlap as specified by the function parameter
if (maxOverlap > overlapLimit) {
maxOverlap = overlapLimit;
}
// compute the width to be used for rectangles in this region
const width = parseInt(containerWidth / maxOverlap);
// create and initialize an array to keep track of which columns are in use
let usedColumns = new Array(maxOverlap);
for (let i = 0; i < maxOverlap; i++) {
if (usedColumns[i] == event.rectID) {
usedColumns[i] = -1;
break;
}
}
// process the region, computing left and right X values for each rectangle
while (event = queuePop(regionQueue)) {
if (event.type == 0) {
// find an available column for this rectangle, and assign the X values
for (let column = 0; column < maxOverlap; column++) {
if (usedColumns[column] < 0) {
usedColumns[column] = event.rectID;
rectArray[event.index].leftX = column * width;
rectArray[event.index].rightX = (column + 1) * width;
break;
}
}
} else {
// free the column that's being used for this rectangle
for (let i = 0; i < maxOverlap; i++)
if (usedColumns[i] == event.rectID) {
usedColumns[i] = -1;
break;
}
}
}
}
return rectArray;
}
const displayResults = (completedRectangleList) => {
const rectangleColors = ['cyan', 'magenta', 'green', 'yellow', 'orange']
completedRectangleList.forEach((rectangle, index) => {
if (rectangle.leftX > -1 && rectangle.rightX > -1) {
let newRectangle = document.createElement('div');
newRectangle.style.position = 'absolute';
newRectangle.style.height = rectangle.yBottom - rectangle.yTop + 'px';
newRectangle.style.top = rectangle.yTop + 'px';
newRectangle.style.left = parseInt(rectangle.leftX) + '%';
newRectangle.style.width = rectangle.rightX - rectangle.leftX + "%";
newRectangle.style.backgroundColor = rectangleColors[index % rectangleColors.length];
newRectangle.innerHTML = rectangle.rectID;
if (rectangle.isMax) {
newRectangle.innerHTML += '- more hidden';
}
document.body.appendChild(newRectangle);
}
})
}
let results = optimizeLeftAndRightXStartPointsForNormalizedRectangleAreaWithoutOverlapping(rectangles, (rectangles.length), 3, 100);
console.log('results ' + JSON.stringify(results));
displayResults(results);下面是java代码
public class Main {
public static void main(String[] args) {
ArrayList<stRect> inputArray = new ArrayList<>();
inputArray.add(new stRect( 0,150,-1,-1));
inputArray.add(new stRect( 30,180,-1,-1));
inputArray.add(new stRect( 180,360,-1,-1));
inputArray.add(new stRect( 360,450,-1,-1));
inputArray.add(new stRect( 420,540,-1,-1));
inputArray.add(new stRect( 450,570,-1,-1));
inputArray.add(new stRect( 480,540,-1,-1));
arrangeRectangles(inputArray, inputArray.size(), 3, 100);
for(int i = 0;i<inputArray.size();i++){
System.out.println(inputArray.get(i).topY+" "+inputArray.get(i).bottomY+" "+inputArray.get(i).leftX+" "+inputArray.get(i).rightX);
}
}
private static void arrangeRectangles(ArrayList<stRect>rectArray, int length, int overlapLimit, int containerWidth){
int EVENT_START = 0, EVENT_STOP = 1;
PriorityQueue<stEvent> eventQueue = new PriorityQueue<>(new MyComparator());
Queue<stEvent> regionQueue = new LinkedList<>();
for (int i = 0; i < length; i++) {
stEvent startEvent = new stEvent(rectArray.get(i).topY,EVENT_START, i);
eventQueue.add(startEvent);
stEvent stopEvent = new stEvent(rectArray.get(i).bottomY,EVENT_STOP, i);
eventQueue.add(stopEvent);
}
while (!eventQueue.isEmpty()){
int overlap = 0;
int maxOverlap = 0;
stEvent event;
while (!eventQueue.isEmpty()){ // take from the event queue
event = eventQueue.remove();
regionQueue.add(event); // save in the region queue
if (event.type == EVENT_START)
overlap++;
else
overlap--;
if (overlap == 0) // reached the end of a region
break;
if (overlap > maxOverlap)
maxOverlap = overlap;
}
// limit the overlap as specified by the function parameter
if (maxOverlap > overlapLimit)
maxOverlap = overlapLimit;
// compute the width to be used for rectangles in this region
int width = containerWidth / maxOverlap;
int usedColumns[] = new int[maxOverlap];
for (int i = 0; i < maxOverlap; i++)
usedColumns[i] = -1;
while (!regionQueue.isEmpty()){
event = regionQueue.remove();
if (event.type == EVENT_START) {
// find an available column for this rectangle, and assign the X values
for (int column = 0; column < maxOverlap; column++){
if (usedColumns[column] < 0) {
usedColumns[column] = event.rectID;
rectArray.get(event.rectID).leftX = column * width;
rectArray.get(event.rectID).rightX = (column+1) * width;
break;
}
}
}else {
// free the column that's being used for this rectangle
for (int i = 0; i < maxOverlap; i++){
if (usedColumns[i] == event.rectID)
{
usedColumns[i] = -1;
break;
}
}
}
}
}
eventQueue.clear();
regionQueue.clear();
}
}
public class MyComparator implements Comparator<stEvent> {
@Override
public int compare(stEvent o1, stEvent o2) {
if(o1.y<o2.y)
return -1;
if(o1.y>o2.y)
return 1;
if(o1.type == 0 && o2.type ==1)
return 1;
if(o1.type == 1 && o2.type ==0)
return -1;
if(o1.rectID<o2.rectID)
return -1;
if(o1.rectID>o2.rectID)
return 1;
return 0;
}
}
class stEvent {
int y;
int type;
int rectID;
stEvent(int y, int type, int rectID) {
this.y = y;
this.type = type;
this.rectID = rectID;
}
}
class stRect {
int topY; // input parameter, filled in by the caller
int bottomY; // input parameter, filled in by the caller
int leftX; // output parameter, must be initially -1
int rightX;
stRect(int topY, int bottomY, int leftX, int rightX) {
this.topY = topY;
this.bottomY = bottomY;
this.leftX = leftX;
this.rightX = rightX;
}
}
关于javascript - 返回优化的 x 坐标以标准化/最大化具有定义的 y 位置的矩形数组的区域，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/53215825/