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.

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.