#javascript #algorithm #data-structures
#язык JavaScript #алгоритм #структуры данных
Вопрос:
Я реализовал Джарвиса марча в 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--; } } } } }
Любая помощь, указывающая на то, как я мог бы улучшить это или выйти из бесконечного цикла, была бы очень признательна.
Комментарии:
1. Две вещи побудят пользователей ответить. (1) Вместо вставки кода с помощью { } используйте значок в двух шагах справа. Это позволяет создать исполняемый фрагмент, который пользователи могут запустить, щелкнув. (2) Включите пример тестового случая, который входит в бесконечный цикл.
2. @Eureka Я не могу показать тестовый пример, так как он скрыт. Очень сожалею
3. В этом случае создайте дело самостоятельно, которое потерпит неудачу. В противном случае вы просите других людей решить головоломку, которую кто-то вам задал.