CODEWITHSUNDEEP
javascripthtmlalgorithmcanvasbezier
Hans
Hans

Reputation: 2800

Detecting mouse collision with closed Bezier curved shapes in Canvas

My situation:

I am working on a HTML5/Canvas/JavaScript framework for zooming-user-interface, which I then use for a data visualization web application project. One of the features that I need for my framework is to be able to detect whether the user's mouse is over a rendered shape. For more complex shapes like polygons and shapes with Bezier curves, this becomes a challenge.

I found two ways of solving this problem:

(1) One way is to draw everything on the canvas twice. The first time, every shape gets filled with a unique color from a hash table. The second time, the shapes get their real colors and masks over the first layer. To detect mouse-shape collision, I'd have to grab the color of the pixel under the mouse from the first layer and map the color I get to the corresponding shape in the hash table.

(2) Or I can use the ray casting algorithm (http://en.wikipedia.org/wiki/Point_in_polygon#Ray_casting_algorithm). I have actually implemented this algorithm with code that detect ray-line collisions and ray-Bezier collisions.

The actual question:

I dislike the first approach because everything has to be drawn twice, which is not computationally cheap. But the second approach does not guarantee accuracy, due to rounding errors from computations.

Ideally, I would like to improve the accuracy of the second approach to near-perfection.

My attempt to improve accuracy is to cast 4 rays in different directions: top, left, bottom and right. If at least one horizontal and one vertical ray suggest the mouse is inside the shape, then I conclude the point is inside the shape. Although this eliminates most misfires, errors (not firing) still do occur when the mouse is inside the shape.

It would be awesome if someone can suggest a fix to the ray casting algorithm, or perhaps even a third option!

Thanks in advance.

Upvotes: 1

Views: 1272

Answers (1)

user1693593
user1693593

Reputation:

You can do ray-casting but you could also use the built-in function on the context:

var flag = ctx.isPointInPath(x, y);

What you need to do is simply to rebuild each path you want to test (no need to stroke or fill them) and do this test.

There is also:

var flag = ctx.isPointInStroke(x, y);

if you also want to consider the stroke itself in case it has a width > 1. This function is not supported on IE as of yet though.

For example:

/// build some polygon/shape/...
ctx.beginPath();;
ctx.moveTo(x1, y1);
ctx.lineTo(x2, y2);
ctx.lineTo(x3, y3);
ctx.closePath();

/// no need to fill/stroke it, just test the path:
var flag = ctx.isPointInPath(x, y);

You need to do this for each unique shape but the performance is quite ok unless you are having zillion shapes in which case you can consider quad-trees and the like.

To detect which shape you clicked you can store the shapes as objects instead of using unique color (depends on the actual scenario though) so when you iterate through your object array you will know which object you're currently checking, and if true hit then abort the iteration.

Upvotes: 7

Related Questions