# Jarvis March Algorithm always breaking because P equals Q

I am currently working on an implementation of the Jarvis March gift wrapping Algorithm.

Jarvis march is done with the following logic according to geeks for geeks.

 Algorithm:
Step 1) Initialize p as leftmost point.
Step 2) Do following while we don’t come back to the first (or leftmost) point.
2.1) The next point q is the point, such that the triplet (p, q, r) is counter clockwise for any other point r.

To find this, we simply initialize q as next point, then we traverse through all points.

For any point i, if i is more counter clockwise, i.e., orientation(p, i, q) is counter clockwise, then we update q as i.

Our final value of q is going to be the most counter clockwise point.
2.2) next[p] = q (Store q as next of p in the output convex hull).
2.3) p = q (Set p as q for next iteration).



Graph:

Once I first run 2.1 to 2.3 and have found the right most point q and set p as q, then add q to the hull. However, the the program stops because now p and q are equal to each other. On the next iteration (2.1 through 2.3) p and q will always be collinear and, as a result, will halt (step 2.0).

To avoid this, I set p as the zero index in this point array and then q as the 1st index. However, this will fall apart after you set a new value for p.

My implementation is the following (with logging).

My code uses a convert to Desmos so I can simply copy and paste into Desmos graphing calculator and visualize the issues (this may not work due to font on exchange).

const formatToDesmos = (arr) => JSON.stringify(arr).replaceAll("[", "(").replaceAll("]", ")").replaceAll("((", "(").replaceAll("))", ")");

function pointOrientation(p1, p2, p3) {
let val = (p3[1] - p2[1]) * (p2[0] - p1[0]) - (p2[1] - p1[1]) * (p3[0] - p2[0])
return val < 0 ? "counterClockwise" : val > 0 ? "clockwise" : "collinear"
}
function distanceXY(p1, p2) {
return Math.sqrt(Math.pow(p2[1] - p1[1], 2) + Math.pow(p2[0] - p1[0], 2))
}
function convexHull(points) {
if (points.length <= 3) {
return points
}
// Grab the inital point
// Sort by y value then by x value (lower left point)
points = points.sort((a, b) => a[1] - b[1]).sort((a, b) => a[0] - b[0]);
console.log("Sorted points: \n"+formatToDesmos(points))
let p = [...points[0]];
let hull = [[...p]];
// Create point q as the contender as the left most point to p.
let q = [...points[1]];
while (true) {
// loop back through the points and grab a 3rd point
for (let point of points) {
console.log("Current p, point, q");
console.log(p,point,q)
console.log(pointOrientation(p,point,q))
// If the 3rd point is more countclockwise to p then q or
// if the points are collinear and p to point is greater than q to point
if ((pointOrientation(p,point,q) === "collinear" && distanceXY(p, point) > distanceXY(q,point)) || pointOrientation(p,point,q) === "counterClockwise") {
console.log('-- > Setting q: '+JSON.stringify(q)+" to point: "+JSON.stringify(point));
// Then q now becomes that point
q = [...point]
}
}
// If the most counterclockwise point is the starting point, stop the execution.
if ((JSON.stringify(q) === JSON.stringify(p))) {
console.log("HALT: Current p, q");
console.log(p,q)
console.log("Breaking because q = p")
break
}
console.log("\n --> Adding q to hull: "+JSON.stringify(q) +" <-- \n")
hull.push([...q])
// Now the far left point becomes the most counterclockwise point.
p = [...q]

}
return hull
}
let points = [[10, 27], [0, 28], [0, 29], [4, 9], [0, 3]];
console.log(formatToDesmos(points));
console.log(formatToDesmos(convexHull(points)));


The following log is created to visuizle this problem. It correctly fnd that (0,29) is a convex hull point, but then since p and q are then equal, it will result in the program halting.

Input points:
(10,27),(0,28),(0,29),(4,9),(0,3)
Sorted points:
(0,3),(0,28),(0,29),(4,9),(10,27)
Current p, point, q
[ 0, 3 ] [ 0, 3 ] [ 0, 28 ]
collinear
Current p, point, q
[ 0, 3 ] [ 0, 28 ] [ 0, 28 ]
collinear
-- > Setting q: [0,28] to point: [0,28]
Current p, point, q
[ 0, 3 ] [ 0, 29 ] [ 0, 28 ]
collinear
-- > Setting q: [0,28] to point: [0,29]
Current p, point, q
[ 0, 3 ] [ 4, 9 ] [ 0, 29 ]
clockwise
Current p, point, q
[ 0, 3 ] [ 10, 27 ] [ 0, 29 ]
clockwise

--> Adding q to hull: [0,29] <--

Current p, point, q
[ 0, 29 ] [ 0, 3 ] [ 0, 29 ]
collinear
Current p, point, q
[ 0, 29 ] [ 0, 28 ] [ 0, 29 ]
collinear
Current p, point, q
[ 0, 29 ] [ 0, 29 ] [ 0, 29 ]
collinear
Current p, point, q
[ 0, 29 ] [ 4, 9 ] [ 0, 29 ]
collinear
Current p, point, q
[ 0, 29 ] [ 10, 27 ] [ 0, 29 ] <-- always collinear
collinear
HALT: Current p, q
[ 0, 29 ] [ 0, 29 ]
Breaking because q = p
(0,3),(0,29)