Why contour draw out-of-data points

[hoanphi2201]

These points are not in the data.
https://jsfiddle.net/phihoan2201/2nb8op56/1/

[paulo-raca]

Well, this is not really a bug, but just a side effect of relying on automatic delaunay triangulation.

The algorithm doesn't distinguish points on the boundary and on the interior, so the result is always a convex hull.

For now, my suggestion is that you perform triangulation manually and send them into the plugin with the triangles argument.

If there is a triangulation algorithm that accepts boundary hints, I may build it into the plugin, but I don't know of any on the top of my head. Suggestions?

[paulo-raca]

Looks like what you need is called Constrained Delaunay, and there are a few JS libraries out there:

• https://github.com/mikolalysenko/cdt2d
• https://github.com/SINTEF-Geometry/TTL
• https://github.com/r3mi/poly2tri.js
• Conforming/Constrained Delaunay mapbox/delaunator#9

I believe cdt2d could be a drop-in replacement, adding extra arguments for boundaries and running with {interior: true, exterior: false}

@hoanphi2201 Would you mind giving it a try to see if this is good for your needs before I patch the library?

[hoanphi2201]

@paulo-raca Well I will try it. Hopefully you will patch the library as soon as possible. Thank you very much

[hoanphi2201]

@paulo-raca Can you give me a more detailed solution? I do not have much knowledge about delaunay triangulation

[paulo-raca]

This isn't tested, but should be something like this:

// Your current data array, each with X, Y and Value
dataPoints = dataChartContour;
//Array of your data points that represent the boundary, ordered
boundaryIndexes = [0,1,2,3]; 

