Description

The current ConvexHull implementation has a critical bug in the orientation function that causes division by zero when processing points that share the same x-coordinate (vertical lines).

Location

File: Geometry/ConvexHull.js
Function: orientation(a, b, c)

Expected Behavior

The algorithm should handle vertical lines correctly and return the proper convex hull vertices.

Actual Behavior

Current Implementation (Buggy):

function orientation(a, b, c) {
 const alpha = (b.y - a.y) / (b.x - a.x) // ❌ Division by zero!
 const beta = (c.y - b.y) / (c.x - b.x) // ❌ Division by zero!
 
 if (alpha > beta) return 1
 else if (beta > alpha) return -1
 return 0
}

Problem:

When b.x === a.x or c.x === b.x, the division results in Infinity or NaN, causing incorrect results or crashes.
Steps to Reproduce

import { convexHull } from './Geometry/ConvexHull.js'
// Points with same x-coordinate (vertical line)
const points = [
 { x: 2, y: 0 },
 { x: 2, y: 1 }, // Same x as above
 { x: 2, y: 2 }, // Same x as above
 { x: 0, y: 1 },
 { x: 4, y: 1 }
]
convexHull(points) // ❌ Returns incorrect result or crashes