0
$\begingroup$

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:

Desmos 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)
$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.