3

I am looking for a simple library which can check, whether a point is inside a polygon or not. Earlier I found Java Spatial Index library, but couldn't figure out how it works.

I also tried openmap, again without success.

I am totally new to GIS. My application has polygons. I need to check if my point is in a polygon or new polygon(s).

In open map I wrote as follows:

package abc.poi;

import com.bbn.openmap.geo.Geo;
import com.bbn.openmap.geo.OMGeo;

public class PoiTest {

    public static void main(String[] arg) {
        Geo geo1 = new Geo(1,1);
        Geo geo2 = new Geo(3,2);
        Geo geo3 = new Geo(4,4);
        Geo geo4 = new Geo(3,4);
        Geo geo5 = new Geo(4,3);
        Geo geo6 = new Geo(1,1);

        Geo listGeo[] = {geo1,geo2,geo3,geo4,geo5,geo6};

        OMGeo.Polygon poly = new OMGeo.Polygon(listGeo);

        System.out.println(poly.isPointInside(new Geo(2,2)));
    }
}

It always returns false. What am I missing?

3

Well I don't know the openmap library, but your polygon has self-intersections, and openmap likely doesnt account for this scenario.

self intersections

Also I might suggest Openlayers if you're developing a web-based mapping application.

2

You can code it yourself in python. Its like 30 lines of code, max. I did it myself. I can outline the algorithm below, but you need to optimize for bigger data set.

Basic idea: If a point is inside a polygon, the sum of the angles subtended by the line segments at the point must be equal to 360. If it is outside, the summation will be less than 360.

If you have holes, than you need to check for if its in a hole or not. So first check if a point is inside a polygon. Then convert holes in that polygons into polygons and check if its outside of each polygon(i.e. holes). A flow chart is here:

If you need more help with implementation, I can dig in old folders and check if I still have the implementation of this algo.

  • 3
    In general you don't want to code your own algorithm for basic computational geometry operations like point-in-polygon (unless you do it for learning purposes): what's built into GISes will be far more efficient, especially when the operation has to be repeated. Moreover, getting the details and edge cases exactly correct will likely involve a lot of testing and debugging. (In this case, accumulated floating point error will likely introduce a subtle bug at the top decision level: sums of angles will rarely exactly equal 360.) – whuber May 31 '12 at 15:12
  • Agreed and a definitely to the point response. I just posted this so that someone might come looking for an answer to the problem, and for the sake of completeness of the page, I though its a good idea to put a general algorithm here. Also, good point about floating points arithmetic, and truly its never 360. But it works reasonable for 360+-(10^-10). Floating errors will always be there, no matter how elegant your solution is. Thanks again for pointing out things that I missed. – Naresh Jun 1 '12 at 9:16
  • Thanks for those nuanced comments, Naresh. You can be more generous with your tolerance: the total amount of winding of any closed curve has to be a multiple of 360 degrees. Therefore, it's fair to take any sum between 180 and 540 degrees as evidence that 360 is the true value! BTW, there is a simpler, faster algorithm based on the parity of the number of edges crossed by a ray from the point. See the Wikipedia article for a summary and evaluation of some of these algorithms. – whuber Jun 1 '12 at 13:44
  • Thanks whuber. I know about that algorithm too. But the problem of the floating will still remain there. Parity of the edges in nutshell, checks for intersections, which is in fact check by pairwise cross products of the two vectors. You were right. I had a choice to program once for my class assignments and chose the sum=360 approach. May be some advanced algorithms takes some factors into account. But I think the person looking for answer is happy with java implementation. Cheers and have happy triangles. – Naresh Jun 1 '12 at 14:54
0
import java.util.Date;
import java.util.Scanner;
public class polygon
{

public static void main(String args[])
{
    System.out.println("PROGRAMMED BY:\nName:BHAGIRATH BHATT");

    System.out.println(" *******Program to check if a given point lies inside or outside of any polygon******** ");

Scanner a=new Scanner(System.in);
System.out.println("Enter the number of sides of the polygon..");
int side=a.nextInt();
if (side<=2)
{
    System.out.println("You have not formed a polygon.So using this program is of no meaning.Run it again with a valid number of sides");
}
else
{

double x[]= new double [side];
double y[]= new double[side];
double lengthtopoint[]=new double [side];
double sidelength[]=new double [side];
double angles[]=new double [side];

for(int u=0;u<=desirednumber;u++)
{
System.out.println("\nEnter the "+(u+1)+" coordinate for which you need to check");
System.out.println("Xcheck= ");
double xcheck=a.nextDouble();
System.out.println("Ycheck= ");
double ycheck=a.nextDouble();

for(int i=0;i<side;i++)
{
System.out.println("Enter x for vertex "+i);
x[i]=a.nextDouble();
System.out.println("Enter y for vertex "+i);
y[i]=a.nextDouble();
lengthtopoint[i]=Math.sqrt(((x[i]-xcheck)*(x[i]-xcheck))+((y[i]-ycheck)*(y[i]-ycheck)));
//System.out.println("length of line joining given check point and vertex "+i+" is " +lengthtopoint[i]);

}
System.out.println("List of all coordinates");  
for(int j=0;j<side;j++)
{   

System.out.println("Coordinate of vertex "+j+"= " +x[j]+" ,"+y[j] );

}   
for(int k=0;k<side-1;k++)
{   
sidelength[k]=Math.sqrt(((x[k+1]-x[k])*(x[k+1]-x[k]))+((y[k+1]-y[k])*(y[k+1]-y[k])));
//System.out.println("length of side "+k +(k+1)+ " is " +sidelength[k]);
}
sidelength[side-1]=Math.sqrt(((x[0]-x[side-1])*(x[0]-x[side-1]))+((y[0]-y[side-1])*(y[0]-y[side-1])));
//System.out.println("length of side "+(side-1)+"0 is " +sidelength[side-1]);

/*for(int w=0;w<side-1;w++)
{   
System.out.println("length  is " +sidelength[w]);
}*/
for(int l=0;l<side-1;l++)
{
angles[l] =((180/(Math.PI)))*Math.acos(((lengthtopoint[l]*lengthtopoint[l])+(lengthtopoint[l+1]*lengthtopoint[l+1])-(sidelength[l]*sidelength[l]))/(2*lengthtopoint[l]*lengthtopoint[l+1]));
//System.out.println("Angle= " +angles[l]); 
}

angles[side-1] =((180/(Math.PI)))*Math.acos(((lengthtopoint[side-1]*lengthtopoint[side-1])+(lengthtopoint[0]*lengthtopoint[0])-(sidelength[side-1]*sidelength[side-1]))/(2*lengthtopoint[side-1]*lengthtopoint[0]));    
//System.out.println("Angle= " +angles[side-1]);    

double sum=0;
for(int m=0;m<side;m++)
{
sum=sum+angles[m];
}

System.out.println("The sum of all the angles is  " +sum);  

if (sum==360)
{
System.out.println(" The  point"+(xcheck)+","+(ycheck) +"lies inside  polygon ");   
}
else if(sum<360)
    System.out.println(" The point"+(xcheck)+","+(ycheck)+"lies outside the polygon");
{

}

}


}

}
}
  • 1
    Can you please explain what this code does? – Devdatta Tengshe Apr 23 '13 at 9:35
0

You can use JTS and GeoGson libraries, which is what I needed (GeoJson compatibility).

GeoJson library link: https://github.com/filosganga/geogson

I have written myself a Java (Android compatible) code that checks if a given Point is in any of several Polygons. Being these Polygon, either a GeometryCollection or a MultiPolygon Geometry.

Gson gson = new GsonBuilder()
                .registerTypeAdapterFactory(new JtsAdapterFactory())
                .registerTypeAdapterFactory(new GeometryAdapterFactory())
                .create();
File geojsonDirectory = new File("directory-where-geojsons-are-placed");

File[] geojsonFiles = geojsonDirectory.listFiles();

if (geojsonDirectory.isDirectory()) {
    for (File geojsonFile : geojsonFiles) {
        Reader reader = new FileReader(geojsonFile);
                com.vividsolutions.jts.geom.Geometry geometry = gson.fromJson(reader, com.vividsolutions.jts.geom.Geometry.class);

        // This extra check will avoid a crash due to trying 
        // to check if a Point is contained in a GeometryCollection, 
        // which doesn't support that method. So it's necessary to 
        // get the MultiPolygon/Polygon that is inside of the GeometryCollection
        if (geometry.getGeometryType().equals("GeometryCollection")) {
            geometry = geometry.getGeometryN(0);
        }
        GeometryFactory gf = new GeometryFactory();
        boolean pointIsInPolygon = geometry.contains(gf.createPoint(new Coordinate(3.04033, 41.95569)));
    }
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.