How can I tell if a closed path contains a given point?

Question

In Android, I have a Path object which I happen to know defines a closed path, and I need to figure out if a given point is contained within the path. What I was hoping for was something along the lines of

path.contains(int x, int y)

but that doesn't seem to exist.

The specific reason I'm looking for this is because I have a collection of shapes on screen defined as paths, and I want to figure out which one the user clicked on. If there is a better way to be approaching this such as using different UI elements rather than doing it "the hard way" myself, I'm open to suggestions.

I'm open to writing an algorithm myself if I have to, but that means different research I guess.

Answer 1

I know I'm a bit late to the party, but I would solve this problem by thinking about it like determining whether or not a point is in a polygon.

http://en.wikipedia.org/wiki/Point_in_polygon

The math computes more slowly when you're looking at Bezier splines instead of line segments, but drawing a ray from the point still works.

Answer 2

Here is what I did and it seems to work:

RectF rectF = new RectF();
path.computeBounds(rectF, true);
region = new Region();
region.setPath(path, new Region((int) rectF.left, (int) rectF.top, (int) rectF.right, (int) rectF.bottom));

Now you can use the region.contains(x,y) method.

Point point = new Point();
mapView.getProjection().toPixels(geoPoint, point);

if (region.contains(point.x, point.y)) {
  // Within the path.
}

** Update on 6/7/2010 ** The region.setPath method will cause my app to crash (no warning message) if the rectF is too large. Here is my solution:

// Get the screen rect.  If this intersects with the path's rect
// then lets display this zone.  The rectF will become the 
// intersection of the two rects.  This will decrease the size therefor no more crashes.
Rect drawableRect = new Rect();
mapView.getDrawingRect(drawableRect);

if (rectF.intersects(drawableRect.left, drawableRect.top, drawableRect.right, drawableRect.bottom)) {
   // ... Display Zone.
}

Answer 3

The android.graphics.Path class doesn't have such a method. The Canvas class does have a clipping region that can be set to a path, there is no way to test it against a point. You might try Canvas.quickReject, testing against a single point rectangle (or a 1x1 Rect). I don't know if that would really check against the path or just the enclosing rectangle, though.

The Region class clearly only keeps track of the containing rectangle.

You might consider drawing each of your regions into an 8-bit alpha layer Bitmap with each Path filled in it's own 'color' value (make sure anti-aliasing is turned off in your Paint). This creates kind of a mask for each path filled with an index to the path that filled it. Then you could just use the pixel value as an index into your list of paths.

Bitmap lookup = Bitmap.createBitmap(width, height, Bitmap.Config.ALPHA_8);
//do this so that regions outside any path have a default
//path index of 255
lookup.eraseColor(0xFF000000);

Canvas canvas = new Canvas(lookup);
Paint paint = new Paint();

//these are defaults, you only need them if reusing a Paint
paint.setAntiAlias(false);
paint.setStyle(Paint.Style.FILL);

for(int i=0;i<paths.size();i++)
    {
    paint.setColor(i<<24); // use only alpha value for color 0xXX000000
    canvas.drawPath(paths.get(i), paint); 
    }

Then look up points,

int pathIndex = lookup.getPixel(x, y);
pathIndex >>>= 24;

Be sure to check for 255 (no path) if there are unfilled points.