Questions tagged [algorithm]

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

Filter by
Sorted by
Tagged with
176 votes
8 answers
288k views

Algorithm for offsetting a latitude/longitude by some amount of meters

I'm looking for an algorithm which when given a latitude and longitude pair and a vector translation in meters in Cartesian coordinates (x,y) would give me a new coordinate. Sort of like a reverse ...
Thomas O's user avatar
  • 2,053
143 votes
14 answers
74k 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 (Wikipedia)...
Adam Matan's user avatar
  • 6,820
96 votes
8 answers
125k views

Finding minimum-area-rectangle for given points?

As you see in the figure, the question is: How to find the minimum-area-rectangle (MAR) fitted on the given points? and a supporting question is: Is there any analytical solution for the ...
Developer's user avatar
  • 3,387
70 votes
2 answers
14k 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 ...
THX1138's user avatar
  • 1,611
59 votes
7 answers
159k views

Calculating Latitude/Longitude 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 ...
Jason Whitehorn's user avatar
53 votes
3 answers
18k 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 value,...
ejel's user avatar
  • 867
46 votes
3 answers
46k 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 floating-...
Afriza N. Arief's user avatar
46 votes
12 answers
29k views

Map matching links and ideas? [closed]

I'm using OpenStreetMap 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 ...
46 votes
3 answers
12k 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 ...
culebrón's user avatar
  • 2,314
45 votes
6 answers
61k views

Trilateration using 3 latitude/longitude points, and 3 distances?

I want to find out an unknown target location (latitude and longitude co-ordinates). There are 3 known points (latitude and longitude co-ordinate pairs) and for each point a distance in kilometers to ...
nohat's user avatar
  • 555
43 votes
1 answer
46k views

Finding center of geometry of object?

Given a set of 2D or 3D points: How to find the center of geometry of an object? According to the following figure, the center of geometry differs from the center of mass if it is calculated in the ...
Developer's user avatar
  • 3,387
36 votes
6 answers
126k views

Finding if two polygons intersect in Python

I'm looking for an algorithm, a high-level solution, or even a library which can help me determine if two polygons intersect, in Python. I have the vertices of the two polygons (These are single-part ...
Devdatta Tengshe's user avatar
30 votes
4 answers
28k 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 ...
Developer's user avatar
  • 3,387
29 votes
3 answers
12k views

Dividing polygon into specific sizes using ArcGIS Desktop?

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 ...
djq's user avatar
  • 16.3k
29 votes
2 answers
10k views

Calculating areal distortion outside 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 ...
kenbuja's user avatar
  • 5,680
25 votes
6 answers
10k views

Algorithms for matching segments [closed]

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. ...
Adam Matan's user avatar
  • 6,820
25 votes
2 answers
1k views

Seeking Algorithm to detect circling and beginning and end of circle?

I've got lots of flight data from glider pilots in the form of gps fixes in a fixed interval. I would like to analyze the flight path and detect the start and the end of the 'circling' the glider ...
pgross's user avatar
  • 493
23 votes
1 answer
1k 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 ...
Developer's user avatar
  • 3,387
22 votes
6 answers
41k views

Finding boundary co-ordinates from given set of point 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 ...
Khaja Minhajuddin's user avatar
22 votes
3 answers
7k 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 ...
Devdatta Tengshe's user avatar
22 votes
2 answers
609 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 ...
Kirk Kuykendall's user avatar
21 votes
2 answers
8k views

Finding the Center Line from a set of 3D Points

I have a set of 3D points. They follow a curved pattern with a rather constant diameter as shown below. What would be the algorithm to trace the approximate center line of these points?
vinayan's user avatar
  • 7,282
21 votes
1 answer
6k 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 ...
geogeek's user avatar
  • 4,566
20 votes
4 answers
19k views

Calculating roundness/compactness of polygon?

I am trying to find ways to quantitatively describe the shapes of various polygons. For my project, these polygons represent lakes, rivers, lagoons, and parks. So they can be almost any shape. One ...
user25201's user avatar
  • 361
20 votes
3 answers
25k views

Algorithm to find nearest point

I have 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 ...
lujop's user avatar
  • 365
20 votes
5 answers
4k 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 ...
Petr Krebs's user avatar
  • 10.3k
20 votes
5 answers
3k 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 ...
Graviton's user avatar
  • 928
