返回优化的 x 坐标以标准化/最大化具有定义的 y 位置的矩形数组的区域

// 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);

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);