Android Finding intersection of polygon?

Question

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

enter image description here

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

You've got a type: `getCorrdinateList` should be `getCoordinateList`. To fix it, click on it and hit Ctrl-Shift-R in most IDE's. — Martijn Courteaux, Jul 30 '12 at 08:33
oh typo, that is a custom class for storing polygon coordiate — ericlee, Jul 30 '12 at 08:49

score 1 · Accepted Answer · edited May 23 '17 at 12:30

1

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?

edited May 23 '17 at 12:30

Community

1
1

answered Jul 30 '12 at 08:38

Thomas

87,414
12
119
157

this is true only for convex polygons. – Marek R Jul 30 '12 at 08:49
@MarekR, did you see my notes? `Additionally, this approach might not always work for concave polygons` - it might work for some points and doesn't work for others. – Thomas Jul 30 '12 at 08:50
yep I didn't read all. Sorry about that. Anyway your algorithm is wrong since it shouldn't be a dot product but cross product! – Marek R Jul 30 '12 at 09:00
@MarekR no, the dot product is fine. I've used it myself this way. The cross product only applies to 3D and we have 2D polygons here. – Thomas Jul 30 '12 at 09:12
negative example: polygon=equilateral triangle, hit point outside but verry close to the center of one of the sides. Your test will say that hit point is insde. If you use cross product (dx1*dy2-dy1*dx2) which in 2d gives single number it will be ok. – Marek R Jul 30 '12 at 09:25
@MarekR why should my test result in the point being reported as inside in that case? And even if the point is close to the polygon, there are always precision errors to be taken into account, thus you'd need an epsilon anyways. But as I said, the links I added describe the more general approach which work for concave polygons as well. – Thomas Jul 30 '12 at 09:38
I think the easiest way to check whether a point is in a polygon is to pick a random slope, draw a line and see how many times it intersects the polygon. try to come up with a polygon and a point that fail at this (as long as your slope doesn't go along a line) even number means it's out of the polygon, odd number means it's inside the polygon. – Shark Jul 30 '12 at 10:20
@Shark, yes that's one way that is already suggested in the linkes articles/threads. – Thomas Jul 30 '12 at 10:59

Marek R · Answer 2 · 2012-07-30T09:03:11.300

0

I'm surprised that android.graphics.Path and android.graphics.PathMeasure doesn't provide API for that. It should.

The algotithm is described here.

edited Jul 30 '12 at 09:03

answered Jul 30 '12 at 08:51

Marek R

32,568
6
55
140

Android Finding intersection of polygon?

2 Answers2