Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit 6b197a0

Browse filesBrowse files
rreusserrreusser
authored
Merge pull request plotly#1223 from plotly/heatmap-contour-refactor
Heatmap contour refactor
2 parents 8265df5 + 016090a commit 6b197a0
Copy full SHA for 6b197a0

File tree

Expand file treeCollapse file tree

9 files changed

+758
-679
lines changed
Filter options
Expand file treeCollapse file tree

9 files changed

+758
-679
lines changed

‎src/traces/contour/constants.js

Copy file name to clipboard
+38Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
/**
2+
* Copyright 2012-2016, Plotly, Inc.
3+
* All rights reserved.
4+
*
5+
* This source code is licensed under the MIT license found in the
6+
* LICENSE file in the root directory of this source tree.
7+
*/
8+
9+
'use strict';
10+
11+
// some constants to help with marching squares algorithm
12+
// where does the path start for each index?
13+
module.exports.BOTTOMSTART = [1, 9, 13, 104, 713];
14+
module.exports.TOPSTART = [4, 6, 7, 104, 713];
15+
module.exports.LEFTSTART = [8, 12, 14, 208, 1114];
16+
module.exports.RIGHTSTART = [2, 3, 11, 208, 1114];
17+
18+
// which way [dx,dy] do we leave a given index?
19+
// saddles are already disambiguated
20+
module.exports.NEWDELTA = [
21+
null, [-1, 0], [0, -1], [-1, 0],
22+
[1, 0], null, [0, -1], [-1, 0],
23+
[0, 1], [0, 1], null, [0, 1],
24+
[1, 0], [1, 0], [0, -1]
25+
];
26+
27+
// for each saddle, the first index here is used
28+
// for dx||dy<0, the second for dx||dy>0
29+
module.exports.CHOOSESADDLE = {
30+
104: [4, 1],
31+
208: [2, 8],
32+
713: [7, 13],
33+
1114: [11, 14]
34+
};
35+
36+
// after one index has been used for a saddle, which do we
37+
// substitute to be used up later?
38+
module.exports.SADDLEREMAINDER = {1: 4, 2: 8, 4: 1, 7: 13, 8: 2, 11: 14, 13: 7, 14: 11};

‎src/traces/contour/find_all_paths.js

