Computational Geometry

Introduction

Computational Geometry is a branch of computer science that focuses on developing algorithms to solve geometric problems. It combines principles from mathematics, particularly geometry and topology, with algorithm design techniques to efficiently manipulate and analyze spatial data.

Whether you're developing a video game, building a geographic information system (GIS), or working on computer graphics, computational geometry provides the foundational algorithms to solve complex spatial problems efficiently.

In this article, we'll explore the fundamental concepts of computational geometry, common algorithms, and their practical applications.

Basic Geometric Primitives

Before diving into complex algorithms, let's understand some basic geometric primitives that form the building blocks of computational geometry.

Points

A point in a 2D plane is represented by its x and y coordinates.

javascript

class Point {
  constructor(x, y) {
    this.x = x;
    this.y = y;
  }
  
  distanceTo(otherPoint) {
    const dx = this.x - otherPoint.x;
    const dy = this.y - otherPoint.y;
    return Math.sqrt(dx * dx + dy * dy);
  }
}

// Example usage
const p1 = new Point(0, 0);
const p2 = new Point(3, 4);
console.log(p1.distanceTo(p2)); // Output: 5

Lines and Line Segments

A line in 2D can be represented in several ways, but one common approach is to use the equation ax + by + c = 0.

A line segment is defined by its two endpoints.

javascript

class LineSegment {
  constructor(p1, p2) {
    this.p1 = p1;
    this.p2 = p2;
  }
  
  length() {
    return this.p1.distanceTo(this.p2);
  }
  
  // Check if point p is on this line segment
  containsPoint(p) {
    // Distance from p to both endpoints should equal the length of the segment
    const d1 = this.p1.distanceTo(p);
    const d2 = this.p2.distanceTo(p);
    const lineLength = this.length();
    
    // Using epsilon for floating point comparison
    const epsilon = 0.0001;
    return Math.abs(d1 + d2 - lineLength) < epsilon;
  }
}

Polygons

A polygon is represented as an ordered collection of points (vertices).

javascript

class Polygon {
  constructor(points) {
    this.vertices = points;
  }
  
  perimeter() {
    let result = 0;
    for (let i = 0; i < this.vertices.length; i++) {
      const next = (i + 1) % this.vertices.length;
      result += this.vertices[i].distanceTo(this.vertices[next]);
    }
    return result;
  }
  
  // Simple area calculation using the Shoelace formula
  area() {
    let sum = 0;
    for (let i = 0; i < this.vertices.length; i++) {
      const j = (i + 1) % this.vertices.length;
      sum += this.vertices[i].x * this.vertices[j].y;
      sum -= this.vertices[j].x * this.vertices[i].y;
    }
    return Math.abs(sum) / 2;
  }
}

// Example usage
const square = new Polygon([
  new Point(0, 0),
  new Point(0, 1),
  new Point(1, 1),
  new Point(1, 0)
]);

console.log("Perimeter:", square.perimeter()); // Output: 4
console.log("Area:", square.area());           // Output: 1

Core Computational Geometry Algorithms

Let's explore some fundamental algorithms in computational geometry.

1. Checking if Two Line Segments Intersect

One of the basic problems in computational geometry is determining if two line segments intersect.

javascript

function orientation(p, q, r) {
  // Calculate the orientation of triplet (p, q, r)
  // 0 --> Collinear
  // 1 --> Clockwise
  // 2 --> Counterclockwise
  const val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
  
  if (val === 0) return 0;
  return (val > 0) ? 1 : 2;
}

