Nick, More information on JTS indexes:
1) STRTree - a packed R-Tree that does not support insert/delete once built 2) QuadTree - slower than STRTree but supports insert/delete http://jump-pilot.sourceforge.net/pdfs/jts_secrets_foss4g2007.pdf Stuart On Fri, Jul 10, 2009 at 10:39 AM, Stuart Moffatt <[email protected]>wrote: > Nick, > > Correct, as in, not yet. The reference app just parses well-known text on > the fly to create geometry (server side only), and tests that geometry > (which is usually complex) against incoming coordinates (so far only points > and map bounds). Next stop, figuring out the right kind of index and its > implementation. > > If you care to elaborate on the comment you made with regard to R-trees or > space-filling curve algorithms, I'm open to implementation ideas. > > Stuart > > > On Fri, Jul 10, 2009 at 10:32 AM, Nick Johnson (Google) < > [email protected]> wrote: > >> >> Hi Stuart, >> >> Am I correct in inferring that you're not storing geospatial indexes >> persistently at all, then? This seems impractical for the App Engine >> architecture, and for the scale it is intended to support. >> >> -Nick Johnson >> >> On Fri, Jul 10, 2009 at 5:29 PM, Stuart Moffatt<[email protected]> >> wrote: >> > Nick, >> > >> > First, there was a typo in my announcement that I just realized. The >> second >> > last paragraph should state that the "current version of the application >> > does NOT demonstrate use of the datastore", that is, I am still in the >> > process of implementing fetches of WKT from my entities, but that's the >> > plan. >> > >> > As to your questions: >> > >> > 1) JTS indexes. From their technical spec: "There is a large literature >> of >> > efficient algorithms for intersection detection. Unfortunately, many of >> them >> > involve substantial code complexity. JTS tries to balance code >> simplicity >> > with performance gains. It uses some special techniques to produce >> > substantial performance gains for common types of input data. These >> > techniques include in-memory spatial indexes of various types, and >> > sophisticated methods for structuring data such as the technique of >> Monotone >> > Chains." (See >> > http://www.vividsolutions.com/jts/bin/JTS%20Technical%20Specs.pdf). >> > >> > 2) I am using brute force (ie CPU) to do point-in-polygon and >> > polygon-in-polygon in this version of the app, so I am letting JTS worry >> > about managing its own in-memory indexes. Nothing fancy built on top of >> > AppEngine (yet), but I will be looking at App Engine indexes and perhaps >> > blobs. >> > >> > Stuart >> > >> > On Fri, Jul 10, 2009 at 7:21 AM, Nick Johnson (Google) >> > <[email protected]> wrote: >> >> >> >> Hi Stuart, >> >> >> >> Very nice! >> >> >> >> Out of curiosity, what indexing scheme does JTS use? Are you building >> >> an R-Tree or other tree based structure on top of the datastore, or >> >> are you using a hilbert-curve type approach? >> >> >> >> -Nick Johnson >> >> >> >> On Fri, Jul 10, 2009 at 8:03 AM, Stuart Moffatt< >> [email protected]> >> >> wrote: >> >> > >> >> > Announcement: >> >> > >> >> > The GIS in the Cloud (App Engine + JTS) reference project is now >> >> > available at http://giscloud.appspot.com with the source code >> >> > available at http://giscloud.googlecode.com (documentation >> >> > forthcoming). >> >> > >> >> > While many GIS/spatial App Engine discussions center on the python >> SDK >> >> > (with pre-computing grids or geocells and heavy lifting done with set >> >> > membership in the datastore), this reference project uses the Java >> >> > Topology Suite (http://www.vividsolutions.com/jts/jtshome.htm) >> within >> >> > the App Engine server to demonstrate point-in-polygon and polygon-in- >> >> > polygon spatial queries. >> >> > >> >> > The GIS in the Cloud app is pure Java and was built with >> >> > >> >> > * Google App Engine SDK for Java >> >> > * Google Plugin for Eclipse >> >> > * Google Web Toolkit >> >> > * Google Web Toolkit API Libraries - Google Maps 1.0 Library >> >> > * Java Topology Suite >> >> > >> >> > The Java Topology Suite was ported to C++ and became GEOS, which was >> >> > embedded in PostgreSQL to become PostGIS, allowing users access to >> >> > spatial functions within SQL. While App Engine does not give us >> >> > spatial functions in GQL, the GIS in the Cloud app will demonstrate a >> >> > GQL/JTS combination to accomplish the same effect. >> >> > >> >> > The current version of the application does demonstrate use of the >> >> > datastore (TODO), but it does employ JTS to query point-in-polygon >> and >> >> > polygon-in-polygon. Single clicks on the map trigger the point-in- >> >> > polygon test (the point is the map center and the polygon is Salt >> Lake >> >> > County). With zoom or drag, the polygon-in-polygon test is triggered. >> >> > The first polygon is the map bounds and the second is Salt Lake >> >> > County. >> >> > >> >> > Future versions will use the datastore and be able to access OGC Well >> >> > Known Text (WKT) from which geometry can be created for features such >> >> > as: tracts, census block groups, census blocks, and parcels. >> >> > >> >> > >> >> > >> >> > >> >> > >> >> > >> >> > >> >> > > >> >> > >> >> >> >> >> >> >> >> -- >> >> Nick Johnson, App Engine Developer Programs Engineer >> >> Google Ireland Ltd. :: Registered in Dublin, Ireland, Registration >> >> Number: 368047 >> >> >> >> >> > >> > >> > > >> > >> >> >> >> -- >> Nick Johnson, App Engine Developer Programs Engineer >> Google Ireland Ltd. :: Registered in Dublin, Ireland, Registration >> Number: 368047 >> >> >> >> > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Google App Engine" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/google-appengine?hl=en -~----------~----~----~----~------~----~------~--~---
