Tag Info

Hot answers tagged

49

Different approach. Knowing that the pain is in ST_Intersection, and that true/false tests are fast, trying to minimize the amount of geometry passing through the intersection might speed things up. For example, parcels that are totally contained in a jurisdiction don't need to be clipped, but ST_Intersection will still probably go to the trouble of building ...


38

Every polygon has, at a minimum, four distinct "centers": The barycenter of its vertices. The barycenter of its edges. Its barycenter as a polygon. A GIS-specific "center" useful for labeling (usually calculated with undocumented proprietary methods). (They may accidentally coincide in special cases, but for "generic" polygons they are distinct points.) ...


32

As scw points out, you want an implementation of α-shapes. Alpha shapes can be considered a generalisation of the convex hull. They were first described in 1981 in: Edelsbrunner, H.; Kirkpatrick, D.; Seidel, R.; , "On the shape of a set of points in the plane," Information Theory, IEEE Transactions on , vol.29, no.4, pp. 551- 559, Jul 1983 ...


26

The problem is indicated by the word "well-conditioned." It's an issue of computer arithmetic, not mathematics. Here are the basic facts to consider: One radian on the earth spans almost 10^7 meters. The cosine function for arguments x near 0 is approximately equal to 1 - x^2/2. Double-precision floating point has about 15 decimal digits of precision. ...


25

Here is what you are looking for. You can download and test the program: (in java, under GPL license) The paper presenting the algorithm is there: Duckham, M., Kulik, L., Worboys, M.F., Galton, A. (2008) Efficient generation of simple polygons for characterizing the shape of a set of points in the plane. Pattern Recognition v41, 3224-3236


25

This problem has many valid solutions. One of them works a little like your description, but instead of slicing the polygons at "random" locations you can do it purposefully in a way designed to minimize the amount of computation. Here is the basic algorithm. Its input consists of any plane sweep direction, a polygon P of nonzero area, a target area a ...


24

Yes, there is an analytical solution for this problem. The algorithm you are looking for is known in polygon generalisation as "smallest surrounding rectangle". The algorithm you describe is fine but in order to solve the problems you have listed, you can use the fact that the orientation of the MAR is the same as the one of one of the edges of the point ...


22

To supplement @julien's great solution, here is a working implementation in R, which could serve as pseudocode to guide any GIS-specific implementation (or be applied directly in R, of course). Input is an array of point coordinates. Output (the value of mbr) is an array of the vertices of the minimum bounding rectangle (with the first one repeated to ...


19

