Making a geometry from points: How to shrink wrap a convex hull around some points?

Questions
9

@donmccurdy Made a small test on Runkit. I inputted this code:

var alphaShape = require("alpha-shape")

var points = []
for(var i=0; i<10; ++i) {
  points.push([Math.random(), Math.random(), Math.random()])
}

const result = alphaShape(1, points)

console.log(result)

and the result is an array like

[[7, 0, 1], [6, 2, 0], [3, 5, 1], [0, 9, 1], [2, 9, 0], …]

with 16 items.

I can’t seem to make sense of the resulting numbers though: if the points I supplied are all between 0 and 1, why do the result points have bigger numbers like 6,2,0?

EDIT: Ah, I see, each item in the result of my example is a triangle of the resulting concave hull, where each number in the triangle represents the index into the original array of points.

For example, let’s use hard coded points:

var alphaShape = require("alpha-shape")

var points = [
    [0.9016381627581787, 0.5003897457914939, 0.11064094454278495],
    [0.6677021645723598, 0.5190459142762935, 0.4221100146124732],
    [0.5813531630779389, 0.18900966289335175, 0.9217677173114724],
    [0.865059478284703, 0.71477564849315, 0.36260754458255406],
    [0.6939529153474795, 0.753540893509971, 0.8871682472417979],
    [0.7955499479483117, 0.3198809832101075, 0.8399213925680513],
    [0.25982865736532323, 0.33538550898296315, 0.2163119470963415],
    [0.04633728090568856, 0.8991183094645228, 0.8169232630725838],
    [0.08399524814515691, 0.2571676753335388, 0.5900703744472551],
    [0.5312113415688489, 0.07245885095901672, 0.4157959075950943],
]

const result = alphaShape(1, points)

console.log(result)

// output:
// [
//     [5, 3, 0],
//     [3, 6, 0],
//     [2, 4, 5],
//     [4, 3, 5],
//     [4, 2, 7],
//     [9, 5, 0],
//     [3, 4, 7],
//     [6, 9, 0],
//     [9, 2, 5],
//     [3, 7, 6],
//     [2, 8, 7],
//     [8, 2, 9],
//     [6, 7, 8],
//     [6, 8, 9],
// ]

Then in the result, the first item, [5, 3, 0] represents the triangle made from the items in the points array at indices 5, 3, and 0, which is the following triangle:

[
    [0.7955499479483117, 0.3198809832101075, 0.8399213925680513],
    [0.865059478284703, 0.71477564849315, 0.36260754458255406],
    [0.9016381627581787, 0.5003897457914939, 0.11064094454278495],
]

(runkit example)

2 Likes