22

Given a set of coordinates, How do we find the boundary coordinates.
set of coordinates <== Figure 1
Given the coordinates in the above set, How can I get the coordinates on the red boundary. Boundary is the polygon which is formed by the input coordinates for vertices, in such a way that it maximizes the area.

I am working on an app which searches properties within 'x' miles of a city. What I have is:

  1. Coordinates of all the properties.
  2. A set of coordinates for each city (I have one coordinate for each zip. And since most cities have more than one zip, Every city has a set of coordinates)

The reason I am asking for the maximum area is so that I don't come up with a polygon like the one below:

crooked polygon <== Figure 2

What I need is the algorithm to come up with the set of coordinates for the boundary. An algorithm which will allow me to come up with boundary coordinates for Figure 1.

PolyGeo
  • 65,136
  • 29
  • 109
  • 338
Khaja Minhajuddin
  • 323
  • 1
  • 2
  • 7
  • 1
    possible duplicate of Concave Hull: Definition, Algorithms and Practical Solutions – Ian Turton Jan 24 '11 at 16:41
  • 4
    No, not duplicate, this is convex hull, not concave – Nicklas Avén Jan 24 '11 at 17:24
  • 1
    Are you looking for code, theoretical references, or solutions in specific existing software environments? – WolfOdrade Jan 24 '11 at 17:29
  • What software / platform are you wiling to use for that? – radek Jan 24 '11 at 18:18
  • 1
    @Khaja No, you don't want to maximize the area, you want to minimize it among all convex polygons containing the points. (The only way to maximize the area is to use the entire world as the containing polygon.) – whuber Jan 24 '11 at 19:15
  • Re: the votes to close. This question would duplicate http://gis.stackexchange.com/questions/8/how-do-i-create-a-convex-hull-in-arcgis only if the desired solution is in ArcGIS. Otherwise there is no valid reason to close it. – whuber Jan 24 '11 at 19:17
  • The question linked to by @iant has a lot of pointers, Thanks, I'll look into it. – Khaja Minhajuddin Jan 24 '11 at 19:44
  • @Khaja Re the edit (Figure 2): Convexity is the key property here, not area. However, it is not clear what either of these has to do with proximity, which is what seems to be your ultimate interest. Are you looking for a data structure that makes proximity searches more efficient? – whuber Jan 24 '11 at 19:54
  • @radek This is being used in an asp.net mvc web application, and I am planning to do this computation on our database (SQL Server 2008 R2) – Khaja Minhajuddin Jan 25 '11 at 05:44
  • @WolfOdrade I wanted an algorithm, but it seems like this is a common problem and there are lots of pre-built functions in SQL Server to help with this. This is one => http://www.dotnetsolutions.co.uk/blog/archive/2010/02/08/creating-convex-hull-in-sql-server-2008/ – Khaja Minhajuddin Jan 25 '11 at 05:46
  • 1
    @whuber Yeah, now I see what you mean, I want a convex polygon with the minimal area. My ultimate goal is to do a proximity search. The way we want our proximity search to work is: In a given city (convex hull), if we search for homes (each home has a coordinate) within "x" miles, it should give me all the homes which are either inside the convex hull or are at an orthogonal distance of less than "x" miles – Khaja Minhajuddin Jan 25 '11 at 05:52

6 Answers6

23

There are many algorithms to solve this problem (Wikipedia "Convex_hull_algorithms"):

  • Gift wrapping aka Jarvis march — O(nh): One of the simplest algorithms. It has O(nh) time complexity, where n is the number of points in the set, and h is the number of points in the hull. In the worst case the complexity is O(n2).
  • Graham scan — O(n log n): Slightly more sophisticated, but much more efficient algorithm. If the points are already sorted by one of the coordinates or by the angle to a fixed vector, then the algorithm takes O(n) time. [pseudo code]
  • QuickHull: Like the quicksort algorithm, it has the expected time complexity of O(n log n), but may degenerate to O(nh) = O(n2) in the worst case. [illustrated description]
  • Divide and conquer — O(n log n): This algorithm is also applicable to the three dimensional case.
  • Monotone chain — O(n log n): A variant of Graham scan which sorts the points lexicographically by their coordinates. When the input is already sorted, the algorithm takes O(n) time.
  • Incremental convex hull algorithm — O(n log n)
  • Marriage-before-conquest — O(n log h): Optimal output-sensitive algorithm.
  • Chan's algorithm — O(n log h): Simpler optimal output-sensitive algorithm .
Glorfindel
  • 1,096
  • 2
  • 9
  • 14
underdark
  • 84,148
  • 21
  • 231
  • 413
8

  1. Convex Hull in GRASS GIS

  2. Convex Hull in Qgis Vector Tools (very easy to use):

enter image description here

Glorfindel
  • 1,096
  • 2
  • 9
  • 14
Pablo
  • 9,827
  • 6
  • 43
  • 73
3

What you want is the Convex hull. In PostGIS there is a function (actually GEOS) that gives you the Convex hull, ST_ConvexHull(geometry).

At wikipedia there is a lot of info about concave hulls.

Brad Koch
  • 475
  • 5
  • 23
Nicklas Avén
  • 13,241
  • 1
  • 39
  • 48
3

Hawth's Tools for ArcGIS has this functionality. Plus a script for ArcInfo 10.

There is also convex hull tool in QuantumGIS via ftools plugin.

radek
  • 10,579
  • 12
  • 86
  • 121
1

If you want an algorithm to do this (rather than packages that can do it) then I'd think you would need to triangulate the data; or basically define a line from each point to every other point. Then, starting at (say) the point with the highest Y value, trace a route around the outside following the connected line with the smallest exterior angle/bearing.

You would be able to speed up the tracing by throwing away intersecting lines first. The external boundary won't have intersections.

btw - FME will do this too with the ConvexHullAccumulator or ConvexHullReplacer transformers!

Mark Ireland
  • 13,147
  • 3
  • 33
  • 67
1

If you're interested in looking at an existing algorithm implemented in code, NetTopologySuite has an algorithm to do this

See ConvexHull.cs

Incidentally NTS and a bunch of other libraries are wrapped up in a cool project called DotSpatial, found here

detroit_hc
  • 807
  • 1
  • 9
  • 20
WolfOdrade
  • 2,748
  • 21
  • 24