[BUG]: ConvexHull algorithm crashes with division by zero on vertical lines

[bhautikrathod9]

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

[Vedant794]

Hi @bhautikrathod9, I analyzed the bug in the orientation function, and I believe the issue comes from using slope calculations, which leads to division by zero when handling vertical lines.

🔧 Proposed Solution

Instead of comparing slopes, we can use the cross product method to determine orientation. This avoids division and correctly handles vertical, horizontal, and collinear points.

Updated orientation(a, b, c) implementation:

function orientation(a, b, c) {
  const val = (b.y - a.y) * (c.x - b.x) - 
              (b.x - a.x) * (c.y - b.y);

  if (val === 0) return 0;        // collinear
  return (val > 0) ? 1 : -1;      // 1 = clockwise, -1 = counterclockwise
}

✅ Why This Works

• No division involved → prevents Infinity / NaN issues.
• Handles vertical and horizontal lines correctly.
• Standard computational geometry approach for convex hull algorithms.

🙌 Request

I’d like to collaborate on fixing this issue and implementing the change. Could you please assign this issue to me?

Do you want me to also prepare a **pull request description template** (`fix: orientation bug in ConvexHull.js`) in markdown that you can directly use when you raise the PR?

[bhautikrathod9]

Thanks for you to getting interest in this buddy. but i already open a pull request for this. waiting for review. you can checkout issue.

[Haarush2006]

Hi, I'd like to work on this issue, as a part of my first contribution

[vishalpanchal0003]

"Can I work on this?"