3

I have a closed path consisting of multiple Bezier curves and straight line segments. How can I tell whether the current position of my mouse pointer is inside or outside the path?

Example of mouse leaving the area:
on mouse leave

Example of mouse entering the area:
on mouse enter

Pops
  • 30,199
  • 37
  • 136
  • 151
Glebka
  • 1,420
  • 3
  • 20
  • 37
  • You have a closed path consisting of multiple Bezier curves and straight line segments, and you want to know if a given position is inside or outside the path? – Tom Jun 22 '11 at 18:28
  • It would help to know how the curves and lines are represented in your program. – Pops Jun 22 '11 at 18:32
  • bezier(85, 20, 10, 10, 90, 90, 15, 80);(http://processingjs.org/content/reference/bezier_.gif) – Glebka Jun 22 '11 at 18:35
  • or curve(73, 24, 73, 61, 15, 65, 15, 65);(http://processingjs.org/content/reference/curve_.gif) – Glebka Jun 22 '11 at 18:35
  • This is kind of a hack, but if you have a way of getting the color of the region under the mouse pointer (either through methods of your graphics library or through OS API functions), the problem is solved, and there's no math involved. – IVlad Jun 22 '11 at 19:01

3 Answers3

7

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).

Tom
  • 1,329
  • 6
  • 15
1

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.

MrO
  • 685
  • 5
  • 8
1

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

tskuzzy
  • 35,812
  • 14
  • 73
  • 140