A mathematical procedure used to solve problems with a series of steps. Algorithms are usually encoded as a sequence of computer commands.
2
votes
1answer
53 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
87 views
What are efficient algorithms to join segments and to split a line into segments?
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.
4
votes
2answers
95 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 ...
1
vote
0answers
32 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
115 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 ...
2
votes
1answer
80 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) ...
14
votes
4answers
1k 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 ...
6
votes
2answers
683 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 routepoints that are impossible because it would require acceleration that the vehicle can not achieve. Are there good ...
1
vote
1answer
422 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
286 views
Breakline detection algorithms for LIDAR dataset
I'm searching for algorithms or open source tools I could use to detect breaklines from a LIDAR dataset; more specifically, from the terrain points of the dataset. At the moment the only thing I've ...
3
votes
0answers
43 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
96 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 ...
7
votes
2answers
105 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
90 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 ...
6
votes
1answer
232 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 :(
5
votes
0answers
81 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 ...
15
votes
3answers
5k 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
...
4
votes
1answer
58 views
Which flow routing algorithms does ArcGis support?
Other than standard D8 are there support for multiple flow algorithms like FD8, DEMON, Dinfinity etc?
5
votes
4answers
998 views
explode overlapping polygons to new non-overlapping features
Given multiple polygons that overlap in multiple ways, I would like to export from this feature all polygons that don't overlap with others iteratively. The product would be a number of features with ...
4
votes
1answer
91 views
Learning resources for beginning differential topology for a programmer?
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 ...
6
votes
1answer
337 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
29 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
57 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
310 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 ...
10
votes
4answers
364 views
Dikes extraction from DEM
I do have DEM of 1x1 meter and original LiDAR point cloud in .las, that DEM is made of. I need to extract river dikes (highest points of the dikes) to vector feature (point, polyline). Any idea for ...
0
votes
1answer
87 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
93 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 ...
10
votes
2answers
235 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 ...
4
votes
1answer
77 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
100 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 ...
4
votes
1answer
196 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 ...
3
votes
1answer
116 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 ...
8
votes
1answer
207 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
0answers
64 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.
51
votes
12answers
12k views
Concave Hull: Definition, Algorithms and Practical Solutions
Convex Hull
A convex hull of a shape is defined as:
In mathematics, the convex hull or convex envelope for a set of points X in a real vector space V is the minimal convex set containing X ...
2
votes
1answer
89 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, ...
31
votes
3answers
4k 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 ...
1
vote
0answers
55 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:
...
3
votes
1answer
215 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 ...
13
votes
4answers
798 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 ...
4
votes
1answer
99 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 ...
4
votes
3answers
2k views
Parameters for ED50 -> ETRS89/WGS84 seven-parameter transformation which are good for Denmark?
I am looking for parameters for a seven-parameter transformation (Rx, Ry, Rz, Tx, Ty, Tz, s) from ED50 UTM (zone 32U) to ETRS89 and/or WGS84.
The best match I could find is here: ...
10
votes
4answers
2k 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 ...
5
votes
2answers
144 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 ...
12
votes
3answers
957 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 ...
2
votes
0answers
30 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
2answers
150 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 ...
6
votes
3answers
863 views
tiny JS discretization library for choropleth representation
I'd like to know if there is somewhere a tiny stat/discretization js library ready to use?
Actually I know the existence of jStat (which I may explore a little bit more), and I know mapfish has a ...
10
votes
2answers
581 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 ...
19
votes
3answers
2k 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) ...
