Based on/using delaunator as basis for delaunay triangulations, this module uses the algorithm proposed in this paper, [CONCAVE HULL: A K-NEAREST NEIGHBOURS APPROACH FOR THE COMPUTATION OF THE REGION OCCUPIED BY A SET OF POINTS], in order to create a concave hull around a point cloud.
- Additionally, the module takes in point sets as additional optional arguments. When these are supplied, the a seperate concave boundary is created for the boundary points.
- These points also have their own triagulation created by taking available points from the source data and clipping that area out to match the created concave boundary.
- A delaunay triangulation with a new set of points overlayed in black - the black line is to help with visibility of the points, the points are at vertices of the polygon:
- The same set of points but with a concave boundary created around it in blue, the arrows indicate a ccw direction. (CCW from the origin (0,0) which is at the top left point of this image) The concave algorithm follows the left hand rule to determine the most suitable next point in the k grouping.
- At this point, additional points are added along the boundary for intersections with the main triangulation. This follows a minimum distance logic, where the points are not considered for an intersection with the boundary unless one of the points perpindicular line intersects the boundary and is less than or equal to that minimum distance from that intersection. [Further Details]
- Finally the concave boundary of the inner points are used to clip the original points into a seperate delaunay object. This object then has any triangle outside of the new concave boundary removed. It is done in this order to in order to minimize the size of the initial delaunay object and also to include the boudnary intersection points in the triangulation calculation. The new triangulation is shown overlayed in blue.
- uses rollup for minimizing
npm install [package name]
npm start
//ES import
import ConstrainoDelaunato as CD from 'constrainodelaunato'
//this is it, it will do the hole triangle calc on its own
let rictusempra = new CD(points, 3, holeBoundary)
// can add multiple holes
let tarantallegra = new CD(points, 3, hole1, hole2, holeN)
// hole boundaries and hole delaunay objects are stored as seperate arrays
console.log(tarantallegra.boundaries[0])
console.log(tarantallegra.boundedDelaunators[0])
- The bounded delaunator objects for the holes are useable as delaunay objects
ConstrainoDelaunato
Kind: global class
- ConstrainoDelaunato
- new ConstrainoDelaunato(coords, k, dist)
- .coords2D ⇒
Array
- .coords ⇒
Array
- .triangles ⇒
Array
- .hull ⇒
Array
- .delaunator ⇒
Object
- .boundaries ⇒
Array
- .holes ⇒
Array
- .setTrianglesInsideBound(boundary)
- .update(point)
creates a delaunator object for the larger coord point cloud, and any smalle concave boundaries and delaunator objects for holes/boundaries supplied
Param | Type | Description |
---|---|---|
coords | Array |
Coordinate cloud, can be 2D or 1D, prefer 1D of type [x0, y0, x1, y1, ... xN, yN] |
k | Integer |
lower bound for point selection in k grouping - minimum possible value is 3 - you have to make a polygon |
dist | Integer |
distance for adding points along boundary, distance between line segment perpindicular to either point of triangle segment |
...boundaries | Array |
Point clouds of holes in coords, stored in array boundary for concave boundaries and boundedDelaunator for created delaunator objects |
coords2D
Kind: instance property of ConstrainoDelaunato
Returns: Array
- 2D coordinate array
coords
Kind: instance property of ConstrainoDelaunato
Returns: Array
- 1D coordinate array
triangles
Kind: instance property of ConstrainoDelaunato
Returns: Array
- Index array of delaunator triangles
hull
Kind: instance property of ConstrainoDelaunato
Returns: Array
- Array of hull indices
delaunator
Kind: instance property of ConstrainoDelaunato
Returns: Object
- Return delaunator object for parent points
boundaries
Kind: instance property of ConstrainoDelaunato
Returns: Array
- concave boundary index array of parent points and hole points includes parent points as final array item
holes
Kind: instance property of ConstrainoDelaunato
Returns: Array
- Delaunator object array for all hole/boundary points supplied, includes parent points as final array item
setTrianglesInsideBound
Function used to clip coords to inside of boundary or hole
Kind: instance method of ConstrainoDelaunato
Param | Type | Description |
---|---|---|
boundary | BoundaryExtra |
boundary extra object |
update
Kind: instance method of ConstrainoDelaunato
Param | Type | Description |
---|---|---|
point | Array |
x and y coord of point to add the delaunator object |
// 3 is k starting value
let b = new BoundaryExtra(points, 3)
b.addPoints(parentCoords, parentDelaunatorObject, distance)
// for Object.boundaries 3 is k starting value
let b = new Boundary(points, 3)
//below is already done on object creation
const hull = b.findConcaveHull(k)// -> returns: sorted array of indices of x values for coord array
//subset returns the subset of coordinates from an index array
console.log(b.subset[hull])
//other accessors
b.coords2D
b.hullCoords
b.printPoints