Viewing visibility polygons
I mentioned yesterday that it would be nice to see the output of my visibility polygon solution. To that end, I created an extremely simple drawing editor using Processing. I have to say, I loved it.
The most important feature to me is the extreme interactivity. I
can change functions extremely quickly with my tools – redefining a
Clojure function is either one or two keystrokes in emacs, depending
how I choose to do it – so I like a graphics environment that
changes just as quickly. This is what Processing, and in particular
clj-processing, offers. I was able to define a function that
draws the various objects (in this case, the polygon, the point
where the mouse is, and the visibility polygon of the mouse point
inside the polygon). If I wanted to make any changes to this
function – for example, changing the color of the point where the
mouse is – I can simply redefine the function using my emacs tools
and the change shows up immediately on the drawing.
I was able to use this to find a couple of minor bugs in my visibility-polygon-finding code, but in general, it worked really well on the first try.
Shortcomings
There were a couple of things that slightly bothered me about
clj-processing. First, it used quite a lot of CPU just to
display a simple polygon without too many points. I am probably
using it rather naïvely, so it is possible that this is my problem
and not the problem of clj-processing. However, the second
problem is just that clj-processing is showing its age. I think
it was probably one of the first Clojure libraries out there and
much of the coding style hasn't evolved with the Clojure best
practices that people use. For example, some of the features do
not work if you only require the library – you must use it. I
try to only require libraries, to avoid my namespace becoming
overly populated, so it is frustrating when that doesn't work.
Going forward
I need to clean up the code a bit before I can put it up on github, but it should be there soon. It currently needs me to explicitly call the function in order to find the visibility polygon. I would really like it to find the visibility polygon of any point where the mouse is inside the polygon. However, determining if a point is inside a non-convex polygon tends to be a bit harder than it sounds. You can shoot a ray in one direction from a point, and count the number of polygon edges that it crosses – if it's even you are outside and if it's odd you are inside – but what happens if the ray crosses a vertex? There was a good experimental paper on this problem at a recent EuroCG.
So that's a slightly non-trivial problem. I also coded an implementation of the Voronoi Diagram problem recently. I should add a Processing UI to that as well. I have a feeling that would be the easier task to do next, and I would surely discover some bugs in it while I did.