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
1answer
81 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
332 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
325 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
83 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
335 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
262 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 ...
7
votes
2answers
175 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
172 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 ...
5
votes
2answers
1k 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
627 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
309 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 ...
21
votes
1answer
672 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
113 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
82 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 ...
14
votes
3answers
997 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
684 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
1k 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
676 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
143 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
1k 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
222 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
502 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
2k 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
694 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
199 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 ...
13
votes
2answers
2k 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
338 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 ...
9
votes
1answer
428 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
2answers
563 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 ...
29
votes
2answers
3k views

Acquiring ArcGIS-like speed in Postgis

I have been using Postgis 2.0 for 3/4 of a year now and while I really enjoy using it, excessive query processing time has rendered it basically unusable for my use case. I tend to do heavy ...
10
votes
1answer
521 views

How to visualize azimuthal data with uncertainties?

I am trying to make a figure showing azimuthal data with a different range of uncertainties at each point. This oldschool figure from a 1991 paper captures the "bowtie plot" idea that I'm aiming for: ...
5
votes
1answer
537 views

Polar grids in ArcGIS

I am looking automate the creation of a polar grid shapefile (polygon). I am currently creating this in a many-step editing process, starting from a concentric buffer. Here is how I think I should be ...
3
votes
1answer
235 views

how to implement genetic algorithm in ArcGIS?

I want to implement genetic algorithm to find optimum location for placement problem with ArcGIS. Can any body explain it (step by step ) or any resources about that ?
9
votes
4answers
2k views

How to filter wrong GPS points?

I have a database of GPS points. There aren't any tracks, only points. I need to calculate some value for every 100 meters, but sometimes GPS gave a wrong coordinates that lies far from real GPS ...
8
votes
3answers
389 views

Find Duplicate Polygons Algorithm

I have a group of polygons. My objective is to find the duplicate polygons from these group of polygons. Using NetTopologySuite(A c# port of JTS), it is possible to compare two geometires and check ...
4
votes
1answer
270 views

How To Calculate Height of Point B?

I have a survey point data which has coordinates X,Y, Height, Angle(Dip),Azimuth, and Depth(Distance). for Example, point A: Easting: 290694 Northing: 715927 Elevation: 1060 Angle: 65° ...
3
votes
2answers
2k views

How to split a line at point positions?

I am a rooky with QGIS and i am stuck from a basic problems. I have a polyline and i have some points (2) on the polyline. I would like to know if there is a tool or script that i could use to ...
10
votes
1answer
317 views

Are there any intelligent travelling salesmen?

Jokes aside, I have had a routing problem that is almost a travelling salesman problem (TSP): the starting point is defined the end point coincides with the starting point each node has to be ...
14
votes
1answer
159 views

Alternative indexing methods for point set operations

It is common to use a bounding box spatial index to improve performance when working with a large number of features. Where operations are performed against individual geometries with a large number ...
4
votes
1answer
226 views

Given a known batch of mobile-obtained gps data with timestamps, what algorithms can be used to clean it?

I'm working on the backend for an iOS/Android app that collects locations every hour and syncs with the server every three hours. The mobile apps themselves are not under my control and so I can't ...
4
votes
2answers
740 views

How to calculate area of 1 x 1 degree cells in a raster

I have a simple array (not geo-referenced in any way) in Matlab (which is not a language I know a huge amount about...so I can export it to other languages if needed) which has the dimensions 180 x ...
8
votes
1answer
768 views

Given a line on the earth's surface, how do I plot a line perpendicular to it?

Given a line on the earth's surface, how do I plot a line perpendicular to it? Apologies if this is a very simple question. I thought this would be a straightforward task, but it is proving ...
6
votes
2answers
377 views

how to find the point in a country furthest from a boundary

i'm trying to find the point in south africa furthest from the sea or a landward boundary. my method thus far: i obtained a first guess at the centre of the inscribed circle and the three segments ...
4
votes
2answers
5k views

Calculate bearing between two decimal GPS coordinates

I'm building a virtual tour application that uses custom panoramas in conjunction with Google's StreetView service. With StreetView, you can have 1 to n links at each particular location to move to, ...
8
votes
1answer
1k views

Computational most efficient way to convert Cartesian to Geodetic Coordinates

As far as I understand the literature there are several ways to convert a set of geoecentric cartesian coordinates to geodetic coordinates Bowring, 1976 Borkowski, 1989 Lin & Wang, 1995 Toms, ...
6
votes
1answer
394 views

How to calculate the bearing of a building (ArcGIS)

How is it possible to get the main bearing of buildings by floor plan? I want to have a building (by ID) and it's main bearing (e.g. E/90° or W/270°). The idea is to change the polygon-feature class ...
11
votes
4answers
542 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 ...
1
vote
1answer
104 views

Algorithm to find distance of an uneven polygonal road

While working for my summer internship I have got a task to implement an algorithm to find the crosssecting points of two roads or more and then place that cross-section point a number and then find ...
3
votes
2answers
1k views

How to find a point on given line that its distance from another point is given also?

I have this input: (lat1,lon1), (lat2,lon2) - Two coordinates that create the line (lat0, lat0) - Point on this line d - distance I want to find a point (lat, lon), where (lat, lon) is on the ...
2
votes
3answers
275 views

Get the LatLon of middle points of a road segment?

Suppose I have the LatLon of the two end points as well as a small number of middle points of a road segment. What is the best way to calculate the LatLon of a middle point P of the road segment ...