Лучший способ рассчитать толерантность Рамера-Дугласа-Пекера

Question

Я использую реализацию алгоритма Рамера Дугласа Пекера, чтобы уменьшить количество точек, которые у меня есть для маршрута карты. Например, если у меня больше 500 баллов, я хочу запустить алгоритм с допуском, который уменьшит количество баллов до менее 500, будучи как можно ближе к нему. То, что я пробовал до сих пор, что невероятно неэффективно, это следующее:

      simp = coordSimplify(data.tableData, 0)
while (simp.length > 400) {
    i += 0.0001;
    simp = coordSimplify(data.tableData, i);
}

Но я понимаю, что это сильно замедлит весь процесс.

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

TIA

Answer 1

Предложите попробовать что-нибудь в следующих строках, что по сути является бинарным поиском, ищущим epsilonзначение (используя терминологию https://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93Peucker_algorithm), которое попадает в диапазон длины целевой точки simpTargetLo и simpTargetHi.

(Обратите внимание, что я не тестировал это, так как у меня нет доступа, поэтому может быть несколько синтаксических ошибок, но логика должна быть правильной.)

      // Set the acceptable result.
let simpTargetLo = 490;
let simpTargetHi = 510;

// Set the initial epsilon range which needs to be outside the estimated solution.
let epsilonLo = 0;
let epsilonHi = 1;
let epsilonMid;

// Calculate the initial low and high simp values.
let simpLo = coordSimplify(data.tableData, epsilonLo);
let simpHi = coordSimplify(data.tableData, epsilonHi);
let simpMid;

// Ensure that the initial simp values fall outside the target range.
if ( !( simpLo.length <= simpTargetLo && simpTargetHi <= simpHi.length ) ) {
  throw new Error( `Initial epsilon need expanding.\n  epsilonLo ${epsilonLo} returns ${simpLo.length}\n  epsilonHi ${epsilonHi} returns ${simpHi.length}` );
}

// Finally, let's ensure we don't get into an infinite loop in the event that
// their is no solution or the solution oscillates outside the target range.
let iterations = 0;
let maxIterations = 100;

do {
  
  // Calculate the simp at the midpoint of the low and high epsilon.
  epsilonMid = ( epsilonLo + epsilonHi ) / 2;
  simpMid = coordSimplify(data.tableData, epsilonMid );
  
  // Narrow the epsilon low and high range if the simp result is still outside
  // both the target low and high.
  if ( simpMid.length < simpTargetLo ) {
    epsilonLo = epsilonMid;
  } else if ( simpTargetHi < simpMid.length ) {
    epsilonHi = epsilonMid;
  } else {
    // Otherwise, we have a solution!
    break;
  }
  
  iterations++;
  
while( iterations < maxIterations );

if ( iterations < maxIterations ) {
  console.log( `epsilon ${epsilonMid} returns ${simpMid.length}` );
} else {
  console.log( `Unable to find solution.` );
}

Обратите внимание, что этот метод сужения к решению зависит от правильного выбора начальной epsilonLo и epsilonHi, в дополнение к предположению, что coordSimplify() имеет довольно непрерывный характер ...