A collection of algorithms and tools for geometric problem solving in HTML5
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Type Name Latest commit message Commit time
Failed to load latest commit information.


What is GeoKit?

GeoKit is a graphical tool for sketching out ideas in Computational Geometry. You're provided with a canvas and the ability to insert various geometric primitives over which you can apply several algorithms.

You can quickly draw some obstacles, compute their visibility graph, and take the minimum spanning tree of that graph. Then drag around the original obstacles to visualize how the constructed graphs change accordingly. This is great for gaining an intuition on how different structures relate.

GeoKit takes inspiration form Ipe and KSEG and tries to bring their ideas to general geometric algorithms.

What isn't GeoKit?

There are many things GeoKit isn't.

GeoKit is not optimal

GeoKit was not designed to by a high-performance system for benchmarking algorithms or powering enterprise systems. It's designed to make sketching out ideas on small inputs easier. While we don't purposefully implement the worst possible algorithm, we tend to lean towards the algorithms that are easiest to write and maintain.

For instance, as of this writing we compute the MST of a set of points by simply computing their complete graph and then computing the MST of that. This is obviously wasteful, but also easy to write and verify the correctness of. Especially since we're dealing with exceptionally small inputs, where random constants will dominate any assymptotic performance. The only thing we really strive to obtain is correctness in the algorithms.

GeoKit is not correct

Being able to construct an entity in GeoKit in no way functions as a proof of its existence. Internally we work with double-precision floating point numbers. Anyone who has worked with floats for a while knows that this means that computations can be very error-prone. In particular, compounded FP operations tend to diverge from the real result. While we try to not store the results of many actual equations, they do feature prominently in various algorithmic decisions, such as determining if lines intersect or if an angle is reflex. As such we make no guarantees that our outputs are 100% correct, particularly on degenerate or near-degenerate inputs.

GeoKit is not done

GeoKit has plenty left to get done. The GUI, in particular, is still lacking key features, and the set of algorithms provided is quite small. If you agree, please consider contributing!

GeoKit is not Ipe

If you want pretty vector diagrams, just use Ipe.

How do I contribute?

GeoKit is hosted on Github and licensed under the BSD 2-clause license. Basically this means you can fork it off and do whatever with it. The GUI code is a bit harsh as it's mostly a pile of organic jQuery hacks, but the actual algorithms and structures seem to be pretty alright (if sparsely documented). Feel free to contact me if you want any features added or want to help out. Just forking it or submiting an issue on Github would be the easiest.

Hosting your instance is very easy, as GeoKit has no build step (this may change as the number of files increases) or uncommitted dependencies. Just download the latest blob and drop it into any directory that will serve the static files. You can even run it from your local file system by just opening the index.html in your favourite (modern) browser.