Copy file name to clipboard
+268Lines changed: 268 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,268 @@
1+
/**
2+
* Copyright 2012-2016, Plotly, Inc.
3+
* All rights reserved.
4+
*
5+
* This source code is licensed under the MIT license found in the
6+
* LICENSE file in the root directory of this source tree.
7+
*/
8+
9+
'use strict';
10+
11+
var Lib = require('../../lib');
12+
var constants = require('./constants');
13+
14+
module.exports = function findAllPaths(pathinfo) {
15+
var cnt,
16+
startLoc,
17+
i,
18+
pi,
19+
j;
20+
21+
for(i = 0; i < pathinfo.length; i++) {
22+
pi = pathinfo[i];
23+
24+
for(j = 0; j < pi.starts.length; j++) {
25+
startLoc = pi.starts[j];
26+
makePath(pi, startLoc, 'edge');
27+
}
28+
29+
cnt = 0;
30+
while(Object.keys(pi.crossings).length && cnt < 10000) {
31+
cnt++;
32+
startLoc = Object.keys(pi.crossings)[0].split(',').map(Number);
33+
makePath(pi, startLoc);
34+
}
35+
if(cnt === 10000) Lib.log('Infinite loop in contour?');
36+
}
37+
};
38+
39+
function equalPts(pt1, pt2) {
40+
return Math.abs(pt1[0] - pt2[0]) < 0.01 &&
41+
Math.abs(pt1[1] - pt2[1]) < 0.01;
42+
}
43+
44+
function ptDist(pt1, pt2) {
45+
var dx = pt1[0] - pt2[0],
46+
dy = pt1[1] - pt2[1];
47+
return Math.sqrt(dx * dx + dy * dy);
48+
}
49+
50+
function makePath(pi, loc, edgeflag) {
51+
var startLocStr = loc.join(','),
52+
locStr = startLocStr,
53+
mi = pi.crossings[locStr],
54+
marchStep = startStep(mi, edgeflag, loc),
55+
// start by going backward a half step and finding the crossing point
56+
pts = [getInterpPx(pi, loc, [-marchStep[0], -marchStep[1]])],
57+
startStepStr = marchStep.join(','),
58+
m = pi.z.length,
59+
n = pi.z[0].length,
60+
cnt;
61+
62+
// now follow the path
63+
for(cnt = 0; cnt < 10000; cnt++) { // just to avoid infinite loops
64+
if(mi > 20) {
65+
mi = constants.CHOOSESADDLE[mi][(marchStep[0] || marchStep[1]) < 0 ? 0 : 1];
66+
pi.crossings[locStr] = constants.SADDLEREMAINDER[mi];
67+
}
68+
else {
69+
delete pi.crossings[locStr];
70+
}
71+
72+
marchStep = constants.NEWDELTA[mi];
73+
if(!marchStep) {
74+
Lib.log('Found bad marching index:', mi, loc, pi.level);
75+
break;
76+
}
77+
78+
// find the crossing a half step forward, and then take the full step
79+
pts.push(getInterpPx(pi, loc, marchStep));
80+
loc[0] += marchStep[0];
81+
loc[1] += marchStep[1];
82+
83+
// don't include the same point multiple times
84+
if(equalPts(pts[pts.length - 1], pts[pts.length - 2])) pts.pop();
85+
locStr = loc.join(',');
86+
87+
// have we completed a loop, or reached an edge?
88+
if((locStr === startLocStr && marchStep.join(',') === startStepStr) ||
89+
(edgeflag && (
90+
(marchStep[0] && (loc[0] < 0 || loc[0] > n - 2)) ||
91+
(marchStep[1] && (loc[1] < 0 || loc[1] > m - 2))))) {
92+
break;
93+
}
94+
mi = pi.crossings[locStr];
95+
}
96+
97+
if(cnt === 10000) {
98+
Lib.log('Infinite loop in contour?');
99+
}
100+
var closedpath = equalPts(pts[0], pts[pts.length - 1]),
101+
totaldist = 0,
102+
distThresholdFactor = 0.2 * pi.smoothing,
103+
alldists = [],
104+
cropstart = 0,
105+
distgroup,
106+
cnt2,
107+
cnt3,
108+
newpt,
109+
ptcnt,
110+
ptavg,
111+
thisdist;
112+
113+
// check for points that are too close together (<1/5 the average dist,
114+
// less if less smoothed) and just take the center (or avg of center 2)
115+
// this cuts down on funny behavior when a point is very close to a contour level
116+
for(cnt = 1; cnt < pts.length; cnt++) {
117+
thisdist = ptDist(pts[cnt], pts[cnt - 1]);
118+
totaldist += thisdist;
119+
alldists.push(thisdist);
120+
}
121+
122+
var distThreshold = totaldist / alldists.length * distThresholdFactor;
123+
124+
function getpt(i) { return pts[i % pts.length]; }
125+
126+
for(cnt = pts.length - 2; cnt >= cropstart; cnt--) {
127+
distgroup = alldists[cnt];
128+
if(distgroup < distThreshold) {
129+
cnt3 = 0;
130+
for(cnt2 = cnt - 1; cnt2 >= cropstart; cnt2--) {
131+
if(distgroup + alldists[cnt2] < distThreshold) {
132+
distgroup += alldists[cnt2];
133+
}
134+
else break;
135+
}
136+
137+
// closed path with close points wrapping around the boundary?
138+
if(closedpath && cnt === pts.length - 2) {
139+
for(cnt3 = 0; cnt3 < cnt2; cnt3++) {
140+
if(distgroup + alldists[cnt3] < distThreshold) {
141+
distgroup += alldists[cnt3];
142+
}
143+
else break;
144+
}
145+
}
146+
ptcnt = cnt - cnt2 + cnt3 + 1;
147+
ptavg = Math.floor((cnt + cnt2 + cnt3 + 2) / 2);
148+
149+
// either endpoint included: keep the endpoint
150+
if(!closedpath && cnt === pts.length - 2) newpt = pts[pts.length - 1];
151+
else if(!closedpath && cnt2 === -1) newpt = pts[0];
152+
153+
// odd # of points - just take the central one
154+
else if(ptcnt % 2) newpt = getpt(ptavg);
155+
156+
// even # of pts - average central two
157+
else {
158+
newpt = [(getpt(ptavg)[0] + getpt(ptavg + 1)[0]) / 2,
159+
(getpt(ptavg)[1] + getpt(ptavg + 1)[1]) / 2];
160+
}
161+
162+
pts.splice(cnt2 + 1, cnt - cnt2 + 1, newpt);
163+
cnt = cnt2 + 1;
164+
if(cnt3) cropstart = cnt3;
165+
if(closedpath) {
166+
if(cnt === pts.length - 2) pts[cnt3] = pts[pts.length - 1];
167+
else if(cnt === 0) pts[pts.length - 1] = pts[0];
168+
}
169+
}
170+
}
171+
pts.splice(0, cropstart);
172+
173+
// don't return single-point paths (ie all points were the same
174+
// so they got deleted?)
175+
if(pts.length < 2) return;
176+
else if(closedpath) {
177+
pts.pop();
178+
pi.paths.push(pts);
179+
}
180+
else {
181+
if(!edgeflag) {
182+
Lib.log('Unclosed interior contour?',
183+
pi.level, startLocStr, pts.join('L'));
184+
}
185+
186+
// edge path - does it start where an existing edge path ends, or vice versa?
187+
var merged = false;
188+
pi.edgepaths.forEach(function(edgepath, edgei) {
189+
if(!merged && equalPts(edgepath[0], pts[pts.length - 1])) {
190+
pts.pop();
191+
merged = true;
192+
193+
// now does it ALSO meet the end of another (or the same) path?
194+
var doublemerged = false;
195+
pi.edgepaths.forEach(function(edgepath2, edgei2) {
196+
if(!doublemerged && equalPts(
197+
edgepath2[edgepath2.length - 1], pts[0])) {
198+
doublemerged = true;
199+
pts.splice(0, 1);
200+
pi.edgepaths.splice(edgei, 1);
201+
if(edgei2 === edgei) {
202+
// the path is now closed
203+
pi.paths.push(pts.concat(edgepath2));
204+
}
205+
else {
206+
pi.edgepaths[edgei2] =
207+
pi.edgepaths[edgei2].concat(pts, edgepath2);
208+
}
209+
}
210+
});
211+
if(!doublemerged) {
212+
pi.edgepaths[edgei] = pts.concat(edgepath);
213+
}
214+
}
215+
});
216+
pi.edgepaths.forEach(function(edgepath, edgei) {
217+
if(!merged && equalPts(edgepath[edgepath.length - 1], pts[0])) {
218+
pts.splice(0, 1);
219+
pi.edgepaths[edgei] = edgepath.concat(pts);
220+
merged = true;
221+
}
222+
});
223+
224+
if(!merged) pi.edgepaths.push(pts);
225+
}
226+
}
227+
228+
// special function to get the marching step of the
229+
// first point in the path (leading to loc)
230+
function startStep(mi, edgeflag, loc) {
231+
var dx = 0,
232+
dy = 0;
233+
if(mi > 20 && edgeflag) {
234+
// these saddles start at +/- x
235+
if(mi === 208 || mi === 1114) {
236+
// if we're starting at the left side, we must be going right
237+
dx = loc[0] === 0 ? 1 : -1;
238+
}
239+
else {
240+
// if we're starting at the bottom, we must be going up
241+
dy = loc[1] === 0 ? 1 : -1;
242+
}
243+
}
244+
else if(constants.BOTTOMSTART.indexOf(mi) !== -1) dy = 1;
245+
else if(constants.LEFTSTART.indexOf(mi) !== -1) dx = 1;
246+
else if(constants.TOPSTART.indexOf(mi) !== -1) dy = -1;
247+
else dx = -1;
248+
return [dx, dy];
249+
}
250+
251+
function getInterpPx(pi, loc, step) {
252+
var locx = loc[0] + Math.max(step[0], 0),
253+
locy = loc[1] + Math.max(step[1], 0),
254+
zxy = pi.z[locy][locx],
255+
xa = pi.xaxis,
256+
ya = pi.yaxis;
257+
258+
if(step[1]) {
259+
var dx = (pi.level - zxy) / (pi.z[locy][locx + 1] - zxy);
260+
return [xa.c2p((1 - dx) * pi.x[locx] + dx * pi.x[locx + 1], true),
261+
ya.c2p(pi.y[locy], true)];
262+
}
263+
else {
264+
var dy = (pi.level - zxy) / (pi.z[locy + 1][locx] - zxy);
265+
return [xa.c2p(pi.x[locx], true),
266+
ya.c2p((1 - dy) * pi.y[locy] + dy * pi.y[locy + 1], true)];
267+
}
268+
}

