# Tagged Questions

A mathematical procedure used to solve problems with a series of steps. Algorithms are usually encoded as a sequence of computer commands.

231 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 ...
1k 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 ...
661 views

### Which flow routing algorithms does ArcGis support?

Other than standard D8 are there support for multiple flow algorithms like FD8, DEMON, Dinfinity etc?
969 views

### Finding projection of point to 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) ...
43 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 ...
161 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)?
2k 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 ...
3k 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 ...
385 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 ...
633 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 <...
216 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 ...
394 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 ...
116 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 ...
554 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. ...
718 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 ...
242 views

### Oil palm stand census algorithm? [closed]

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?
733 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, ...
76 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: ...
1k 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 ...
1k 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 ...
154 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 ...
645 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 ...
478 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 ...
134 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 ...
1k 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: 121....
246 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 ...
385 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 ...
3k 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 ...
3k 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 ...
775 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 ...
815 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 ...
191 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 ...
98 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 ...
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 ...
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 :)
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 ...
1k 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 ...
188 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 ...
3k 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.
406 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 ...
899 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 ...
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 ...
1k 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 ...
347 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 ...
4k 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 ...
574 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 ...
798 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 ...
1k 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 ...