Convert Brush to Polygon: Graham Scan

[danielsteinkogler]

Today i tested the Graham Algorithm to calculate a convex hull from drawn lines using this package: https://www.npmjs.com/package/graham_scan

It was very easy to implement and i made a test in the drawing layer:

I pretty like the result from the test. The black shape is the area I was drawing with a brush and the red line is the calculated polygon. The polygon in the test is smaller that the black area because I didn't take the stroke width of the black line into account.

@markus2330 we can discuss my findings on monday but whats your first impression if you look at the screenshot?

[danielsteinkogler]

with "curvy" areas its not working that well because then also big areas that are not colored are included in the polygon

[chr-schr]

@danielsteinkogler I found an interesting library for alpha shapes (wikipedia): alpha-shape
It looks like it could be useful, but requires fiddling with the alpha value.

Example:

[chr-schr]

Here is another one for concave hulls: Hull.js

It seems to be very fast, 52k points in 60ms (in my browser)

Example:

[danielsteinkogler]

@chr-schr that looks very very nice