Using Geometry and Computational Geometry

1. Implementing Point and Line Structures

Structure	Properties	Description
Point	`{ x: number, y: number }`	Represents a point in 2D space with x and y coordinates
Line	`{ p1: Point, p2: Point }`	Represents a line defined by two points

Example: Point and Line Creation

const pointA = { x: 3, y: 4 };
const pointB = { x: 7, y: 1 };

const line = {
  p1: pointA,
  p2: pointB
};

console.log(line); // { p1: { x: 3, y: 4 }, p2: { x: 7, y: 1 } }

Example: Distance Between Two Points

function distance(p1, p2) {
  return Math.sqrt(
    Math.pow(p2.x - p1.x, 2) + Math.pow(p2.y - p1.y, 2)
  );
}

const dist = distance(pointA, pointB);
console.log(dist); // ~5.66

Example: Slope of a Line

function slope(line) {
  const { p1, p2 } = line;
  return (p2.y - p1.y) / (p2.x - p1.x);
}

const lineSlope = slope(line);
console.log(lineSlope); // -0.75

2. Calculating Cross Product

Property	Description	Values
crossProduct	Computes the cross product of two 3D vectors	`[a1, a2, a3] × [b1, b2, b3]`
resultVector	Resulting vector from cross product operation	`[a2b3 - a3b2, a3b1 - a1b3, a1b2 - a2b1]`

Example: Cross Product Calculation

const vectorA = [1, 2, 3];
const vectorB = [4, 5, 6];

const crossProduct = [
  vectorA[1] * vectorB[2] - vectorA[2] * vectorB[1],
  vectorA[2] * vectorB[0] - vectorA[0] * vectorB[2],
  vectorA[0] * vectorB[1] - vectorA[1] * vectorB[0]
];

console.log(crossProduct); // [-3, 6, -3]

Note: The cross product is anti-commutative: A × B = -(B × A).

3. Calculating Dot Product

Property	Description	Example
dotProduct(a, b)	Computes the dot product of two vectors a and b	`const a = [1, 2, 3]; const b = [4, 5, 6]; const result = dotProduct(a, b); // 32`

Example: Dot Product Calculation

function dotProduct(a, b) {
  return a.reduce((sum, val, i) => sum + val * b[i], 0);
}

const vectorA = [2, 3, 4];
const vectorB = [1, 0, -1];
console.log(dotProduct(vectorA, vectorB)); // Output: 2

Note: The dot product is a scalar value obtained by multiplying corresponding elements of two vectors and summing those products.

4. Finding Convex Hull

The convex hull of a set of points is the smallest convex polygon that contains all the points. It's a fundamental problem in computational geometry with applications in computer graphics, robotics, and geographic information systems.

Algorithm	Description	Time Complexity	Space Complexity
Graham Scan	Sorts points by polar angle and uses a stack to build the hull. Starts with the bottom-most point.	`O(n log n)`	`O(n)`
Jarvis March (Gift Wrapping)	Starts with the leftmost point and iteratively selects the next point that makes the smallest angle.	`O(nh)` where `h` is the number of hull points	`O(h)`
QuickHull	Divide-and-conquer approach that recursively partitions points and builds hulls.	`O(n log n)` average, `O(n^2)` worst	`O(n)`

Example: Graham Scan Implementation

function grahamScan(points) {
  // Sort points by x-coordinate, then y-coordinate
  points.sort((a, b) => a.x - b.x || a.y - b.y);
  const hull = [points[0], points[1]];
  
  for (let i = 2; i < points.length; i++) {
    while (hull.length > 1 && crossProduct(hull[hull.length - 2], hull[hull.length - 1], points[i]) <= 0) {
      hull.pop();
    }
    hull.push(points[i]);
  }
  
  return hull;
}

function crossProduct(o, a, b) {
  return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}

Example: Convex Hull Points

const points = [
  { x: 0, y: 3 },
  { x: 1, y: 1 },
  { x: 2, y: 2 },
  { x: 4, y: 4 },
  { x: 0, y: 0 },
  { x: 1, y: 2 },
  { x: 3, y: 1 },
  { x: 3, y: 3 }
];