function doIntersect(p1, q1, p2, q2) {
  // Find orientations
  const o1 = orientation(p1, q1, p2);
  const o2 = orientation(p1, q1, q2);
  const o3 = orientation(p2, q2, p1);
  const o4 = orientation(p2, q2, q1);
  
  // General case
  if (o1 !== o2 && o3 !== o4) return true;
  
  // Special Cases - When points are collinear
  // p1, q1 and p2 are collinear and p2 lies on segment p1q1
  if (o1 === 0 && onSegment(p1, p2, q1)) return true;
  
  // p1, q1 and q2 are collinear and q2 lies on segment p1q1
  if (o2 === 0 && onSegment(p1, q2, q1)) return true;
  
  // p2, q2 and p1 are collinear and p1 lies on segment p2q2
  if (o3 === 0 && onSegment(p2, p1, q2)) return true;
  
  // p2, q2 and q1 are collinear and q1 lies on segment p2q2
  if (o4 === 0 && onSegment(p2, q1, q2)) return true;
  
  return false;
}

function onSegment(p, q, r) {
  return (q.x <= Math.max(p.x, r.x) && q.x >= Math.min(p.x, r.x) &&
          q.y <= Math.max(p.y, r.y) && q.y >= Math.min(p.y, r.y));
}

// Example usage
const p1 = new Point(1, 1);
const q1 = new Point(10, 1);
const p2 = new Point(1, 2);
const q2 = new Point(10, 2);

console.log("Do segments intersect?", doIntersect(p1, q1, p2, q2)); // Output: false

const p3 = new Point(10, 0);
const q3 = new Point(0, 10);

console.log("Do segments intersect?", doIntersect(p1, q1, p3, q3)); // Output: true

2. Convex Hull

The convex hull of a set of points is the smallest convex polygon that contains all the points. One popular algorithm to compute the convex hull is Graham's scan.

javascript

function grahamScan(points) {
  if (points.length <= 3) return points;
  
  // Find the bottom-most point (and leftmost if tied)
  let bottomPoint = points[0];
  for (let i = 1; i < points.length; i++) {
    if (points[i].y < bottomPoint.y || 
        (points[i].y === bottomPoint.y && points[i].x < bottomPoint.x)) {
      bottomPoint = points[i];
    }
  }
  
  // Sort points based on polar angle with respect to bottom point
  const sortedPoints = points.slice();
  sortedPoints.sort((a, b) => {
    const orientation = getOrientation(bottomPoint, a, b);
    if (orientation === 0) {
      // If collinear, choose the closest one first
      return (distanceSquare(bottomPoint, a) <= distanceSquare(bottomPoint, b)) ? -1 : 1;
    }
    
    return (orientation === 2) ? -1 : 1;
  });
  
  // Build the convex hull
  const stack = [sortedPoints[0], sortedPoints[1]];
  
  for (let i = 2; i < sortedPoints.length; i++) {
    // Keep removing top while the angle formed by points next-to-top, top, and points[i] makes a non-left turn
    while (stack.length > 1 && getOrientation(stack[stack.length-2], stack[stack.length-1], sortedPoints[i]) !== 2) {
      stack.pop();
    }
    stack.push(sortedPoints[i]);
  }
  
  return stack;
}

function getOrientation(p, q, r) {
  const val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
  if (val === 0) return 0;  // collinear
  return (val > 0) ? 1 : 2; // 1 for clockwise, 2 for counterclockwise
}

function distanceSquare(p1, p2) {
  return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
}

// Example usage
const pointSet = [
  new Point(0, 3),
  new Point(1, 1),
  new Point(2, 2),
  new Point(4, 4),
  new Point(0, 0),
  new Point(1, 2),
  new Point(3, 1),
  new Point(3, 3)
];

const hull = grahamScan(pointSet);
console.log("Convex Hull points:", hull);
// Output will be the points forming the convex hull in counter-clockwise order

3. Point in Polygon

Determining if a point is inside a polygon is a common computational geometry problem.

javascript

