How to Tell If a Closed Path Contains a Given Point

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

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.

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

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.

Finding Points contained in a Path in Android

I came up against this same problem a little while ago, and after some searching, I found this to be the best solution.

Java has a Polygon class with a contains() method that would make things really simple. Unfortunately, the java.awt.Polygonclass is not supported in Android. However, I was able to find someone who wrote an equivalent class.

I don't think you can get the individual points that make up the path from the Android Path class, so you will have to store the data in a different way.

The class uses a Crossing Number algorithm to determine whether or not the point is inside of the given list of points.

/**
 * Minimum Polygon class for Android.
 */
public class Polygon
{
    // Polygon coodinates.
    private int[] polyY, polyX;

    // Number of sides in the polygon.
    private int polySides;

    /**
     * Default constructor.
     * @param px Polygon y coods.
     * @param py Polygon x coods.
     * @param ps Polygon sides count.
     */
    public Polygon( int[] px, int[] py, int ps )
    {
        polyX = px;
        polyY = py;
        polySides = ps;
    }

    /**
     * Checks if the Polygon contains a point.
     * @see "http://alienryderflex.com/polygon/"
     * @param x Point horizontal pos.
     * @param y Point vertical pos.
     * @return Point is in Poly flag.
     */
    public boolean contains( int x, int y )
    {
        boolean oddTransitions = false;
        for( int i = 0, j = polySides -1; i < polySides; j = i++ )
        {
            if( ( polyY[ i ] < y && polyY[ j ] >= y ) || ( polyY[ j ] < y && polyY[ i ] >= y ) )
            {
                if( polyX[ i ] + ( y - polyY[ i ] ) / ( polyY[ j ] - polyY[ i ] ) * ( polyX[ j ] - polyX[ i ] ) < x )
                {
                    oddTransitions = !oddTransitions;          
                }
            }
        }
        return oddTransitions;
    }  
}

determine if a point sits inside an arbitrary shape?

Easiest way to do it is cast a ray from that point and count how many times it crosses the boundary. If it is odd, the point is inside, even the point is outside.

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

Note that this only works for manifold shapes.

check if point exists in QPainterPath

I once needed something similar than you. I needed to test two paths for similarity. Therefore I created a path from a list of points (I hope you don't need a more complex path since this solution would become extremely more difficult for general QPaintingPaths). This path is constructed using a given "tolerance", this is your selectionMargin.

The function returns a QPainterPath which "draws a region around the given polyline". This region can then be filled and would result in the same image as drawing the original polyline using a pen width of tolerance using round cap and round join options.

You can also, and this is what you want to do, check if a given point is contained in this path. Note that QPainterPath::contains checks for a point to lie within the closed region defined by the path. E.g., this closed region is empty for a single line segment and a triangle for two line segments, so this is not what you want if you use contains directly on your path (as I mentioned in the 3rd comment to your question).

QPainterPath intersectionTestPath(QList<QPointF> input, qreal tolerance)
{
    //will be the result
    QPainterPath path;

    //during the loop, p1 is the "previous" point, initially the first one
    QPointF p1 = input.takeFirst(); 

    //begin with a circle around the start point
    path.addEllipse(p1, tolerance, tolerance); 

    //input now starts with the 2nd point (there was a takeFirst)
    foreach(QPointF p2, input) 
    {
        //note: during the algorithm, the pair of points (p1, p2)
        //      describes the line segments defined by input.

        //offset = the distance vector from p1 to p2
        QPointF offset = p2 - p1;

        //normalize offset to length of tolerance
        qreal length = sqrt(offset.x() * offset.x() + offset.y() * offset.y());
        offset *= tolerance / length;

        //"rotate" the offset vector 90 degrees to the left and right
        QPointF leftOffset(-offset.y(), offset.x());
        QPointF rightOffset(offset.y(), -offset.x());

        //if (p1, p2) goes downwards, then left lies to the left and
        //right to the right of the source path segment
        QPointF left1 = p1 + leftOffset; 
        QPointF left2 = p2 + leftOffset;
        QPointF right1 = p1 + rightOffset;
        QPointF right2 = p2 + rightOffset;

        //rectangular connection from p1 to p2
        {
            QPainterPath p;
            p.moveTo(left1);
            p.lineTo(left2);
            p.lineTo(right2);
            p.lineTo(right1);
            p.lineTo(left1);
            path += p; //add this to the result path
        }

        //circle around p2
        {
            QPainterPath p;
            p.addEllipse(p2, tolerance, tolerance);
            path += p; //add this to the result path
        }

        p1 = p2;
    }

    //This does some simplification; you should use this if you call
    //path.contains() multiple times on a pre-calculated path, but
    //you won't need this if you construct a new path for every call
    //to path.contains().
    return path.simplified();
}

Meaning of closed Path parameter in matplotlib

All sample conditions are reproduced by the following code, making clear why contains_point([0.5,0.5]) always returned True. An unlucky coincidence of misunderstanding what the Path object considers as the inside of a path and where the test point was positioned:

import matplotlib.pyplot as plt
from matplotlib.path import Path
import matplotlib.patches as patches

fig, axes = plt.subplots(2, 2, figsize=(10, 10))

point1 = [0.5, 0.5]
point2 = [0.3, 0.7]

titles = ["Case 1\nVertices closed, closed parameter false by default",
          "Case 2\nVertices closed, closed parameter true",
          "Case 3\nVertices open, closed parameter false by default",
          "Case 4\nVertices open, closed parameter true"]

paths = [Path([[0,0],[1,0],[1,1],[0,1],[0,0]],closed=True),
         Path([[0,0],[1,0],[1,1],[0,1],[0,0]]),
         Path([[0,0],[1,0],[1,1],[0,1]]),
         Path([[0,0],[1,0],[1,1],[0,1]],closed=True)]

for ax, t, p in zip(axes.flat, titles, paths):
    patch = patches.PathPatch(p, facecolor="orange", lw=2, zorder=0)
    ax.add_patch(patch)
    ax.scatter(*point1, label="Path contains point {}: {}".format(point1, p.contains_point(point1)))
    ax.scatter(*point2, label="Path contains point {}: {}".format(point2, p.contains_point(point2)))
    ax.set_title(t)
    ax.legend()

plt.tight_layout()
plt.show()

Output:

Take-home messages:

• The area "enclosed" by a path is defined by the path vertices
  independent of whether the path is closed or not.
• As Stef linked to in the
  comments, closed=True ignores the last vertex if no codes are
  provided: If codes is None and closed is True, vertices will be
  treated as line segments of a closed polygon. Note that the last
  vertex will then be ignored (as the corresponding code will be set to
  CLOSEPOLY).

Android: How to check if a rectangle contains touched point?

Ok i solved my problem. I post the example code:

Path p;
Region r;

@Override
public void onDraw(Canvas canvas) {

    p = new Path();

    p.moveTo(50, 50);
    p.lineTo(100, 50);
    p.lineTo(100, 100);
    p.lineTo(80, 100);
    p.close();      

    canvas.drawPath(p, paint);

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

}   

public boolean onTouch(View view, MotionEvent event) {

    Point point = new Point();
    point.x = event.getX();
    point.y = event.getY();
    points.add(point);
    invalidate();
    Log.d(TAG, "point: " + point);

    if(r.contains((int)point.x,(int) point.y))
        Log.d(TAG, "Touch IN");
    else
        Log.d(TAG, "Touch OUT");

    return true;
}

How to know if a point is inside of a polygon in android

You need to implement one famous algorithm http://softsurfer.com/Archive/algorithm_0103/algorithm_0103.htm

---

Related Topics