const hull = grahamScan(points);
console.log(hull); // Points forming the convex hull

Note: The Graham Scan algorithm assumes no three points are collinear. In such cases, additional handling is needed to ensure correctness.

5. Implementing Line Intersection

Method	Description	Time Complexity	Space Complexity
Sweep Line Algorithm	Uses a vertical line sweeping across the plane to detect intersections	`O((n log n))`	`O(n)`
Bentley-Ottmann	Optimized sweep line algorithm with event queue and status structure	`O((n log n))`	`O(n)`
Brute Force	Checks every pair of lines for intersection	`O(n²)`	`O(1)`

Example: Bentley-Ottmann Algorithm

class Point {
  constructor(x, y) {
    this.x = x;
    this.y = y;
  }
}

class LineSegment {
  constructor(p1, p2) {
    this.p1 = p1;
    this.p2 = p2;
  }

  intersect(other) {
    // Implementation of line intersection logic
    return null; // Placeholder for actual implementation
  }
}

function findIntersections(segments) {
  const intersections = [];
  for (let i = 0; i < segments.length; i++) {
    for (let j = i + 1; j < segments.length; j++) {
      const inter = segments[i].intersect(segments[j]);
      if (inter) intersections.push(inter);
    }
  }
  return intersections;
}

Note: The Bentley-Ottmann algorithm uses a sweep line approach with an event queue to efficiently detect all intersections among a set of line segments.

6. Solving Closest Pair of Points

The Closest Pair of Points problem involves finding the two points with the smallest Euclidean distance in a set of points in 2D space.

Approach	Description	Time Complexity	Space Complexity
Divide and Conquer	Recursively divide the set into two halves, find closest pairs in each half, and then check for a closer pair across the dividing line.	`O(n log n)`	`O(log n)`
Brute Force	Compute the distance between every pair of points and return the minimum.	`O(n^2)`	`O(1)`

Example: Divide and Conquer Implementation

function distance(p1, p2) {
  return Math.sqrt((p1.x - p2.x) ** 2 + (p1.y - p2.y) ** 2);
}

function bruteForceClosest(points) {
  let minDist = Infinity;
  let closestPair = null;

  for (let i = 0; i < points.length; i++) {
    for (let j = i + 1; j < points.length; j++) {
      const dist = distance(points[i], points[j]);
      if (dist < minDist) {
        minDist = dist;
        closestPair = [points[i], points[j]];
      }
    }
  }

  return { distance: minDist, pair: closestPair };
}

function closestPairDivideConquer(points) {
  // Sort points by x-coordinate
  const sortedPoints = [...points].sort((a, b) => a.x - b.x);
  return closestPairRec(sortedPoints);
}

function closestPairRec(points) {
  const n = points.length;

  if (n <= 3) {
    return bruteForceClosest(points);
  }

  const mid = Math.floor(n / 2);
  const leftPoints = points.slice(0, mid);
  const rightPoints = points.slice(mid);

  const leftResult = closestPairDivideConquer(leftPoints);
  const rightResult = closestPairDivideConquer(rightPoints);

  const minDist = Math.min(leftResult.distance, rightResult.distance);
  const closestPair = leftResult.distance <= rightResult.distance ? leftResult.pair : rightResult.pair;

  // Check for a closer pair across the dividing line
  const midX = points[mid].x;
  const strip = points.filter(p => Math.abs(p.x - midX) < minDist);

  strip.sort((a, b) => a.y - b.y);
  const stripResult = closestInStrip(strip, minDist);

  if (stripResult.distance < minDist) {
    return stripResult;
  }

  return { distance: minDist, pair: closestPair };
}

function closestInStrip(strip, minDist) {
  let min = minDist;
  let closestPair = null;

  for (let i = 0; i < strip.length; i++) {
    for (let j = i + 1; j < strip.length && (strip[j].y - strip[i].y) < min; j++) {
      const dist = distance(strip[i], strip[j]);
      if (dist < min) {
        min = dist;
        closestPair = [strip[i], strip[j]];
      }
    }
  }

  return { distance: min, pair: closestPair };
}

