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)

7
votes
2answers
178 views

Generating polygonal blocks using growing lines

We first generate a set of locations (i.e., points(x,y)), randomly. Then we assign for each point a number showing the angle of a line being centred at that point. The criteria for the length of lines ...
7
votes
4answers
423 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 ...
4
votes
1answer
354 views

Which flow routing algorithms does ArcGis support?

Other than standard D8 are there support for multiple flow algorithms like FD8, DEMON, Dinfinity etc?
3
votes
1answer
345 views

Find projection of a point to a line

I have a segment defined by 2 LatLon points(A and B) and a third LatLon point (C). I need an alghorithm, formulae, or some code to find the projection point of C on the segment AB (call this point D) ...
3
votes
0answers
39 views

Clustering driven by an enum/list

Given a set of 2D points ( or vertices if you want ), the values stored for each point are: coordinate on x coordinate on y an enum or a value from a list in general for the sake of this example ...
0
votes
1answer
122 views

Algorithm to merge adjacent raster datasets

I am trying to figure out how to merge adjacent raster datasets. Is there any clear algorithms (may be a pseudo code)?
15
votes
1answer
754 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 ...
0
votes
1answer
1k views

How do services like Google Maps compute the set of instructions for a route?

The problem of computing the driving directions from A to B can be divided into two equally important parts: Finding the best path from A to B. Identifying all the relevant maneuvers along that ...
7
votes
2answers
202 views

Hashing functions for GIS data

I would like to take geometries from a vector dataset and reduce them to a hash. This hash would then be used to verify the integrity of that data and also identify identical geometries. Do any ...
4
votes
1answer
361 views

Splitting large polygons

We need to split large complex polygons into smaller chunks ( Where the area <= x). The tricky bit is that they can only be split where the distance from one side of the polygon to the other is ...
3
votes
1answer
168 views

Curve from a Douglas-Peucker line

When generating a line using the Douglas-Peucker Algorithm the resulting object is a line with steep angles, I would like to "smooth" that line and making it look less "squarish" using curves, like ...
10
votes
2answers
331 views

Algorithm: move a source polyline to a reference polyline (completely or maybe partially)

In our system, there're the requirements that we want to move some source lines (with low precision) to reference lines (with high precision). Following pictures gives the normal use cases. The red ...
3
votes
1answer
109 views

Learning resources for beginning differential topology for a programmer? [closed]

With this question I'm looking for suggestions about how and where to start learning differential topology starting from a good base of linear algebra and geometry, also consider that this know-how is ...
12
votes
8answers
366 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. ...
4
votes
1answer
281 views

Simplification algorithms for 3D topology

