We’re rewarding the question askers & reputations are being recalculated! Read more.

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

128 questions
Filter by
Sorted by
Tagged with
109k 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 ...
182k 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 ...
25k 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 ...
48k views

### What are Definition, Algorithms and Practical Solutions for Concave Hull? [closed]

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 (...
37k 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-...
10k 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 ...
12k 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 ...
71k 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 ...
8k 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 ...
8k 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.
46k 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 ...
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 ...
5k 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 ...
4k 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 ...
11k 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 ...
22k views

### How to calculate grid convergence (True North to Grid North)?

I would like to know how to calculate the grid convergence angle between True North and Grid North for UTM maps. I am using ArcGIS 10.0 (ArcView licence) and have used the Calculate Grid ...
9k views

### Splitting lines automatically at specific distances using ArcGIS Desktop?

I have a set of polylines which I need to split at varying distances from their starting points. In general, I'm looking for a something similar to the SPLIT function within the editor tool. There ...
34k 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 ...
8k 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 ...
1k views

### Numbering polygons according to their spatial relationships?

I have, for example, this layer in postgresql (polygons): table : poly (objectid: integer, num: integer, shape: geometry) I want to enumerate the polygons from left to right and top to bottom like ...
5k views

### Multilateration Code

I am currently writing some code to do multilateration using TDOA and currently struggling and wondering if anyone has any reference code that can be used as a test case with some sample data that I ...
1k 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: ...
366 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....
13k 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 ...
7k views

### How to calculate area of 1 x 1 degree cells in a raster

I have a simple array (not geo-referenced in any way) in Matlab (which is not a language I know a huge amount about...so I can export it to other languages if needed) which has the dimensions 180 x ...
4k views

### Generate polygons from a set of intersecting lines

This is a simple and quite common question which has already been asked for different purposes (see this link and this too, for example), here, however, we are looking for not a software package but ...
1k views

I wrote the following code to start using QGIS APIs. in a very short script seen below, the "Error: Algorithm not found" is thrown and "print processing.alglist()" is showing none. Any idea why this ...
3k views

### splitting a lines layer using points

I'm looking to accomplish a similar task to this thread: Splitting line at point positions using QGIS? Using QGIS and the Processing and GRASS toolboxes available, I'm looking to split a vector layer ...
361 views

### Possible point location algorithm

I need to calculate possible point location based on its speed and some other factors. For example, there is a man in the middle of the forest and I need to calculate his possible location at some ...
8k 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. ...
16k views

### Calculating Topographic Wetness Index (choosing from different algorithms)

Topographic Wetness Index can be expressed as Ln(a/tanB) based on the idea of Beven and Kirkby (1979) where a is the specific catchment area (a=A/L, catchment area (A)divided by contour length(...
38k views

### Calculate bearing between two decimal GPS coordinates

I'm building a virtual tour application that uses custom panoramas in conjunction with Google's StreetView service. With StreetView, you can have 1 to n links at each particular location to move to, ...
27k 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 ...
13k 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 ...
4k views

### Exploding overlapping to new non-overlapping polygons?

Given multiple polygons that overlap in multiple ways, I would like to export from these features all polygons that don't overlap with others, iteratively. The product would be a number of features ...
1k 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 ...
4k 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 ...
1k 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 ...
2k views

### How do I find least cost path over a DEM based on slope magnitude and direction?

What sort of algorithms can I use to find a least cost path through a DEM where it costs more to traverse a cell going downhill or uphill than it does to follow the contour of the land? All the ...
2k views

### Identify the latitudinal and longitudinal point directly beneath an object in space

Given the azimuth and altitude / latitude and longitude from the observer to the satellite, how can I accurately find the latitude and longitude of the point of intersection directly under the ...
3k views

### WGS point to WGS line segment (great circle) distance

How would I go about resolving this in C#? I have a line segment (great circle distance) defined by two Lon-Lat pairs (call them points A and B). A third point somewhere on the Earth sphere. The ...
13k 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 ...
4k views

### Similarity between two raster maps

Having two raster maps as the examples below: We are interested in evaluating their similarities. As shown, they are not fully overlapping. We guess one way is to clip small one area from the bigger ...
6k 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 ...
11k 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,...
15k 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 ...
45k 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 ...
3k 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 ...