A mathematical procedure used to solve problems with a series of steps. Algorithms are usually encoded as a sequence of computer commands.
3
votes
0answers
32 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
82 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 ...
5
votes
0answers
69 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
97 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
81 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
53 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
68 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
26 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
49 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
287 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
79 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
89 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
71 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
88 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
233 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
90 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 ...
3
votes
1answer
111 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
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.
2
votes
1answer
82 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
54 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
94 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
130 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
28 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
185 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
141 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
37 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
103 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
127 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
109 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
81 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
515 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
196 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
...
0
votes
0answers
47 views
Finding the “best” sections of a waypoint track
Sports tracker applications usually record a timestamp and a location in regular intervals in order to store the entire track. Analytical applications then allow to find certain statistics, such as ...
4
votes
2answers
111 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 ...
15
votes
0answers
351 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
66 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
70 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 ...
11
votes
3answers
460 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
266 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 :)
11
votes
0answers
482 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
399 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
105 views
How do you integrate road networks into 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 VRPTW?
...
4
votes
6answers
543 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
118 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
352 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
946 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 ...
2
votes
0answers
373 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 ...
2
votes
1answer
142 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 ...
11
votes
2answers
755 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
186 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 ...