The truth is that most people use a custom variation of the A* algorithm. You will see this across the most of the "big guys"(I can't say who they are in a public forum, but I can tell you that you probably use one of them - guaranteed), where the modification of the heuristics is very dependent on the datasets that they use. You mentioned pgrouting ...


19

UTM uses a transverse Mercator projection with a scale factor of 0.9996 at the central meridian. In the Mercator, the distance scale factor is the secant of the latitude (one source: http://en.wikipedia.org/wiki/Mercator_projection), whence the area scale factor is the square of this scale factor (because it applies in all directions, the Mercator being ...


18

This seems to be a specific application of alpha shapes, which are from my reading a more general form of this problem. R has the alphahull module, which has excellent documentation on computing alpha shapes. Also check this detailed background on alpha shapes. If you only want to compute convex/concave hulls, check out lasboundary, part of lastools, it ...


18

I investigated exactly this question 20 years ago when designing a desktop GIS. We needed to find point-to-point distances interactively; our target was to do the computations in less than 1/2 second for thousands of points. Testing (on a 25 MHz 486 PC!) showed that we could compute all the distances, exactly as you describe (with the simple obvious ...


18

The tolerance is a distance. Roughly, any "wiggles" in a curve that vary from a straight line by less than this amount will be straightened out. The algorithm finds the most extreme wiggles that exceed the tolerance, pins down the points where they deviate the most from a straight path, and then recursively applies itself to the arcs between the ...


13

From Text to Geographic Coordinates: The Current State of Geocoding Daniel W. Goldberg, John P. Wilson, and Craig A. Knoblock Abstract: This article presents a survey of the state of the art in geocoding practices through a cross-disciplinary historical review of existing literature. We explore the evolving concept of geocoding and the fundamental ...


13

Not sure if it is newer but pgRouting has a Shooting-Star algorithm: Shooting-Star algorithm is the latest of pgRouting shortest path algorithms. Its speciality is that it routes from link to link, not from vertex to vertex as Dijkstra and A-Star algorithms do. This makes it possible to define relations between links for example, and it ...


13

Well, I coded something yesterday and released it under MIT License. The library, named geostats is available on github. The package includes examples. You will also be able to see it in action on http://www.empreinte-urbaine.eu/mapping/geostats/ (with a concrete choropleth representation sample). It supports the 8 methods listed above : Quantile Equal ...


12

If you are interested in an implementation look at jsts a Javascript implementation of the much used Java Topology Suite library -- depending on whether you prefer reading Javascript or Java, I suppose. A general idea of how the algorithm works. For points, it is trivial, you simply buffer them by a given radius. If you have multiple points, you will have ...


11

MapAnalyst - The Map Historian's Tool for the Analysis of Old Maps Calculates Displacement in Historical Maps(displacement vectors,distortion grid,scale isolines,rotation isolines.) "MapAnalyst is a Java application that runs on all major computer platforms. It allows for the efficient identification and management of control points in a historical map and ...


11

There is an implementation of ST_ConcaveHull in PostGIS trunk. http://postgis.net/docs/ST_ConcaveHull.html /Nicklas


11

I created a highly-efficient tool, called [lasboundary][1,2], that computes a concave hull for LIDAR in LAS/LAZ/SHP/ASCII format and stores the result as a vector boundary polygon in ESRI Shapefile format or a geo-referenced KML file. Here is an example run: C:\lastools\bin>lasboundary -i SerpentMound.las -o SerpentMound_boundary.shp reading 3265110 ...


11

Spatial Statistics is probably classic example here. Also Spatial Data Analysis offers solid overview Statistical Methods for Spatial Data Analysis, Geospatial Analysis - a comprehensive guide and Geographic Information Analysis will give you nice overview as well. Another, more practical oriented way to go would be to look at R. Have a look at CRAN ...


11

The Hausdorff distance may be used: matching segments could be 'close' segments according to this distance. It is quite simple to compute on segments. A free java implementation is available in JTS - see here. You may also have a look at the JCS Conflation Suite.


11

Introduction Because this issue (of discrepancies in standard deviations, variances, or other statistical summaries) comes up periodically, especially when a thoughtful and careful GIS analyst checks their work, I thought it would be good to share the "forensic analysis" of the discrepancy so that readers can carry out similar checks in their own ...


10

There are many algorithms to solve this problem (Wikipedia "Convex_hull_algorithms"): Gift wrapping aka Jarvis march — O(nh): One of the simplest algorithms. It has O(nh) time complexity, where n is the number of points in the set, and h is the number of points in the hull. In the worst case the complexity is O(n2). Graham scan — O(n log n): Slightly more ...


10

It seems that you are looking for examples of Agent-based Modeling (ABM). There are many GIS models adopt the ABM mechanism. For example, urban planning used lots of cellular automata models that are essentially same as the flocking model. I have implemented a ABM for U.S. logistics industry using AnyLogic to detect the dynamic organizational structure for ...


10

you can check out k-means clustering algorithm here. In data mining, k-means clustering is a method of cluster analysis which aims to partition n observations into k clusters in which each observation belongs to the cluster with the nearest mean. This results into a partitioning of the data space into Voronoi cells. kmeans-postgresql ...


9

I don't know what would be the "best," because that will depend on the particulars of your segments. A generally good approach is to hash the segments into crucial geometric information. This would include, at a minimum, location of the center (x,y), orientation (0 to 180 degrees), and length. With appropriate weights applied, and some finessing of the ...


9

I'd be curious how results from this formula compare with Esri's pe.dll. (citation). A point {lat,lon} is a distance d out on the tc radial from point 1 if: lat=asin(sin(lat1)*cos(d)+cos(lat1)*sin(d)*cos(tc)) IF (cos(lat)=0) lon=lon1 // endpoint a pole ELSE lon=mod(lon1-asin(sin(tc)*sin(d)/cos(lat))+pi,2*pi)-pi ENDIF This ...


9

A Smarter Planet had a great blog entry on why Watson got the answer wrong. Also, Bruce Upbin wrote specifically about Watson performing a spatial operation: There are many reasons Watson is good at Jeopardy!. It has something like a million pages of documents and a geospatial database in its memory. It can run the board on categories like ...


9

It is a consequence of a theorem of Archimedes (c. 287-212 BCE) that for a spherical model of the earth, the area of a cell spanning longitudes l0 to l1 (l1 > l0) and latitudes f0 to f1 (f1 > f0) equals (sin(f1) - sin(f0)) * (l1 - l0) * R^2 where l0 and l1 are expressed in radians (not degrees or whatever). l1 - l0 is calculated modulo 2*pi (e.g., -179 ...



Only top voted, non community-wiki answers of a minimum length are eligible