How to find if a point exists in which polygon

Question

How to find if a point exists in which given set of polygons ? I have coordinates like

polygonA = 1(0,0),2(0,5),3(3,4),4(3,5),5( 2,2)
polygonB = 1(10,10),2(10,15),3(13,14),4(13,15),5(12,12)

I have a point as (6,4) now want to search if this point is in any of this polygon or in both or nearest to which polygon.

How to store such data (polygon) ? is there a system / database / algorithm to do this search ?

Update : Thanks all for such fast response...I think i need to be more specific...

How to search = Yes...got list of algorithms and library for the same.

How to store = based on my research SQL and NoSQL db have their solutions. NoSQL = MongoDb seems closest what i needed. But issue is I can query like "db.places.find({ "loc" : { "$within" : { "$polygon" : polygonB } } })" But cant make query like db.places.find({ "loc" : { "$within" : { } } }) SQL checked postgre and openGIS for some help. But colud not figureout if its possible.

If someone can help me with that...Thanks in advance.

Mcroberts

Are your polygon convex, concave, self-intersecting? – Suzansuzann

Ray casting – Cassady

See also this answer. – Juryman

@nhahtdh, what does it matter? – Erleena

@Erleena - Some algorithms are inefficient or do not work for certain types of polygons. That is why it matters. However, some algorithms cover all cases (if I recall correctly), but are not as fast as special-case algorithms. – Illtreat

@nhahtdh, I was about to write that the general algorithm is O(n) and that a special-case algorithm couldn't do better, but on second thought I think you're right. I can see an algorithm for convex, non-self-intersecting algorithms that appears to be O(log(n)). – Erleena

@Beta: I'm not sure whether that works or not... I originally asked that question because I only know algorithm for convex (CCW test) and concave polygon (sum of angle = 2 * pi). I am also not aware that Java has support for this. – Suzansuzann

Answer 1

The basic method (if you have a small number of polygons) is to store all polygons in a collection and loop over the elements to check if a point is inside a polygon.

On the other hand, if you have a considerable number of polygons, I would recommend using an R-tree data structure, which is not available in the standard library. You should check this project, if you want to go with R-tree option: http://sourceforge.net/projects/jsi/.

R-tree allows you to index rectangles (bounding boxes of the polygons in this case). So you can find a small number of candidate polygons very fast using R-tree. Then you can loop over the candidate list to get the final result.

Rossini

I think the point more was how to check if a point is in a particular polygon, not how to scale the algorithm. – Illtreat

I am not really sure about that, because java.awt.Polygon already has a number of contains() methods to do that. Anyway, it is not that obvious from the question, so you can be right as well. – Rossini

Hi vizier Thanks for help. Yes, i need how to find and how to store , but also efficient. While looking at different structures i found MongoDB closest to what i needed. Issue with mongoDB is i cant make query like "select poly from poly_table where near point(x,y)" ... as per mongo description i can say "" db.places.find({ "loc" : { "$within" : { "$polygon" : polygonB } } }) ""...can some one help me (updating question) – Mcroberts

You should also check this question (if not already): https://mcmap.net/q/402895/-nosql-and-spatial-data – Rossini

Answer 2

You can use the GeneralPath class to help you with deciding if a point intersects a polygon. First, create a GeneralPath with your coordinates added:

    GeneralPath gp = new GeneralPath();
    double[] x = ...
    double[] y = ...
    gp.moveTo(x[0], y[0]);
    for (int i =1; i < x.length; i++) {
        gp.lineTo(x[i], y[i]);
    }
    gp.closePath();

    if (gp.contains(pointX, pointY)) {
        ...
    }

For the problem of which polygon a point is nearer to, this depends a little on how accurately you need a solution.

For an accurate solution., this amounts (without optimisation) to:

• take the shortest distance between the point and each of the lines (segments) connecting the vertices of each of the polygons (Java2D apparently doesn't provide a method for this, but the shortest distance from a point to a line is a fairly simple calculation)
• which polygon has the line with the shortest distance to the point?

In practice, you can approximate this process for some applications. For example, you could much more efficiently do this:

• take the centre point of the bounding rectangle of each polygon (GeneralPath.getBounds() will give you this)
• take the distance between the query point and each of these centre points, and see which is closest.

If you do need an accurate answer, then you can combine these techniques to optimise your search among all the vertices. For example, you could order the polygons by the distance to their "centrepoint" (defined as above). Search from minimum to maximum distance. If the minimum distance to a segment that you have found so far is d, then you can automatically rule out any polygon P where the distance from your query point to its "centrepoint" is d + r, where r is half the length of the diagonal of P's bounding rectangle (in other words, for simplicity, you imagine a bounding circle around that bounding box and check that the distance to that bounding circle is further than the nearest point found so far on other polygons).

I don't quite understand the bit about the database. Your polygons are just defined as a series of points. How you decide to store these in memory/file doesn't essentially make any difference to the algorithm.

Mitre

The accurate solution part is a bit weird. I think the method should be: You have to calculate the shortest distance to line segment, in which you have to calculate distance to line once and distance to point twice for each line segment of the polygon. For the case of self-intersecting polygon, this may be a bit ill-defined. – Suzansuzann

I'm not sure I understand. I'm basically saying: "treat the distance from the point to the polygon as being the distance to the closest vertex". Are you treating it as something else? – Mitre

P.S. I am ignoring the case of a self-intersecting polygon. – Mitre

I think shortest distance from point to polygon is the shortest distance from point to all line segments connecting the vertices that defines the polygon, not the shortest distance to the vertices alone. – Suzansuzann

Sorry, I see what happened now-- we're defining it the same way, but I mixed up my terminology. By "vertex" I meant "line/segment connecting vertices" (hence I mentioned the algorithm to calculate the distance from point to line, for example). Sorry for the mix-up -- have corrected in the above. – Mitre

Sorry, but I am still not satisfy: shortest distance to a line (unbounded) and shortest distance to a line segment (bounded) are different. For shortest distance to a line segment, you have to compare 3 distances: distance to the congruent (unbounded) line, and distances to the 2 vertices of the line segment and take the smallest value. – Suzansuzann

OK, well I meant the actual line that defines part of the perimeter of the polygon. Maybe there's some secret meeting I missed where the word "line" can only be used in English to mean an unbounded line. But hopefully what I've put is clear enough. – Mitre

I think English is too ambiguous. Let us take a look at this code: #849711 – Suzansuzann