A mathematical procedure used to solve problems with a series of steps. Algorithms are usually encoded as a sequence of computer commands.
50
votes
12answers
12k views
Concave Hull: Definition, Algorithms and Practical Solutions
Convex Hull
A convex hull of a shape is defined as:
In mathematics, the convex hull or convex envelope for a set of points X in a real vector space V is the minimal convex set containing X ...
31
votes
3answers
4k views
Are there newer routing algorithms (than Dijkstra, A*) in GIS databases?
There are works like Reach for A* from Microsoft researchers and Highway Hierarchies by Sanders and Schtolz (if I spell the name correctly) from Karlsruhe Uni. Both of them reduce the calculations ...
21
votes
1answer
2k views
How to find the center of geometry of an object?
Well it might be a simple question. Given a set of 2D or 3D points, the question is:
How to find the center of geometry of an object?
According to the following figure, the center of geometry ...
19
votes
3answers
2k views
How to find the minimum-area-rectangle for given points?
The following is another problem that I am working on it these days.
As you see in the figure, (BTW, I tried to make it self-presenter) the question is:
How to find the minimum-area-rectangle (MAR) ...
18
votes
2answers
356 views
How does Watson solve Geography problems?
In spite of losing to humans on the geography question, Watson still won Jeopardy.
The explanations regarding this incorrect answer seem a bit lame to me (at 3:40 in the video).
With a logo like ...
17
votes
2answers
1k views
Acquiring ArcGIS-like speed in Postgis
I have been using Postgis 2.0 for 3/4 of a year now and while I really enjoy using it, excessive query processing time has rendered it basically unusable for my use case.
I tend to do heavy ...
16
votes
1answer
3k views
How to divide a polygon into specific sizes using ArcGIS?
I have several thousand irregularly shaped polygons in a shapefile. I want to be able to split each polygon into three areas, and to specify what the size of those areas (they sum to the previous ...
15
votes
3answers
5k views
Why is law of cosines more preferable than haversine when calculating distance between two latitude-longitude points?
In fact, when Sinnott published the
haversine formula, computational
precision was limited. Nowadays,
JavaScript (and most modern computers
& languages) use IEEE 754 64-bit
...
15
votes
5answers
998 views
Algorithm to fix topological errors in GIS software apps
Related question here.
I notice that ensuring topological correctness is essential for GIS applications, this is because the input from user or polygon boolean operation can have severe topological ...
15
votes
3answers
2k views
Find tunnel 'center line'?
I have some map files consisting of 'polylines' (each line is just a list of vertices) representing tunnels, and I want to try and find the tunnel 'center line' (shown, roughly, in red below).
I've ...
15
votes
0answers
360 views
Space filling between random 2D lines
Consider a region (2D) filled with lines randomly (following Figure). We are interested in filling the empty spaces between lines including four boundary edges in a way:
0- maximizing the size of ...
14
votes
5answers
1k views
Good resources on geocoding algorithms
Do you know of any good resources on geocoding algorithms?
I am particularly interested in address query parsing, including matching and weighting parts of the query, dealing with misspellings and ...
14
votes
4answers
1k views
Different approaches for map matching : links / ideas?
I'm using Open Street Map and its vectorial road network and I'd like to implement a map matcher algorithm.
Currently I'm able, for each GPS position, to retrieve the nearest road segment and ...
14
votes
1answer
297 views
Heatmap algorithm to visualise point diversity
Can anyone suggest an algorithm to generate a heatmap for visualising point diversity? An example application would be for mapping areas of high species diversity. For some species, every single plant ...
13
votes
4answers
787 views
algorithm to place maximum number of points within constrained area at a minimum spacing
I have a polygon layer that describes a constraint; I wish to add points within this area. I want to add as many points as possible, but they must have a minimum spacing between them. Is it possible ...
13
votes
1answer
684 views
Robust alternatives to Moran's I
Moran’s I, a measure of spatial autocorrelation, is not a particularly robust statistic (it can be sensitive to skewed distributions of the spatial data attributes).
What are some more robust ...
12
votes
5answers
1k views
Algorithms for matching segments
What are the best algorithms to match segments?
I'm trying to match corresponding segments from two map sources, one less accurate but with segment names, and one more accurate without segment names. ...
11
votes
3answers
3k views
Algorithm to find nearest point
I've a list of a few hundred cities with their latitude/longitude. Given another location (also in lat/long) I need to find the nearest city.
As I don't use any GIS, by now the obvious algorithm is ...
11
votes
2answers
778 views
Calculate distortion outside a UTM zone
One of my colleagues is working with data that is spread across two UTM zone. The majority of the data is in one zone, with a few outliers in another zone. He would like to know what the area ...
11
votes
4answers
343 views
How to generalize coastlines?
I have a large set of data points that essentially represent the coastline of the world. I don't know the exact resolution but I'd say it's in the neighbourhood of 5-10m.
Imagine a set of points ...
11
votes
3answers
472 views
Algorithm to find out points of inflection for a polyline
I am trying to find out the points of inflection , i.e. points where the curves in a line start and end. If you look at the image, the green line may be a road or a stream, and the black points are ...
11
votes
3answers
3k views
How to split a line into a set of equidistant points
Used to rely on XTools for this, but in my current environment, I don't have access to it.
I'm trying to do this in ArcMap10.
The goal is to break a line representation of a stream into a set of ...
11
votes
0answers
500 views
How to Split a Concave Polygon Into Convex Polygons in Arcpy?
I'm looking for a tool or algorithm to detect concave polygons and split them into convex polygons. Like explained in the picture, the blue polygon is split into A and B polygons
I'm using Arcpy ...
10
votes
4answers
616 views
Point Pattern Analysis Algorithms
I'm looking for point pattern analysis algorithms and literature on point pattern analysis, online resources and book titles welcome. The topics may range from general descriptions of algorithms to ...
10
votes
3answers
935 views
Meaning of Simplify's tolerance parameter
The standard parameters of Douglas-Peucker's simplify algorithm are geometry and tolerance (e.g ST_Simplify in PostGIS). What's the meaning of the tolerance parameter? I know that the bigger the ...
10
votes
4answers
362 views
Dikes extraction from DEM
I do have DEM of 1x1 meter and original LiDAR point cloud in .las, that DEM is made of. I need to extract river dikes (highest points of the dikes) to vector feature (point, polyline). Any idea for ...
10
votes
4answers
586 views
Algorithm to calculate coverage + overlaps from a set of arcs
I have a shapefile containing arcs representing the path travelled by a truck spreading fertiliser onto a farm.
Let's say I know the spread width is 30m, i.e. the truck can spread fertiliser 15m ...
10
votes
2answers
234 views
Algorithm: move a source polyline to a reference polyline (completely or maybe partially)
In our system, there're the requirements that we want to move some source lines (with low precision) to reference lines (with high precision). Following pictures gives the normal use cases. The red ...
10
votes
2answers
576 views
Drawing Day and Night on a Google Map
I'm looking to plot day/night on a Google map, for an arbitrary point in time. I'm familiar with generating map tiles; I'm just looking for an algorithm to tell me whether a particular point on the ...
10
votes
4answers
2k views
Clustering Trajectories (GPS data of (x,y) points) and Mining the data
I've got 2 questions on analyzing a GPS dataset.
1) Extracting trajectories I have a huge database of recorded GPS coordinates of the form (latitude, longitude, date-time). According to date-time ...
10
votes
1answer
226 views
Are there any intelligent travelling salesmen?
Jokes aside, I have had a routing problem that is almost a travelling salesman problem (TSP):
the starting point is defined
the end point coincides with the starting point
each node has to be ...
9
votes
3answers
312 views
How can Flocking Algorithms be used in GIS?
The first flocking algorithm was written by Craig Reynolds in 1986. A recent browser implementation can be found here.
...
9
votes
6answers
1k views
How to find the boundary co-ordinates from a given set of co-ordinates
Given a set of coordinates, How do we find the boundary coordinates.
<== Figure 1
Given the coordinates in the above set, How can I get the coordinates on the red boundary. Boundary is the polygon ...
9
votes
9answers
4k views
Algorithm for finding irrregular polygon centroid (label point)
I need to find a centroid (or label point) for irregularly shaped polygons in Google Maps. I'm showing InfoWindows for parcels and need a place to anchor the the InfoWindow that is guaranteed to be on ...
9
votes
1answer
253 views
How to visualize azimuthal data with uncertainties?
I am trying to make a figure showing azimuthal data with a different range of uncertainties at each point. This oldschool figure from a 1991 paper captures the "bowtie plot" idea that I'm aiming for:
...
9
votes
2answers
229 views
Custom implementation of ArcGIS function
I would like to find out what it takes to create a custom implementation of an ArcGIS function. In particular, I would like to implement GeoAnalyst.ISurfaceOp2.Visibility() in order to get it to run ...
9
votes
2answers
713 views
PostGIS: split a polygon in a given ratio
Is there a convenient way to split a polygon into n parts, more-or-less equal in size in PostGIS?
8
votes
2answers
337 views
Tools for importing historical maps into modern GIS systems
What tools exist to derive geometries for use with modern GIS systems from older scanned maps? I am referring more to libraries that generate actual data rather than present an interface for manually ...
8
votes
3answers
146 views
Location storage and query algorithms. How do they work?
One of the most important aspects of a GIS-equipped database is that it provides the user with the capability to quickly query for all points within some arbitrary geographic area that match some ...
8
votes
2answers
437 views
Elevation profile sample point algorithm
In generating an elevation profile, samples from the underlying raster must be taken. If the objective is to create a profile of maximum quality, how should the locations of sample points be ...
8
votes
1answer
377 views
Given a line on the earth's surface, how do I plot a line perpendicular to it?
Given a line on the earth's surface, how do I plot a line perpendicular to it?
Apologies if this is a very simple question. I thought this would be a straightforward task, but it is proving ...
8
votes
3answers
3k views
Bilinear interpolation of point data on a raster in Python?
I have a raster that I'd like to do some point interpolations with. Here is where I'm at:
from osgeo import gdal
from numpy import array
# Read raster
source = gdal.Open('my_raster.tif')
nx, ny = ...
8
votes
1answer
206 views
An example Tissot ellipse for an Equirectangular Projection?
I am trying to calculate distortion of an equirectangular projection via Tissot indicatrices. I have tried following the directions on this post (among other things) but it is beyond my understanding ...
8
votes
3answers
280 views
Find Duplicate Polygons Algorithm
I have a group of polygons. My objective is to find the duplicate polygons from these group of polygons.
Using NetTopologySuite(A c# port of JTS), it is possible to compare two geometires and check ...
8
votes
2answers
979 views
Incremental spatial clustering algorithm
I'm in search of a incremental spatial clustering algorithm. Here is my use case:
users create entries with an initial position
users may change the positions of existing entries
I now want to ...
8
votes
0answers
54 views
Alternative indexing methods for point set operations
It is common to use a bounding box spatial index to improve performance when working with a large number of features. Where operations are performed against individual geometries with a large number ...
7
votes
6answers
2k views
Lines to Polygons
I have failed to find the "name" of the algorithm that would allow one to convert lines to polygons. Since this issues crosses GIS and the fields of computational geometry and computer science. I am ...
7
votes
4answers
4k views
Calculating Lat/Lng X miles from point
I am wanting to find a latitude and longitude point given a bearing, a distance, and a starting latitude and longitude.
This appears to be the opposite of this question (Distance between lat/long ...
7
votes
2answers
90 views
Hashing functions for GIS data
I would like to take geometries from a vector dataset and reduce them to a hash. This hash would then be used to verify the integrity of that data and also identify identical geometries.
Do any ...
7
votes
1answer
507 views
How does one calculate an angle in a geographic coordinate system?
Given three points on a line in a geographic coordinate system, how does one calculate the angle formed by these three points?
Please, give a general solution but also include system specific ...