‎src/traces/contour/make_crossings.js

Copy file name to clipboard
+90Lines changed: 90 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,90 @@
1+
/**
2+
* Copyright 2012-2016, Plotly, Inc.
3+
* All rights reserved.
4+
*
5+
* This source code is licensed under the MIT license found in the
6+
* LICENSE file in the root directory of this source tree.
7+
*/
8+
9+
'use strict';
10+
11+
var constants = require('./constants');
12+
13+
// Calculate all the marching indices, for ALL levels at once.
14+
// since we want to be exhaustive we'll check for contour crossings
15+
// at every intersection, rather than just following a path
16+
// TODO: shorten the inner loop to only the relevant levels
17+
module.exports = function makeCrossings(pathinfo) {
18+
var z = pathinfo[0].z,
19+
m = z.length,
20+
n = z[0].length, // we already made sure z isn't ragged in interp2d
21+
twoWide = m === 2 || n === 2,
22+
xi,
23+
yi,
24+
startIndices,
25+
ystartIndices,
26+
label,
27+
corners,
28+
mi,
29+
pi,
30+
i;
31+
32+
for(yi = 0; yi < m - 1; yi++) {
33+
ystartIndices = [];
34+
if(yi === 0) ystartIndices = ystartIndices.concat(constants.BOTTOMSTART);
35+
if(yi === m - 2) ystartIndices = ystartIndices.concat(constants.TOPSTART);
36+
37+
for(xi = 0; xi < n - 1; xi++) {
38+
startIndices = ystartIndices.slice();
39+
if(xi === 0) startIndices = startIndices.concat(constants.LEFTSTART);
40+
if(xi === n - 2) startIndices = startIndices.concat(constants.RIGHTSTART);
41+
42+
label = xi + ',' + yi;
43+
corners = [[z[yi][xi], z[yi][xi + 1]],
44+
[z[yi + 1][xi], z[yi + 1][xi + 1]]];
45+
for(i = 0; i < pathinfo.length; i++) {
46+
pi = pathinfo[i];
47+
mi = getMarchingIndex(pi.level, corners);
48+
if(!mi) continue;
49+
50+
pi.crossings[label] = mi;
51+
if(startIndices.indexOf(mi) !== -1) {
52+
pi.starts.push([xi, yi]);
53+
if(twoWide && startIndices.indexOf(mi,
54+
startIndices.indexOf(mi) + 1) !== -1) {
55+
// the same square has starts from opposite sides
56+
// it's not possible to have starts on opposite edges
57+
// of a corner, only a start and an end...
58+
// but if the array is only two points wide (either way)
59+
// you can have starts on opposite sides.
60+
pi.starts.push([xi, yi]);
61+
}
62+
}
63+
}
64+
}
65+
}
66+
};
67+
68+
// modified marching squares algorithm,
69+
// so we disambiguate the saddle points from the start
70+
// and we ignore the cases with no crossings
71+
// the index I'm using is based on:
72+
// http://en.wikipedia.org/wiki/Marching_squares
73+
// except that the saddles bifurcate and I represent them
74+
// as the decimal combination of the two appropriate
75+
// non-saddle indices
76+
function getMarchingIndex(val, corners) {
77+
var mi = (corners[0][0] > val ? 0 : 1) +
78+
(corners[0][1] > val ? 0 : 2) +
79+
(corners[1][1] > val ? 0 : 4) +
80+
(corners[1][0] > val ? 0 : 8);
81+
if(mi === 5 || mi === 10) {
82+
var avg = (corners[0][0] + corners[0][1] +
83+
corners[1][0] + corners[1][1]) / 4;
84+
// two peaks with a big valley
85+
if(val > avg) return (mi === 5) ? 713 : 1114;
86+
// two valleys with a big ridge
87+
return (mi === 5) ? 104 : 208;
88+
}
89+
return (mi === 15) ? 0 : mi;
90+
}

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.