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)

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 ...
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 ...
23
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 ...
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 ...
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 ...
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 ...
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 ...
5
votes
2answers
778 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 ...
27
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) ...
4
votes
2answers
1k 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 ...
29
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 ...
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 ...
4
votes
2answers
448 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 ...
10
votes
1answer
607 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: ...
6
votes
3answers
4k 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 ...
7
votes
6answers
3k 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 ...
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 ...
9
votes
1answer
483 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 ...
5
votes
4answers
2k 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 ...
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 ...
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 ...
3
votes
1answer
1k 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 ...
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. ...
7
votes
5answers
2k views

Algorithm to find polygons enclosing points

I'm trying to find an algorithm that can determine the smallest possible polygons to cover a number of points. I know how to get the convex hull around all the points, but say that the points are ...
4
votes
2answers
8k 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, ...
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 ...
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 ...
6
votes
4answers
2k views

Point in polygon algorithm for multiple polygons

I've a Google map with bunch of polygons on it. Here is a problem I'm interested in: Given a lat,lng point, what's the best way to determine all the polygons that this point lies in? The obvious way ...
4
votes
3answers
251 views

How to number 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 ...
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 ...
7
votes
2answers
2k 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 ...
3
votes
2answers
3k views

How to split a line at point positions?

I am a rooky with QGIS and i am stuck from a basic problems. I have a polyline and i have some points (2) on the polyline. I would like to know if there is a tool or script that i could use to ...
9
votes
2answers
325 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 ...
7
votes
4answers
460 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 ...
6
votes
6answers
2k views

How to calculate the maximum distance within a polygon in x-direction (east-west direction) in PostGIS?

I am interested in the maximum width of a polygon, e.g. a lake, in the east-west direction. Bounding boxes will help only in simple polygons but not in complex concave polygons.
6
votes
3answers
806 views

Retrieve polygon smallest MBR

I have a postgis table containing polygons. I want to transform my polygons to 4 points polygons : retrieve the smallest MBR. Here comes an illustration of what I want : My original polygon is ...
0
votes
3answers
306 views

splitting a lines layer using points

I'm looking to accomplish a similar task to this thread: How to split a line at point positions? Using QGIS and the Processing and GRASS toolboxes available, I'm looking to split a vector layer ...
35
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 ...
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 ...
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 ...
8
votes
2answers
2k 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 ...
12
votes
4answers
628 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
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
358 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
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 = ...
8
votes
1answer
874 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 ...
6
votes
2answers
898 views

How do I select only those features, that are connected?

I have a polygon layer of water reservoirs and a polyline layer of canals. In my data, some canals are originating from reservoirs, and leading to other canals. On the other hand there are some ...
5
votes
1answer
2k 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 spesific catchment area (a=A/L, catchment area (A)divided by contour ...
4
votes
2answers
592 views

Method for finding circle center points that cover an extent

If I have a geographic extent, is there any way to find all of the center points of all of the 5km circles that would be needed to cover the entire extent? I'm working with an API that will return ...