Sorting Coordinates in Polar Order for Graham Scan

Questions
,
1

Hello, Three.JS community,

I am attempting to implement the Graham Scan convex hull algorithm.

The pseudo-code calls for the inputted points to be sorted by “polar order” in relation to the bottom left point. The issue is that my method of using arctangent is resulting in incorrect degrees values via the built-in JavaScript V8 math library.

let points be the list of points
let stack = empty_stack()

find the lowest y-coordinate and leftmost point, called P0
sort points by polar angle with P0, if several points have the same polar angle then only keep the farthest

for point in points:
    # pop the last point from the stack if we turn clockwise to reach this point
    while count stack > 1 and ccw(next_to_top(stack), top(stack), point) <= 0:
        pop stack
    push point to stack
end

My Attempted Solution for Sorting by Polar Order:

To test my methods, I first wanted to sort all of the points based on P0 being just (0,0).

First, to print the equivalent polar coordinate for a set of points I used the following:

let inputPoints = [[1,0],[0,1],[-1,0],[0,-1]];
for (let i = 0; i < inputPoints.length; i++) {
     // Calculuate the angle in degrees as y over x
    let angle = Math.atan((inputPoints[i][1]) / (inputPoints[i][0])) * 57.2958;
    // Convert to positive degree values only.
    angle += angle < 0 ? 360 : 0;
    console.log(
       JSON.stringify(inputPoints[i]) + " For " + 
       // Calculate the radius
       JSON.stringify([Math.sqrt(Math.pow(inputPoints[i][0], 2) + Math.pow(inputPoints[i][1], 2)), 
       // Round the angle
       Math.round(angle)])
     )
  }

Output:

Now calling this code does reveal the following output:

[-1,0] For [1,0]
[0,1] For [1,90]
[0,-1] For [1,270]
[1,0] For [1,0]

The issue I am having is that the input for arctangent is y/x. For [-1,0], this results in -0, which is just interpreted as 0 by the function, resulting in 0 degrees instead of 180.

What modification can I make to my method to correctly interpret negative radius?

I tried tracking down the source code for arctangent in the V8 source code and noticed that the function returns zero angle if it is +/- zero.

  // Set up non-enumerable functions of the Math object and
  // set their names.
InstallFunctions($Math, DONT_ENUM, $Array(
    "random", MathRandom,
    "abs", MathAbs,
    "acos", MathAcosJS,
    "asin", MathAsinJS,
    "atan", MathAtanJS,
    [...]
}

// ECMA 262 - 15.8.2.4
function MathAtanJS(x) {
  return %MathAtan(TO_NUMBER_INLINE(x));
}


// ES6 draft 09-27-13, section 20.2.2.7.
function MathAtanh(x) {
  if (!IS_NUMBER(x)) x = NonNumberToNumber(x);
  // Idempotent for +/-0.
  if (x === 0) return x;
  // Returns NaN for NaN and +/- Infinity.
  if (!NUMBER_IS_FINITE(x)) return NAN;
  return 0.5 * MathLog((1 + x) / (1 - x));
}
2

Instead of Math.atan(y/x) try Math.atan2(y,x):

atan( 0/1 ) = 0
atan( 0/-1 ) = -0

atan2( 0, 1 ) = 0
atan2( 0, -1) = pi

Reference:
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/atan2

1 Like