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)

6
votes
1answer
659 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 ...
3
votes
0answers
263 views

How to get all intersections between two simple polygons in O(n+k)? [closed]

Can someone help with a following problem: report all intersections between two simple polygons in O(n+k) where n - is a total number of polygon edges and k - is number of intersections. As a result - ...
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 ...
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) ...
30
votes
1answer
10k 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 ...
6
votes
1answer
405 views

How to find the smallest-area ellipse circumscribing a convex polygon?

We are currently dealing with the problem of: How to find an ellipse circumscribing a convex polygon? Recent googling and lots of reading could not help me so much :(
3
votes
1answer
436 views

How Can I Calculate Time from Coordinate?

For my application I am searching for an API or an algorithm for clicking point time and time zone. I dont know how I can do this but after getting time I want to calculate giving coordinate sun ...
5
votes
1answer
231 views

algorithm for displaying holes in a polygon by translating it into several hole-less polygons?

I'd like to plot polygons with holes on a framework that doesn't support holes. The approach to me seems to be to translate the single polygon into several ones adding up to the whole polygon, leaving ...
3
votes
2answers
253 views

Need an explanation on a network simplification algorithm

I try to implement the algorithm described in this paper (page 8), but there's a place that I can't understand, and the authors do not provide a more detailed explanation or pseudocode. They show how ...
3
votes
2answers
982 views

Finding the minimum and maximum distance between an observer and a lat/lon bounding box

I have three points in geographic coordinates (latitude, longitude, altitude). One of the points represents an observer, above the Earth. The other two points define a bounding box. I'd like a ...
2
votes
1answer
2k views

How to get the radius of a “circle” in Openlayers

How do you get the radius of a circle in openlayers? I have searched quite a bit and cannot find any resource for this. please help. Here is my code but I want the radius or circumference of the ...
2
votes
1answer
229 views

Is there any simple Map Labeling Algorithm?

I was looking into how to Label a few features on a small Map, and want to label them on the fly. I would be adding a few features (a maximum of around 6 to 7) as graphics on a web-Map which has ...
3
votes
1answer
986 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 ...
7
votes
2answers
2k 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 ...
1
vote
4answers
259 views

Looking for compute intensive GIS vector operations

I am looking to make efficient algorithms for those vector GIS operation that take a long time for GIS software like Arc-GIS, Grass etc. I have considered polygon overlay but looking for other ...
1
vote
1answer
539 views

How to speed up batch watershed delineation?

Hi this is probably a longer-winded question than it needs to be, but please bear with me. I have a large number of pour points - approximately 250,000 for which I want to delineate the upstream ...
7
votes
2answers
230 views

How to handle interpolation of multiple (quality) tiers of irregular data?

I'm going to try to provide a high level overview of the issue - realizing that more details/info will be necessary - but I don't want to write a novel that seems too overwhelming for people to ...
2
votes
2answers
231 views

How to remove roads from dataset

I've got a shape file that I loaded into PostGIS that has both road and parcel multipolygons and I need to remove the roads. I tried loading the shp file in qgis and it loads them both as a single ...
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 ...
6
votes
2answers
914 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 ...
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 ...
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 ...
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 ...
4
votes
2answers
2k views

Problems using the 'Split' tool with ArcGIS

I'm running into difficulty when using the split tool with ArcGIS 10. I am trying to split lines using a grid that I generated using the Fishnet command. Each gridcell has a unique text value as a ...
5
votes
3answers
1k views

Why doesn't the split tool return any records in the attribute table?

I've been trying to split a large land use shapefile using a set of study area polygons as the split feature, but when the function finally finishes running (the land use dataset is quite large), all ...
5
votes
1answer
1k views

How to create a polygon from other polygon boundaries?

I want to write an algorithm that creates a polygon inside a hole made by a set of other polygons. It's something like a flood fill and it's like the "boundary" tool in Autocad. The image shows an ...
2
votes
1answer
436 views

polygon map overlay algorithm

There are many algorithms for binary map overlay operation in vector data format which take two layers of map and produce resultant layer i.e overlaid layer as output. I am wondering whether there are ...
6
votes
6answers
1k views

Finding shortest path while avoiding polygon features

I'm developing an extension to ArcMap where I have a set of static, concave polygon features and I'm trying to find the shortest path between 2 points without crossing any of the polygons. Is there ...
7
votes
1answer
208 views

Optimize GEOSGeometry's spatial operations by avoiding thread-safety checks

A ranking algorithm I'm developing for a Django webapp requires performing spatial operations (within, intersections, sym_difference, etc.) using a query against large number of geometry objects. ...
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 ...
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 ...
6
votes
3answers
1k views

tiny JS discretization library for choropleth representation

I would like to know if a tiny stat/discretization js library ready to use exists. I do know about the existence of jStat (which I may explore a little bit more thoroughly), and I know that mapfish ...
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 ...
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 ...
7
votes
1answer
716 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 ...
8
votes
2answers
626 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 ...
3
votes
2answers
166 views

How to bring polygons closer to a point?

I have some scattered polygons with a lot of space between them. I want to make a thematic map but all that white space doesn't look very good, so I want to bring the polygons closer to the center of ...
3
votes
1answer
3k views

How to convert a bing maps quadkey to mercator coordinates

How do you convert a bing maps quad key, such as "03200320023" to coordinates in mercator virtual earth (epsg 3857) coordinate system? I've got an algorithm to convert to coordinates in latitude ...
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 ...
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 = ...
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 ...
1
vote
1answer
609 views

Is there any pseudocode for MFD (multiple flow direction) algorithm available?

Still stuck with the simulation system, is there any good pseudocode for the multiple flow direction (MFD) algorithm? I read a pseudocode example and implemented it, however the simulation was linear: ...
6
votes
1answer
643 views

Best routing algorithm for this scenario

Trying to work out the most appropriate routing algorithm to use for this situation. Even better if it's available as part of pgrouting or similar.. Here's the requirements: Specified date/time for ...
9
votes
3answers
359 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. ...
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 ...
6
votes
2answers
315 views

Auto Balancing in EarthWork

I am not sure whether this question belongs here. I think it belongs more to Geo-technical, but anyway, I just give it a shot. During earthwork development, earth terrain has to be cut ( if the ...
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 ...
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 ...
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
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 ...