Showing posts with label graphics. Show all posts
Showing posts with label graphics. Show all posts

Friday, February 24, 2017

bézier curves

De Casteljau's algorithm is a fast, numerically stable way to rasterize Bézier curves. This code implements an interactive demo: click to append nodes to the curve's defining polygon, and drag any node to alter the curve.

Wednesday, February 22, 2017

convex hulls

This code demonstrates the Graham scan, an O(n log n) method for finding the convex hull (smallest enclosing polygon) of a planar point set. It's a great example of exploiting order: it works by sorting the set by angle about a known extreme point, allowing the hull points to be found in linear time.

A variation on the algorithm, noted by A.M. Andrew, sorts the set lexicographically and finds the upper and lower hull chains separately. This 'monotone chain' version is often preferred, since it's easier to do robustly.

Friday, June 3, 2016

segment intersection search

Here's a simple method I learned from Gareth Rees for finding the intersection (or parallel / collinear status) of two line segments. Rees credits Ronald Goldman, though I'd imagine the technique goes further back.

Sunday, June 28, 2015

triangle geometry

Here's a trivial post, mostly just to show off how nice mathematical code can look in Haskell. It illustrates the centroid, incircle, and circumcircle of a random triangle, with everything defined in terms of vertex triples. The viewport centers on the circumcenter, and the triangle's interior is filled using barycentric coordinates.

Tuesday, September 9, 2014

color space conversion

Recently I was working on some C code for an image-manipulation app, and I had to write logic to convert between RGB and HSL (hue-saturation-lightness) representations of color. For extra confidence in its correctness, I decided to cross-check the C version against this Haskell implementation.