// Convert to array of [ [x0, y0], [x1, y1], ....]
2dPoints = dataPoints.map(function(p) { return [p.x, p.y]; };
//Convert boundaryIndexes in a list of edges
constraintEdges = []
for (var i=0; i<boundaryIndexes.length; i++) {
  constraintEdges.push([boundaryIndexes[i], boundaryIndexes[(i+1) % boundaryIndexes.length])
}

//Use cdt2d to perform triangulation
triangles = cdt2d(2dPoints, constraintEdges, {exterior: false});

[...]

Highcharts.chart("container, {
    [...]
    series: [{
        type: 'contour',
        data: dataChartContour,
        triangles: triangles,
        [...]
    }]
});

[hoanphi2201]

Hello @paulo-raca why boundaryIndexes is a 1-dimensional array. I thought the boundary is a 2-dimensional array of x and y

[paulo-raca]

They are indexes of dataPoints

[hoanphi2201]

@paulo-raca triangles return [] array. why ? boundaryIndexes from the dataPoints array that at that point is the boundary
I used nodejs to be able to use cdt2d

 // Contour Config
    const x = w7cData['charts'][0]['additonalInfo']['data'].x;
    const y = w7cData['charts'][0]['additonalInfo']['data'].y;
    const z = w7cData['charts'][0]['additonalInfo']['data'].z;
    let dataChartContour = [];
    for (let i = 0; i < y.length; i++) {
        for (let j = 0; j < x.length; j++) {
            dataChartContour.push([x[j], y[i], z[i][j]]);
        }
    }
    dataChartContour.sort((a, b) => {
        return a[0] - b[0];
    })
    // Your current data array, each with X, Y and Value
    dataPoints = dataChartContour;

    //Array of your data points that represent the boundary, ordered
    boundaryIndexes = [4, 30, 55, 75, 96, 117, 138, 157, 176, 197, 217, 235, 256, 279, 295, 315, 330, 347, 366, 385, 402];

    // Convert to array of [ [x0, y0], [x1, y1], ....]
    _2dPoints =  [];
    for(let i = 0; i < dataPoints.length; i++) {
        _2dPoints.push([dataPoints[i][0], dataPoints[i][1]])
    }

    //Convert boundaryIndexes in a list of edges
    let constraintEdges = []
    for (var i = 0; i < boundaryIndexes.length; i++) {
        constraintEdges.push([boundaryIndexes[i], boundaryIndexes[(i + 1) % boundaryIndexes.length]]);
    }

    //Use cdt2d to perform triangulation
    triangles = cdt2d(_2dPoints, constraintEdges, { exterior: false });
    

[hoanphi2201]

If remove { exterior: false } return array 747 element

[paulo-raca]

I guess the boundary might be open? 🤔

Can you dump the contents of constraintEdges ?

[hoanphi2201]

@paulo-raca

constraintEdges = [
                        [
                            4,30
                        ],
                        [
                            30,55
                        ],
                        [
                            55,75
                        ],
                        [
                            75,96
                        ],
                        [
                            96,117
                        ],
                        [
                            117,138
                        ],
                        [
                            138,157
                        ],
                        [
                            157,176
                        ],
                        [
                            176,197
                        ],
                        [
                            197,217
                        ],
                        [
                            217,235
                        ],
                        [
                            235,256
                        ],
                        [
                            256,279
                        ],
                        [
                            279,295
                        ],
                        [
                            295,315
                        ],
                        [
                            315,330
                        ],
                        [
                            330,347
                        ],
                        [
                            347,366
                        ],
                        [
                            366,385
                        ],
                        [
                            385,402
                        ],
                        [
                            402,4
                        ]
                    ]

[paulo-raca]

Sounds right....
I'll have to take a deeper look at it later -- Can you put it all in a jsfiddle, please?

Thank you

[hoanphi2201]

@paulo-raca
I used nodejs to be able to use cdt2d so I will create 1 repo Repo
And jsfiddle to draw chart: https://jsfiddle.net/phihoan2201/2nb8op56/1/

Thank you, I hope to receive your feedback soon

[hoanphi2201]

@paulo-raca here is boundary index

 [1.999, 0.148, 0]  "index: 4"
 [3, 0.37, 0] "index: 30"
 [4, 0.555, 0] "index: 55"
 [5.5, 0.555, 0] "index: 75"
 [7, 0.592, 0] "index: 96"
 [8.5, 0.629, 0] "index: 117"
 [10, 0.666, 0] "index: 138"
 [11.5, 0.629, 0] "index: 157"
 [13, 0.592, 0] "index: 176"
 [14.5, 0.629, 0] "index: 197"
 [16, 0.629, 0] "index: 217"
 [17.5, 0.555, 0] "index: 235"
 [19, 0.592, 0] "index: 256"
[20.5, 0.703, 0] "index: 279"
 [22, 0.555, 0.1184] "index: 295"
 [23.5, 0.555, 0] "index: 315"
 [25, 0.37, 0.106] "index: 330"
[26.5, 0.259, 0] "index: 347"
 [28, 0.222, 0.0762] "index: 366"
[29, 0.185, 0.0702] "index: 385"
 [30.001, 0.074, 0] "index: 402"

[hoanphi2201]

@paulo-raca I have seen it run properly.
Looks like the graph is jumping off the x axis. Is it due to my data or a calculation error?
Do the boundary points here include points at zero coordinates?

[paulo-raca]

Nice, what did you have to change?

You mean the zig-zaging at the bottom of the image?
🤔 It's hard to tell, but maybe an artifact of the new triangulation algorithm? Can you set showTriangles=true?

[paulo-raca]

Got an idea: the delaunay triangulation is sensitive to stretching the aspect ratio, and in your case the scale on the x-axis is about 50 times bigger than on the y-axis.

To work around that the plug-in normally works with screen coordinates, but we can work around that
Simply scaling the coordinates we feed into the algorithm:
_2dPoints.push([dataPoints[i][0], 50*dataPoints[i][1]])

[hoanphi2201]

It has not changed since the beginning. points with y = 0 coordinates have disappeared

[hoanphi2201]

Use _2dPoints.push([dataPoints[i][0], 50*dataPoints[i][1]]) does not change triangles

[paulo-raca]

Oh, I hadn't understood the problem 🤦‍♂️

From you previous post, the boundary doesn't include any point with y=0, so it seems like the algorithm is ignoring all points at the bottom of the chart

[hoanphi2201]

data still exists points y = 0.
Can you reconsider the algorithm?

[paulo-raca]

I meant they are not inside the boundary you mentioned earlier:

 [1.999, 0.148, 0]  "index: 4"
 [3, 0.37, 0] "index: 30"
 [4, 0.555, 0] "index: 55"
 [5.5, 0.555, 0] "index: 75"
 [7, 0.592, 0] "index: 96"
 [8.5, 0.629, 0] "index: 117"
 [10, 0.666, 0] "index: 138"
 [11.5, 0.629, 0] "index: 157"
 [13, 0.592, 0] "index: 176"
 [14.5, 0.629, 0] "index: 197"
 [16, 0.629, 0] "index: 217"
 [17.5, 0.555, 0] "index: 235"
 [19, 0.592, 0] "index: 256"
[20.5, 0.703, 0] "index: 279"
 [22, 0.555, 0.1184] "index: 295"
 [23.5, 0.555, 0] "index: 315"
 [25, 0.37, 0.106] "index: 330"
[26.5, 0.259, 0] "index: 347"
 [28, 0.222, 0.0762] "index: 366"
[29, 0.185, 0.0702] "index: 385"
 [30.001, 0.074, 0] "index: 402"

Keep in mind that these form a close polygon,. So you must also include all points with y=0

[hoanphi2201]

I did not understand the boundary point. Do I need to get points with y = 0?
I tried it and triangles return [] array

[paulo-raca]

Yes, that's what I meant.

🤔 I don't know why you are getting an empty result...

[hoanphi2201]

here is here is boundary index, include points with y = 0 (42 element)

[[[1.999,0,0],"index: 0"],[[1.999,0.148,0],"index: 4"],[[3,0,0.0241],"index: 20"],[[3,0.37,0],"index: 30"],[[4,0,0.102],"index: 40"],[[4,0.555,0],"index: 55"],[[5.5,0,0.1229],"index: 60"],[[5.5,0.555,0],"index: 75"],[[7,0,0.1625],"index: 80"],[[7,0.592,0],"index: 96"],[[8.5,0,0.2073],"index: 100"],[[8.5,0.629,0],"index: 117"],[[10,0,0.175],"index: 120"],[[10,0.666,0],"index: 138"],[[11.5,0,0.2165],"index: 140"],[[11.5,0.629,0],"index: 157"],[[13,0,0.2179],"index: 160"],[[13,0.592,0],"index: 176"],[[14.5,0,0.2113],"index: 180"],[[14.5,0.629,0],"index: 197"],[[16,0,0.2632],"index: 200"],[[16,0.629,0],"index: 217"],[[17.5,0,0.2559],"index: 220"],[[17.5,0.555,0],"index: 235"],[[19,0,0.2355],"index: 240"],[[19,0.592,0],"index: 256"],[[20.5,0,0.1878],"index: 260"],[[20.5,0.703,0],"index: 279"],[[22,0,0.1817],"index: 280"],[[22,0.555,0.1184],"index: 295"],[[23.5,0,0.1766],"index: 300"],[[23.5,0.555,0],"index: 315"],[[25,0,0.1625],"index: 320"],[[25,0.37,0.106],"index: 330"],[[26.5,0,0.18],"index: 340"],[[26.5,0.259,0],"index: 347"],[[28,0,0.1168],"index: 360"],[[28,0.222,0.0762],"index: 366"],[[29,0,0.1077],"index: 380"],[[29,0.185,0.0702],"index: 385"],[[30.001,0,0],"index: 400"],[[30.001,0.074,0],"index: 402"]]

[paulo-raca]

Thanks!
Order matters here, you need to sort your points either clockwork or counterflow -- you currently have a crazy sawtooth polygon :P

One way is to start your list with upper boundary points ordered by +X, followed by the lower boundary points ordered by -X

[hoanphi2201]

@paulo-raca
The cdt2d library has performed well. But it cannot be used in javascript. Can you suggest a similar library used in js?

[willmac321]

Hey guys, come over here from mapbox post, I just made a js library that can be used to create concave polygons, takes in points in unsorted order and spits out a delaunay object or coord array or boundary, what have you...

https://www.npmjs.com/package/constrainodelaunato

[paulo-raca]

Probably too late, but I've added support for cdt2d in the plugin and wrote a demo with concave external boundary:
https://jsfiddle.net/mt5fyL6z/