CODEWITHSUNDEEP
kdtreer-tree
user12153559
user12153559

Reputation: 31

Polygon searching

Which of these (k-d tree, r-tree) would be suitable for searching and indexing polygon. My usecase is that i have been given some lat-long points (min 3 for a valid polygon) and from these points i need to find the polygon which is the smallest one. By smallest i mean that if there is a polygon inside another polygon, then the inside polygon should be returned. And if polygon overlap, they should not be chosen. I think finding the location and then the area might be tried but i am not sure.

I would also like get some idea about which data structure would be useful. I think postgis uses R-tree indexing.

Upvotes: 1

Views: 928

Answers (1)

Antonin
Antonin

Reputation: 157

R-tree is good for polygons, because it works on bounding boxes, including all the points for a particular polygon. You can easily find candidate polygons and then do a fine-grain check for overlap, area, etc.

Kd-tree works on points, so polygons would be hard to index.

R-tree also supports adding and removing data items. As I recall a kd-tree, once built, is hard to update for new or changing data.

Upvotes: 3

Related Questions