Questions tagged [convex-hull]

Smallest bounding area for an object or group of objects with no concave angles.

Filter by
Sorted by
Tagged with
116
votes
13answers
46k views

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

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 (...
68
votes
7answers
68k views

Finding minimum-area-rectangle for given points?

As you see in the figure, the question is: How to find the minimum-area-rectangle (MAR) fitted on the given points? and a supporting question is: Is there any analytical solution for the ...
27
votes
2answers
33k 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, ...
18
votes
6answers
26k views

Finding boundary co-ordinates from given set of point 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 ...
14
votes
8answers
20k views

Creating 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: ...
13
votes
2answers
1k 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 ...
8
votes
5answers
4k 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 ...
7
votes
3answers
2k 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 ...
6
votes
1answer
464 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 ...
5
votes
2answers
795 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 ...
5
votes
1answer
3k views

Is there a QGIS equivalent to ArcGIS' Convex Hull and Circle under the Minimum Bounding Geometry tool?

I have the opportunity to run ArcGIS and QGIS side by side for a few months and was looking to see what comparisons there are. So I'm interested to know if there is a similar tool on QGIS?
5
votes
1answer
1k views

Growing several concave hulls until they completely fill larger area without overlap using QGIS? [closed]

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 ...
5
votes
1answer
351 views

Packing polygons without intersection and empty places [closed]

How can I pack polygons without empty places and intersections? Please tell me everything that might help me (API, algorithms, etc.) I'm using: USPS API to get carrier routes. dbscan.js to ...
5
votes
1answer
1k 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
1answer
466 views

Clustering (ConvexHull) data based on distance

First I would like to mention that I am not an expert with PostGreSQL so my question may seem dumb, but here it goes: I have a database with over 800 000 points associated to a geometry (EPSG 2950) ...
4
votes
1answer
5k 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
573 views

Convex hull with n points using computational geometry libraries

I've been searching for a function to make the Convex Hull of a Spatial Object with N points, to make an spatial approximation with n-corners, as shown in the article "Comparison of Approximations of ...
4
votes
1answer
330 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 ...
3
votes
1answer
545 views

Convex Hull operation not specific enough

I have yield data as point values, and I simply want to create the boundary around this layer. I have used the Minimum Bounding Geometry tool and selected Convex Hull to do this, however it maintains ...
3
votes
1answer
156 views

qgis: generalisation & covex - how to? what plugin?

I'm looking for a way to generalize and simlify polygon to remove "internal spikes" as ilustrated below. The violet in input and green expected poligon.
3
votes
1answer
278 views

PostGIS ST_ConvexHull for cube corners not as expected

I'm new to PostGIS and am wondering whether ST_ConvexHull will be of use in a particular work problem. Trying out some simple cases to make sure I understand what it's doing, I didn't expect this: =&...
3
votes
1answer
115 views

Extracting points bordering shape extent

I'm using ArcGIS 9.31. I have a set of points as elevation and in order to get a soft clip area for the TIN, I would like to extract only all the points bordering the extent of this shape, or to get ...
3
votes
1answer
285 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
197 views

'Joining' polygons using PostGIS?

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 like ...
2
votes
5answers
2k views

Creating Minimum Convex Polygon - Home Range from Points in QGIS

I just downloaded QGIS (3.0.2) and trying to create minimum convex polygon around points using minimum bounding geometry (convex hull). The videos and help documents I see online appear to be from ...
2
votes
1answer
3k views

Creating perimeter around multiple polygons using ArcGIS for Desktop?

This may have a simple answer that I'm just missing. I have multiple polygons in one shapefile I would like to make a larger Polygon around all of them. Is there a tool that is able to do this? ...
2
votes
3answers
780 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?
2
votes
1answer
63 views

Knowing/converting AREA, PERIMETER units in QGIS?

I use Convexhull tool in QGIS and there are result value : AREA = 0.0017494390 PERIMETER = 0.1725495172 I thought the result was strange. So, I took a rough estimate of the points through the ...
2
votes
1answer
1k views

Creating polygons layer from point layer with conveks buffer

I have a point layer of >750000 points representing dwellings with district heating. Now, I want to create polygons for every n of points with a distance of n meters to the next point. I have a ...
2
votes
2answers
373 views

Visualizing convex hull in QGIS?

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
264 views

Convex hull area: what are the output units?

I have what I hope is a simple question. I'm doing convex hull calculations. What I have is area(convex_hull($geometry)). I get a number and that's all well and fine. Since I need to get a ratio of ...
2
votes
1answer
374 views

DBScan with Convexhull

I am new to GIS, I am using PostGIS(2.3). I have two problems I am not clear with Problem-1: I have list of locations(longitude, latitude, 4326), what is best/correct projection to use while ...
2
votes
1answer
442 views

Computing convex hull of table using PostGIS Query in MapServer?

I am basically trying to compute the convex hull of a table in postgresql but I can't seem to get the query correct. My ultimate goal is to use this query as a polygon layer. The columns in the table ...
2
votes
1answer
150 views

Make convex hulls opaque or transparent

I have a series of convex hulls that I want to overlay but I want to be able to see all of them at the same time. How do I do this so? I'm guessing making them slightly transparent will do the trick
2
votes
2answers
880 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
671 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
41 views

Polygons hull QGIS [duplicate]

I'm currently working with old french cadastre on QGIS, I've vectorised it and now I want to tile it. I've georeferenced it, but it's not sufficient for a great result. To improve the result, I would ...
2
votes
0answers
122 views

Adapting a ConvexHull fonction to a ConcaveHull one

I have a database with over 150 000 points in a EPSG 2950 projection. As I wanted to cluster those points in polygons, I used a ConvexHull fonction. The goal was to create clusters where I would find ...
1
vote
2answers
155 views

Creating a large amount of convex polygons using existing coordinates

I downloaded the georeferenced event dataset (top left) from this website: http://ucdp.uu.se/downloads/ It consists of coordinates of violent conflicts which differ in time and space. My aim is to ...
1
vote
1answer
379 views

Defining convex-hull of (clouds of) points using R? [closed]

I have multiple (clouds of) points, and would like to take the outer envelope of these points. This will allow me to polygonize my points. Using the convex-hull would help me, but in some cases, my ...
1
vote
1answer
192 views

How do I draw the shortest imaginary boundary around a point dataset?

I would like to produce a range map for my species (smooth snakes in the south of England) using the IUCN-defined 'extent of occurrence' (EOO) as my metric. EOO is defined as 'the area contained ...
1
vote
1answer
383 views

QGIS generate convex hull for common attributes that have many values

If I have a points file where the points share common attributes, what's the best way to draw a convex hull around those common points using QGIS?
1
vote
2answers
211 views

Summarizing point data to multi point data and creating convex hull in R

I have latitude and longitude information like 26.847905 73.9575005 for about 800 points, I need to trim these lat/lon information to say 3 decimal places. I used the following syntax in R # ...
1
vote
1answer
53 views

PostGIS- convert points to polygon based on multiple shared attributes

I have a PostgreSQL PostGIS point table (not multi-points). I want to convert the points to polygons (using convex-hull?) grouping the points by shared attributes from 2 columns. In this example, '...
1
vote
2answers
89 views

Converting trajectory to outer edges polygon

Using PostGIS, I'm trying to solve the following problem: I have trajectory data (coordinates from API query), like on this image: and want to convert it into polygon, having only outer edges:
1
vote
1answer
296 views

How to create a convex hull in R based on the larger of two shapefiles' extents?

In R, I have two shapefiles: Shapefile A represents roads (polylines), Shapefile B some location (points). I want to plot the convex hull enclosing the study region, and it has to be set to the larger ...
1
vote
2answers
175 views

Create convex hull over DEM

I am trying to virtually put a blanket over a DEM so to say, in more technical terms, a convex hull over 3d point data. To get some insight in what I'm doing exactly, I will first explain my entire ...
1
vote
1answer
104 views

Select tracks or part of tracks that are within a polygon?

I am studying a monkey species, I have GPS observation points which I used to make a convex polygon (Hull). I also have all of the survey trails imported and displayed in QGIS (See screen shot for ...
1
vote
2answers
113 views

OpenJump LoCoH Analysis Output?

I really need some help! I am doing a k-LoCoH analysis in OpenJump. The analysis is working, but I'm having trouble understanding the output. There is a "density" column in the output, and I'm not ...
1
vote
1answer
1k 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 ...