Finding Points contained in a Path in Android

Tried the other answer, but it gave an erroneous outcome for my case. Didn't bother to find the exact cause, but made my own direct translation from the algorithm on: http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html

Now the code reads:

/**
 * 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 c = false;
        int i, j = 0;
        for (i = 0, j = polySides - 1; i < polySides; j = i++) {
            if (((polyY[i] > y) != (polyY[j] > y))
                && (x < (polyX[j] - polyX[i]) * (y - polyY[i]) / (polyY[j] - polyY[i]) + polyX[i]))
            c = !c;
        }
        return c;
    }  
}

I would just like to comment on @theisenp answer: The code has integer arrays and if you look on the algorithm description webpage it warns against using integers instead of floating point.

I copied your code above and it seemed to work fine except for some corner cases when I made lines that didnt connect to themselves very well.

By changing everything to floating point, I got rid of this bug.

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;
    }  
}