Class ComputationalGeometry2D

java.lang.Object

org.episteme.core.mathematics.geometry.ComputationalGeometry2D

public class ComputationalGeometry2D
extends Object

Computational geometry algorithms for 2D.

Includes: convex hull, closest pair, line segment intersection, etc.

Since:

1.0

Author:

Silvere Martin-Michiellot, Gemini AI (Google DeepMind)

Method Summary

Modifier and Type	Method	Description
static Point2D[]	closestPair(List<Point2D> points)	Closest pair of points - O(n log n) divide and conquer.
static List<Point2D>	convexHull(List<Point2D> points)	Convex Hull using Graham Scan - O(n log n).
static Real	intersectRayCircle(Ray2D ray, Point2D center, Real radius)	Intersects a ray with a circle.
static Real	intersectRaySegment(Ray2D ray, Point2D p1, Point2D p2)	Intersects a ray with a line segment.
static int	orientation(Point2D p, Point2D q, Point2D r)	Computes the orientation of triplet (p, q, r).
static boolean	pointInPolygon(Point2D point, List<Point2D> polygon)	Checks if a point is inside a polygon using ray casting.
static Real	polygonArea(List<Point2D> vertices)	Computes the area of a polygon defined by its vertices.
static boolean	segmentsIntersect(Point2D p1, Point2D q1, Point2D p2, Point2D q2)	Check if two line segments intersect.

Methods inherited from class Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Details

convexHull

public static List<Point2D> convexHull(List<Point2D> points)

Convex Hull using Graham Scan - O(n log n).

Parameters:

points - the input points

Returns:

the convex hull as a list of points in counterclockwise order

closestPair

public static Point2D[] closestPair(List<Point2D> points)

Closest pair of points - O(n log n) divide and conquer.

Parameters:

points - the input points

Returns:

array of two closest points, or null if fewer than 2 points

segmentsIntersect

public static boolean segmentsIntersect(Point2D p1,
 Point2D q1,
 Point2D p2,
 Point2D q2)

Check if two line segments intersect.

Parameters:

p1 - first endpoint of segment 1

q1 - second endpoint of segment 1

p2 - first endpoint of segment 2

q2 - second endpoint of segment 2

Returns:

true if segments intersect

orientation

public static int orientation(Point2D p,
 Point2D q,
 Point2D r)

Computes the orientation of triplet (p, q, r).

Returns:

0 if collinear, 1 if clockwise, 2 if counterclockwise

polygonArea

public static Real polygonArea(List<Point2D> vertices)

Computes the area of a polygon defined by its vertices.

Parameters:

vertices - the polygon vertices in order

Returns:

the area (positive if counterclockwise, negative if clockwise)

pointInPolygon

public static boolean pointInPolygon(Point2D point,
 List<Point2D> polygon)

Checks if a point is inside a polygon using ray casting.

Parameters:

point - the point to test

polygon - the polygon vertices

Returns:

true if point is inside the polygon

intersectRaySegment

public static Real intersectRaySegment(Ray2D ray,
 Point2D p1,
 Point2D p2)

Intersects a ray with a line segment.

Parameters:

ray - the ray

p1 - first endpoint of segment

p2 - second endpoint of segment

Returns:

distance t to intersection, or null if no intersection

intersectRayCircle

public static Real intersectRayCircle(Ray2D ray,
 Point2D center,
 Real radius)

Intersects a ray with a circle.