function isPointInPolygon(point, polygon) {
  // Ray casting algorithm
  let inside = false;
  
  for (let i = 0, j = polygon.vertices.length - 1; i < polygon.vertices.length; j = i++) {
    const vi = polygon.vertices[i];
    const vj = polygon.vertices[j];
    
    // Check if point is on an edge
    const lineSegment = new LineSegment(vi, vj);
    if (lineSegment.containsPoint(point)) {
      return true;
    }
    
    // Check if ray cast from point crosses this edge
    if ((vi.y > point.y) !== (vj.y > point.y) &&
        point.x < (vj.x - vi.x) * (point.y - vi.y) / (vj.y - vi.y) + vi.x) {
      inside = !inside;
    }
  }
  
  return inside;
}

// Example usage
const testPoint = new Point(0.5, 0.5);
console.log("Is point in polygon?", isPointInPolygon(testPoint, square)); // Output: true

const outsidePoint = new Point(2, 2);
console.log("Is point in polygon?", isPointInPolygon(outsidePoint, square)); // Output: false

Advanced Topics in Computational Geometry

Triangulation

Triangulation is the process of dividing a polygon into triangles. One common algorithm is the Ear Clipping algorithm.

javascript

// Simplified ear-clipping algorithm for triangulating a simple polygon
function triangulate(polygon) {
  // This is a simplified version; a robust implementation needs to handle more cases
  const vertices = [...polygon.vertices];
  const triangles = [];
  
  while (vertices.length > 3) {
    for (let i = 0; i < vertices.length; i++) {
      const prev = (i === 0) ? vertices.length - 1 : i - 1;
      const next = (i === vertices.length - 1) ? 0 : i + 1;
      
      // Check if this vertex forms an "ear"
      const isEar = isVertexEar(vertices, prev, i, next);
      
      if (isEar) {
        // Add this ear as a triangle
        triangles.push([vertices[prev], vertices[i], vertices[next]]);
        
        // Remove the ear tip
        vertices.splice(i, 1);
        break;
      }
    }
  }
  
  // Add the final triangle
  if (vertices.length === 3) {
    triangles.push([vertices[0], vertices[1], vertices[2]]);
  }
  
  return triangles;
}

function isVertexEar(vertices, prev, current, next) {
  // Simplified check - in a real implementation, we'd need to ensure no other vertices
  // lie inside the potential ear triangle
  const triangle = [vertices[prev], vertices[current], vertices[next]];
  
  // Check if the vertex forms a convex angle (a requirement for an ear)
  return isConvex(vertices[prev], vertices[current], vertices[next]);
}

function isConvex(p1, p2, p3) {
  // Check if the three points make a "right turn"
  return (p2.x - p1.x) * (p3.y - p2.y) - (p2.y - p1.y) * (p3.x - p2.x) >= 0;
}

Voronoi Diagrams

A Voronoi diagram divides the plane into regions, where each region consists of points closer to one particular point than to any others.

javascript

// Note: Implementing a full Voronoi diagram algorithm is complex
// This is a high-level explanation of Fortune's algorithm approach

/*
Fortune's Algorithm steps:
1. Start with an empty diagram
2. Process events (site events and circle events) in order of their y-coordinate
3. Maintain a beach line (a sequence of parabolas)
4. For site events: add a new arc to the beach line
5. For circle events: remove an arc and add a Voronoi vertex
6. When all events are processed, complete any unbounded edges

Due to its complexity, most implementations use libraries like d3-voronoi or CGAL.
*/

// Pseudocode for creating a simple Voronoi diagram
function createVoronoiDiagram(sites) {
  // Initialize event queue with all site events
  const events = [];
  for (const site of sites) {
    events.push({ type: 'site', point: site });
  }
  
  // Sort events by y-coordinate (decreasing)
  events.sort((a, b) => b.point.y - a.point.y);
  
  // Initialize diagram structures
  const edges = [];
  const beachline = new BeachLine();
  
  // Process events
  while (events.length > 0) {
    const event = events.pop();
    
    if (event.type === 'site') {
      handleSiteEvent(event.point, beachline, edges, events);
    } else if (event.type === 'circle') {
      handleCircleEvent(event, beachline, edges, events);
    }
  }
  
  // Finish incomplete edges
  completeEdges(beachline, edges);
  
  return { edges };
}

