Some points outside hull

[wwaltersdavis]

A case where not all points are contained within the concave hull. This issue also occurs when using the C++ port though not necessarily with the given examples.

A six point example:

import concaveman from 'concaveman';
const points = [
    [1.911, 4.157], // A
    [5.668, 0.704], // B
    [6.134, 2.879], // C
    [8.045, 2.904], // D
    [9.942, 3.167], // E
    [7.757, 3.387]  // F
];
const hull = concaveman(points);

returned hull: [
  [ 5.668, 0.704 ],
  [ 1.911, 4.157 ],
  [ 7.757, 3.387 ],
  [ 9.942, 3.167 ],
  [ 6.134, 2.879 ],
  [ 5.668, 0.704 ]
]

point outside hull: [8.045, 2.904]

The hull is visualised below. In this example I believe when looking for a candidate for edge B-E, point D is rejected by line 118 as it is closer to edge E-A. This means C is selected as the criteria are met so a flex inwards occurs isolating D from the hull. When looking for a candidate for C-E, D is selected at first, however this then fails line 65 as it is close to the centre of edge C-E and therefore fails the concavity check.

This flexing inwards causing another point to be exterior occurs quite frequently, however in most cases a flex back outwards to include that point happens on the next iteration and only when a later check fails the issue occurs.

This issue happens more frequently at higher concavities where more points will fail check line 65. With some rough testing of 6 random points found this issue occurs at ~1/3m at a concavity of 2, but this rises to ~1/85k at a concavity of 3.

A real world example:

Below shows the first 1000 points on a graph reachable from a given start point. Using points real_world_points.json.

Potential solution

I wrote a Rust port of concaveman for the Geo library where I first encountered this issue. The fix I implemented is recording each rejected node during candidate selection. Then if a node is selected, check these recorded nodes to ensure none would be moved to outside the hull and if so use that selected node as the candidate.

Some pros:

• Ensures no points outside hull
• Very minor drop in performance (<1% for the Rust implementation)
• Changes are very rare, so resulting hulls are extremely similar to the current output hulls, with the majority returning the same hull

Some cons:

• Nodes which are as close/closer to an adjacent line may be selected as candidate