forked from redblobgames/delaunator
-
Notifications
You must be signed in to change notification settings - Fork 0
/
test.js
137 lines (118 loc) · 64.4 KB
/
test.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
import {test} from 'tape';
import Delaunator from './index.js';
const points = [[168, 180], [168, 178], [168, 179], [168, 181], [168, 183], [167, 183], [167, 184], [165, 184], [162, 186], [164, 188], [161, 188], [160, 191], [158, 193], [156, 193], [152, 195], [152, 198], [150, 198], [147, 198], [148, 205], [150, 210], [148, 210], [148, 208], [145, 206], [142, 206], [140, 206], [138, 206], [135, 206], [135, 209], [131, 209], [131, 211], [127, 211], [124, 210], [120, 207], [120, 204], [120, 202], [124, 201], [123, 201], [125, 198], [125, 194], [127, 194], [127, 191], [130, 191], [132, 189], [134, 189], [134, 186], [136, 184], [134, 182], [134, 179], [134, 176], [136, 174], [139, 174], [141, 177], [142, 176], [144, 176], [147, 178], [148, 176], [151, 178], [154, 178], [153, 175], [152, 174], [152, 170], [152, 168], [150, 166], [148, 166], [147, 165], [145, 162], [146, 160], [146, 157], [146, 155], [144, 155], [142, 152], [140, 150], [138, 150], [138, 148], [140, 145], [140, 142], [140, 138], [139, 138], [137, 138], [135, 138], [133, 135], [132, 132], [129, 132], [128, 132], [124, 132], [124, 130], [123, 130], [118, 126], [116, 124], [112, 122], [109, 122], [105, 122], [102, 124], [100, 124], [97, 124], [95, 126], [92, 127], [89, 127], [88, 130], [85, 132], [80, 134], [72, 134], [69, 134], [65, 138], [64, 138], [58, 137], [56, 133], [52, 133], [51, 133], [48, 133], [44, 133], [41, 131], [38, 130], [35, 130], [32, 127], [30, 127], [27, 127], [24, 127], [24, 126], [23, 124], [20, 122], [17, 122], [16, 118], [15, 116], [15, 110], [18, 108], [20, 102], [24, 97], [28, 102], [28, 98], [26, 97], [28, 94], [27, 85], [29, 79], [32, 76], [39, 70], [44, 66], [48, 65], [53, 61], [53, 58], [51, 54], [54, 54], [52, 48], [51, 43], [48, 42], [49, 38], [48, 34], [51, 30], [53, 33], [58, 30], [61, 30], [60, 27], [64, 26], [68, 24], [74, 24], [80, 24], [85, 26], [92, 26], [96, 29], [103, 32], [109, 33], [112, 37], [116, 37], [120, 37], [124, 35], [126, 35], [128, 38], [132, 38], [134, 41], [138, 38], [140, 36], [142, 40], [144, 43], [145, 41], [149, 41], [155, 41], [159, 41], [161, 46], [165, 46], [164, 42], [164, 39], [164, 34], [167, 30], [173, 24], [178, 24], [184, 24], [189, 26], [195, 21], [195, 20], [199, 20], [203, 20], [207, 17], [211, 17], [216, 17], [218, 16], [222, 22], [225, 27], [228, 31], [226, 34], [224, 34], [226, 39], [228, 43], [230, 46], [236, 46], [242, 46], [243, 50], [245, 50], [247, 54], [247, 56], [248, 60], [248, 65], [253, 66], [255, 64], [260, 64], [264, 67], [268, 71], [272, 66], [275, 66], [281, 61], [285, 66], [286, 70], [292, 74], [294, 74], [296, 74], [296, 71], [301, 74], [307, 74], [311, 78], [315, 74], [315, 77], [319, 77], [322, 82], [328, 82], [331, 81], [331, 84], [333, 86], [333, 90], [330, 95], [326, 98], [328, 99], [332, 98], [333, 101], [331, 104], [329, 104], [327, 106], [329, 111], [332, 116], [333, 119], [333, 122], [332, 126], [332, 130], [327, 130], [321, 130], [317, 130], [315, 134], [312, 134], [308, 138], [306, 138], [306, 144], [306, 149], [306, 152], [301, 152], [297, 154], [295, 154], [292, 154], [292, 158], [288, 158], [283, 162], [281, 164], [279, 163], [276, 163], [273, 166], [272, 169], [268, 168], [265, 170], [260, 172], [256, 176], [252, 176], [248, 181], [246, 182], [246, 189], [246, 194], [248, 197], [250, 198], [252, 200], [252, 203], [254, 205], [260, 205], [264, 202], [267, 202], [269, 202], [272, 199], [280, 199], [278, 202], [278, 207], [278, 211], [276, 211], [272, 213], [268, 213], [265, 213], [264, 211], [262, 210], [260, 210], [257, 212], [257, 214], [255, 217], [253, 217], [253, 221], [249, 220], [247, 220], [243, 222], [240, 223], [239, 226], [234, 231], [229, 231], [224, 231], [219, 227], [220, 227], [222, 224], [222, 222], [222, 219], [224, 217], [222, 214], [220, 212], [217, 210], [215, 210], [211, 209], [208, 206], [202, 209], [202, 205], [206, 202], [211, 198], [216, 195], [220, 192], [224, 192], [221, 186], [218, 186], [214, 185], [208, 185], [204, 186], [200, 186], [193, 183], [190, 182], [188, 182], [190, 178], [186, 178], [184, 174], [182, 171], [178, 171], [173, 174], [169, 174], [169, 175], [169, 179], [167, 182], [164, 186], [160, 192], [155, 195], [152, 198], [150, 198], [148, 198], [148, 202], [151, 208], [148, 210], [146, 208], [144, 205], [140, 205], [137, 208], [132, 208], [132, 210], [127, 210], [124, 210], [120, 206], [120, 202], [123, 202], [124, 201], [124, 198], [128, 195], [131, 191], [133, 187], [135, 183], [130, 203], [129, 208], [123, 203], [129, 203], [129, 198], [133, 198], [136, 200], [142, 200], [143, 199], [143, 197], [137, 196], [136, 194], [133, 194], [136, 186], [136, 182], [141, 186], [144, 186], [150, 186], [150, 190], [155, 190], [159, 188], [156, 182], [151, 182], [144, 182], [164, 176], [161, 177], [157, 177], [166, 176], [168, 165], [175, 167], [180, 167], [188, 159], [195, 164], [195, 162], [187, 162], [178, 163], [173, 166], [168, 170], [156, 170], [157, 165], [164, 165], [164, 161], [170, 159], [167, 158], [159, 154], [149, 151], [145, 145], [145, 138], [152, 138], [152, 146], [159, 146], [165, 153], [176, 153], [180, 153], [187, 153], [194, 153], [202, 153], [202, 158], [197, 158], [193, 158], [193, 142], [180, 142], [171, 142], [163, 135], [176, 135], [186, 139], [201, 139], [206, 139], [205, 147], [205, 160], [198, 160], [206, 174], [205, 178], [196, 178], [196, 182], [202, 182], [206, 181], [209, 181], [215, 181], [222, 181], [230, 177], [238, 175], [241, 175], [237, 175], [237, 168], [237, 161], [232, 156], [231, 162], [225, 166], [217, 169], [210, 173], [224, 173], [227, 173], [235, 175], [237, 178], [228, 192], [222, 199], [216, 199], [211, 204], [205, 206], [219, 207], [222, 211], [229, 214], [236, 214], [244, 211], [247, 211], [268, 206], [277, 201], [279, 201], [281, 202], [278, 202], [242, 178], [236, 170], [236, 162], [255, 162], [251, 156], [240, 156], [253, 152], [261, 152], [277, 157], [268, 151], [255, 143], [260, 142], [267, 145], [271, 149], [273, 154], [258, 146], [257, 131], [256, 134], [248, 137], [260, 137], [260, 134], [271, 137], [276, 138], [276, 144], [289, 144], [285, 150], [294, 150], [298, 149], [301, 145], [292, 145], [282, 134], [276, 134], [283, 127], [282, 116], [277, 113], [283, 113], [288, 106], [296, 106], [297, 113], [297, 118], [298, 118], [310, 122], [310, 128], [300, 130], [300, 140], [292, 129], [292, 114], [283, 122], [289, 122], [299, 122], [299, 134], [294, 134], [288, 124], [314, 121], [311, 113], [308, 110], [304, 96], [299, 90], [299, 82], [305, 87], [309, 94], [311, 101], [312, 102], [314, 107], [320, 112], [320, 115], [326, 116], [323, 109], [321, 102], [321, 94], [321, 90], [328, 90], [328, 88], [316, 88], [316, 84], [307, 84], [290, 77], [289, 88], [289, 97], [278, 97], [268, 106], [268, 110], [261, 105], [255, 103], [244, 103], [252, 100], [252, 91], [252, 82], [242, 78], [252, 78], [259, 78], [264, 87], [267, 92], [272, 91], [272, 83], [264, 83], [260, 79], [276, 79], [283, 84], [283, 94], [289, 94], [284, 86], [272, 77], [253, 110], [248, 110], [239, 110], [234, 114], [222, 125], [219, 127], [219, 131], [219, 138], [219, 141], [224, 139], [224, 135], [225, 130], [232, 136], [240, 138], [237, 131], [237, 118], [248, 120], [256, 122], [262, 127], [255, 118], [245, 110], [207, 129], [199, 134], [195, 134], [188, 130], [180, 130], [165, 129], [156, 129], [165, 128], [173, 125], [185, 126], [193, 126], [201, 124], [204, 123], [208, 116], [214, 114], [207, 114], [196, 114], [183, 121], [183, 111], [189, 117], [196, 112], [172, 126], [164, 126], [159, 114], [174, 106], [186, 106], [192, 105], [184, 105], [184, 96], [173, 96], [163, 111], [159, 110], [152, 110], [168, 110], [171, 106], [183, 98], [193, 101], [219, 96], [225, 97], [225, 104], [232, 92], [240, 92], [237, 86], [229, 86], [216, 88], [214, 79], [203, 79], [203, 75], [212, 75], [221, 75], [229, 80], [230, 89], [217, 88], [217, 77], [228, 77], [228, 69], [235, 71], [240, 71], [244, 66], [236, 54], [236, 62], [232, 68], [229, 61], [216, 61], [212, 58], [212, 47], [212, 39], [214, 28], [215, 48], [225, 55], [236, 55], [202, 65], [202, 54], [202, 44], [202, 24], [198, 32], [199, 38], [192, 38], [185, 38], [174, 42], [174, 48], [178, 51], [184, 51], [194, 55], [191, 68], [182, 68], [174, 69], [167, 67], [153, 59], [153, 49], [147, 49], [152, 58], [152, 74], [154, 83], [161, 83], [165, 88], [153, 97], [153, 89], [152, 82], [168, 88], [168, 101], [156, 102], [156, 119], [173, 110], [184, 110], [177, 106], [160, 106], [145, 125], [137, 122], [131, 120], [124, 120], [122, 118], [113, 118], [114, 111], [129, 111], [140, 110], [143, 106], [137, 102], [127, 102], [119, 98], [126, 93], [139, 93], [139, 99], [141, 95], [128, 89], [118, 74], [128, 76], [135, 76], [141, 83], [141, 71], [137, 61], [137, 50], [129, 50], [118, 50], [109, 52], [112, 61], [123, 60], [134, 60], [129, 76], [121, 67], [124, 76], [123, 76], [111, 74], [128, 73], [109, 83], [109, 94], [105, 103], [102, 118], [92, 113], [98, 105], [99, 93], [94, 93], [94, 81], [99, 81], [100, 73], [100, 89], [100, 60], [100, 55], [105, 37], [101, 34], [93, 37], [90, 37], [90, 49], [99, 49], [88, 68], [80, 68], [78, 64], [88, 62], [86, 77], [76, 89], [71, 91], [71, 106], [78, 106], [82, 118], [84, 110], [71, 104], [76, 103], [76, 91], [78, 83], [85, 89], [83, 103], [83, 119], [76, 130], [62, 130], [68, 127], [74, 126], [83, 123], [62, 123], [56, 123], [59, 129], [59, 120], [49, 110], [46, 106], [56, 100], [62, 94], [62, 109], [72, 112], [67, 112], [57, 112], [61, 122], [60, 102], [52, 125], [44, 121], [36, 114], [32, 110], [20, 110], [22, 118], [35, 118], [44, 124], [32, 119], [22, 111], [44, 96], [36, 106], [36, 94], [32, 94], [35, 83], [44, 91], [52, 91], [52, 80], [59, 80], [62, 76], [62, 70], [47, 78], [55, 75], [64, 71], [64, 60], [58, 53], [58, 43], [65, 43], [65, 60], [76, 52], [73, 38], [76, 36], [93, 48], [89, 39], [99, 40], [98, 50], [94, 63], [117, 63], [131, 67], [131, 74], [142, 78], [140, 61], [124, 58], [124, 48], [136, 55], [236, 200], [228, 200], [226, 192], [232, 198], [238, 210], [248, 210], [236, 220], [230, 223], [230, 213], [175, 32], [172, 32], [171, 38], [184, 30]];
test('triangulates plain array', (t) => {
const d = new Delaunator([].concat(...points));
t.same(d.triangles, Delaunator.from(points).triangles);
t.end();
});
test('triangulates typed array', (t) => {
const d = new Delaunator(Float64Array.from([].concat(...points)));
t.same(d.triangles, Delaunator.from(points).triangles);
t.end();
});
test('constructor errors on invalid array', (t) => {
/* eslint no-new: 0 */
t.throws(() => {
new Delaunator({length: -1});
}, /Invalid typed array length/);
t.throws(() => {
new Delaunator(points);
}, /Expected coords to contain numbers/);
t.end();
});
test('produces correct triangulation', (t) => {
validate(t, points);
t.end();
});
test('issue #11', (t) => {
validate(t, [[516, 661], [369, 793], [426, 539], [273, 525], [204, 694], [747, 750], [454, 390]]);
t.end();
});
test('issue #24', (t) => {
validate(t, [[382, 302], [382, 328], [382, 205], [623, 175], [382, 188], [382, 284], [623, 87], [623, 341], [141, 227]]);
t.end();
});
test('issue #13', (t) => {
validate(t, [[4, 1], [3.7974166882130675, 2.0837249985614585], [3.2170267516619773, 3.0210869309396715], [2.337215067329615, 3.685489874065187], [1.276805078389906, 3.9872025288851036], [0.17901102978375127, 3.885476929518457], [-0.8079039091377689, 3.3940516818407187], [-1.550651407188842, 2.5792964886320684], [-1.9489192990517052, 1.5512485534497125], [-1.9489192990517057, 0.44875144655029087], [-1.5506514071888438, -0.5792964886320653], [-0.8079039091377715, -1.394051681840717], [0.17901102978374794, -1.8854769295184561], [1.276805078389902, -1.987202528885104], [2.337215067329611, -1.6854898740651891], [3.217026751661974, -1.021086930939675], [3.7974166882130653, -0.08372499856146409]]);
t.end();
});
test('robustness', (t) => {
const points = [[66.103648384371410, 68.588612471664760], [146.680713462100413, 121.680713462100428], [128.868896560467447, 117.261797559041411], [66.103648384371439, 68.588612471664774], [169.552139667571992, 146.133776538276890], [126.629392246050883, 181.111404660392082], [74.434448280233709, 78.630898779520691], [121.111404660392054, 153.370607753949116], [98.888595339607888, 186.629392246050855], [52.660668968140221, 63.178539267712423], [85.321337936280443, 86.357078535424832], [129.615705608064615, 173.901806440322616], [91.522409349774278, 162.346331352698143], [137.240951282800551, 112.240951282800537], [93.370607753949116, 158.888595339607917], [175, 150], [124.142135623730908, 184.142135623730979], [96.208227592327205, 94.083258291328988], [98.888595339607988, 153.370607753949059], [117.982006904420700, 109.535617803137270], [116.194470264303831, 108.267043413376910], [54.324378061245710, 62.306334965997713], [30.886889656046740, 47.726179755904141], [107.095117248373952, 101.809438047233129], [38.892261948632665, 52.594841299088443], [146.680713462100413, 121.680713462100399], [95.857864376269077, 155.857864376269020], [54.324378061245703, 62.306334965997706], [137.240951282800551, 112.240951282800551], [161.529565528607690, 140.440336826753821], [90.384294391935398, 166.098193559677383], [113.220729676874285, 93.717722494332946], [77.882918707497154, 74.870889977331813], [50, 60], [85.321337936280457, 86.357078535424847], [41.773779312093481, 55.452359511808289], [89.662189030622869, 81.153167482998867], [101.441459353748570, 87.435444988665906], [124.142135623730965, 155.857864376269048], [172.416455184654381, 148.166516582657948], [63.547558624186912, 70.904719023616522], [150.642675872560943, 132.714157070849694], [109.999999999999928, 190], [128.477590650225721, 177.653668647301827], [90, 169.999999999999943], [128.477590650225749, 162.346331352698200], [156.120475641400275, 131.120475641400275], [90.384294391935384, 173.901806440322502], [95.857864376268992, 184.142135623730894], [77.882918707497140, 74.870889977331799], [139.755786216514195, 124.987977314945553], [130, 170], [102.346331352698129, 188.477590650225693], [41.773779312093481, 55.452359511808282], [91.522409349774235, 177.653668647301714], [27.784523897265298, 45.189682598176865], [126.629392246050912, 158.888595339607974], [106.098193559677355, 189.615705608064587], [52.660668968140200, 63.178539267712395], [74.434448280233681, 78.630898779520677], [106.098193559677469, 150.384294391935384], [117.653668647301728, 188.477590650225749], [125, 100], [38.892261948632565, 52.594841299088379], [52.660668968140228, 63.178539267712416], [129.615705608064615, 166.098193559677440], [20, 40], [117.653668647301813, 151.522409349774278], [161.529565528607662, 140.440336826753821], [63.547558624186969, 70.904719023616564], [127.801189103500675, 102.801189103500675], [89.662189030622840, 81.153167482998853], [102.346331352698243, 151.522409349774250], [93.370607753949059, 181.111404660391968], [113.901806440322502, 189.615705608064615], [121.111404660391997, 186.629392246050940], [113.901806440322587, 150.384294391935384], [110.000000000000028, 150], [165.560237820700137, 140.560237820700137]];
validate(t, points);
validate(t, points.map(p => [p[0] / 1e9, p[1] / 1e9]));
validate(t, points.map(p => [p[0] / 100, p[1] / 100]));
validate(t, points.map(p => [p[0] * 100, p[1] * 100]));
validate(t, points.map(p => [p[0] * 1e9, p[1] * 1e9]));
validate(t, [[0.226270008640849, -0.5484478681473859], [0.22627000864084906, -0.5484478681473857], [0.766192698520777, -0.06114560279536302], [0.7661926985207771, -0.06114560279536302], [0.40151121510492016, 0.08616979557470032], [0.40151121510492027, 0.08616979557470034], [-0.41675996433129736, -0.5902787491305856], [-0.4167599643312972, -0.5902787491305853], [-0.2479064469635639, -0.7472011647497873], [-0.24790644696356384, -0.7472011647497872], [0.6078988481689899, -0.8087190266174613], [0.6078988481689901, -0.808719026617461], [0.6844238681986647, -0.22229148851718702], [0.6844238681986647, -0.222291488517187], [0.6486832941181451, 0.3706194950394349], [0.6486832941181452, 0.3706194950394349], [-0.5361048842131249, -0.16765691382574804], [-0.5361048842131245, -0.167656913825748], [0.4588358986737203, -0.9000280551977525], [0.4588358986737205, -0.9000280551977525], [0.3960651926938643, 0.19117525930527385], [0.39606519269386437, 0.1911752593052739], [0.30699987842448867, -0.4067155996580057], [0.3069998784244887, -0.4067155996580056], [0.47811583559881354, 0.4551485080955586], [0.47811583559881354, 0.4551485080955586], [0.5569494202770435, 0.3174275448747843], [0.5569494202770439, 0.3174275448747845], [-0.4277027605175392, 0.09695587866512022], [-0.4277027605175391, 0.09695587866512025], [-0.5748114807265807, -0.03838218657575568], [-0.5748114807265806, -0.03838218657575567], [-1.0317070883952917, -0.5245256032470283], [-1.031707088395291, -0.5245256032470283], [0.14712374452633492, 0.33141471681448986], [0.147123744526335, 0.33141471681448986], [-0.2834737219004291, -0.9271587984120542], [-0.2834737219004289, -0.9271587984120538], [-0.6098149486946731, 0.5553773725836295], [-0.6098149486946729, 0.5553773725836295], [1.1206314478250745, 0.3921423623286639], [1.1206314478250745, 0.39214236232866406], [0.4477538973665876, -0.04256704865570235], [0.4477538973665877, -0.04256704865570235], [-0.6156635308889042, -0.10817302193016937], [-0.6156635308889041, -0.10817302193016932], [0.17897362794557034, -0.04224227852769616], [0.17897362794557034, -0.04224227852769614], [-0.9646885789850332, -1.4563419829050452], [-0.9646885789850331, -1.456341982905045], [0.2911613415160255, 0.015655417967490592], [0.29116134151602563, 0.015655417967490596], [-0.3698918540831971, 0.6983267205999204], [-0.3698918540831969, 0.6983267205999205], [1.4056553730213062, -0.41615789580202767], [1.4056553730213066, -0.41615789580202767], [0.34141990921721344, -0.5679551502988661], [0.3414199092172136, -0.5679551502988661], [0.2957318137669341, 0.8416499601535058], [0.29573181376693425, 0.841649960153506], [0.035141462612931273, -0.45835970615650135], [0.03514146261293129, -0.45835970615650123], [-1.3263110033694971, 0.8223290351908346], [-1.326311003369497, 0.8223290351908346], [-0.18787969354847422, 1.4601214758378256], [-0.18787969354847417, 1.4601214758378258], [-0.5421684590742957, -0.5196118080038157], [-0.5421684590742956, -0.5196118080038157], [-0.15415956428809274, 0.2553265483092856], [-0.15415956428809266, 0.25532654830928564], [0.24744639466303925, 0.36561549310806263], [0.24744639466303933, 0.36561549310806274], [-0.007949225522230624, -0.4463313570187974], [-0.00794922552223062, -0.4463313570187972], [0.4314282749865176, 0.6907165244683744], [0.4314282749865177, 0.6907165244683744], [0.22721916356346672, -1.145924985720078], [0.22721916356346675, -1.1459249857200775], [0.11627266697915434, 0.5679584977485386], [0.11627266697915438, 0.5679584977485389], [-0.004760241854834868, 1.341758406463988], [-0.004760241854834866, 1.3417584064639887], [0.34070213758085, -0.4524446934513693], [0.3407021375808501, -0.45244469345136923], [0.8842875090593054, -0.4369329059094983], [0.8842875090593055, -0.43693290590949824], [0.1514286184534766, -0.17725085421066233], [0.15142861845347666, -0.17725085421066225], [-0.4255258812089902, -0.48986352859695054], [-0.42552588120899015, -0.4898635285969505], [0.9377261482762783, -0.1443481348548356], [0.9377261482762784, -0.14434813485483552], [0.04260345503852292, 0.951377045867543], [0.04260345503852292, 0.951377045867543], [0.305243584013604, -0.3875472629266138], [0.305243584013604, -0.3875472629266138], [0.03603755940893599, 0.34504467425927055], [0.036037559408936, 0.34504467425927055], [0.7432869522329792, -0.7836440067269177], [0.7432869522329795, -0.7836440067269175]]);
validate(t, [[0.226270008640849, -0.5484478681473859], [0.22627000864084906, -0.5484478681473857], [0.766192698520777, -0.06114560279536302], [0.7661926985207771, -0.06114560279536302], [0.40151121510492016, 0.08616979557470032], [0.40151121510492027, 0.08616979557470034], [-0.41675996433129736, -0.5902787491305856], [-0.4167599643312972, -0.5902787491305853], [-0.2479064469635639, -0.7472011647497873], [-0.24790644696356384, -0.7472011647497872], [0.6078988481689899, -0.8087190266174613], [0.6078988481689901, -0.808719026617461], [0.6844238681986647, -0.22229148851718702], [0.6844238681986647, -0.222291488517187], [0.6486832941181451, 0.3706194950394349], [0.6486832941181452, 0.3706194950394349], [-0.5361048842131249, -0.16765691382574804], [-0.5361048842131245, -0.167656913825748], [0.4588358986737203, -0.9000280551977525], [0.4588358986737205, -0.9000280551977525], [0.3960651926938643, 0.19117525930527385], [0.39606519269386437, 0.1911752593052739], [0.30699987842448867, -0.4067155996580057], [0.3069998784244887, -0.4067155996580056], [0.47811583559881354, 0.4551485080955586], [0.47811583559881354, 0.4551485080955586], [0.5569494202770435, 0.3174275448747843], [0.5569494202770439, 0.3174275448747845], [-0.4277027605175392, 0.09695587866512022], [-0.4277027605175391, 0.09695587866512025], [-0.5748114807265807, -0.03838218657575568], [-0.5748114807265806, -0.03838218657575567], [-1.0317070883952917, -0.5245256032470283], [-1.031707088395291, -0.5245256032470283], [0.14712374452633492, 0.33141471681448986], [0.147123744526335, 0.33141471681448986], [-0.2834737219004291, -0.9271587984120542], [-0.2834737219004289, -0.9271587984120538], [-0.6098149486946731, 0.5553773725836295], [-0.6098149486946729, 0.5553773725836295], [1.1206314478250745, 0.3921423623286639], [1.1206314478250745, 0.39214236232866406], [0.4477538973665876, -0.04256704865570235], [0.4477538973665877, -0.04256704865570235], [-0.6156635308889042, -0.10817302193016937], [-0.6156635308889041, -0.10817302193016932], [0.17897362794557034, -0.04224227852769616], [0.17897362794557034, -0.04224227852769614], [-0.9646885789850332, -1.4563419829050452], [-0.9646885789850331, -1.456341982905045], [0.2911613415160255, 0.015655417967490592], [0.29116134151602563, 0.015655417967490596], [-0.3698918540831971, 0.6983267205999204], [-0.3698918540831969, 0.6983267205999205], [1.4056553730213062, -0.41615789580202767], [1.4056553730213066, -0.41615789580202767], [0.34141990921721344, -0.5679551502988661], [0.3414199092172136, -0.5679551502988661], [0.2957318137669341, 0.8416499601535058], [0.29573181376693425, 0.841649960153506], [0.035141462612931273, -0.45835970615650135], [0.03514146261293129, -0.45835970615650123], [-1.3263110033694971, 0.8223290351908346], [-1.326311003369497, 0.8223290351908346], [-0.18787969354847422, 1.4601214758378256], [-0.18787969354847417, 1.4601214758378258], [-0.5421684590742957, -0.5196118080038157], [-0.5421684590742956, -0.5196118080038157], [-0.15415956428809274, 0.2553265483092856], [-0.15415956428809266, 0.25532654830928564], [0.24744639466303925, 0.36561549310806263], [0.24744639466303933, 0.36561549310806274], [-0.007949225522230624, -0.4463313570187974], [-0.00794922552223062, -0.4463313570187972], [0.4314282749865176, 0.6907165244683744], [0.4314282749865177, 0.6907165244683744], [0.22721916356346672, -1.145924985720078], [0.22721916356346675, -1.1459249857200775], [0.11627266697915434, 0.5679584977485386], [0.11627266697915438, 0.5679584977485389], [-0.004760241854834868, 1.341758406463988], [-0.004760241854834866, 1.3417584064639887], [0.34070213758085, -0.4524446934513693], [0.3407021375808501, -0.45244469345136923], [0.8842875090593054, -0.4369329059094983], [0.8842875090593055, -0.43693290590949824], [0.1514286184534766, -0.17725085421066233], [0.15142861845347666, -0.17725085421066225], [-0.4255258812089902, -0.48986352859695054], [-0.42552588120899015, -0.4898635285969505], [0.9377261482762783, -0.1443481348548356], [0.9377261482762784, -0.14434813485483552], [0.04260345503852292, 0.951377045867543], [0.04260345503852292, 0.951377045867543], [0.305243584013604, -0.3875472629266138], [0.305243584013604, -0.3875472629266138], [0.03603755940893599, 0.34504467425927055], [0.036037559408936, 0.34504467425927055], [0.7432869522329792, -0.7836440067269177], [0.7432869522329795, -0.7836440067269175], [-0.2963957383054346, -0.8541077824286829], [-0.2963957383054344, -0.8541077824286829], [-0.5957774790480242, -0.600709712349726], [-0.5957774790480241, -0.6007097123497258], [-0.16224562470708315, 0.34537414926581733], [-0.16224562470708306, 0.34537414926581733], [-0.7424662163367453, -0.41130625924230096], [-0.742466216336745, -0.41130625924230085], [-0.3624590396531042, -0.10563984421746442], [-0.3624590396531041, -0.10563984421746442], [-0.5392904110560361, -0.08518185259429017], [-0.5392904110560358, -0.08518185259429016], [-0.6778672159722301, 0.3431673449069855], [-0.6778672159722301, 0.3431673449069856], [0.36715717958832705, -0.5910728761089766], [0.36715717958832716, -0.5910728761089764], [-0.025023155416355747, 0.049551540818041445], [-0.025023155416355747, 0.04955154081804146], [-0.24819669042158904, 1.551076727423892], [-0.24819669042158898, 1.5510767274238921], [0.567193157662795, 0.11906741314152564], [0.567193157662795, 0.11906741314152564], [-0.040143445247768667, 0.26972252794743534], [-0.04014344524776866, 0.26972252794743534], [-0.2625294670890006, -0.9866393501381076], [-0.2625294670890005, -0.9866393501381073], [0.44843907219373064, 0.8048081754922025], [0.44843907219373064, 0.8048081754922027], [0.0645600537587031, 1.0817638655728792], [0.06456005375870313, 1.0817638655728798], [0.7675432088110417, -0.8812717114610312], [0.7675432088110417, -0.8812717114610309], [-0.08286494268897, -0.4289421536808215], [-0.08286494268896998, -0.42894215368082134], [-0.41612370586918423, 0.4886715855834002], [-0.41612370586918423, 0.48867158558340035], [0.19771717248920714, -0.1094932114101852], [0.19771717248920723, -0.10949321141018517], [0.3325743770435765, 0.3050059606614455], [0.3325743770435766, 0.3050059606614456], [-0.6076675750885592, -0.2488880571567846], [-0.6076675750885588, -0.24888805715678455], [-0.13216710101702264, -0.5066473875502346], [-0.13216710101702256, -0.5066473875502345], [0.8513876721292416, -0.5489241609365357], [0.8513876721292416, -0.5489241609365356], [-0.382289175026138, -0.47285448091622573], [-0.38228917502613796, -0.4728544809162256], [-0.22454842691828375, 0.6151379112650053], [-0.22454842691828367, 0.6151379112650056], [-0.8646014175536286, -0.42386569643498184], [-0.8646014175536284, -0.4238656964349818], [0.3117316226386966, 0.2627613357418179], [0.3117316226386967, 0.262761335741818], [-0.15249103914387663, 0.4395379613315442], [-0.15249103914387657, 0.4395379613315443], [-0.8535303948590758, -0.5171136892316436], [-0.8535303948590756, -0.5171136892316435], [0.5548908499705427, 0.7505471621260598], [0.5548908499705427, 0.7505471621260601], [-0.06051133138765111, 0.10241755750407933], [-0.0605113313876511, 0.10241755750407933], [0.5337288423213871, -0.4674709006951539], [0.5337288423213873, -0.4674709006951539], [0.05432726705458686, 0.7404240043361822], [0.054327267054586875, 0.7404240043361824], [0.18755513858332273, -0.33846461008241124], [0.1875551385833228, -0.33846461008241124], [-0.8591170242442958, 0.10096092456106642], [-0.8591170242442956, 0.10096092456106642], [-0.6532878500824677, 0.06191743854152687], [-0.6532878500824675, 0.06191743854152687], [-0.8539614587215372, -0.7324824009962402], [-0.8539614587215372, -0.7324824009962402], [-0.5863802667964559, -1.056546154929931], [-0.5863802667964556, -1.0565461549299304], [-0.1790469166305501, 0.2959320232236789], [-0.17904691663055006, 0.2959320232236789], [-0.1360834565364501, -0.11972427421383847], [-0.13608345653645007, -0.11972427421383845], [1.000279652308404, 0.5677840712010568], [1.0002796523084043, 0.5677840712010568], [-0.2539417014734854, -0.24824262411661902], [-0.2539417014734853, -0.24824262411661896], [-0.5513314210236925, 0.164455936053998], [-0.5513314210236921, 0.16445593605399808], [-0.35669084505120763, -0.5579365995173293], [-0.3566908450512076, -0.557936599517329], [-0.00479028693868494, 0.5747959597699825], [-0.004790286938684939, 0.5747959597699829], [0.9274618857336762, 0.3137388167061812], [0.9274618857336765, 0.3137388167061813], [-0.1582654462645559, 0.08532244403569378], [-0.1582654462645559, 0.08532244403569382], [-0.7338606250043278, 0.03884536523072413], [-0.7338606250043278, 0.038845365230724134], [0.441630546674704, -0.4757978998267975], [0.4416305466747042, -0.4757978998267975], [-0.340639188849867, -0.016461235375619054], [-0.340639188849867, -0.01646123537561905], [0.6944973204450795, -0.05127049077067958], [0.6944973204450798, -0.051270490770679564], [0.05692195764635159, -0.4860234898913355], [0.05692195764635161, -0.4860234898913355], [-0.34909544551668503, 0.07925987763994416], [-0.3490954455166849, 0.07925987763994416], [0.020842670418798892, -0.18962128485770935], [0.020842670418798902, -0.1896212848577093], [-0.24296262993119017, -0.7557062436624338], [-0.24296262993119008, -0.7557062436624334], [0.07767785036524773, -0.0756745138376198], [0.07767785036524774, -0.0756745138376198], [-0.5383587124935423, 0.3149908402335876], [-0.538358712493542, 0.3149908402335876], [-0.3672547557130592, 0.8497352282145765], [-0.3672547557130592, 0.8497352282145768], [1.0306858576839981, 0.6132170100848149], [1.0306858576839986, 0.6132170100848152], [0.026403641820751278, -0.11123958700346126], [0.02640364182075129, -0.11123958700346125], [-0.39673068933170313, 0.7365210212380586], [-0.3967306893317031, 0.7365210212380586], [-0.273859110739041, 0.15083421880672626], [-0.2738591107390409, 0.15083421880672626], [-0.7502503591118193, -0.6273750425323015], [-0.7502503591118191, -0.6273750425323014], [1.040458273889268, 0.3592162639445413], [1.0404582738892683, 0.3592162639445414], [-0.30951481303178596, -0.7990197975684153], [-0.30951481303178585, -0.7990197975684152], [-0.3049861667890695, 1.6737307580052914], [-0.30498616678906937, 1.673730758005292], [0.601935475297747, 1.1660575124169412], [0.601935475297747, 1.1660575124169419], [0.8838992370838099, 0.2656415636074353], [0.8838992370838102, 0.2656415636074353], [-0.5085727248068516, -0.23584500534815295], [-0.5085727248068515, -0.2358450053481529], [0.5396217328637709, -0.39810497658583466], [0.5396217328637712, -0.39810497658583466], [0.8665494841240842, 0.11624211166929022], [0.8665494841240843, 0.11624211166929023], [-0.51942267345288, 0.5395224235439922], [-0.5194226734528796, 0.5395224235439922], [0.19088288221197763, -0.4663336215970121], [0.19088288221197763, -0.4663336215970119], [-0.23194847381262582, 0.21901474700861162], [-0.23194847381262573, 0.21901474700861162], [0.8359436402369345, -0.2679779650730807], [0.8359436402369346, -0.2679779650730805], [0.4468309121482219, 0.724738511770195], [0.4468309121482219, 0.7247385117701953], [0.5963791684457523, 0.8746079737915003], [0.5963791684457525, 0.8746079737915007], [-0.16268657840268694, -0.10458689278692812], [-0.16268657840268685, -0.10458689278692809], [0.15167543844454376, 0.3810633395493045], [0.1516754384445438, 0.3810633395493046], [0.3175047149330903, -0.4680659139099735], [0.31750471493309046, -0.4680659139099735], [0.24518019737678892, 0.14105859064554405], [0.24518019737678892, 0.1410585906455441], [0.1337014618382204, 0.216053384319761], [0.1337014618382205, 0.21605338431976104], [-0.5196743788563577, -0.24381508621133063], [-0.5196743788563577, -0.24381508621133063], [0.16145768845022127, -0.18548235309792105], [0.16145768845022135, -0.18548235309792097], [0.5267956022472777, -0.07806817831728718], [0.5267956022472777, -0.07806817831728716], [0.2690528801662905, 0.007775444056135339], [0.2690528801662905, 0.00777544405613534], [0.7565821160819859, -0.3047749278545374], [0.7565821160819859, -0.30477492785453736], [-0.7016467625353928, 0.04470959700747512], [-0.7016467625353925, 0.04470959700747514], [0.2415239307661166, 0.2972238198129453], [0.24152393076611664, 0.2972238198129453], [0.2284592008150542, -0.6608245027366711], [0.2284592008150542, -0.6608245027366711], [0.2123088556780684, 0.01782161739519142], [0.21230885567806848, 0.017821617395191426], [-0.14619514581307758, -0.8833238459080084], [-0.14619514581307758, -0.8833238459080082], [0.1989466009909055, -0.6118402241082294], [0.1989466009909055, -0.6118402241082291], [0.49059993119084305, -0.16493514201871323], [0.4905999311908431, -0.1649351420187132], [-0.4129648372506063, -0.05944366961592451], [-0.4129648372506062, -0.059443669615924496], [0.586485692893329, 0.3271185970911774], [0.5864856928933292, 0.32711859709117747], [-0.06023227911161408, -0.7107842875157466], [-0.06023227911161407, -0.7107842875157466], [0.6310359079249456, 0.29992699270395096], [0.6310359079249456, 0.29992699270395107], [-0.6703089300986523, 0.6107470941705689], [-0.670308930098652, 0.6107470941705689], [0.5005957282133777, 0.01407262429060302], [0.500595728213378, 0.014072624290603021], [-0.18934890988546538, -0.9372780070318394], [-0.1893489098854653, -0.9372780070318394], [-0.2863087126284564, -0.40444718862380247], [-0.28630871262845636, -0.4044471886238023], [1.190084782443751, 0.5322874598725964], [1.1900847824437517, 0.5322874598725967], [0.1341442916393324, -0.8420626196661292], [0.13414429163933247, -0.8420626196661289], [-0.7649861084427345, -0.7071073574041574], [-0.7649861084427344, -0.7071073574041573], [-0.362881463482392, 0.4530261596665785], [-0.3628814634823919, 0.45302615966657866], [0.13437240869925704, 0.0763221848731111], [0.13437240869925712, 0.0763221848731111], [1.0481657649638807, -0.004257185833033583], [1.0481657649638814, -0.004257185833033581], [-0.7474948815245823, -0.9786844358659653], [-0.7474948815245823, -0.9786844358659653], [0.12735871993303205, -0.3185548367971229], [0.12735871993303208, -0.31855483679712276], [0.36855220211615, -0.5588123239347687], [0.36855220211615003, -0.5588123239347685], [-0.18314335566244416, -0.5442250179734792], [-0.18314335566244408, -0.544225017973479], [0.08693873231351551, -0.6447286294698766], [0.08693873231351551, -0.6447286294698766], [-0.05481436374055537, 0.20956141264894845], [-0.05481436374055537, 0.2095614126489485], [-0.27114580055426557, 0.12928945128646963], [-0.2711458005542655, 0.12928945128646968], [-0.4451760474692624, 0.46862844610576626], [-0.4451760474692623, 0.4686284461057663], [0.1341730804119372, -0.5079494612186458], [0.13417308041193723, -0.5079494612186456], [0.3257440025696646, 0.4153507171529827], [0.3257440025696647, 0.4153507171529827], [-1.2231311278955395, 0.5704928559937266], [-1.223131127895539, 0.5704928559937269], [-0.07375248343426033, -0.5524759317685063], [-0.0737524834342603, -0.5524759317685063], [-0.6413383012441964, -0.3892879515624541], [-0.6413383012441963, -0.38928795156245405], [-0.000884182358095037, -0.003185720596142992], [-0.0008841823580950368, -0.003185720596142991], [0.737566803637365, -0.7615040446353664], [0.7375668036373654, -0.761504044635366], [0.23446047289831606, 0.19035505393365781], [0.23446047289831606, 0.19035505393365784], [-0.07211988377390469, -0.13169854040950443], [-0.07211988377390469, -0.13169854040950443], [0.18143877838398617, 1.132013860293268], [0.18143877838398625, 1.1320138602932683], [-0.22066292105815377, -0.19117568196580417], [-0.22066292105815372, -0.19117568196580417], [-0.4347453028054331, 0.5888401578252912], [-0.43474530280543294, 0.5888401578252915], [0.24005504098930414, 0.8021441938204985], [0.24005504098930416, 0.8021441938204986], [-0.34929799898447755, -0.261775797658851], [-0.34929799898447744, -0.26177579765885084], [0.3490077668059596, -0.007752337813972554], [0.3490077668059597, -0.0077523378139725515], [-0.6025788068137587, 0.46068756636034236], [-0.6025788068137585, 0.4606875663603424], [-0.7122333712891852, 0.26308462754739115], [-0.7122333712891852, 0.26308462754739115], [0.15764425398809745, 0.18964163728856187], [0.15764425398809748, 0.18964163728856193], [0.1853787174021873, -0.6789040209134625], [0.18537871740218737, -0.6789040209134621], [0.634911453390334, 0.13339968677329644], [0.6349114533903343, 0.13339968677329647], [-1.2578415170869763, 0.2517963788258869], [-1.2578415170869757, 0.2517963788258869], [0.1400845593846478, 0.40593141307431857], [0.14008455938464787, 0.4059314130743186], [-0.7095485725512902, 0.8225233205642902], [-0.7095485725512899, 0.8225233205642903], [-1.1960848307098382, 0.17404679607890605], [-1.196084830709838, 0.17404679607890608], [0.21828979413603433, -0.3280264848946596], [0.2182897941360344, -0.3280264848946595], [0.2662387358530971, 0.3568929623829047], [0.26623873585309726, 0.3568929623829048], [0.24305026107578037, -0.23724020319018074], [0.24305026107578043, -0.23724020319018066], [-0.3433832627650342, 0.3389417719770061], [-0.34338326276503406, 0.3389417719770061], [-0.0437269904343551, 0.5869495454659391], [-0.04372699043435508, 0.5869495454659392], [-0.12109570623011018, -0.8772834803160542], [-0.12109570623011016, -0.8772834803160542], [0.09631218123471452, -0.12108887934946555], [0.09631218123471456, -0.12108887934946555], [-0.41811390046020547, 0.8465092639539217], [-0.4181139004602053, 0.8465092639539218], [-0.34396631561394114, 0.8358904797678759], [-0.343966315613941, 0.8358904797678759], [0.43085589801084057, -0.16054297058369527], [0.4308558980108406, -0.1605429705836952], [-0.19787245165430847, 0.8949780141072381], [-0.19787245165430842, 0.8949780141072381], [-0.5907860100454578, 0.18974221311023962], [-0.5907860100454575, 0.18974221311023964], [-0.5306691342020886, -0.7275053842709899], [-0.5306691342020886, -0.7275053842709899], [-0.345074608245379, 1.207589321519286], [-0.34507460824537883, 1.207589321519286], [-0.32302823411726667, 0.08250252511437048], [-0.32302823411726667, 0.0825025251143705], [-0.1000939664088763, -1.056428113867832], [-0.10009396640887627, -1.056428113867832], [0.0057223538613018765, -0.07997801149692216], [0.005722353861301878, -0.07997801149692216], [-1.0232923766303312, 0.22905472765407248], [-1.0232923766303312, 0.22905472765407253], [-0.04071787429636753, 0.03839904161757046], [-0.04071787429636751, 0.03839904161757047], [-0.5114614823431506, -0.0673439850879256], [-0.5114614823431503, -0.06734398508792559], [-0.033395285925899576, -0.25197193535594753], [-0.03339528592589957, -0.2519719353559475], [-1.3238866550876203, -0.34335648499193994], [-1.3238866550876196, -0.3433564849919398], [0.3098949809621799, -0.692558554406312], [0.30989498096218, -0.6925585544063119], [-0.7778172969650805, -0.7251725696504421], [-0.7778172969650804, -0.7251725696504421], [0.5832467520992983, -0.0005585979375463679], [0.5832467520992983, -0.0005585979375463677], [0.6402717430536337, -0.24460516745019825], [0.6402717430536337, -0.24460516745019825], [0.3744231501345624, 0.23752933224278633], [0.37442315013456257, 0.23752933224278638], [-0.5526534599107001, 0.2959174882702319], [-0.5526534599106999, 0.29591748827023195], [0.0870980709703463, 0.011155933053077993], [0.08709807097034632, 0.011155933053077997], [0.10294466025799387, 0.6246279155358483], [0.10294466025799387, 0.6246279155358484], [0.7907530514131953, 0.7968130944966136], [0.7907530514131955, 0.796813094496614], [-0.06771348768905705, -0.19742894579933645], [-0.06771348768905704, -0.19742894579933642], [1.7336246702438183, -0.08111369728186346], [1.7336246702438185, -0.08111369728186343], [0.39279504341227045, -0.2803428186493195], [0.39279504341227056, -0.2803428186493194], [-0.3837990187335033, 0.5817465996045292], [-0.38379901873350314, 0.5817465996045292], [-0.15897299229161954, 0.2123178635236439], [-0.15897299229161949, 0.21231786352364398], [1.2871753315186103, -0.2936546706485327], [1.2871753315186105, -0.2936546706485326], [-0.28157817609809926, 0.015215204873323618], [-0.28157817609809926, 0.015215204873323621], [-0.8407785771058587, 0.11715953275528568], [-0.8407785771058583, 0.11715953275528568], [0.057427665729494065, 0.17741033446395021], [0.057427665729494086, 0.17741033446395027], [-0.3919333534914909, -0.8777063099779623], [-0.3919333534914909, -0.8777063099779623], [1.046062759037447, 0.12566529633175702], [1.0460627590374476, 0.1256652963317571], [0.05208282489856039, 0.23074154552008772], [0.05208282489856039, 0.23074154552008772], [0.3090093991217477, -0.28949051651550656], [0.3090093991217478, -0.2894905165155065], [-0.903992079888195, -0.08968028913527537], [-0.903992079888195, -0.08968028913527537], [0.1114034542194284, -0.1420055490952354], [0.11140345421942845, -0.1420055490952354], [0.49928483909803145, -1.031860401303775], [0.49928483909803145, -1.031860401303775], [-0.25021332122685536, -0.23430348924020267], [-0.2502133212268553, -0.23430348924020258], [0.45788605189844944, 0.008986832993373578], [0.45788605189844944, 0.008986832993373583], [0.9922986143818168, -0.3970601247358978], [0.9922986143818171, -0.3970601247358978], [0.3242247399299542, 0.00883592005445788], [0.3242247399299542, 0.008835920054457881], [0.6104748391149722, -0.1588370496187479], [0.6104748391149722, -0.15883704961874784], [-0.2328772934092499, -0.28654852459626834], [-0.23287729340924987, -0.28654852459626823], [0.2591579326588679, -0.48250620169929226], [0.2591579326588679, -0.4825062016992922], [0.030769057057074042, -0.6677902182695195], [0.030769057057074042, -0.6677902182695192], [0.5724668628416123, 0.17684659209108886], [0.5724668628416124, 0.17684659209108886], [-0.1936816938025718, 0.017884183939394893], [-0.19368169380257177, 0.017884183939394897], [0.3927424946727771, -0.3589320240798228], [0.3927424946727773, -0.35893202407982266], [-0.13217719866296695, 0.4509072577920714], [-0.13217719866296687, 0.4509072577920715], [0.7771200989698435, 0.07094000492318109], [0.7771200989698438, 0.07094000492318112], [-0.043208921594939775, -0.7058014850795868], [-0.043208921594939755, -0.7058014850795865], [-0.44161734737621083, 0.17508260808335738], [-0.44161734737621083, 0.17508260808335738], [0.3111521947954433, 0.5211230285003844], [0.3111521947954433, 0.5211230285003846], [-0.5089025606249975, -0.08897969566205755], [-0.5089025606249975, -0.08897969566205753], [-0.785274533858358, 0.2966023384405856], [-0.785274533858358, 0.2966023384405857], [0.13643734685972797, -0.5487534801505365], [0.136437346859728, -0.5487534801505362], [-0.5113536157192956, -0.38818343681854633], [-0.5113536157192953, -0.3881834368185463], [0.6482527388360249, -0.3660801422494009], [0.6482527388360252, -0.3660801422494007], [0.1219550825441264, 0.2636220365395331], [0.12195508254412644, 0.2636220365395332], [0.830646565838305, 0.05595258169938715], [0.8306465658383052, 0.055952581699387154], [0.02087272912166732, -0.2757601788166507], [0.02087272912166733, -0.2757601788166507], [-0.8969757534742673, -1.0096320440536182], [-0.8969757534742671, -1.0096320440536182], [0.281470556211261, -0.5392051870077439], [0.281470556211261, -0.5392051870077438], [0.09939015666169382, -0.0010699511947921958], [0.09939015666169386, -0.0010699511947921952], [-0.002256115172019346, -0.04020319566150099], [-0.0022561151720193458, -0.04020319566150097], [0.4504785560293585, 0.373102472756903], [0.4504785560293585, 0.3731024727569031], [0.5231672603524817, 0.16985255790851625], [0.5231672603524821, 0.16985255790851628], [-0.7514640400004967, 0.07080018087746165], [-0.7514640400004965, 0.07080018087746165], [0.13303832542382837, 0.2602273203264872], [0.1330383254238284, 0.2602273203264874], [0.19343395931079577, -0.5502548672222486], [0.1934339593107958, -0.5502548672222483], [-0.20823169078587966, -0.925945416171643], [-0.20823169078587964, -0.925945416171643], [-1.0354112179615744, 0.9009086420084467], [-1.035411217961574, 0.9009086420084467], [-0.13833287790394402, 0.33595123313495734], [-0.13833287790394397, 0.3359512331349575], [-0.48681401106341476, 0.012840401303908289], [-0.4868140110634147, 0.012840401303908292], [-0.38580806564875847, -0.3414309718415358], [-0.3858080656487583, -0.3414309718415357], [-0.387387928447792, 0.3363647167396555], [-0.387387928447792, 0.3363647167396555], [-0.7289577885281368, 0.11000344782305926], [-0.7289577885281364, 0.11000344782305929], [0.5996652640170703, -0.3788676471009784], [0.5996652640170704, -0.37886764710097826], [0.1184108904136601, -0.36481788339618465], [0.11841089041366011, -0.36481788339618465], [-0.030883796635844396, -0.2470002368704879], [-0.030883796635844393, -0.24700023687048783], [0.003754694361758959, -0.19869298401291166], [0.0037546943617589594, -0.1986929840129116], [0.11693502055240339, 0.2098964093295748], [0.11693502055240342, 0.20989640932957487], [-0.44372931923544234, 0.056472315155220026], [-0.44372931923544234, 0.05647231515522005], [-0.2835673309912712, -0.5631986234801009], [-0.2835673309912712, -0.5631986234801006], [0.6006827467154858, -0.5932750105917384], [0.6006827467154859, -0.593275010591738], [0.24363277450292076, -0.14517064380485928], [0.24363277450292084, -0.14517064380485925], [-0.4381173292277971, 0.8515765445495456], [-0.4381173292277971, 0.8515765445495457], [-0.4772264554892779, -0.4558040067081244], [-0.4772264554892779, -0.4558040067081244], [0.42511520260261526, -0.11760098022868892], [0.4251152026026154, -0.11760098022868892], [-0.317536469473846, -0.6047699984659938], [-0.31753646947384584, -0.6047699984659937], [-0.47946248289928994, -0.6870741625598951], [-0.47946248289928994, -0.6870741625598947], [0.24756054302633185, 0.738575212829874], [0.24756054302633188, 0.738575212829874], [0.30991707565082616, -0.1730076242522987], [0.3099170756508263, -0.17300762425229868], [0.1762415438802143, -0.45603299469545666], [0.17624154388021437, -0.4560329946954566], [-0.5684090790521096, -0.5323520385817601], [-0.5684090790521092, -0.5323520385817597], [1.1773067064626908, -0.31618798230516987], [1.177306706462691, -0.3161879823051697], [-0.2853416740347503, -0.7541701445620144], [-0.28534167403475025, -0.7541701445620143], [-0.3324739283651593, -0.041138670378205386], [-0.33247392836515915, -0.041138670378205386], [1.2664180977863824, -0.7401911722318033], [1.2664180977863828, -0.740191172231803], [0.4182693143279388, -0.7039334975576141], [0.41826931432793885, -0.703933497557614], [0.3813359912592416, -1.0453256669790556], [0.3813359912592416, -1.0453256669790554], [0.6509129030314083, -0.5412696201327558], [0.6509129030314084, -0.5412696201327558], [0.12018094767199916, 0.5279211204926886], [0.12018094767199916, 0.5279211204926887], [-0.45305717081196895, 0.008198588994697165], [-0.45305717081196883, 0.008198588994697166], [1.1671283999119613, -0.15065449704305311], [1.167128399911962, -0.1506544970430531], [-0.9008096320814036, 0.1402761647761295], [-0.9008096320814036, 0.14027616477612953], [-0.33154219658246964, 0.2612070104089204], [-0.3315421965824696, 0.2612070104089204], [-0.03280139984795011, -0.46647401981355685], [-0.032801399847950094, -0.46647401981355685], [0.01502591710973531, -0.5159959791954403], [0.015025917109735313, -0.51599597919544], [0.08126445056757484, -0.059451961687364746], [0.08126445056757486, -0.05945196168736473], [-0.4257412994811337, -0.20546840486340784], [-0.4257412994811336, -0.20546840486340776], [0.38799639318217627, 0.3512270928822726], [0.3879963931821764, 0.35122709288227266], [0.21154693848150546, -0.03634275654418231], [0.21154693848150552, -0.0363427565441823], [-0.23511045964865424, -0.3182820554745927], [-0.23511045964865424, -0.3182820554745926], [-0.27930734350964126, -0.34019779603069944], [-0.27930734350964115, -0.3401977960306993], [-0.7191434211894179, 0.018581718879366438], [-0.7191434211894179, 0.018581718879366448], [-0.020348708221664874, -0.11541476308320475], [-0.020348708221664864, -0.11541476308320471], [-0.869130537954744, 0.5168791425703672], [-0.8691305379547439, 0.5168791425703672], [-0.30797478551715907, 0.16894312777393505], [-0.30797478551715896, 0.16894312777393514], [-0.3412253953512523, -0.13703919671643483], [-0.3412253953512523, -0.1370391967164348], [-0.2363788997551411, 0.020160959823633195], [-0.2363788997551411, 0.020160959823633202], [-1.1342573157600304, -1.0490903515949865], [-1.1342573157600302, -1.0490903515949863], [-0.7951801524174422, -0.39048765852721024], [-0.7951801524174421, -0.39048765852721024], [-0.37682393173602985, -0.7154876526440125], [-0.37682393173602974, -0.7154876526440123], [-0.7261698499159233, 0.25576182656428276], [-0.7261698499159229, 0.25576182656428287], [0.6047122068958138, 0.3531321759458359], [0.604712206895814, 0.35313217594583596], [-0.3347865534686024, -0.44639370766792674], [-0.3347865534686024, -0.4463937076679267], [-0.3162737402922597, -0.6054254978296343], [-0.3162737402922597, -0.6054254978296342], [-0.38296113359720985, 1.055727844318872], [-0.38296113359720985, 1.0557278443188722], [-0.002541168924166004, -0.08959542143473792], [-0.0025411689241660036, -0.08959542143473788], [-0.46847678028199197, 0.3128229066138286], [-0.4684767802819919, 0.3128229066138288], [-0.7474510887594696, -0.11273520921655422], [-0.7474510887594695, -0.11273520921655422], [-0.10138857243233154, 0.6540514477632215], [-0.10138857243233154, 0.6540514477632217], [0.7025815823095183, -0.6472293123262207], [0.7025815823095184, -0.6472293123262207], [0.7918249248447928, -0.19424553454596438], [0.7918249248447932, -0.19424553454596438], [0.054665259285737594, -0.1426160884627486], [0.05466525928573761, -0.14261608846274854], [0.8678958225451003, 0.7680573370722297], [0.8678958225451004, 0.7680573370722298], [0.2527320686719843, -0.10300747956510839], [0.25273206867198444, -0.10300747956510836], [0.013030931888632663, 0.2996259196764839], [0.013030931888632665, 0.2996259196764839], [1.2101948699429645, 0.7680276029628541], [1.210194869942965, 0.7680276029628543], [0.001739080834353146, 0.7050842932559666], [0.0017390808343531463, 0.7050842932559666], [0.7920805263720672, -0.5649631474553106], [0.7920805263720672, -0.5649631474553105], [0.25575043599568525, 0.0889317006762374], [0.25575043599568525, 0.08893170067623742], [0.09261316731698108, 0.2703067174076892], [0.0926131673169811, 0.27030671740768925], [-0.5747802180771169, 0.08613851106223658], [-0.5747802180771168, 0.08613851106223662], [0.40507673833837643, -0.8945358512704514], [0.40507673833837643, -0.8945358512704511], [0.3856111747477545, -0.11976774680260635], [0.3856111747477546, -0.11976774680260632], [-0.25578702556512617, 0.3677566511805598], [-0.255787025565126, 0.36775665118055983], [-0.20976738975410314, 0.6671667928732408], [-0.20976738975410314, 0.6671667928732408], [-0.21007992057543357, 0.11101431938197523], [-0.21007992057543348, 0.11101431938197523], [-0.5538419739084758, -0.050566470413442005], [-0.5538419739084757, -0.05056647041344199], [-0.26983745787555147, -0.005254721629673997], [-0.2698374578755514, -0.0052547216296739965], [-0.31654388864740896, 0.4356887820490702], [-0.3165438886474089, 0.43568878204907036], [-0.6124922582532396, -0.22656761299178974], [-0.6124922582532395, -0.22656761299178974], [0.5136728866074527, -0.14672923625352396], [0.513672886607453, -0.14672923625352388], [-0.06100014188022765, -0.07483055132359873], [-0.06100014188022765, -0.07483055132359868], [0.0632389321030824, -0.3727037315430909], [0.06323893210308244, -0.3727037315430909], [-0.6239765829480394, -0.43378186506793615], [-0.6239765829480394, -0.43378186506793603], [-0.2962023614106011, -0.24082492622254642], [-0.296202361410601, -0.24082492622254636], [-0.08363974045743232, 0.4635673337808054], [-0.08363974045743229, 0.4635673337808054], [-0.07869730556773968, 0.7594146318238462], [-0.07869730556773967, 0.7594146318238463], [0.559161552723403, 0.26005051714491845], [0.5591615527234033, 0.2600505171449186], [0.009099193447173748, -0.8925628969298484], [0.00909919344717375, -0.892562896929848], [-0.01551647656911137, -0.38885814801603924], [-0.015516476569111365, -0.38885814801603924], [-0.01567035614455939, -0.3579485826040038], [-0.015670356144559385, -0.35794858260400375], [0.446781462990565, -0.052239411468506664], [0.446781462990565, -0.05223941146850665], [1.0710389841912518, -0.2731132034289364], [1.0710389841912522, -0.2731132034289364], [0.23533790163003582, -0.23476194158747798], [0.23533790163003585, -0.23476194158747793], [0.07915424936926652, 0.6036539628377416], [0.07915424936926652, 0.6036539628377419], [0.6311044368999582, -0.6562564634414947], [0.6311044368999585, -0.6562564634414947], [-0.21077148265812098, 0.032523815759867236], [-0.2107714826581209, 0.03252381575986725], [-0.7231240597670221, -0.006544627251553192], [-0.7231240597670221, -0.006544627251553192], [-0.08060584759784664, 0.13336777305165762], [-0.08060584759784663, 0.13336777305165762], [0.48597827619774187, -0.6069162101181359], [0.48597827619774203, -0.6069162101181359], [-0.4507483055292626, 0.19434862886898324], [-0.4507483055292625, 0.19434862886898324], [0.2827195867383647, -0.22519487430374507], [0.2827195867383647, -0.22519487430374502], [-0.8215093346304647, -0.03268014435976413], [-0.8215093346304647, -0.03268014435976413], [-0.11933763497114419, 0.25235131805383626], [-0.11933763497114419, 0.25235131805383626], [-0.050641541900826315, -0.05481336786080909], [-0.05064154190082631, -0.05481336786080908], [0.37639163137503584, -0.04913023720926801], [0.37639163137503595, -0.049130237209268006], [0.2754899163868257, -1.2892018379461803], [0.27548991638682585, -1.28920183794618], [0.19113786193208002, -0.49992907513642937], [0.1911378619320801, -0.4999290751364293], [-0.18408107881733532, -0.6738283284096425], [-0.18408107881733524, -0.6738283284096425], [0.26736586776080096, 0.35645201936711196], [0.2673658677608011, 0.35645201936711196], [1.1765511302564113, -0.5480893596413949], [1.176551130256412, -0.5480893596413949], [1.1542398998705217, -0.3147952918363603], [1.1542398998705217, -0.3147952918363603], [-0.6689853024562176, 0.8040377543458188], [-0.6689853024562172, 0.804037754345819], [0.24120212235388105, -0.07423471553787372], [0.2412021223538811, -0.0742347155378737], [0.5689391732853385, -0.4334628652354342], [0.5689391732853388, -0.43346286523543415], [-0.4229071860412019, 0.11827577249881677], [-0.4229071860412019, 0.11827577249881677], [-0.5721332694193333, 0.26812444739865027], [-0.5721332694193333, 0.26812444739865043], [-0.14648803653271852, 0.4305316791577641], [-0.1464880365327185, 0.43053167915776425], [0.05374623984152754, -0.4459959249147729], [0.053746239841527564, -0.4459959249147729], [0.5896530144495327, 0.07735649659442079], [0.589653014449533, 0.07735649659442081], [-0.25257596915203095, -0.1831343633500895], [-0.2525759691520309, -0.18313436335008942], [0.6519199000082152, 0.8113502122689806], [0.6519199000082153, 0.811350212268981], [-0.20987680281715365, 0.31018961232143716], [-0.2098768028171536, 0.3101896123214372], [0.488852615545995, -0.7694857263920457], [0.488852615545995, -0.7694857263920457], [0.32498664525642773, 0.35466894818618966], [0.3249866452564279, 0.3546689481861898], [-0.21867254773101694, 0.33653237135631914], [-0.21867254773101685, 0.3365323713563192], [-0.1628632057456908, 0.12513912098254698], [-0.16286320574569077, 0.12513912098254704], [-0.2482127546806861, 0.054592620932045616], [-0.24821275468068604, 0.05459262093204564], [0.19972864932719311, 0.48470032915534], [0.19972864932719311, 0.4847003291553401], [0.5194203708908046, 0.6086898891039105], [0.519420370890805, 0.6086898891039109], [0.19766219439600413, -0.624494348335875], [0.1976621943960042, -0.6244943483358748], [-0.6659766058933296, 0.5642507949642299], [-0.6659766058933294, 0.56425079496423], [0.6380303702196312, 0.7911458327140173], [0.6380303702196312, 0.7911458327140173], [-0.2639580944341406, 1.0973674142268384], [-0.26395809443414053, 1.0973674142268388], [-0.013043068475538544, -0.18048505417693753], [-0.013043068475538539, -0.1804850541769375], [-0.6177459783187123, -0.2779905668540201], [-0.6177459783187123, -0.27799056685401996], [0.6541020344580163, 0.582124792529954], [0.6541020344580166, 0.5821247925299543], [-1.0384774049322054, 0.8009193618277922], [-1.0384774049322048, 0.8009193618277922], [-0.1554306169575903, 0.44885645072316704], [-0.15543061695759022, 0.4488564507231671], [-0.21901225075291414, 0.029572470395186623], [-0.21901225075291408, 0.029572470395186626], [0.06665349581693292, 0.2278463140029154], [0.06665349581693296, 0.22784631400291547], [-0.18730209014152358, -0.44204961843797247], [-0.1873020901415235, -0.44204961843797247], [-0.8954194222707068, -0.09622762051569644], [-0.8954194222707068, -0.09622762051569644], [0.6876813467148475, -0.1006745035590906], [0.6876813467148476, -0.10067450355909059], [0.8020144882556199, -0.4557444532553835], [0.80201448825562, -0.4557444532553834], [0.11678579588295551, 0.4778013596576872], [0.11678579588295553, 0.4778013596576872], [-0.6173779479953273, -0.1463086195272349], [-0.6173779479953271, -0.1463086195272348], [0.04109570275886973, -0.38022576288843984], [0.04109570275886973, -0.3802257628884398], [0.8314003498756972, -0.48166469434786263], [0.8314003498756976, -0.4816646943478625], [-0.3417449594665635, 0.2351852756985343], [-0.34174495946656336, 0.23518527569853434], [-0.747231864230736, -0.05533196936496787], [-0.7472318642307357, -0.055331969364967856], [0.44786515872763016, -0.8581662077619436], [0.4478651587276303, -0.8581662077619435], [0.2394196493059546, 0.5685962507505915], [0.23941964930595466, 0.5685962507505915], [-0.47370747024486054, -0.518217306207919], [-0.4737074702448605, -0.5182173062079186], [-0.24686466238928517, 0.5140980999371543], [-0.24686466238928517, 0.5140980999371544], [0.4465869335283311, -0.37822156772624715], [0.4465869335283311, -0.378221567726247], [0.7216840280411014, -0.12155234552799939], [0.7216840280411017, -0.12155234552799934], [0.015204864396908546, 0.6376683618342354], [0.015204864396908548, 0.6376683618342357], [-0.42393694982300156, -0.5218089477315881], [-0.42393694982300145, -0.5218089477315878], [0.07415078821601045, 0.6371956908817733], [0.07415078821601047, 0.6371956908817734], [-0.1903574628038755, -0.38684400671343444], [-0.19035746280387544, -0.38684400671343444], [-0.3773559131237457, 0.0068579608273421355], [-0.3773559131237457, 0.006857960827342137], [0.08501466839094085, 0.27421860297639405], [0.08501466839094089, 0.2742186029763941], [1.3703190609240201, -0.6705242349995242], [1.3703190609240201, -0.6705242349995238], [0.22067502222484947, -0.42972719575427676], [0.22067502222484955, -0.4297271957542766], [0.4496324731373458, -0.5997904924904096], [0.44963247313734583, -0.5997904924904094], [0.4606769016215748, -0.4028663766293615], [0.4606769016215748, -0.4028663766293614], [0.20461881450521396, 0.23845839738985905], [0.20461881450521396, 0.2384583973898591], [-0.177021903697815, 0.0017472361069717779], [-0.17702190369781493, 0.0017472361069717785], [0.33088666738271627, 0.39635242461181414], [0.33088666738271644, 0.39635242461181425], [-0.5126793030962896, -0.9816818891160128], [-0.5126793030962894, -0.9816818891160127], [-0.20315580021343643, 0.25993483522132416], [-0.2031558002134364, 0.2599348352213242], [0.01157315314252727, -0.0752286580183012], [0.011573153142527272, -0.07522865801830117], [-0.2122874953702656, 1.0455265018271471], [-0.2122874953702656, 1.0455265018271478], [-0.4118959539781374, 0.2565463745780656], [-0.41189595397813733, 0.2565463745780657], [-0.40504807761153394, -0.826767279687959], [-0.40504807761153383, -0.8267672796879587], [0.8728370056581523, -0.8489146211330629], [0.8728370056581523, -0.8489146211330626], [-0.15484731030271964, 0.2978543674333216], [-0.15484731030271962, 0.2978543674333217], [0.9598395979151622, -0.021475535817715843], [0.9598395979151622, -0.021475535817715833], [-0.3813769756912948, 0.7192828208488169], [-0.38137697569129464, 0.719282820848817], [0.21951101473819934, 0.6480843500744788], [0.21951101473819934, 0.6480843500744791], [-0.3113427744080721, 0.045948715073330315], [-0.31134277440807195, 0.045948715073330336], [-0.16009981684527497, -0.17250123317199526], [-0.16009981684527497, -0.17250123317199526], [0.25568807750253153, 0.30423782531372767], [0.2556880775025317, 0.30423782531372784], [0.2534978588720535, 0.41258202395216825], [0.25349785887205356, 0.4125820239521684], [-0.22823188438717018, 0.3555909158613313], [-0.22823188438717018, 0.3555909158613314], [-0.043847734475191566, 0.546988883272136], [-0.04384773447519155, 0.5469888832721362], [0.0022848127328267687, 0.16581911916150355], [0.0022848127328267695, 0.16581911916150358], [-0.9664510167365821, 0.5772556019222926], [-0.9664510167365818, 0.5772556019222929], [0.19331577714046103, 0.16819098929912168], [0.1933157771404611, 0.16819098929912168], [0.880938028512706, 1.3996876457175011], [0.8809380285127063, 1.3996876457175018], [-0.6403207225525454, 0.2297596920614577], [-0.640320722552545, 0.22975969206145774], [-0.926993144927124, -0.7404608887419831], [-0.9269931449271237, -0.7404608887419828], [-0.30368277421537726, -0.5055446699316368], [-0.3036827742153772, -0.5055446699316366], [0.5466694604144853, 0.07004761038909013], [0.5466694604144854, 0.07004761038909016], [0.25500851421300097, -0.29367076034138706], [0.25500851421300114, -0.29367076034138695], [0.15138727668563495, -0.0049418965549759275], [0.151387276685635, -0.004941896554975927], [-0.43887856303510187, 0.8136477342030863], [-0.4388785630351018, 0.8136477342030866], [-0.33880265875092413, -0.31551224415527107], [-0.33880265875092397, -0.315512244155271], [1.377423681456482, 0.012704561359672462], [1.377423681456482, 0.012704561359672462], [-0.041263422421853435, 0.4035844851267748], [-0.041263422421853414, 0.40358448512677497], [-0.08610165644909173, -0.7986737010728233], [-0.08610165644909172, -0.7986737010728232], [0.3836918938530838, 0.8390085156051033], [0.38369189385308383, 0.8390085156051033], [-0.17307936456124118, -0.06474709047756155], [-0.1730793645612411, -0.06474709047756153], [-0.02753475823767776, -0.15870621273858665], [-0.02753475823767775, -0.15870621273858657], [-0.5116996522331295, -0.4553457116638264], [-0.5116996522331294, -0.45534571166382637], [0.6086269804673172, 0.015815755110900165], [0.6086269804673176, 0.015815755110900165], [-0.3066696359213093, -0.6490796718967194], [-0.3066696359213093, -0.6490796718967194], [0.2573582808012723, 0.49429943061451787], [0.25735828080127243, 0.4942994306145179], [-0.5573569025227104, 0.10864971359925568], [-0.5573569025227101, 0.1086497135992557], [0.10100854569812368, -0.5775400700305715], [0.10100854569812368, -0.5775400700305712], [0.16011849083924728, -0.5182501761924749], [0.1601184908392473, -0.5182501761924749], [1.1626364195660153, -0.027141868869618918], [1.162636419566016, -0.027141868869618915], [-0.45286020053725284, 0.46618578082394724], [-0.4528602005372528, 0.4661857808239473], [0.32258327609642495, -0.2102016160014837], [0.3225832760964251, -0.21020161600148368], [-0.4469041249092892, -0.30385833257152894], [-0.4469041249092891, -0.30385833257152894], [0.8377224062973287, -0.5225876068528582], [0.8377224062973289, -0.5225876068528581], [-0.35063350958529577, -0.44521824304962737], [-0.3506335095852957, -0.44521824304962726], [0.042917945172412694, -0.2699072536318396], [0.0429179451724127, -0.2699072536318395], [0.28617439894992625, -0.6241441143108587], [0.28617439894992625, -0.6241441143108584], [-0.21331655993940007, 1.1315954154549954], [-0.21331655993940002, 1.1315954154549959], [-0.7071603986591413, -0.0587365030909921], [-0.7071603986591409, -0.0587365030909921], [-0.43104678259786616, -0.4031905103539523], [-0.4310467825978661, -0.40319051035395215], [0.479647329346727, -0.6208557999362405], [0.47964732934672716, -0.6208557999362404], [-0.27104983788326825, 0.005338803231299233], [-0.2710498378832682, 0.0053388032312992354], [-0.0041329173810210895, 0.3935166528530436], [-0.004132917381021089, 0.39351665285304366]]);
t.end();
});
test('throws on small number of points', (t) => {
t.throws(() => {
Delaunator.from(points.slice(0, 1));
});
t.throws(() => {
Delaunator.from(points.slice(0, 2));
});
t.end();
});
test('throws on all-collinear input', (t) => {
t.throws(() => {
Delaunator.from([[0, 0], [1, 0], [2, 0], [3, 0]]);
});
t.end();
});
test('supports custom point format', (t) => {
const d = Delaunator.from(
[{x: 5, y: 5}, {x: 7, y: 5}, {x: 7, y: 6}],
p => p.x,
p => p.y);
t.same(d.triangles, [0, 2, 1]);
t.end();
});
function validate(t, points) {
const d = Delaunator.from(points);
// validate halfedges
for (let i = 0; i < d.halfedges.length; i++) {
const i2 = d.halfedges[i];
if (i2 !== -1 && d.halfedges[i2] !== i) {
t.fail('invalid halfedge connection');
}
}
t.pass('halfedges are valid');
// validate triangulation
const hullAreas = [];
for (let i = 0, len = d.hull.length, j = len - 1; i < len; j = i++) {
const [x0, y0] = points[d.hull[j]];
const [x, y] = points[d.hull[i]];
hullAreas.push((x - x0) * (y + y0));
}
const hullArea = sum(hullAreas);
const triangleAreas = [];
for (let i = 0; i < d.triangles.length; i += 3) {
const [ax, ay] = points[d.triangles[i]];
const [bx, by] = points[d.triangles[i + 1]];
const [cx, cy] = points[d.triangles[i + 2]];
triangleAreas.push(Math.abs((by - ay) * (cx - bx) - (bx - ax) * (cy - by)));
}
const trianglesArea = sum(triangleAreas);
const err = Math.abs((hullArea - trianglesArea) / hullArea);
if (err <= Math.pow(2, -51)) {
t.pass(`triangulation is valid: ${err} error`);
} else {
t.fail(`triangulation is broken: ${err} error`);
}
}
// Kahan and Babuska summation, Neumaier variant; accumulates less FP error
function sum(x) {
let sum = x[0];
let err = 0;
for (let i = 1; i < x.length; i++) {
const k = x[i];
const m = sum + k;
err += Math.abs(sum) >= Math.abs(k) ? sum - m + k : k - m + sum;
sum = m;
}
return sum + err;
}