How can I tell if the mouse pointer is inside a path defined by Bezier curves and lines?

I have a closed path consisting of multiple Bezier curves and straight line segments. How can I tell wheth开发者_C百科er the current position of my mouse pointer is inside or outside the path?

Example of mouse leaving the area:

Example of mouse entering the area:

First you should check if the graphics library you're using already provides this hit-testing.

If you have to code it yourself, then a completely precise answer would require solving quadratic or cubic equations (depending on the degree of your Bezier curves) to determine the intersection with these paths. There seems to be a paper on exactly this problem.

However I think it would be much more sensible to build a linear approximation to your path (i.e. evaluate the path densely) and then use a standard point-in-polygon test. This can be accurate to whatever tolerance you choose (e.g. one pixel).

If the regions are relatively small, you could run a floodfill starting from the mouse location. If the floodfill goes outside of a bounding box (which you can precompute) then it's outside of the region.

See: http://en.wikipedia.org/wiki/Flood_fill

To test whether a point is inside or outside a bezier path, draw a line in any direction from the point, and count the number of times the line crosses the path. If the number is odd, then you are inside, if it is even then you are outside.

So, an inside-ness test can be re-expressed as an intersection test. Intersections can be tackled in several ways. A relatively simple approach is to approximate your bezier patches with straight line segments using deCasteljau's algorithm, reducing the bezier-line intersection test to a series of line-line intersection tests.

Note that you can take several shortcuts in your calculation. If, for example, the line you're drawing lies completely outside the bounding box of a given bezier patch's control points, then you can assume that it's not going to cross the patch. You can take advantage of this particular shortcut when recursively splitting your curves with deCasteljau to discard split sections of curves that are not going to intersect your line segment.