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)

3
votes
3answers
1k views

Efficient algorithms to split and join lines?

Referring to the Figure below: How to efficiently join segments into lines? How to efficiently break lines into segments? The above will be applied million times.
1
vote
0answers
109 views

An algorithm for locating candidate labelling boxes within a polygon

Has anyone implemented this algorithm In PostGIS? Quoting from the paper: Vector-based geographic information systems usually require annotation, such as a polygon number or attribute data, in a ...
5
votes
2answers
573 views

inner convex-hulls in a set of 2D points

A set of 2D Points are scattered randomly (i.e., no specified pattern), we are interested in finding all inner-convex-hulls (ICH) in an order of largest in area to a minimum until the entire study ...
4
votes
0answers
261 views

GPS data based track/trip calculation algorithm available?

Currently I'm receiving position data of moving assets every 90 or 120 seconds (depending on the asset). What I'd like to achieve now is to detect standstill and movement phases (tracks/trips) on the ...
0
votes
2answers
509 views

How to split a linestring every 1000 points in postgis

To assume compatibility with my survey software, I would like to lighten geometries of my linestrings by cutting them every 1000 points without creating or interpolating points. I transformed a ...
14
votes
3answers
3k views

How to find the maximum-area-rectangle inside a convex polygon?

In this post we are looking for algorithms / ideas on how to find the maximum-area-rectangle inside a convex polygon. In the following figure, numbers are the areas of the fitted rectangles. As shown ...
7
votes
2answers
208 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
771 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
506 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
569 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
40 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
141 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
1k 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
2k 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
295 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
487 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
198 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
365 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
112 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 ...
13
votes
8answers
453 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
473 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
182 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
499 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
71 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
948 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
874 views

Making 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
2answers
119 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
493 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
418 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
105 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
694 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: ...
8
votes
2answers
219 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
279 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 ...
8
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 ...
6
votes
1answer
2k 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
593 views

How to remove redundant points using Open Source GIS (preferably)?

We 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 easily ...
21
votes
1answer
737 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
158 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
88 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 ...
15
votes
3answers
2k 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
1k 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
2k 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
959 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
167 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
318 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
712 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 ...
6
votes
4answers
3k 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
977 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
283 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 ...