sml-clipper

2D polygon geometry and convex Boolean operations for Standard ML. Provides polygon measures (area, perimeter, centroid, bounding box, orientation, convexity), point-in-polygon queries, total segment intersection, a convex hull (Andrew's monotone chain), convex intersection (Sutherland-Hodgman), and a convex union built on the hull.

Polygons are vertex lists (point list), implicitly closed.

API sketch

type point = real * real
datatype orientation = CW | CCW | Degenerate

(* measures *)
val signedArea    : point list -> real          (* +CCW, -CW *)
val area          : point list -> real
val perimeter     : point list -> real
val centroid      : point list -> point
val boundingBox   : point list -> {min:point, max:point}
val orientationOf : point list -> orientation
val isConvex      : point list -> bool

(* point queries *)
val pointInPolygon : point list -> point -> bool   (* boundary counts as inside *)
val onBoundary     : point list -> point -> bool

(* segments / hull *)
val segmentIntersect : (point*point) -> (point*point) -> point option
val convexHull       : point list -> point list    (* CCW *)

(* Boolean operations *)
val intersect : point list -> point list -> point list   (* convex clip *)
val union     : point list -> point list -> point list   (* convex union via hull *)

Examples

val squareA = [(0.0,0.0),(2.0,0.0),(2.0,2.0),(0.0,2.0)]
val squareB = [(1.0,1.0),(3.0,1.0),(3.0,3.0),(1.0,3.0)]

val isect = Clipper.intersect squareA squareB   (* unit square, area 1.0 *)
val a     = Clipper.area isect                   (* 1.0 *)
val c     = Clipper.centroid squareA             (* (1.0, 1.0) *)
val ins   = Clipper.pointInPolygon squareA (1.0,1.0)  (* true *)

(* two adjacent unit squares -> a 2x1 rectangle (area 2) *)
val u = Clipper.union
          [(0.0,0.0),(1.0,0.0),(1.0,1.0),(0.0,1.0)]
          [(1.0,0.0),(2.0,0.0),(2.0,1.0),(1.0,1.0)]

Algorithms

• intersect subject clip clips subject against each edge of the convex clip polygon (Sutherland-Hodgman).
• convexHull uses Andrew's monotone chain (lexicographic sort + lower/upper chains), returning vertices in CCW order with no collinear interior points.
• union a b = convexHull (a @ b).
• pointInPolygon uses the ray-crossing test; points on the boundary count as inside.

Scope and limitations

• Convex intersect: Sutherland-Hodgman requires the clip polygon to be convex. The subject may be non-convex, but the result can be wrong for concave subjects.
• Convex union: the union is the convex hull of all vertices. This is exact when the true union is convex (overlapping or adjacent convex polygons) and an over-approximation otherwise. It is no longer the old vertex-list concatenation stub. There is still no general (concave) union / difference / XOR — those need a Weiler-Atherton or Vatti clipper.
• segmentIntersect returns NONE for parallel/collinear segments (no single crossing point) and for crossings that fall outside either finite segment.
• Degenerate inputs (fewer than 3 vertices, zero area) are handled gracefully: signedArea/area return 0.0, centroid falls back to the vertex average, isConvex returns false.

Installing with smlpkg

smlpkg add github.com/sjqtentacles/sml-clipper
smlpkg sync

Reference from your .mlb:

lib/github.com/sjqtentacles/sml-clipper/clipper.mlb

Example

make example builds and runs examples/demo.sml, which computes measures, point queries, a convex hull, and convex Boolean ops over literal polygons (output is byte-identical under MLton and Poly/ML):

Convex pentagon [(0,0),(4,0),(6,2),(3,5),(-1,3)]:
  signedArea    = 23.0000
  area          = 23.0000
  perimeter     = 18.7055
  centroid      = (2.3478, 2.1449)
  boundingBox   = {min=(~1.0000, 0.0000), max=(6.0000, 5.0000)}
  orientationOf = CCW
  isConvex      = true

Point queries:
  pointInPolygon (3,2)   = true
  pointInPolygon (10,10) = false

convexHull of the pentagon vertices plus 3 interior points:
  hull = [(~1.0000, 3.0000), (0.0000, 0.0000), (4.0000, 0.0000), (6.0000, 2.0000), (3.0000, 5.0000)]

Overlapping squares [0,4]x[0,4] and [2,6]x[2,6]:
  intersect = [(2.0000, 2.0000), (4.0000, 2.0000), (4.0000, 4.0000), (2.0000, 4.0000)]
  union     = [(0.0000, 0.0000), (4.0000, 0.0000), (6.0000, 2.0000), (6.0000, 6.0000), (2.0000, 6.0000), (0.0000, 4.0000)]

Building and testing

make test        # MLton
make test-poly   # Poly/ML
make all-tests   # both
make clean

Project layout

sml.pkg
Makefile
lib/github.com/sjqtentacles/sml-clipper/
  clipper.sig     CLIPPER signature
  clipper.sml     polygon geometry, PIP, convex hull, intersect + convex union
  clipper.mlb
test/
  test.sml        area/orientation/PIP/hull/segmentIntersect/intersect/union

License

MIT. See LICENSE.