Hot answers tagged algorithm
32
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.)
...
30
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 ...
29
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
...
23
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 ...
22
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.
...
20
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
17
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 ...
17
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 ...
15
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 ...
15
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 ...
15
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 ...
14
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 ...
12
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 ...
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
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 ...
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
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 ...
10
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.
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 ...
9
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 ...
9
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 3 methods listed above :
Quantile
Equal ...
9
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 ...
8
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 ...
8
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
...
8
An algorithm for your problem is described here. You may be interested by its implementation in CGAL.
8
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 ...
8
This requires a kind of "field calculation" in which the value computed (based on a latitude, longitude, central azimuth, uncertainty, and distance) is the bowtie shape rather than a number. Because such field calculation capabilities were made much more difficult in the transition from ArcView 3.x to ArcGIS 8.x and have never been fully restored, nowadays ...
7
In terms of premade GIS, there's a bunch of stuff out there for travel costs on raster surfaces, e.g. r.cost, r.walk (different costs for uphill vs downhill!)
If you prefer brewing up code yourself so you know the exact algorithm:
http://stackoverflow.com/questions/2311486/how-to-calculate-the-shortest-path-between-two-points-in-a-grid
7
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 ...
7
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 ...
Only top voted, non community-wiki answers of a minimum length are eligible
