Point Intersection With Polygon in Ruby

Question

How can I quickly find which of a set of polygons contain a given point?

I have a collection of polygons in a POSTGis database. I'm using RGeo on the ruby side to manipulate, save, and pull information from/to the database.

I receive a point (x and y coordinates) from an external machine and need to know which of my polygons this point lies within. I can't use the database because I need this to be done in memory for performance reasons.

I believe I might need an r-tree, but I don't exactly want to write one.

RGeo provides a contains? method that I can use to ensure a point is within a polygon of interest, but I need to know which polygon to check. I have on the order of 1,000 polygons and doing a linear search is not time efficient enough for my needs.

Answer 1

can this help? otherwise, there is this.

It seems that neartree is a better thing to search for w.r.t. ruby.

Hope this helps!

EDIT: if you need a general purpose implementation of an rtree, maybe the boost (c++) library can help there are bindings for it here. that has bindings for methods which should help your use-case:

intersects?
intersects_each?
intersects_rect?
intersects_rect_each?