Mapping Pixels to Data

Question

I've written some basic graphing software in Clojure/Java using drawLine() on the graphics context of a modified JPanel. The plotting itself is working nicely, but I've come to an impasse while trying to converting a clicked pixel to the nearest data point.

I have a simple bijection between the list of all pixels that mark end points of my lines and my actual raw data. What I need is a surjection from all the pixels (say, 1200x600 px²) of my graph window to the pixels in my pixel list, giving me a trivial mapping from that to my actual data points.

e.g.

<x,y>(px) ----> <~x,~y>(pixel points) ----> <x,y>(data)

This is the situation as I'm imagining it now:

• A pixel is clicked in the main graph window, and the MouseListener catches that event and gives me the <x,y> coordinates of the action.

• That information is passed to a function that returns a predicate which determines whether or not a value passed to it is "good enough", and filter though the list with that pred, and take the first value it okays.

  • Possibly, instead of a predicate, it returns a function which is passed the list of the pixel-points, and returns a list of tuples (x index) which indicate how good the point is with the magnitude of x, and where that point is with index. I'd do this with both the x points and the y points. I then filter though that and find the one with the max x, and take that one to be the point which is most likely to be the one the user meant.

Are these reasonable solutions to this problem? It seems that the solution which involves confidence ratings (distance from pix-pt, perhaps) may be too processor heavy, and a bit memory heavy if I'm holding all the points in memory again. The other solution, using just the predicate, doesn't seem like it'd always be accurate.

This is a solved problem, as other graphing libraries have shown, but it's hard to find information about it other than in the source of some of these programs, and there's got to be a better way then to dig through the thousands of lines of Java to find this out.

I'm looking for better solutions, or just general pointers and advice on the ones I've offered, if possible.

Answer 1

So I'm guessing something like JFreeChart just wasn't cutting it for your app? If you haven't gone down that road yet, I'd suggest checking it out before attempting to roll your own.

Anyway, if you're looking for the nearest point to a mouse event, getting the point with the minimum Euclidean distance (if it's below some threshold) and presenting that will give the most predictable behavior for the user. The downside is that Euclidean distance is relatively slow for large data sets. You can use tricks like ignoring the square root or BSP trees to speed it up a bit. But if those optimizations are even necessary really depends on how many data points you're working with. Profile a somewhat naive solution in a typical case before going into optimization mode.

Answer 2

I think your approach is decent. This basically only requires one iteration through your data array, a little simple maths and no allocations at each step so should be very fast.

It's probably as good as you are going to get unless you start using some form of spatial partitioning scheme like a quadtree, which would only really make sense if your data array is very large.

Some Clojure code which may help:

(defn squared-distance [x y point]
  (let [dx (- x (.x point))
        dy (- y (.y point))]
     (+ (* dx dx) (* dy dy))))

(defn closest 
  ([x y points]
    (let [v (first points)] 
      (closest x y (rest points) (squared-distance x y v) v)))
  ([x y points bestdist best]
    (if (empty? points)
      best
      (let [v (first points)
            dist (squared-distance x y v)] 
        (if (< dist bestdist)
          (recur x y (rest points) dist v)
          (recur x y (rest points) bestdist best))))))