// Example usage:
const points = [
  { x: 2, y: 3 },
  { x: 12, y: 30 },
  { x: 40, y: 50 },
  { x: 5, y: 1 },
  { x: 12, y: 10 }
];

const result = closestPairDivideConquer(points);
console.log("Closest distance: ", result.distance);
console.log("Closest pair: ", result.pair);

Note: The divide and conquer approach is more efficient for large datasets, with a time complexity of O(n log n) compared to O(n^2) for brute force.

7. Finding Point in Polygon

Determining whether a point lies inside, outside, or on the boundary of a polygon is a fundamental problem in computational geometry. The most common approach is the Ray Casting Algorithm.

Method	Description	Time Complexity	Space Complexity
Ray Casting	Cast a horizontal ray from the point to infinity and count intersections with polygon edges. If odd, point is inside.	O(n)	O(1)
Winding Number	Calculate the winding number of the point around the polygon. If non-zero, point is inside.	O(n)	O(1)

Example: Ray Casting Implementation in JavaScript

function isPointInPolygon(point, polygon) {
  const [x, y] = point;
  let inside = false;

  for (let i = 0, j = polygon.length - 1; i < polygon.length; j = i++) {
    const [x1, y1] = polygon[i];
    const [x2, y2] = polygon[j];

    if (((y1 > y) !== (y2 > y)) && (x < (x2 - x1) * (y - y1) / (y2 - y1) + x1)) {
      inside = !inside;
    }
  }

  return inside;
}

// Example usage:
const polygon = [[0, 0], [4, 0], [4, 4], [0, 4]];
const point = [2, 2];
console.log(isPointInPolygon(point, polygon)); // true

Note: The Ray Casting algorithm assumes the polygon is defined with a consistent winding order (e.g., counter-clockwise). For polygons with self-intersections or holes, more complex algorithms like the Non-Zero Winding Number are required.

Warning: Points lying exactly on an edge may produce inconsistent results depending on the implementation. Handling boundary cases requires careful consideration.

8. Implementing Rotating Calipers

The rotating calipers algorithm is a powerful technique for solving problems in computational geometry, particularly for finding the diameter of a convex polygon or computing the widest rectangle inside a convex polygon.

Operation	Description	Time Complexity	Space Complexity
Finding Diameter of Convex Polygon	Computes the maximum distance between any two points on the convex hull.	`O(n)`	`O(1)`
Finding Widest Rectangle	Determines the largest rectangle that can fit inside a convex polygon.	`O(n)`	`O(1)`

Example: Finding Diameter of Convex Polygon

function rotatingCalipersDiameter(points) {
  const n = points.length;
  if (n < 2) return 0;

  let maxDist = 0;
  let p1 = 0, p2 = 0;

  // Find the leftmost and rightmost points
  let leftmost = 0, rightmost = 0;
  for (let i = 1; i < n; i++) {
    if (points[i][0] < points[leftmost][0]) leftmost = i;
    if (points[i][0] > points[rightmost][0]) rightmost = i;
  }

  // Initialize the calipers
  let i = leftmost, j = rightmost;
  while (true) {
    const dist = Math.hypot(
      points[i][0] - points[j][0],
      points[i][1] - points[j][1]
    );
    maxDist = Math.max(maxDist, dist);

    // Rotate the calipers
    const cross = crossProduct(
      points[(i + 1) % n],
      points[i],
      points[j]
    );
    const cross2 = crossProduct(
      points[i],
      points[(j + 1) % n],
      points[j]
    );

    if (cross < cross2) {
      i = (i + 1) % n;
    } else if (cross > cross2) {
      j = (j + 1) % n;
    } else {
      i = (i + 1) % n;
      j = (j + 1) % n;
    }

    if (i === leftmost && j === rightmost) break;
  }

  return maxDist;
}

function crossProduct(a, b, c) {
  return (b[0] - a[0]) * (c[1] - b[1]) - (b[1] - a[1]) * (c[0] - b[0]);
}

