Android Finding intersection of polygon?

Issue

i've currently a few polygon shapes as shown below that is being drawn onto my mapview with the following code

    CustomPolygon customPolygon= data.getCustomPolygonList().get(i);
            Path path = new Path();
            path.setFillType(Path.FillType.EVEN_ODD);
            for(int n=0;n<customPolygon.getCorrdinateList().size();n++)
            {

                GeoPoint sector1 = new GeoPoint((int)(customPolygon.getCorrdinateList().get(n).getLatitude()*1e6), (int)((customPolygon.getCorrdinateList().get(n).getLongitude())*1e6));
                if(n==0){
                    mapView.getProjection().toPixels(sector1, point1_draw);
                    path.moveTo(point1_draw.x,point1_draw.y);
                }else
                {
                    mapView.getProjection().toPixels(sector1, point1_draw);
                    path.lineTo(point1_draw.x,point1_draw.y);
                }
            }

            path.close();
            canvas.drawPath(path, paint);

Right now i'm figuring on how do i know if the ontap button is intersecting any of the polygon. for example if it intersect one of the polygon, a message will display the current polygon.

I'm stuck at the ontap part for the overlay.

    @Override
public boolean onTap(GeoPoint p, MapView ) {



        Point point1_draw = new Point();     
        mapView.getProjection().toPixels(p, point1_draw);


        for (int i =0;i<data.getCustomPolygonList().size();i++)
        {
            CustomPolygon customPolygon= data.getCustomPolygonList().get(i);
            for(int n=0;n<customPolygon.getCorrdinateList().size();n++)
            {
            }

        }

    return  true;
}

Solution

I assume you need some code to check whether the button is inside a polygon right?

I can't give you code right now, but here's a rough algorithm:

for each line segment in the polygon
  calculate the dot product for the line segment and the line formed by the starting vertex and the point to check
  if all dot products have the same sign, the point is inside the polygon

Note that for this to work, you need the polygon to have a continous winding, i.e. all vertices are either added clockwise or counter clockwise. Additionally, this approach might not always work for concave polygons. Thus you might want to split concave polygons into a series of convex ones.

For more general (but also more costly) algorithms have a look at this wiki page: http://en.wikipedia.org/wiki/Point_in_polygon

Another source of information (along with some code): How can I determine whether a 2D Point is within a Polygon?

Answered By - Thomas