Brunobkr/llama.cpp_AlgMor24_github

1import cross from "./cross.js";2 3function lexicographicOrder(a, b) {4  return a[0] - b[0] || a[1] - b[1];5}6 7// Computes the upper convex hull per the monotone chain algorithm.8// Assumes points.length >= 3, is sorted by x, unique in y.9// Returns an array of indices into points in left-to-right order.10function computeUpperHullIndexes(points) {11  const n = points.length,12      indexes = [0, 1];13  let size = 2, i;14 15  for (i = 2; i < n; ++i) {16    while (size > 1 && cross(points[indexes[size - 2]], points[indexes[size - 1]], points[i]) <= 0) --size;17    indexes[size++] = i;18  }19 20  return indexes.slice(0, size); // remove popped points21}22 23export default function(points) {24  if ((n = points.length) < 3) return null;25 26  var i,27      n,28      sortedPoints = new Array(n),29      flippedPoints = new Array(n);30 31  for (i = 0; i < n; ++i) sortedPoints[i] = [+points[i][0], +points[i][1], i];32  sortedPoints.sort(lexicographicOrder);33  for (i = 0; i < n; ++i) flippedPoints[i] = [sortedPoints[i][0], -sortedPoints[i][1]];34 35  var upperIndexes = computeUpperHullIndexes(sortedPoints),36      lowerIndexes = computeUpperHullIndexes(flippedPoints);37 38  // Construct the hull polygon, removing possible duplicate endpoints.39  var skipLeft = lowerIndexes[0] === upperIndexes[0],40      skipRight = lowerIndexes[lowerIndexes.length - 1] === upperIndexes[upperIndexes.length - 1],41      hull = [];42 43  // Add upper hull in right-to-l order.44  // Then add lower hull in left-to-right order.45  for (i = upperIndexes.length - 1; i >= 0; --i) hull.push(points[sortedPoints[upperIndexes[i]][2]]);46  for (i = +skipLeft; i < lowerIndexes.length - skipRight; ++i) hull.push(points[sortedPoints[lowerIndexes[i]][2]]);47 48  return hull;49}50