19 votes
2 answers
10k views

Finding 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 ...
sje397's user avatar
  • 291
19 votes
1 answer
4k 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 ...
rudivonstaden's user avatar
19 votes
1 answer
4k 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 ...
MannyG's user avatar
  • 653
18 votes
3 answers
2k views

Clustering undirected lines

I'm looking for an efficient way to cluster lines independent of their direction. That means that a line between New York and Los Angeles should be in the same cluster as a line in the other direction ...
underdark's user avatar
  • 84k
17 votes
5 answers
5k views

Simplifying polygons to linestring?

I would like to simplify some polygons that represent rivers into linestrings. I assume that holes in polygons can be omitted. Anybody has some good idea how to simply do it? It would be nice, if it ...
stachu's user avatar
  • 861
17 votes
5 answers
5k views

Seeking algorithm to place maximum number of points within constrained area at 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 ...
Matthew Snape's user avatar
17 votes
5 answers
21k 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 ...
Murat's user avatar
  • 517
17 votes
1 answer
232 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 ...
Matthew Snape's user avatar
16 votes
2 answers
13k views

Is there an optimal algorithm to find the longest shortest path in a network?

I have a large set of linear networks and I would like to find the two ends of each network that are the most distant from each other along the network (on the image below, it would be D to K). The ...
radouxju's user avatar
  • 49.6k
16 votes
2 answers
8k views

Point of Intersection for a Ray and Earth's Surface

Say I have a ray vector originating from somewhere out in space. An example might be a ray of light from the sun. How can I calculate the point of intersection (if it exists) between the ray and the ...
Pris's user avatar
  • 1,251
15 votes
4 answers
2k views

Performing 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 ...
Tomek's user avatar
  • 2,923
15 votes
3 answers
9k views

Calculating a spherical polygon centroid

I'd like a general way to calculate centroids for polygons on a sphere. So far, the best online reference appears to be: Tools for Graphics and Shapes by Jeff Jenness. The method described there ...
Jason Davies's user avatar
15 votes
1 answer
481 views

Matching segments of different lengths

I'm trying to match small segments with a larger segment they are the most probably related to: relatively close, similar bearing, and facing each other. Here is a typical example of the data I have: ...
Jukurrpa's user avatar
  • 331
14 votes
7 answers
10k views

Calculating maximum distance within polygon in x-direction (east-west direction) in PostGIS?

I am interested in the maximum width of a polygon e.g. a lake, in east-west direction. Bounding boxes will help only in simple polygons but not in complex concave polygons.
cardiopteris's user avatar
14 votes
2 answers
1k views

Detecting branched polygon shape?

I have a vector layer with millions of polygons making continuous coverage. I need to classify them according to their shape. I am already using several shape indexes from landscape ecology like ...
nadya's user avatar
  • 2,471
14 votes
1 answer
14k views

Python: find a method to calculate the “inner centroid” (also known as labelPoint in arcmap) of a polygon

I am looking for a method to compute the X,Y coordinate of an inner point (also known as labelPoint in arcmap) of a (irregular) polygon. I try to find a solution without the use of ArcGIS module. The ...
Gianni's user avatar
  • 409
13 votes
2 answers
4k views

Creating "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 ...
slowhand's user avatar
  • 141
13 votes
5 answers
20k views

Calculating coordinates of square x miles from center point?

I am trying to create a x mile square (or circle) around a central point, where all sides of the square would be x miles from the centre. I need the 4 corner coordinates. It is scrambling my brain ...
Bex's user avatar
  • 323
13 votes
10 answers
16k 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 ...
Jason's user avatar
  • 698
13 votes
2 answers
16k views

What algorithm should I use to remove outliers in trace data?

I have GPX traces and want to remove outlying observations. There are some route points that are impossible because it would require acceleration that the vehicle can not achieve. Are there good ...
fgregg's user avatar
  • 378
13 votes
4 answers
23k 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 = ...
Mike T's user avatar
  • 42k
13 votes
2 answers
490 views

Minimising number of dynamic pages to map scattered points using ArcGIS Desktop?

From time to time I have to produce mapbook to show points of interest. First step to create pages, using regular mesh: I don't like the solution because a) there are some pages with single points (e....
FelixIP's user avatar
  • 22.8k
13 votes
8 answers
877 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. ...
FredB's user avatar
  • 741

1
2 3 4 5
12