Questions tagged [quadtree]

a quadtree is a tree data structure in which each internal node has exactly four children.

Filter by
Sorted by
Tagged with
1 vote
0 answers
113 views

Finding the closest point on a line to a given point (and their distance) efficiently

I am working on a problem that involves some geometry and spatial points. Given a query, consisting of a point p and a line L (point not necessarily on the line), then find the point q on L that is ...
M. Fire's user avatar
  • 31
3 votes
1 answer
427 views

New Quadkey system for Bing's Birds eye view?

Has anyone noticed that Bing Maps' Birds eye view seems to be using a new Quadkey system, probably since V8 ? Has anyone been able to convert coordinates to this new system? The documentation on Bing'...
crtn-hrd's user avatar
  • 171
0 votes
0 answers
62 views

Creating Quadtree/Space Filling Curve Index atop GeoTiFF

I'm a complete beginner in GeoTiFF manipulation. I'd like to get some help in possible Java/Python/Scala project which performs spatial indexing (Quadtree, Space Filling Curves) atop given image(s). I ...
SBHera's user avatar
  • 1
1 vote
1 answer
360 views

How to store / what algorithm to use to find closest points from a given set of points to a polyline layer

I have a polyline layer and a points layer with features that are nearby the polylines. For the latter I want to find the closest points on the polylines (as existing vertices or new-created vertices ...
Fred's user avatar
  • 21
2 votes
1 answer
7k views

TypeError: cannot unpack non-iterable NoneType object on Spatial Join

I'm working with two spatial dataframes and am trying to do a spatial join on the two. parcels_sdf -- a frame with around ~370,000 real estate parcels. subdivisions_sdf -- a frame with all ...
leeprevost's user avatar
1 vote
1 answer
567 views

Quadtree based polygon indexing? (Python/Java)

I was wondering how to best represent the inside of any given polygon (GeoJSON coordinates) with some sort of indexing, like a grid or quadtree? See image below for an approximation of what I have in ...
bucky's user avatar
  • 11
3 votes
2 answers
2k views

Is there a Java API for in-memory geo indexes?

My application is backed by PostGIS. There is a particular set of tables which have one of their columns being a geographic polygon. They are relatively small in size (few thousand rows) and can ...
jbx's user avatar
  • 199
1 vote
0 answers
138 views

Retrieve all points within a given radius using quadkeys

I'm new to GIS concepts and I'm learning about quadkeys and usage. I am inserting few points with its quadkey into DB, and want to retrieve all points within a given radius using quadkeys. Assume ...
krithikaGopalakrishnan's user avatar
2 votes
0 answers
396 views

Use QuadTree in R to create Geospatial clusters [closed]

I am currently looking into different clustering techniques to form clusters from geospatial data. Is it possible to utilize quadtrees(from the SearchTrees package in R) to come up with something ...
user109785's user avatar
5 votes
2 answers
2k views

How can I convert Bing's "quadtree" tile addresses to ZXY tile addresses in Python?

Bing uses a quadtree-based addressing scheme to come up with a single number (or all-digit string) as the address of a tile. Each digit/character (starting from left / most significant) identifies the ...
das-g's user avatar
  • 1,445
0 votes
1 answer
321 views

Use QuadTree for better complexity on search features

I want to improve the complexity of search specific feature when using this function : map.forEachFeatureAtPixel(e.pixel, function (feature, layer) { // Do something.. }); The improvment ...
Elad Israeli's user avatar
0 votes
2 answers
2k views

Using Bing Maps Quadkeys as Openlayers 3 Tile source

I have a number of tile sources which utilise Bing Maps' Quadkey system in an old Silverlight application and I would like to use them in a new Openlayers 3 map. I have found several examples of ...
dvmac01's user avatar
  • 1,055
7 votes
1 answer
6k views

Finding N nearest points to point using JTS?

I'm trying to build a mobile app, and find the x number of points closest to a users location that satisfy certain conditions that the user chooses on the front end. My current solution is to ...
Boo's user avatar
  • 195
2 votes
1 answer
2k views

How to query a JTS QuadTree using a query envelope with holes

I have a Java Topology Suite QuadTree containing Points, now I'm trying to query the QuadTree with a polygon that contains a hole. Here's how I create the polygon. //Method will create a searchable ...
Boo's user avatar
  • 195
1 vote
0 answers
2k views

Creating quadtree index on latitude, longitude data in PostGIS

I have a table of locations in which one of the columns represents the lat-long for the location. These coordinates have been extracted from the OpenStreetMap file. How can I create a quadtree index ...
user87407's user avatar
  • 111
11 votes
2 answers
7k views

Are there trade offs between using a geohash vs using a quadkey as a spatial index?

QuadKey Bing Maps uses a quadkey structure for their tiling scheme. Here is an overview of the concept http://msdn.microsoft.com/en-us/library/bb259689.aspx. GeoHash A geohash seems to be the more ...
agentargo's user avatar
  • 111
1 vote
0 answers
726 views

Can I get a list of points in a polygon using Quadtrees?

I'm storing vertices in a PR (or PM if needed) quadtree and would like to be able to: Find out if a given polygon contains at least one point Optionally: Get a list of all the points within a given ...
Nick's user avatar
  • 121
1 vote
0 answers
277 views

Tree structure for muticolored region quadtree [closed]

Is a B+ tree suitable for a multicolored region quadtree (for example, one segmenting a plot of land into several crops)? I recently purchased a copy of Samet's 'Foundations of Multidimensional and ...
bendicott's user avatar
  • 119
25 votes
4 answers
6k views

How can I generate irregular grid containing minimum n points?

Given a large (~ 1 million) sample of unevenly distributed points - is it possible to generate irregular grid (in size, but could also be irregular in shape if that is possible?) that will contain ...
radek's user avatar
  • 10.6k
1 vote
0 answers
124 views

trim a global quadtree by population density?

I'm looking for a way to match people so as to find other members that are 'nearby' - not for those dreadful 'girls near you' ads, don't worry ;_) Of course 'nearby' in the country is a different ...
utunga's user avatar
  • 883