# Tagged Questions

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

278 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 ...
939 views

### How to speed up batch watershed delineation?

I have a large number of pour points - approximately 250,000 for which I want to delineate the upstream watershed area using ArcHydro's "Batch Watershed Delineation". Given that it takes roughly 4-5 ...
253 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 ...
273 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 ...
314 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 ...
2k views

### Selecting only canals that are connected to reservoirs?

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 ...
3k 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 ...
4k 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 ...
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 ...
495 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 ...
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 ...
2k 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 ...
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 ...
550 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 ...
2k 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 ...
252 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. ...
5k 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,...
4k 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 ...
2k 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 ...
181 views

### Understanding location storage and query algorithms?

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 ...
9k 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 ...
946 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 ...
773 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 ...
179 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 ...
4k 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 ...
7k 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 ...
8k 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 = ...
2k 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 ...
828 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: ...
697 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 ...
389 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.              &...
485 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 ...
366 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 ...
1k 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 ...
3k 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 ...
9k 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 ...
41k 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 ...
1k 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?
15k 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 ...
5k 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. ...
722 views

### How to split polygons without ArcView? [closed]

I'm trying to split polygons into equal areas. While fishnet sort of works; the areas I'm trying to split don't touch; they're national parks. Fishnet spans the whole area, not just the polygons in ...
7k 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 ...
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 ...
4k views

### Create centreline from a polygon

I am working on a project to create a centerline from a polygon automatically. The user select a polygon and click a button, the centerline will create for him. I have tried the build-in function “...
7k views

### Dividing 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 ...
4k 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 ...
22k 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-...
6k 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 ...
2k 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 ...