A mathematical procedure used to solve problems with a series of steps. Algorithms are usually encoded as a sequence of computer commands.

learn more… | top users | synonyms (1)

64
votes
15answers
20k views

What are Definition, Algorithms and Practical Solutions for Concave Hull?

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 ...
36
votes
3answers
7k 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 ...
33
votes
2answers
4k 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 ...
30
votes
1answer
9k 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 ...
28
votes
4answers
8k 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) ...
24
votes
12answers
6k 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 ...
22
votes
3answers
11k 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 ...
21
votes
1answer
705 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 ...
20
votes
3answers
3k 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 ...
19
votes
1answer
1k 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 ...
18
votes
2answers
387 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
3answers
3k 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 ...
16
votes
1answer
5k 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 ...
16
votes
1answer
1k 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 ...
15
votes
5answers
2k 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 ...
15
votes
2answers
2k 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 ...
15
votes
5answers
2k 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
4answers
1k 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 ...
15
votes
3answers
1k 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 ...
15
votes
1answer
870 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 ...
14
votes
5answers
3k 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. ...
14
votes
3answers
2k views

How to find the maximum-area-rectangle inside a convex polygon?

In this post we are looking for algorithms / ideas on how to find the maximum-area-rectangle inside a convex polygon. In the following figure, numbers are the areas of the fitted rectangles. As shown ...
14
votes
1answer
165 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 ...
12
votes
3answers
4k 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 ...
12
votes
4answers
639 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 ...
12
votes
8answers
377 views

Looking for pedestrian-specific routing engines

Most of the applications providing pedestrian routing I see are sufficient for many needs but not optimal: you cannot cross open spaces like town squares, routing is in the middle of the street etc. ...
12
votes
4answers
5k 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 ...
11
votes
6answers
3k 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 ...
11
votes
5answers
12k 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 ...
11
votes
4answers
425 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
5k 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
2answers
1k 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 ...
11
votes
1answer
365 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 ...
10
votes
4answers
728 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
2answers
376 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 ...
10
votes
9answers
7k 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 ...
10
votes
1answer
621 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: ...
10
votes
4answers
807 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
339 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
4answers
2k views

How to filter wrong GPS points?

I have a database of GPS points. There aren't any tracks, only points. I need to calculate some value for every 100 meters, but sometimes GPS gave a wrong coordinates that lies far from real GPS ...
10
votes
1answer
286 views

Looking for a trajectory similarity measure

For my final academic work I have developed a compression algorithm for GPS trajectories. I can estimate the quality of the spatio-temporal compression by computing the syncronized euclidean distance ...
9
votes
3answers
358 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
2answers
331 views

Creating an “average” polygon

I found this thread in the old ESRI forums with the same type of problem I am facing today. The solution to the problem is explained in little detail and since I am not an expert, I was wondering if ...
9
votes
2answers
285 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
4answers
5k 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 = ...
9
votes
2answers
991 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?
9
votes
1answer
495 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 ...
9
votes
1answer
3k views

How does ArcGIS Desktop calculate INSIDE point for Feature to Point?

Let me back up and say that from what I understand there are two common ways to calculate the centroid of a polygon in ArcGIS Desktop: Using Calculate Geometry on fields within the attribute table ...
8
votes
1answer
1k views

Grouping map points into fixed cluster sizes?

I have a dataset of 655 lat/long pairs which I'd like to split into about 100 groups. A group should have 5-10 pairs which are geographically close to each other. Dense groups should have more ...
8
votes
3answers
168 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 ...