I've put up some preliminary code for finding visibility polygons on my github repo. I have only tested it with one polygon, but so far things are looking good. My idea from yesterday of using monads to "parse" the polygon seems to be paying off. Here is the relevant code:

(defn- add-new-pt [poly]
  (fn [pt stack]
    (when (or (empty? stack) ; First two points are guaranteed to be visible
              (empty? (rest stack))
              (visible? pt (first poly) (first stack)))
      [pt (rest poly) (cons (first poly) stack)])))

(defn- pop-stack [poly]
  (fn [pt stack]
    (let [the-seg (seg/new-seg pt (first poly))
          top-seg (seg/new-seg (first stack) (second stack))]
      (when (pt/left-turn? (second stack) (first stack) (first poly))
        (if (seg/intersection-on-seg? the-seg top-seg)
          [pt poly (cons (seg/intersection the-seg top-seg) stack)]
          [pt poly (rest stack)])))))

(defn- skip-pt [poly]
  (fn [pt stack]
   (let [the-seg (seg/new-seg pt (first stack))
         poly-seg (seg/new-seg (first poly) (second poly))]
     (when (not (pt/left-turn? (second stack) (first stack) (first poly)))
       (if (seg/intersection-on-seg? the-seg poly-seg)
         [pt (cons (seg/intersection the-seg poly-seg) (rest poly)) stack]
         [pt (rest poly) stack])))))

(defn- all-conditions [poly]
  (with-monad polygon-parser-m
    (m-plus (add-new-pt poly) (pop-stack poly) (skip-pt poly))))

This defines three actions to be performed when the polygon and stack are in certain configurations. The first executes when the next point on the polygon doesn't obscure any of the stack. In that case, it removes the point from poly and puts it on stack. The second executes by popping points off the stack until the next point on the polygon no longer obscures the stack. The final condition activates when the next point on the polygon is hidden by the stack. It skips the points of poly until it finds one that would be visible. We combine the three conditions using m-plus, which is defined to try the conditions in order until one returns something that is not nil.

Is this solution any better than a functional programming solution without monads? I think it is. First, the conditions are easy to see and very explicitly laid out. Using a cond to accomplish the same thing is certainly possible, but gets more complicated as the number of conditions grows. Also, we are explicitly managing state in this solution. Doing so in an ad-hoc manner would be much more difficult. In fact, I am not really sure how I would loop until there are no more points in poly in a solution without monads (especially since not all the conditions consume a point from poly). With monads, it is quite simple:

(defn- visibility-polygon-helper [pt poly]
  ((with-monad polygon-parser-m
     (m-until empty? all-conditions poly)) pt []))

Doing something like that with a reduce seems like it would veer off into unreadability fairly quickly.

Are there downsides to this solution? I think there is at least one. That is, the conditions must be functions that return functions. This makes them a bit more confusing than they really should be. I needed to do this so that I could have a test in the m-until function above. On the whole, though, this is a fairly cosmetic gripe, and can be hidden by using helper functions like the one above.

I would like to test the code quite a bit more. However, doing so by drawing out polygons by hand and then figuring out their visibility polygons is quite tedious. Therefore, I need some sort of GUI to be able to draw polygons and then I will be able to see whether the computed visibility polygon makes sense.

I am thinking that it might be nice to use the clj-processing library to do this. Unfortunately, that library is currently only using Clojure 1.2. Since I am using Clojure 1.3, that might be a problem. So I might need to do some porting from 1.2 to 1.3. However, doing so should give me a good idea of how processing works, and could give a nice tool for more interactive geometry programs.