Stack Overflow
Stack Overflow

Questions tagged [concave-hull]

56 questions
67
votes
10 answers

Is there an efficient algorithm to generate a 2D concave hull?

Having a set of (2D) points from a GIS file (a city map), I need to generate the polygon that defines the 'contour' for that map (its boundary). Its input parameters would be the points set and a 'maximum edge length'. It would then output the…
Fabio Ceconello
  • 15,819
  • 5
  • 38
  • 51
16
votes
2 answers

Python Concave Hull Polygon of a set of lines

I'm looking for a python implementation for the Concave Hull problem. My problem is a bit different since I don't have a set of points, but a set of lines, where the result Concave-Hull will roughly bound along the lines (as in the left drawing). I…
user972014
  • 3,296
  • 6
  • 49
  • 89
14
votes
6 answers

Boundary enclosing a given set of points

I am having a bit of a problem with an algorithm that I am currently using. I wanted it to make a boundary. Here is an example of the current behavior: Here is an MSPaint example of wanted behavior: Current code of Convex Hull in…
Mário Gabriel
  • 367
  • 1
  • 2
  • 13
11
votes
4 answers

Estimating an area of an image generated by a set of points (Alpha shapes??)

I have a set of points in an example ASCII file showing a 2D image. I would like to estimate the total area that these points are filling. There are some places inside this plane that are not filled by any point because these regions have been…
Dalek
  • 4,168
  • 11
  • 48
  • 100
9
votes
2 answers

Alpha shapes in 3D

Is there an "alpha shape" function in 3 dimensions in python, other than the CGAL python bindings? Alternatively, is there a way to extend the example below into 3D? 2D example: draw a smooth polygon around data points in a scatter plot, in…
skytaker
  • 4,159
  • 1
  • 21
  • 31
9
votes
4 answers

Translating concave hull algorithm to c#

So I am trying to translate the algorith found here for concave hulls: http://repositorium.sdum.uminho.pt/bitstream/1822/6429/1/ConcaveHull_ACM_MYS.pdf (Page 65) Ive read through the entire thing but I cant figure out how to implement sortByAngle…
FabianCook
  • 20,269
  • 16
  • 67
  • 115
5
votes
1 answer

Determine which points lay outside an irregularly-shaped data footprint in R?

I have a series of points in an area whose 'footprint' shape is highly irregular: I'd like to determine all of the coordinates within the footprint's vertices. The end goal is to determine which data points lay outside this footprint. Does anyone…
theforestecologist
  • 4,667
  • 5
  • 54
  • 91
4
votes
1 answer

MATLAB: Calculate volume of concave polyhedron from set of scattered 3D points

I have 20 to 30 randomly generated 3D points as vertices from which a polyhedron is defined. I have tried using DelaunayTri(points) to enumerate the facets and use the determinant of the cross product to calculate and sum the tetrahedral volumes,…
Slaiyer
  • 444
  • 8
  • 22
3
votes
1 answer

Find points that lie in a concave hull of a point cloud

in this thread a method is suggested for masking out point that lie in a convex hull for example: x = np.array([0,1,2,3,4,4, 4, 6, 6, 5, 5, 1]) y = np.array([0,1,2,3,4,3, 3.5, 3, 2, 0, 3, 0]) xx = np.linspace(np.min(x)-1, np.max(x)+1, 40) yy =…
Alejandro
  • 879
  • 11
  • 27
3
votes
1 answer

2D alpha shape / concave hull problem in Python

I have a large set of 2D points that I've downsampled into a 44x2 numpy array (array defined later). I am trying to find the bounding shape of those points which are effectively a concave hull. In the 2nd image I've manually marked an approximate…
shanryan
  • 33
  • 1
  • 6
3
votes
0 answers

Alpha Shapes in 3D - Follow Up

Problem I am trying to implement Edelsbrunner's Algorithm for the alpha shape of a 3D point cloud in python as presented in this SO post. However, I'm having trouble plotting results. Half my sphere looks good, and the other half garbled. I suspect…
adam.hendry
  • 4,458
  • 5
  • 24
  • 51
3
votes
1 answer

Concave hull algorithm from pseudocode to C#

I am trying to convert the algorithm as described here (page 12) from pseudocode into working C# code. The algorithm describes how a convex hull is 'transformed' into a concave hull by breaking up edges that are considered too long into smaller…
WalterB
  • 110
  • 2
  • 12
3
votes
1 answer

OpenCV - Concave hull

I am looking for an OpenCV implementation of a function to find the concave hull of a set of points (as for the convexHull function). Does anyone know of it? Here is an explanation: http://ubicomp.algoritmi.uminho.pt/local/concavehull.html Thank you…
Alberto Malagoli
  • 1,173
  • 10
  • 14
2
votes
0 answers

Algorithm to create minimal bounding-box composition of point cloud

I have a set of 2D points. I want to find a set of (possibly overlapping and arbitrarily oriented) bounding-boxes for subsets of these points such that each point lies within at least one box, each box contains at least k points and such that the…
matthias_buehlmann
  • 4,641
  • 6
  • 34
  • 76
2
votes
2 answers

Determine if a point is interior or exterior to a 3D Alpha-shapes surface in CGAL

I am using CGAL to create the concave hull of a set of 3D points using ex_alpha_shapes_3 example. Next, I would like to find out whether a point query in space is located within the surface created by the triangular concave hull faces (the output of…
Vahid
  • 125
  • 12
1
2 3 4