Another particular interesting representation is Guibas and Stolfi's "quadedge" data structure from their 1985 paper at "Primitives for the manipulation of general subdivisions and the computation of Voronoi," source http://dl.acm.org/citation.cfm?doid=282918.282923 and pdf at http://www.sccg.sk/~samuelcik/dgs/quad_edge.pdf.

It really is an elegant use of some basic topology with impressive results, a full Voronoi/Delaunay linear-log time algorithm in less than a page of easily implementable pseudocode (once the data structure is written).

Careful, that pseudocode has a famous error in it. Finding it is an illuminating exercise.

Could you give more details?

I believe the error is only in the incremental algorithm. Spoiler: https://people.eecs.berkeley.edu/~jrs/meshpapers/GSflaws.

Amit's pages in general [0][1] are an absolutely amazing and invaluable source of high-quality game programming information.

[0] http://www.redblobgames.com/

[1] http://www-cs-students.stanford.edu/~amitp/gameprog.html

I think they're great too. I'm a complete novice to game development and my normal dev gig doesn't require much understanding of the math I learned in high school.

I needed to draw lines in a little thing I'm doing for https://itch.io/jam/cga-jam and stumbled across http://www.redblobgames.com/grids/line-drawing.html

Implemented it last night and it worked wonderfully.

http://ix.io/wSG/nim

This is cool. Does it have applications beyond computer graphics?

It would provide a fast, grid-like interpolation for any 2D data: think geospatial, GIS, etc. If I understand correctly, could also be used recursively to provide a lazy (but inefficient) way to calculate locations to an arbitrary precision.

Reminds me of topojson[0], a GeoJSON extension, that encodes features as topologies, instead of geometries.

[0]: https://github.com/topojson

Meshes are used in various kinds of simulation calculations: https://en.wikipedia.org/wiki/Finite_element_method ; there's also discrete exterior calculus: http://brickisland.net/cs177fa12/?cat=5

"various" is a crazy simplification: the propogation of radiation (think modeling wifi antenna output, on-chip photonic components, etc.), thermal properties of various electrical objects (think like exact temerature distribution across a resistor, heat distribution around a CPU, jet engines), modelling various materials for mechanical sturdiness and springiness, fluid modelling (the weather, aerodynamicity, etc.).

The list is huge!

mapping and path planning in robotics comes to mind