Вернуть оптимизированные координаты x, чтобы нормализовать / максимизировать область для массива прямоугольников с определенными позициями y

Question

Я включил фрагмент кода, который, надеюсь, должен хорошо подвести итог и представлен в виде состояния «Заполнить пробелы».

Если это помогает понять причину проблемы, рассматривая ее в более широком контексте, то в конечном итоге я показываю ежедневное расписание просмотра календаря на телефоне, что, вероятно, похоже на то, как работает календарь на вашем телефоне. Когда события начинают перекрываться во времени, представленном здесь вертикальной осью Y, я хочу иметь возможность оптимизировать ширину и расположение этих событий, не перекрывая их и не скрывая больше, чем я, для контента - но когда есть слишком много многие в состоянии указать, что вещи скрыты.

Я не ищу никаких решений на основе CSS / HTML, несмотря на то, что образец находится в javascript - структура 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);

Что касается того, что я пробовал, я начинаю что-то, потом я думаю о дополнительных случаях, и все становится немного бесполезным. Даже в ожидаемых результатах, которые я вычислил в своей голове, я думаю, что мои собственные гуманизированные вычисления немного не верны, поэтому при оценке этой проблемы и взгляде на мой ожидаемый результат, а затем на его рендеринг, это немного не так. Надеемся, что смысл и значение, стоящие за optimizeLeftAndRightXStartPointsForNormalizedRectangleAreaWithoutOverlapping(), более или менее ясны.

Я все еще работаю над потенциальными подходами, но в то же время ищу мудрость толпы, пока она не придет ко мне. Мне любопытно найти решение, но я не нашел правильный путь.

Answer 1

Алгоритм в этом ответе пытается расположить прямоугольники внутри ограничительной рамки фиксированной ширины. Входными данными в алгоритм является массив прямоугольников, чьи значения topY и bottomY указаны. Алгоритм вычисляет leftX и rightX для каждого прямоугольника. Прямоугольники имеют размеры и расположение, чтобы избежать наложения. Например, изображение ниже показывает 7 прямоугольников, которые были сгруппированы по алгоритму. В области 1 максимальное перекрытие равно 2, поэтому прямоугольники отрисовываются на половину ширины. Область 2 не имеет перекрытия, поэтому прямоугольник имеет полную ширину. И область 3 имеет перекрытие 3, и поэтому прямоугольники составляют одну треть ширины ограничительной рамки.

Алгоритм состоит из трех основных шагов:

1. Заполните eventQueue на основе информации во входном массиве. Каждый прямоугольник порождает два события: EVENT_START с topY и EVENT_STOP с bottomY. eventQueue является приоритетом очередь, где приоритет основан на трех значениях, которые определяют событие (оценивается в указанном порядке):
   • y: более низкие значения y имеют приоритет.
   • type: EVENT_STOP имеет приоритет над EVENT_START.
   • rectID: более низкие значения rectID имеют приоритет.
2. Поиск конца региона, пока:
   • сохранение событий в regionQueue. regionQueue - это простой FIFO, который позволяет обрабатывать события во второй раз, после определения размера региона.
   • отслеживание maxOverlap (которое ограничено параметром функции). maxOverlap определяет ширину всех прямоугольники внутри региона.
3. Слить 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);