Note: The algorithm uses the fact that the diameter of a convex polygon is determined by antipodal pairs of points. These pairs can be found efficiently using rotating calipers.

9. Solving Rectangle Overlap

Determining whether two rectangles overlap is a common problem in computational geometry and spatial algorithms. The key is to check if the rectangles intersect based on their coordinates.

Property	Description	Notes
Rectangle Representation	Each rectangle is defined by its bottom-left and top-right coordinates.	Format: `[x1, y1, x2, y2]`
Overlap Condition	Rectangles overlap if their projections on both axes intersect.	Check: `x1 < x2' && x1' < x2 && y1 < y2' && y1' < y2`

Example: Rectangle Overlap Check

function doRectanglesOverlap(rect1, rect2) {
  const [x1, y1, x2, y2] = rect1;
  const [x1', y1', x2', y2'] = rect2;

  return x1 < x2' && x1' < x2 && y1 < y2' && y1' < y2;
}

// Example usage
const rectA = [0, 0, 2, 2];
const rectB = [1, 1, 3, 3];
console.log(doRectanglesOverlap(rectA, rectB)); // true

Note: This method assumes rectangles are axis-aligned and defined by their bottom-left and top-right corners.

10. Implementing Line Sweep for Segments

Example: Basic Line Sweep Algorithm

const segments = [
  { x1: 1, y1: 1, x2: 4, y2: 4 },
  { x1: 2, y1: 2, x2: 5, y2: 5 },
  { x1: 0, y1: 3, x2: 3, y2: 0 }
];

function lineSweep(segments) {
  const events = [];
  for (const seg of segments) {
    events.push({ x: seg.x1, type: 'start', y: seg.y1 });
    events.push({ x: seg.x2, type: 'end', y: seg.y2 });
  }

  events.sort((a, b) => a.x - b.x);

  const activeSegments = new Set();
  const intersections = [];

  for (const event of events) {
    if (event.type === 'start') {
      activeSegments.add(event);
    } else {
      activeSegments.delete(event);
    }

    // Check for intersections at current x
    const segList = Array.from(activeSegments);
    for (let i = 0; i < segList.length; i++) {
      for (let j = i + 1; j < segList.length; j++) {
        const s1 = segList[i];
        const s2 = segList[j];
        if (intersect(s1, s2)) {
          intersections.push([s1, s2]);
        }
      }
    }
  }

  return intersections;
}

function intersect(seg1, seg2) {
  // Simplified intersection logic
  return (seg1.x1 < seg2.x2 && seg2.x1 < seg1.x2);
}

console.log(lineSweep(segments));

Component	Description	Notes
Event Processing	Processing events in sorted order by x-coordinate	Essential for correct sweep behavior
Active Set	Set of currently intersecting segments	Used to detect new intersections
Intersection Detection	Checking for intersections among active segments	Can be optimized with spatial data structures

Note: Line sweep is particularly effective for problems involving segments or polygons, such as finding intersections or computing area.

11. Implementing Voronoi Diagram

Operation	Description	Time Complexity	Space Complexity
Voronoi Diagram Construction	Partition space into regions based on distance to a set of points	`O(n log n)`	`O(n)`
Point Location	Find which Voronoi cell a query point belongs to	`O(log n)`	`O(1)`
Nearest Neighbor	Find the closest point to a query point	`O(log n)`	`O(1)`

Example: Voronoi Diagram Construction using Fortune's Algorithm

class VoronoiDiagram {
  constructor(points) {
    this.points = points;
    this.edges = [];
    this.vertices = [];
  }

  // Simplified Voronoi edge generation
  generate() {
    // Implementation of Fortune's algorithm
    return {
      edges: this.edges,
      vertices: this.vertices
    };
  }
}

const points = [
  { x: 1, y: 2 },
  { x: 3, y: 4 },
  { x: 5, y: 6 }
];

const voronoi = new VoronoiDiagram(points);
const result = voronoi.generate();

Note: Fortune's algorithm uses a sweep line approach with a beach line to construct the Voronoi diagram in O(n log n) time.