# Tag Info

66

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 ...

44

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 ...

40

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. ...

40

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.) ...

35

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

33

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 ...

30

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 ...

29

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 ...

26

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 pinned-...

26

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 ...

21

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 ...

21

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 ...

21

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

Have you tried with shapely ? They describe spatial relationships and it work on windows The spatial data model is accompanied by a group of natural language relationships between geometric objects – contains, intersects, overlaps, touches, etc. – and a theoretical framework for understanding them using the 3x3 matrix of the mutual intersections ...

16

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

15

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 ...

14

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 ...

14

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 ...

14

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.intermezzo-coop.eu/mapping/geostats/ (with a concrete choropleth representation sample). It supports the 8 methods listed above : Quantile Equal ...

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

To save you some time here is @MerseyViking answer in javascript: function radians(n) { return n * (Math.PI / 180); } function degrees(n) { return n * (180 / Math.PI); } function getBearing(startLat,startLong,endLat,endLong){ startLat = radians(startLat); startLong = radians(startLong); endLat = radians(endLat); endLong = radians(endLong); ...

12

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 ...

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

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

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 ...

11

When the curve is comprised of line segments, then all interior points of those segments are inflection points, which is not interesting. Instead, the curve should be thought of as being approximated by the vertices of those segments. By splining a piecewise twice-differentiable curve through those segments, we can then compute the curvature. An ...

10

The projecting of points onto the line as you are already doing is possible to do directly in PostGIS. I wrote about is some time ago, here But to solve your problem when the points is closer to wrong segment than the right segment maybe this could be a possible approach. 1) Build a linestring of the points 2) Try the suggested solutions in this Question ...

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