// Note: The above is pseudocode - a real implementation would be much more complex

Practical Applications

Computational geometry has numerous real-world applications:

1. Geographic Information Systems (GIS)

GIS systems use computational geometry for:

• Map projections and coordinate transformations
• Spatial queries like finding all points within a region
• Calculating distances along roads or terrain
• Analyzing geographic patterns

2. Computer Graphics and Game Development

• Collision detection between objects
• Camera visibility calculations
• Terrain generation and manipulation
• Path finding and navigation meshes
• Character animations and physics simulations

3. Robotics

• Motion planning to find paths avoiding obstacles
• Environmental mapping and localization
• Object recognition and manipulation
• Autonomous navigation systems

4. Medical Imaging

• Reconstructing 3D models from 2D image slices
• Segmentation of organs and tissues
• Registration of multiple medical images
• Planning radiation therapy or surgical procedures

5. Industrial Design and Manufacturing

• Computer-aided design (CAD) systems
• 3D printing slicing algorithms
• Path planning for CNC machines and robot arms
• Quality control and inspection systems

Real-World Example: Collision Detection in Games

Let's implement a simple collision detection system for a 2D game:

javascript

class GameObject {
  constructor(x, y, width, height) {
    this.x = x;
    this.y = y;
    this.width = width;
    this.height = height;
  }
  
  getBoundingBox() {
    return {
      left: this.x,
      top: this.y,
      right: this.x + this.width,
      bottom: this.y + this.height
    };
  }
  
  intersectsWith(otherObject) {
    const a = this.getBoundingBox();
    const b = otherObject.getBoundingBox();
    
    // Check if the bounding boxes overlap
    return !(
      a.right < b.left ||
      a.left > b.right ||
      a.bottom < b.top ||
      a.top > b.bottom
    );
  }
}

// Game example usage
const player = new GameObject(100, 100, 50, 50);
const obstacle = new GameObject(130, 120, 40, 40);
const powerUp = new GameObject(200, 200, 20, 20);

function updateGame() {
  // Check collisions
  if (player.intersectsWith(obstacle)) {
    console.log("Player hit an obstacle!");
  }
  
  if (player.intersectsWith(powerUp)) {
    console.log("Player collected a power-up!");
  }
  
  // Move player, update game state, etc.
}

// Call updateGame in the game loop
updateGame();

Summary

Computational geometry provides powerful tools for solving spatial problems efficiently. We've covered:

1. Basic geometric primitives like points, lines, and polygons

2. Core algorithms including:

   • Line intersection detection
   • Convex hull calculation
   • Point-in-polygon testing
   • Triangulation
   • Voronoi diagrams

3. Practical applications in fields like:

   • GIS and mapping
   • Computer graphics and gaming
   • Robotics and autonomous systems
   • Medical imaging
   • Industrial design and manufacturing

As you continue to work with spatial data and geometric problems, these algorithms will serve as building blocks for more complex solutions.

Additional Resources

To deepen your understanding of computational geometry:

1. Books:

   • "Computational Geometry: Algorithms and Applications" by Mark de Berg et al.
   • "Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein (Chapter on Computational Geometry)

2. Online Courses:

   • Coursera's "Computational Geometry" course
   • Khan Academy's geometry modules

3. Libraries:

   • CGAL (Computational Geometry Algorithms Library)
   • d3-voronoi (for Voronoi diagrams in JavaScript)
   • Clipper (for polygon operations)

Exercises

1. Implement a function to determine if a given polygon is convex or concave.
2. Create an algorithm to find the closest pair of points from a given set of points in 2D space.
3. Implement a visualization of Graham's scan algorithm for finding the convex hull.
4. Write code to determine if two convex polygons intersect.
5. Create a simple polygon triangulation program and visualize the results.
6. Implement a point-in-polygon test using different algorithms and compare their performance.

By mastering these concepts, you'll be well-equipped to solve a wide range of geometric problems in your software projects.