My problem is about simplifying a given topology that can be opened ( an usual 3D reconstruction of a given square on a map ), totally closed (like a perfect sphere) or a topology with holes ( a ...
2
votes
0answers
136 views

oil palm stand census algorithm

Anyone have experience in oil palm stand census using tree detection algorithm from satellite images in ArcGIS or QGIS? any references for usable algorithm? What is the accuracy? thanks for help.
2
votes
1answer
321 views

Intersection of convex polygons on a spherical surface

There are a number of algorithms available for the intersection of two convex polygons, but I am interested in an algorithm to find the intersection of two convex polygons on the surface of a sphere, ...
1
vote
0answers
70 views

Allocate places according to distance

I've asked this over on Stack Overflow but thought that someone may have a GI point of view that may help: As an over-simplified example I have a list of events that have a maximum attendance: ...
4
votes
2answers
563 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 ...
5
votes
2answers
626 views

Make Buffer like Offset in Arcpy

I would like to make a buffer for a polyline and get as Output a Polygon with the same angles as the polyline, having not arcs, like in ordinary buffers. i tried the FLAT option in arcpy, but it's ...
3
votes
1answer
86 views

Find gap in / endpoints of linestring

I have a set of features of type linestring. I'm trying to polygonise the linestrings and assumed that they were closed (naive me :) ). Of course some were not closed and I'm trying to locate the gaps ...
4
votes
1answer
355 views

pgrouting: Directed Shortest Path calculation using Dijkstra ignores one-way streets

I think I found an interesting bug in pgrouting. When I use the Dijkstra algorithm (no matter if I use the shortest_path() or dijkstra_sp_delta_directed() method) to calculate the directed shortest ...
4
votes
2answers
356 views

PostGIS algorithm to unite points of two geometries that are within specified radius

I want to find an PostGIS algorithm to unite points of two geometries that are "near" to each other. That is: I want a function, that takes as input two geometries, and returns 1 geometry, that ...
1
vote
0answers
96 views

How can I assign road names from OSM to gis linestrings using open source tools?

Starting with a shapefile of linestrings I want to assign street names to these lines if there is a match with a road/street in OpenStreetMap. There are no exact matches as the linestrings have a ...
2
votes
1answer
414 views

How to Determine to world map size in pixel given this data?

How to Determine the world map size in pixels given this data? Map size of a particular area say, for example: Makati city, Philippines with bounds: Top-Right: 121.0281, 14.56497 Bottom-Left: ...
1
vote
0answers
297 views

Algorithm to place the minimum of rectangles to cover a polygon

I'm trying to cover a polygon with the minimum set of rectangles like explained in the picture below, the used rectangles have the same size a*b (a != b) , the rectangle could be rotated by ...
7
votes
2answers
183 views

Algorithms for optimally locating points

I am trying to compare locations of where several thousand facilities have been actually built to where they would be optimally located to minimize travel times of the population (represented by ...
4
votes
2answers
201 views

Join two lines in one line

I have an array of Lines and I am using it to draw vectors in my map. I want to replace two superposed Lines (or have short distance between them) with one Line. Here is a picture that helps you to ...
6
votes
2answers
1k 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 ...
5
votes
1answer
795 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 a inner point (also known as labelPoint in arcmap) of a (irregular) polygon. I am try to find a solution without the use of ArcGIS module ...
4
votes
2answers
386 views

How to remove redundant points

We basically have points table including vehicle routes.In huge traffic conditions,devices collecting data on route may output redundant points where at any coordinate same points may repeat.We can ...
21
votes
1answer
695 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 ...
2
votes
0answers
127 views

Placement of a fixed-radius circle on a sphere to maximize point containment

There are many papers on the "Circle Placement Problem" in 2D Euclidean space, but I haven't been able to find any papers discussing this problem on the sphere. The problem is: given a set of points ...
2
votes
1answer
85 views

Center-to-Center distance [duplicate]

Possible Duplicate: What is the right solution (and map projection) to compute distances between points located all over the World? I want to know how I could calculate the center-to-center ...
14
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
1answer
813 views

Line intersection with circle on a sphere (globe or earth)

How can I find the intersection point of a line and a circle on a sphere (on earth) Please, if any one knows a good solution help. Thanks in response :)
19
votes
1answer
1k 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 ...
5
votes
2answers
760 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 ...
1
vote
1answer
153 views

How to integrate road networks into Vehicle Routing Problem with Time Windows (VRPTW) algorithms?

I'm trying to determine how routing software integrate road networks. Is there a best-practice (or standard) as to what part of the routing solution road networks are inserted specific to Vehicle ...
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.
4
votes
0answers
240 views

Translate Orientation from Sensor data to Geo location

I am tracking a device that might loose GPS signal then and there. And when the GPS signal is too low, I should use the accelerometer and Gyroscope sensors data to guess which way they should have ...
2
votes
2answers
522 views

Should I implement TSP or Dijkstra?

I was asked to create a shortest path algorithm in java to use with OSRM. I want to create a route between some points (normally more than 3). The first one, will be the starting point and also the ...
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 ...
2
votes
0answers
811 views

Help with Shortest path Algorithm for enormous bus routes database

I am building a bus routes map for Chennai. I use Postgis. In our database we have one table having all the routes along with unique ids given for them. Second table comprises of bus stop names with ...
3
votes
1answer
216 views

Create an optimized point layer derived from a road layer so that the driving distance between each point is x

Consider a classic state-wide or country-wide roadway network. I want to create a point layer, where each point is on the roadway network. This point layer will have each point separated by its ...
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 ...
6
votes
1answer
371 views

Algorithm to fill the gaps adjacent to parcels

I would like to find a way to fill the gaps between the road and its surrounding parcels, like described in picture below: I have different parcels like A and B , i want to fill the gaps by adding ...
9
votes
1answer
470 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 ...
2
votes
2answers
668 views

Algorithm for splitting polygons/polylines into multiple sections at 180° E/W

I have code (in C++) that draws various polygons on a map that uses a cylindrical projection (typically Mercator, sometimes Miller Equidistant if you want to be precise). For simple polygons, curves ...
32
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 ...