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

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

@bhautikrathod9

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?

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.

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

"Can I work on this?"

Navigation Menu

Repository navigation

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

Description

Location

Expected Behavior

Actual Behavior

Current Implementation (Buggy):

Problem:

🔧 Proposed Solution

Updated `orientation(a, b, c)` implementation:

✅ Why This Works

🙌 Request

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

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

Description

Description

Location

Expected Behavior

Actual Behavior

Current Implementation (Buggy):

Problem:

Activity

Vedant794 commented on Oct 3, 2025

🔧 Proposed Solution

Updated orientation(a, b, c) implementation:

✅ Why This Works

🙌 Request

bhautikrathod9 commented on Oct 3, 2025

Haarush2006 commented on Oct 23, 2025

vishalpanchal0003 commented on Nov 24, 2025

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions

Updated `orientation(a, b, c)` implementation: