Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

I am trying to find a simple library which can do point in polygon. Earlier i did hit Java Spatial Index library ...could not figure out.

Tried openmap..looked simple didn't work.

I am totally new to GIS..my application has polygons. i need to search if my point isin 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 i am missing ?

share|improve this question
3  
Have you tried JTS? vividsolutions.com/jts/jtshome.htm –  atlefren May 31 '12 at 6:16
    
Can you please suggest me specific api ? I am very new to GIS system itself. –  Jigar Shah May 31 '12 at 10:32
    
I got the answer..! Thanks...found code on another post. stackoverflow.com/questions/5175216/… –  Jigar Shah May 31 '12 at 18:15
add comment

3 Answers

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.

share|improve this answer
    
(+1) Nice catch! –  whuber May 31 '12 at 15:13
add comment

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.

share|improve this answer
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
add comment
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");
{

}

}


}

}
}
share|improve this answer
    
Can you please explain what this code does? –  Devdatta Tengshe Apr 23 '13 at 9:35
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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