Smallest bounding area for an object or group of objects.

learn more… | top users | synonyms

58
votes
15answers
19k views

What are Definition, Algorithms and Practical Solutions for Concave Hull?

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 ...
26
votes
4answers
6k 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) ...
12
votes
5answers
8k views

How do I create a convex hull in ArcGIS Desktop?

I would like to be able to create a convex hull in ArcGIS Desktop 9.x, but I cannot find an appropriate tool. How does one go about creating one? I am interested in answers for all license levels: ...
10
votes
6answers
3k views

How to find the boundary co-ordinates from a given set of co-ordinates

Given a set of coordinates, How do we find the boundary coordinates. <== Figure 1 Given the coordinates in the above set, How can I get the coordinates on the red boundary. Boundary is the polygon ...
9
votes
2answers
404 views

How to build a minimum convex hull crossing the 180 degrees line?

I've been building convex hulls for species that inhabit the Indo-Pacific (~ from 20 to -65 degrees of longitude). The problem I've encountered is that for the species that can be found on both sides ...
7
votes
5answers
2k views

Algorithm to find polygons enclosing points

I'm trying to find an algorithm that can determine the smallest possible polygons to cover a number of points. I know how to get the convex hull around all the points, but say that the points are ...
6
votes
2answers
3k views

Converting point sets to polygon boundaries

I'm trying to convert sets of points to their respective polygon boundaries. I think this is something like a Voronoi diagram or Convex Hull, but not quite. I'm sure there's a technical term for it, ...
5
votes
2answers
402 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 ...
5
votes
1answer
403 views

create convex hull polygons / cluster for sets of N points in a point dataset

I have 50k points in a feature class which I need to build convex hull or polygon for each set of 50 points that are nearby each other. I guess the question is very similar to create census areas for ...
4
votes
2answers
457 views

Invalid Geometry Error after ST_ConvexHull

I've a Postgis table of around 80,000 points and want to be able to populate a second table summarizing the data with convex hulls based on points with a common attribute. For example, the data ...
4
votes
1answer
2k views

Best way to get Convex Hull/Boundary of millions of points

I've been trying to do some point analysis on some xyz data, I'm at the point where I've decided it is best to produce a boundary of my xyz files and put this with the metadata for each survey. Now ...
4
votes
1answer
119 views

How to grow several concave hulls until they completely fill a larger area without overlap?

This is my problem: I have a very large point layer with polling station locations across one country; each point belongs to a specific constituency (900k points, 4k constituencies). I wish to use ...
3
votes
1answer
147 views

Convex Hull in SAGA Gis

How does one go about creating a convex hull from a set of points in SAGA GIS? I read that this is possible in QGIS, but I prefer SAGA and would like to see if it is possible. Furthermore, if it is ...
2
votes
4answers
114 views

Best way to 'join' polygons

I'm looking for the best ways to 'group' a budge of block polygons in a new polygon that should be the town. My block layer is something like this: Or zoomed: And I'm looking to get something ...
2
votes
2answers
147 views

Is there a way to visualize a convexhull in qgis 1.8 lisboa?

There is no way to visualize a convexhull in qgis 1.8 lisboa? I have tried following views in Postgis 1.5 I was told to use an id column to publish it in Qgis. If you not use an id column, u cannot ...
2
votes
1answer
34 views

R - Occasional error when using alphahull package areaahull() function

I've recently started using the fantastic alphahull R package, which works beautifully most of the time but occasionally I am getting the following error when running the areaahull() function: Error ...
2
votes
2answers
300 views

Quick way to make a convex hull

I am using Python and ArcGIS 10.1. Is there a function or very quick way to extract points out of point feature class into an array without looping through a search cursor (as I have millions of ...
2
votes
2answers
255 views

Is it possible to get the points used for the convex hull in osm2po?

I have a non-convex hull algorithm that I want to use for an app. With OSM2PO, it's possible to get a convexHull, but is there a way to get the points before the hull is constructed? More, it would ...
2
votes
0answers
52 views

How to detect turns of a route?

I'm doing a Python simulation of a vehicle, driving along a specified path. I generate dummy GPS readings, that fetch the current position of the vehicle, with some randomized error added. After a ...
2
votes
0answers
251 views

convex hull over selected features

I am trying to achieve a convex hull over a feature Set returned by a query. But have been facing the error below which i am not able to figure out In order to debug to see how the convex hull works ...
1
vote
2answers
130 views

Is there a Cluster convex hull implementation in OpenLayers?

In this leaflet example. When hovered over a cluster marker, it shows the bounding area of the clustered features which is known as convex hull. Is there a way to reproduce it with OpenLayers?
1
vote
1answer
32 views

Postgis create polygon extent/convex hull from spatial table

Please help, I have a polygon layer representing building footprints. I want to create new view in postgis that will contain rectangle representing bounding box and also another view that will have ...
1
vote
0answers
188 views

Convex Hull issue in QGIS 1.8

When creating convex hulls based on input field in qgis 1.8, there seems to be always one less convex hull created for the unique values in the input field. For example; I have a point vector file, ...
1
vote
0answers
191 views

How can I use Convex Hull to select an area with a space from the points?

This refer to this post : Read Here My goal is to select an area covering some points, but maintaining some space from points of border, like in the follow picture : I think ST_Convexhull will do ...