Блог

Я реализовал Джарвиса марча в javascript, а затем отправил его, оказывается, в некоторых случаях он переходит в бесконечный цикл. Я попытался изменить почти все, и кажется, что код продолжает идти в бесконечный цикл только для нескольких тестовых случаев.

Это мой текущий код, последний цикл for состоит в том, чтобы получить все точки, лежащие на линиях, образованных точками выпуклой оболочки.

 function convexHull(points, n)  {  // There must be at least 3 points  if (n lt; 3) return;   // Find the leftmost point  let l = 0;  let hull = [];  for (let i = 1; i lt; n; i  )  {  if (points[i].x lt; points[l].x)  l = i;  else if (points[i].x == points[l].x amp;amp; points[i].y lt; points[l].y)  l = i;  }   // Start from leftmost point, keep moving  // counterclockwise until reach the start point  // again. This loop runs O(h) times where h is  // number of points in result or output.  let p = l, q;     do  {   // Add current point to result  hull.push(points[p]);  newhull.push(points[p]);  // Search for a point 'q' such that  // orientation(p, q, x) is counterclockwise  // for all points 'x'. The idea is to keep  // track of last visited most counterclock-  // wise point in q. If any point 'i' is more  // counterclock-wise than q, then update q.  q = (p   1) % n;   for (let i = 0; i lt; n; i  )  {  // If i is more counterclockwise than  // current q, then update q  if ((orientation(points[p], points[i], points[q])  == 2))  q = i;  if(p != i amp;amp; orientation(points[p], points[i], points[q]) == 0   amp;amp; onSegment(points[p], points[q], points[i])) {  q = i;  }  }    p = q;   }while (p != l); // While we don't come to first point       for(let i = 0; i lt; hull.length; i  ) {  if(i   1 lt; hull.length) {  for (let j = 0; j lt; points.length; j  ) {  if(orientation(hull[i], points[j], hull[i 1]) == 0) {  newhull.push(points[j]);  points.splice(j, 1);  j--; }  }   }  else if(i   1 == hull.length) {  for (let j = 0; j lt; points.length; j  ) {  if(orientation(hull[i], points[j], hull[i 1]) == 0) {  newhull.push(points[j]);  points.splice(j, 1);  j--;  }  }  }  }  }  

Любая помощь, указывающая на то, как я мог бы улучшить это или выйти из бесконечного цикла, была бы очень признательна.