A mathematical procedure used to solve problems with a series of steps. Algorithms are usually encoded as a sequence of computer commands.
3
votes
1answer
26 views
Placename matching algorithms and services for geocoding
Are there any placename-specific matching algorithms, routines or services available? By placename specific I mean not just a simple string-difference match, or soundex/metaphone, but something that ...
0
votes
1answer
35 views
How to find the most east or west longitude around the date line
I've got a python script that is comparing extents of rasters in various projections.
Generally it works, but sometimes, especially when the rasters are global in extent or cross the dateline it ...
1
vote
0answers
44 views
Divide polygon evenly based on lines and intersection points
I have this purple polygon illustrated in the figure below. I would like to split the polygon so that each line segment (green) split the polygon evenly with the surrounding line segments. A line ...
4
votes
1answer
59 views
meeting point minimizing travel distance for participants?
The problem is to find the point minimizing the travel distance for around 100 persons in different regions who want to meet in the same place. Travel is by car not by plane.
Assuming that I get ...
0
votes
0answers
41 views
How to create polygons over a specific number of points
I came upon this question in a non GIS-related task, but it really interests me how to do a similar thing in GIS-systems.
Problem:
Imagine a random point pattern (see image below)
Now what i want ...
0
votes
1answer
36 views
How do I choose parameters for the Huff model that best fit my data?
I'm using the Huff model for some analysis I'm doing. For those not aware, the Huff model is a probabilistic model for retail trade area analysis.
H_ij is the probability that a person at location ...
1
vote
0answers
31 views
Kalmanfilter GNSS IMU
I want to make an uncoupled Kalman filter. The input data are GPS and the output of my strapdown Algorithm from the IMU. The Strapdown Algorithm is used to calculate the actual position and velocity ...
6
votes
1answer
82 views
Open source implementation of “feature density” algorithm
I'm working on a dataset of house searches - 1 polygon for each area in which people want to find a house from an online search tool.
This produces many overlapping polygons. It would be great to ...
1
vote
2answers
87 views
How to convert self intersecting polygon to multipolygon?
Working with the union and polygonize methods in GDAL/OGR, I often end up with self intersecting polygons. The case is one polygon which essentially consists of two polygons:
In the above example, ...
1
vote
1answer
52 views
Algorithm to find the polygon ID where a point belongs to
I am wondering what is the simplest way to perform a look up of polygon Id based on the point location.
Input: a point with coordinates, a table of polygons
Output: the polygon Id where a point is ...
1
vote
0answers
32 views
Indexing GIS data associated with user with timestamp
I have data for each user in this format user1:(timestamp,lattitude,longitude) user1:(timestamp1,lattitude1,longitude1).....
Here the 1 at the end of timestamp/lat/long is to specify a different ...
0
votes
1answer
26 views
How to contribute for pgrouting.org [closed]
I wanna to contribute for algorithms, that's why i chose pgrouting can anyone help me out and suggest me more organisations to which i can contribute.
Thnks.
1
vote
0answers
37 views
Algorithm to match trajectory [closed]
I've data in the format (lattitude,longitude,timestamp). What I want to do is between timestamp1 and timestamp2 I want to find out which people might have taken the same routes. Is there some kind of ...
2
votes
1answer
94 views
How does QGIS calculate the area of a polygon?
I am working on a project that requires the calculation of the area of a polygon by two different methods. I need to know what algorithm QGIS uses to calculate the area of a polygon. I know ESRI ...
2
votes
3answers
158 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
42 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
180 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 ...
3
votes
0answers
107 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
152 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 ...
6
votes
0answers
127 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
118 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 ...
6
votes
4answers
109 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
83 views
Which flow routing algorithms does ArcGis support?
Other than standard D8 are there support for multiple flow algorithms like FD8, DEMON, Dinfinity etc?
2
votes
1answer
115 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
31 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
64 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)?
14
votes
1answer
414 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
136 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
97 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
102 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
111 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
240 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
93 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
7answers
204 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.
...
3
votes
1answer
149 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
77 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
116 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
61 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
1answer
122 views
Method for finding 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
176 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 ...
2
votes
0answers
34 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
228 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
182 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
47 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
138 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
170 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 ...
6
votes
2answers
124 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
104 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 ...
4
votes
2answers
645 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
256 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
...
