triangulation.js
29.6 KB
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
var samples = {
"typical OSM building": [[661,112,661,96,666,96,666,87,743,87,771,87,771,114,750,114,750,113,742,113,742,106,710,106,710,113,666,113,666,112]],
"dude shape": [[280.35714,648.79075,286.78571,662.8979,263.28607,661.17871,262.31092,671.41548,250.53571,677.00504,250.53571,683.43361,256.42857,685.21933,297.14286,669.50504,289.28571,649.50504,285,631.6479,285,608.79075,292.85714,585.21932,306.42857,563.79075,323.57143,548.79075,339.28571,545.21932,357.85714,547.36218,375,550.21932,391.42857,568.07647,404.28571,588.79075,413.57143,612.36218,417.14286,628.07647,438.57143,619.1479,438.03572,618.96932,437.5,609.50504,426.96429,609.86218,424.64286,615.57647,419.82143,615.04075,420.35714,605.04075,428.39286,598.43361,437.85714,599.68361,443.57143,613.79075,450.71429,610.21933,431.42857,575.21932,405.71429,550.21932,372.85714,534.50504,349.28571,531.6479,346.42857,521.6479,346.42857,511.6479,350.71429,496.6479,367.85714,476.6479,377.14286,460.93361,385.71429,445.21932,388.57143,404.50504,360,352.36218,337.14286,325.93361,330.71429,334.50504,347.14286,354.50504,337.85714,370.21932,333.57143,359.50504,319.28571,353.07647,312.85714,366.6479,350.71429,387.36218,368.57143,408.07647,375.71429,431.6479,372.14286,454.50504,366.42857,462.36218,352.85714,462.36218,336.42857,456.6479,332.85714,438.79075,338.57143,423.79075,338.57143,411.6479,327.85714,405.93361,320.71429,407.36218,315.71429,423.07647,314.28571,440.21932,325,447.71932,324.82143,460.93361,317.85714,470.57647,304.28571,483.79075,287.14286,491.29075,263.03571,498.61218,251.60714,503.07647,251.25,533.61218,260.71429,533.61218,272.85714,528.43361,286.07143,518.61218,297.32143,508.25504,297.85714,507.36218,298.39286,506.46932,307.14286,496.6479,312.67857,491.6479,317.32143,503.07647,322.5,514.1479,325.53571,521.11218,327.14286,525.75504,326.96429,535.04075,311.78571,540.04075,291.07143,552.71932,274.82143,568.43361,259.10714,592.8979,254.28571,604.50504,251.07143,621.11218,250.53571,649.1479,268.1955,654.36208]],
"dude shape with holes": [[280.35714,648.79075,286.78571,662.8979,263.28607,661.17871,262.31092,671.41548,250.53571,677.00504,250.53571,683.43361,256.42857,685.21933,297.14286,669.50504,289.28571,649.50504,285,631.6479,285,608.79075,292.85714,585.21932,306.42857,563.79075,323.57143,548.79075,339.28571,545.21932,357.85714,547.36218,375,550.21932,391.42857,568.07647,404.28571,588.79075,413.57143,612.36218,417.14286,628.07647,438.57143,619.1479,438.03572,618.96932,437.5,609.50504,426.96429,609.86218,424.64286,615.57647,419.82143,615.04075,420.35714,605.04075,428.39286,598.43361,437.85714,599.68361,443.57143,613.79075,450.71429,610.21933,431.42857,575.21932,405.71429,550.21932,372.85714,534.50504,349.28571,531.6479,346.42857,521.6479,346.42857,511.6479,350.71429,496.6479,367.85714,476.6479,377.14286,460.93361,385.71429,445.21932,388.57143,404.50504,360,352.36218,337.14286,325.93361,330.71429,334.50504,347.14286,354.50504,337.85714,370.21932,333.57143,359.50504,319.28571,353.07647,312.85714,366.6479,350.71429,387.36218,368.57143,408.07647,375.71429,431.6479,372.14286,454.50504,366.42857,462.36218,352.85714,462.36218,336.42857,456.6479,332.85714,438.79075,338.57143,423.79075,338.57143,411.6479,327.85714,405.93361,320.71429,407.36218,315.71429,423.07647,314.28571,440.21932,325,447.71932,324.82143,460.93361,317.85714,470.57647,304.28571,483.79075,287.14286,491.29075,263.03571,498.61218,251.60714,503.07647,251.25,533.61218,260.71429,533.61218,272.85714,528.43361,286.07143,518.61218,297.32143,508.25504,297.85714,507.36218,298.39286,506.46932,307.14286,496.6479,312.67857,491.6479,317.32143,503.07647,322.5,514.1479,325.53571,521.11218,327.14286,525.75504,326.96429,535.04075,311.78571,540.04075,291.07143,552.71932,274.82143,568.43361,259.10714,592.8979,254.28571,604.50504,251.07143,621.11218,250.53571,649.1479,268.1955,654.36208,325,437,320,423,329,413,332,423,320.72342,480,338.90617,465.96863,347.99754,480.61584,329.8148,510.41534,339.91632,480.11077,334.86556,478.09046], [94,98]],
"complex OSM water": [[2293,4224,2294,4219,2280,4180,2288,4172,2283,4189,2301,4218,2299,4224,2347,4224,2344,4215,2351,4224,2371,4224,2379,4224,2375,4206,2363,4202,2346,4194,2371,4195,2376,4180,2383,4202,2429,4176,2431,4163,2439,4161,2438,4144,2464,4124,2457,4111,2467,4102,2473,4060,2482,4053,2488,4031,2467,3982,2456,3991,2456,4005,2451,3998,2451,4014,2432,4011,2433,4025,2427,4012,2415,4009,2438,4003,2419,3990,2411,3987,2391,4000,2391,3989,2374,3991,2382,3995,2363,4028,2364,4042,2380,4041,2389,4029,2387,4053,2412,4055,2376,4059,2389,4085,2381,4093,2371,4076,2363,4082,2372,4067,2362,4059,2347,4054,2349,4040,2344,4057,2325,4063,2322,4073,2332,4078,2325,4086,2317,4082,2308,4065,2321,4063,2299,4051,2312,4056,2326,4055,2325,4044,2302,4021,2315,4029,2324,4023,2333,4040,2335,4026,2349,4016,2333,3999,2318,4002,2333,3991,2321,3985,2350,4000,2350,3962,2331,3964,2340,3949,2332,3946,2341,3943,2345,3952,2358,3947,2350,3922,2362,3931,2363,3922,2368,3946,2377,3946,2388,3933,2378,3908,2389,3920,2393,3948,2401,3924,2400,3911,2382,3899,2388,3875,2366,3885,2350,3878,2340,3896,2327,3880,2323,3900,2313,3894,2300,3871,2307,3890,2331,3872,2317,3867,2345,3852,2343,3840,2351,3843,2348,3823,2339,3821,2341,3805,2350,3828,2379,3853,2385,3844,2368,3823,2370,3809,2362,3809,2361,3793,2372,3804,2379,3795,2376,3823,2388,3815,2402,3822,2393,3832,2384,3824,2404,3860,2407,3876,2416,3872,2418,3852,2427,3876,2409,3893,2429,3921,2484,3863,2478,3792,2440,3820,2439,3834,2438,3820,2426,3809,2435,3801,2421,3794,2429,3786,2406,3752,2424,3748,2440,3762,2431,3732,2415,3735,2412,3721,2391,3707,2381,3720,2382,3732,2370,3724,2382,3716,2372,3705,2380,3708,2378,3687,2368,3685,2349,3710,2338,3694,2337,3708,2324,3706,2327,3717,2316,3729,2323,3715,2309,3714,2318,3713,2311,3699,2332,3698,2334,3678,2356,3670,2343,3651,2332,3649,2335,3658,2324,3655,2323,3670,2324,3661,2311,3661,2332,3640,2316,3633,2286,3655,2302,3631,2277,3610,2269,3619,2250,3619,2250,3630,2239,3635,2244,3650,2228,3660,2236,3679,2226,3666,2207,3677,2199,3672,2235,3648,2232,3621,2240,3624,2249,3605,2229,3607,2219,3593,2209,3597,2218,3587,2202,3586,2201,3576,2180,3583,2177,3598,2178,3573,2165,3548,2153,3544,2148,3519,2154,3506,2139,3492,2141,3484,2149,3492,2186,3568,2207,3567,2233,3585,2231,3533,2248,3519,2248,3532,2238,3536,2247,3547,2238,3549,2237,3574,2260,3602,2261,3586,2272,3598,2294,3599,2288,3559,2300,3578,2303,3610,2324,3615,2341,3612,2342,3596,2330,3591,2342,3588,2346,3561,2348,3612,2363,3604,2365,3582,2374,3590,2376,3576,2386,3591,2403,3596,2387,3598,2370,3598,2364,3636,2379,3621,2387,3653,2400,3620,2414,3623,2402,3632,2397,3650,2411,3667,2410,3682,2427,3678,2420,3667,2425,3649,2443,3653,2426,3651,2433,3664,2429,3672,2440,3671,2440,3681,2426,3688,2454,3700,2457,3689,2462,3698,2456,3717,2499,3696,2488,3686,2498,3690,2499,3682,2520,3700,2503,3702,2499,3713,2510,3706,2518,3708,2513,3730,2530,3746,2521,3746,2546,3760,2549,3777,2574,3779,2550,3768,2536,3721,2551,3725,2555,3750,2578,3746,2564,3704,2554,3709,2542,3694,2563,3704,2571,3682,2602,3652,2577,3623,2568,3629,2581,3639,2576,3655,2561,3636,2560,3648,2549,3634,2524,3637,2531,3625,2564,3627,2537,3582,2530,3591,2534,3554,2522,3558,2519,3574,2506,3576,2504,3595,2493,3598,2502,3592,2505,3572,2513,3563,2502,3559,2517,3548,2527,3551,2533,3539,2518,3523,2503,3538,2485,3535,2479,3545,2478,3535,2467,3540,2466,3555,2454,3547,2443,3562,2450,3547,2437,3543,2462,3542,2459,3532,2470,3535,2477,3525,2500,3530,2496,3515,2515,3515,2527,3502,2503,3482,2481,3486,2453,3506,2462,3496,2461,3485,2496,3481,2490,3464,2467,3463,2479,3445,2458,3437,2430,3471,2391,3471,2403,3470,2410,3460,2428,3464,2450,3428,2435,3418,2426,3429,2437,3412,2418,3406,2415,3415,2388,3419,2411,3403,2395,3399,2404,3392,2385,3384,2366,3406,2347,3410,2384,3376,2370,3365,2347,3376,2327,3371,2376,3358,2372,3347,2357,3342,2331,3350,2334,3342,2361,3335,2363,3326,2321,3317,2303,3328,2312,3311,2320,3316,2270,3302,2257,3308,2263,3321,2248,3330,2257,3316,2246,3300,2238,3323,2227,3318,2227,3304,2243,3294,2253,3297,2249,3282,2232,3278,2242,3274,2242,3266,2258,3264,2257,3255,2269,3248,2292,3263,2278,3245,2259,3239,2278,3244,2281,3231,2266,3217,2252,3217,2250,3196,2228,3218,2220,3219,2237,3199,2215,3194,2243,3196,2237,3177,2209,3171,2189,3154,2157,3144,2144,3152,2151,3141,2139,3130,2122,3148,2113,3127,2125,3142,2130,3117,2147,3119,2149,3128,2167,3120,2169,3146,2187,3143,2212,3166,2224,3161,2225,3173,2243,3145,2244,3156,2235,3162,2254,3175,2272,3176,2289,3165,2286,3182,2274,3178,2268,3195,2304,3196,2310,3180,2323,3209,2339,3214,2349,3249,2359,3249,2357,3295,2359,3287,2385,3284,2368,3300,2393,3315,2388,3339,2401,3357,2414,3352,2410,3342,2422,3334,2417,3348,2435,3354,2416,3357,2420,3376,2436,3385,2452,3381,2444,3384,2447,3396,2466,3394,2479,3417,2490,3400,2499,3452,2529,3469,2531,3481,2547,3497,2554,3488,2565,3503,2579,3490,2569,3465,2591,3499,2589,3527,2600,3518,2606,3498,2604,3456,2589,3465,2591,3456,2572,3442,2583,3440,2582,3430,2571,3419,2557,3420,2570,3415,2580,3423,2580,3409,2530,3373,2587,3402,2595,3447,2604,3413,2598,3436,2609,3432,2601,3446,2614,3451,2635,3442,2644,3447,2655,3434,2646,3429,2646,3411,2632,3413,2650,3405,2646,3393,2610,3389,2619,3383,2603,3373,2616,3372,2623,3384,2646,3388,2650,3359,2612,3347,2641,3355,2643,3345,2654,3359,2648,3382,2662,3381,2654,3413,2659,3426,2673,3429,2673,3417,2685,3418,2679,3396,2695,3397,2684,3405,2693,3416,2686,3425,2676,3422,2684,3439,2669,3471,2676,3482,2688,3472,2684,3453,2711,3444,2698,3444,2710,3426,2702,3424,2716,3422,2737,3403,2731,3374,2746,3381,2744,3399,2765,3387,2745,3326,2735,3313,2715,3318,2724,3314,2739,3307,2666,3259,2658,3286,2668,3292,2656,3294,2655,3312,2642,3304,2656,3286,2645,3286,2653,3278,2644,3273,2662,3259,2637,3234,2591,3240,2555,3270,2578,3246,2574,3238,2585,3239,2596,3228,2583,3210,2576,3218,2580,3208,2545,3209,2529,3198,2517,3209,2513,3182,2491,3203,2495,3222,2488,3230,2483,3213,2491,3208,2476,3207,2486,3201,2483,3187,2471,3185,2460,3193,2466,3183,2452,3158,2426,3163,2418,3175,2434,3195,2435,3211,2424,3200,2426,3185,2413,3177,2403,3190,2405,3205,2395,3210,2398,3198,2383,3205,2384,3194,2400,3195,2414,3172,2393,3157,2362,3192,2364,3183,2356,3180,2371,3170,2364,3166,2379,3166,2360,3150,2394,3153,2398,3135,2401,3147,2408,3128,2395,3126,2386,3114,2377,3117,2371,3106,2351,3105,2343,3109,2360,3098,2380,3105,2376,3090,2355,3081,2362,3073,2358,3041,2339,3025,2334,3010,2314,3000,2335,3006,2349,3032,2359,3025,2370,3073,2384,3089,2388,3072,2411,3063,2422,3047,2417,3063,2394,3072,2384,3101,2400,3113,2418,3094,2412,3108,2423,3106,2426,3117,2446,3119,2446,3141,2466,3128,2456,3108,2460,3097,2471,3117,2487,3107,2470,3122,2479,3137,2485,3127,2499,3130,2506,3106,2528,3101,2529,3109,2515,3113,2529,3135,2526,3114,2541,3130,2558,3114,2561,3101,2548,3102,2535,3087,2555,3094,2544,3073,2562,3099,2576,3101,2585,3096,2580,3079,2588,3073,2605,3065,2615,3073,2632,3084,2628,3071,2620,3067,2600,3039,2612,3046,2634,3071,2642,3082,2646,3073,2646,3083,2672,3093,2677,3106,2670,3071,2652,3011,2659,2936,2636,2937,2629,2961,2636,2973,2617,2976,2629,2992,2618,2988,2599,2996,2613,2989,2613,2967,2604,2973,2609,2958,2598,2962,2586,2962,2583,2975,2581,2965,2565,2975,2574,2963,2537,2964,2536,2984,2535,2961,2512,2973,2501,2962,2531,2959,2530,2951,2538,2957,2553,2954,2578,2954,2604,2944,2618,2953,2610,2939,2574,2946,2541,2926,2576,2938,2618,2927,2634,2921,2552,2863,2521,2805,2498,2823,2494,2838,2503,2847,2493,2842,2455,2853,2485,2877,2459,2862,2443,2871,2449,2888,2429,2873,2430,2861,2416,2880,2421,2900,2408,2887,2388,2915,2420,2868,2412,2855,2441,2851,2455,2834,2447,2809,2421,2784,2423,2796,2395,2818,2400,2827,2387,2823,2384,2844,2376,2841,2367,2847,2371,2858,2348,2865,2347,2879,2325,2871,2326,2891,2308,2884,2298,2898,2297,2888,2283,2893,2283,2884,2312,2880,2294,2859,2316,2872,2315,2862,2349,2857,2333,2848,2360,2850,2358,2840,2369,2834,2339,2821,2309,2824,2310,2815,2328,2816,2342,2814,2340,2804,2357,2819,2360,2798,2365,2818,2379,2820,2391,2793,2409,2789,2392,2771,2392,2782,2384,2779,2370,2792,2368,2783,2356,2785,2366,2775,2375,2783,2373,2774,2389,2773,2360,2717,2360,2707,2377,2698,2356,2669,2364,2645,2355,2642,2360,2633,2339,2644,2342,2629,2324,2645,2312,2639,2310,2616,2275,2627,2229,2610,2219,2563,2234,2585,2252,2578,2270,2589,2286,2553,2266,2527,2255,2528,2235,2496,2221,2505,2230,2489,2220,2497,2225,2486,2210,2479,2185,2482,2190,2517,2171,2513,2171,2500,2162,2517,2144,2518,2121,2472,2096,2474,2076,2458,2094,2427,2087,2410,2095,2408,2104,2408,2105,2444,2126,2453,2136,2471,2152,2458,2142,2448,2159,2433,2196,2452,2216,2442,2225,2451,2232,2441,2223,2420,2217,2428,2223,2416,2215,2425,2219,2412,2210,2420,2213,2409,2207,2417,2197,2397,2170,2407,2154,2398,2150,2376,2132,2372,2132,2360,2143,2364,2143,2356,2158,2373,2176,2372,2166,2375,2167,2385,2192,2374,2202,2384,2199,2373,2208,2368,2225,2380,2228,2392,2250,2393,2253,2411,2257,2423,2246,2426,2257,2428,2246,2431,2257,2438,2248,2447,2257,2459,2268,2456,2269,2469,2276,2452,2286,2468,2285,2451,2294,2450,2295,2465,2304,2453,2304,2464,2340,2491,2352,2462,2339,2446,2342,2433,2357,2470,2345,2510,2362,2534,2389,2522,2408,2524,2409,2559,2418,2574,2398,2596,2450,2560,2456,2541,2445,2541,2461,2531,2440,2529,2437,2519,2467,2522,2474,2513,2460,2501,2437,2505,2447,2498,2433,2476,2447,2493,2439,2469,2449,2475,2456,2497,2462,2489,2477,2501,2489,2493,2488,2485,2468,2477,2473,2460,2461,2455,2462,2446,2486,2477,2507,2485,2509,2472,2518,2469,2505,2458,2514,2462,2522,2451,2512,2414,2493,2409,2505,2409,2516,2401,2517,2412,2533,2405,2519,2414,2522,2438,2554,2449,2525,2453,2527,2462,2541,2463,2529,2465,2524,2475,2542,2492,2521,2481,2517,2490,2527,2501,2492,2499,2494,2516,2475,2543,2487,2578,2466,2581,2461,2594,2470,2601,2458,2602,2471,2608,2458,2609,2470,2612,2468,2625,2455,2633,2475,2634,2454,2640,2456,2652,2468,2652,2462,2661,2481,2677,2481,2671,2499,2671,2501,2639,2527,2635,2513,2645,2511,2676,2515,2664,2565,2659,2565,2614,2563,2589,2571,2569,2587,2575,2604,2570,2572,2584,2572,2592,2587,2588,2584,2594,2594,2594,2578,2606,2594,2613,2626,2608,2630,2590,2619,2589,2633,2586,2634,2572,2642,2572,2638,2598,2635,2613,2642,2605,2618,2624,2622,2642,2604,2675,2611,2691,2626,2699,2643,2671,2620,2670,2642,2663,2624,2659,2628,2645,2640,2649,2635,2637,2645,2638,2653,2625,2660,2639,2647,2655,2655,2662,2676,2660,2684,2667,2676,2657,2698,2605,2754,2571,2743,2564,2753,2537,2723,2564,2687,2563,2673,2544,2627,2520,2633,2509,2617,2501,2613,2511,2594,2512,2615,2487,2591,2457,2597,2444,2587,2421,2599,2423,2602,2413,2570,2381,2538,2365,2525,2340,2498,2347,2511,2334,2508,2322,2495,2321,2485,2302,2459,2293,2458,2281,2468,2271,2483,2280,2486,2262,2498,2265,2487,2288,2503,2296,2517,2291,2528,2304,2551,2311,2558,2335,2562,2313,2552,2307,2548,2290,2562,2302,2567,2322,2591,2296,2574,2321,2565,2332,2589,2352,2601,2338,2593,2353,2600,2361,2636,2366,2638,2355,2646,2352,2643,2336,2651,2352,2658,2343,2653,2354,2661,2363,2644,2361,2642,2371,2651,2375,2635,2374,2639,2413,2650,2416,2631,2451,2641,2454,2642,2479,2671,2475,2702,2501,2717,2497,2726,2504,2731,2491,2721,2477,2735,2496,2746,2498,2734,2473,2764,2425,2742,2435,2741,2419,2752,2418,2756,2407,2743,2403,2756,2396,2745,2389,2756,2389,2761,2380,2763,2397,2787,2379,2794,2397,2800,2387,2792,2370,2803,2363,2795,2356,2764,2357,2762,2344,2761,2363,2753,2361,2742,2372,2750,2359,2741,2357,2715,2378,2719,2360,2702,2371,2709,2361,2695,2343,2713,2354,2722,2350,2714,2327,2722,2329,2731,2352,2740,2346,2732,2334,2750,2346,2752,2318,2744,2320,2736,2307,2723,2306,2725,2316,2723,2301,2714,2290,2710,2304,2702,2304,2702,2313,2693,2318,2685,2320,2686,2310,2704,2299,2703,2289,2683,2300,2675,2294,2673,2303,2665,2298,2653,2304,2662,2298,2657,2289,2669,2293,2668,2283,2678,2289,2677,2277,2683,2285,2694,2282,2693,2266,2677,2264,2675,2254,2653,2260,2654,2270,2642,2269,2647,2259,2635,2266,2620,2242,2636,2256,2652,2253,2629,2228,2623,2204,2645,2235,2669,2245,2658,2225,2646,2205,2660,2213,2677,2198,2668,2223,2680,2227,2677,2236,2717,2275,2695,2228,2713,2238,2722,2259,2737,2242,2740,2218,2722,2199,2719,2182,2727,2191,2730,2177,2742,2169,2733,2198,2738,2208,2744,2188,2756,2187,2748,2188,2743,2208,2755,2209,2747,2236,2750,2247,2760,2245,2743,2262,2742,2274,2755,2270,2766,2291,2770,2261,2783,2253,2783,2274,2797,2272,2797,2262,2806,2267,2808,2290,2796,2294,2795,2305,2809,2309,2833,2291,2851,2258,2836,2266,2826,2257,2845,2248,2833,2244,2833,2235,2813,2245,2805,2227,2787,2242,2773,2224,2789,2229,2797,2219,2781,2202,2798,2214,2808,2209,2809,2220,2825,2230,2834,2227,2830,2215,2839,2207,2840,2218,2849,2223,2860,2203,2848,2185,2836,2195,2819,2192,2836,2189,2837,2179,2825,2164,2824,2156,2794,2148,2799,2140,2790,2130,2813,2149,2822,2147,2821,2133,2835,2159,2877,2174,2870,2160,2875,2149,2856,2150,2846,2131,2838,2134,2829,2109,2841,2122,2848,2110,2858,2117,2865,2103,2851,2093,2860,2092,2858,2083,2869,2100,2867,2110,2876,2110,2868,2121,2874,2135,2886,2133,2895,2116,2890,2138,2896,2157,2909,2148,2932,2155,2940,2177,2952,2172,2908,2089,2923,2075,2923,2049,2929,2028,2895,2023,2885,2002,2871,1999,2861,2014,2837,2011,2832,2021,2851,2042,2828,2033,2831,2049,2828,2049,2814,2049,2826,2029,2811,2019,2795,2032,2801,2018,2755,2011,2757,1995,2749,1996,2750,2007,2732,2008,2733,1998,2704,1994,2715,1985,2695,1987,2713,1981,2753,1987,2772,2002,2788,1999,2788,1988,2792,2001,2828,1999,2856,1952,2837,1954,2828,1933,2815,1928,2860,1933,2854,1971,2863,1959,2872,1966,2874,1936,2882,1933,2892,1956,2896,1943,2905,1942,2911,1961,2954,1975,2966,1967,2992,1968,3021,1984,3036,2021,3030,2047,3022,2078,2973,2093,3007,2095,3051,2113,3055,2128,3044,2153,3043,2189,3066,2238,3069,2269,3049,2299,3073,2303,3094,2306,3103,2225,3136,2196,3135,2188,3126,2194,3168,2163,3157,2149,3163,2130,3141,2120,3137,2109,3141,2083,3120,2077,3119,2109,3115,2078,3104,2078,3115,2074,3112,2064,3088,2062,3078,2047,3083,2035,3092,2042,3094,2033,3106,2038,3122,2017,3115,2006,3103,2008,3105,1998,3132,1971,3125,1979,3107,1972,3107,1956,3093,1963,3081,1966,3101,1952,3089,1939,3101,1935,3121,1953,3124,1964,3142,1956,3131,1919,3111,1905,3105,1918,3103,1908,3086,1912,3099,1897,3092,1887,3077,1887,3093,1881,3103,1894,3102,1874,3093,1869,3105,1870,3111,1858,3110,1895,3124,1899,3131,1881,3144,1877,3133,1886,3146,1889,3133,1891,3168,1888,3172,1866,3183,1858,3187,1826,3176,1824,3194,1797,3178,1774,3162,1766,3156,1779,3117,1761,3119,1775,3097,1784,3092,1795,3097,1783,3096,1772,3082,1774,3110,1736,3127,1740,3138,1756,3159,1740,3187,1737,3203,1725,3210,1699,3190,1698,3192,1690,3205,1682,3235,1684,3241,1675,3262,1675,3272,1637,3286,1633,3260,1692,3238,1703,3239,1732,3231,1767,3217,1783,3258,1823,3270,1815,3249,1859,3209,1900,3211,1916,3183,1980,3196,1975,3194,1987,3203,1997,3195,1995,3175,2017,3194,2030,3207,2029,3194,2046,3179,2049,3186,2075,3215,2074,3232,2105,3250,2117,3273,2089,3330,2061,3341,2049,3370,2001,3344,1990,3321,2016,3321,1997,3311,1995,3307,2006,3305,1984,3291,1993,3294,1972,3287,1985,3266,1991,3272,1999,3262,1999,3268,2009,3258,2004,3247,2014,3239,1990,3232,2003,3235,1987,3248,1976,3232,1931,3249,1880,3283,1873,3280,1883,3254,1882,3246,1919,3237,1925,3256,1964,3266,1955,3266,1968,3288,1957,3277,1953,3281,1942,3293,1948,3316,1916,3298,1954,3313,1970,3339,1952,3324,1969,3332,1984,3347,1968,3364,1980,3375,1976,3387,1964,3378,1953,3389,1962,3399,1946,3408,1946,3396,1937,3412,1943,3429,1933,3390,1971,3390,2008,3402,1974,3451,1903,3477,1909,3508,1895,3556,1852,3573,1824,3616,1797,3610,1781,3599,1780,3601,1795,3581,1797,3584,1806,3575,1800,3573,1783,3573,1772,3579,1792,3577,1762,3585,1760,3584,1783,3601,1792,3595,1778,3608,1779,3609,1771,3602,1756,3619,1769,3630,1746,3609,1734,3622,1726,3633,1673,3625,1656,3616,1662,3603,1637,3627,1651,3604,1630,3588,1604,3564,1640,3570,1625,3553,1620,3541,1601,3527,1597,3525,1569,3523,1539,3534,1502,3533,1531,3544,1544,3542,1553,3556,1554,3546,1571,3558,1578,3555,1596,3587,1546,3603,1473,3627,1443,3625,1422,3667,1400,3667,1370,3651,1351,3682,1339,3722,1374,3778,1376,3760,1362,3748,1337,3784,1353,3807,1317,3809,1292,3822,1285,3817,1297,3825,1325,3807,1354,3832,1359,3824,1361,3827,1369,3864,1376,3877,1401,3897,1405,3907,1393,3894,1372,3903,1353,3897,1343,3906,1344,3916,1320,3943,1312,3974,1284,3993,1285,4015,1251,4016,1224,4038,1198,4057,1198,4055,1187,4073,1191,4062,1199,4074,1200,4069,1208,4070,1220,4065,1247,4057,1255,4067,1262,4057,1256,4042,1296,4022,1317,4034,1330,4024,1334,4005,1320,4005,1344,4009,1369,4025,1379,4012,1378,4004,1394,4028,1418,4017,1429,3987,1431,3971,1442,3972,1476,3957,1504,3952,1553,3942,1580,3928,1593,3932,1638,3923,1673,3881,1719,3880,1735,3894,1743,3926,1726,3923,1713,3952,1698,3956,1664,3976,1664,3979,1651,4000,1650,4003,1622,4022,1623,4023,1611,4040,1604,4036,1592,4062,1588,4062,1573,4087,1555,4095,1555,4111,1553,4115,1537,4127,1533,4121,1502,4104,1505,4096,1492,4112,1499,4112,1478,4140,1496,4160,1481,4200,1507,4224,1474,4224,1532,4190,1541,4159,1541,4133,1596,4137,1606,4178,1607,4218,1604,4224,1600,4224,1660,4208,1675,4211,1663,4203,1664,4222,1658,4194,1643,4175,1662,4175,1679,4156,1678,4161,1687,4140,1688,4138,1680,4148,1682,4128,1651,4097,1650,4070,1649,4043,1687,4056,1707,4095,1718,4082,1720,4076,1739,4078,1727,4057,1724,4052,1713,4030,1710,4030,1698,4011,1694,3982,1748,3976,1783,3959,1802,3925,1812,3906,1845,3899,1878,3908,1864,3920,1880,3920,1871,3945,1880,3949,1887,3935,1887,3939,1900,3911,1900,3906,1910,3908,1885,3893,1900,3894,1887,3884,1881,3807,1927,3795,1949,3802,1978,3593,2033,3585,2049,3571,2080,3524,2110,3517,2123,3516,2140,3532,2163,3529,2177,3536,2167,3561,2172,3575,2164,3577,2174,3549,2180,3565,2191,3571,2211,3624,2208,3642,2181,3633,2209,3658,2215,3666,2233,3650,2240,3649,2226,3620,2230,3610,2225,3611,2215,3582,2225,3572,2218,3556,2222,3544,2213,3550,2197,3538,2180,3515,2183,3492,2211,3514,2208,3529,2215,3538,2235,3573,2263,3551,2256,3551,2247,3508,2218,3497,2225,3499,2240,3489,2242,3495,2251,3478,2222,3482,2204,3496,2201,3492,2177,3473,2183,3469,2173,3449,2171,3416,2188,3408,2213,3373,2236,3372,2260,3392,2266,3397,2277,3395,2310,3412,2312,3424,2326,3422,2345,3461,2323,3458,2334,3435,2347,3420,2377,3423,2387,3439,2383,3453,2390,3454,2406,3446,2397,3429,2391,3416,2421,3429,2428,3404,2425,3421,2404,3412,2398,3409,2362,3424,2364,3386,2337,3358,2377,3330,2383,3327,2413,3317,2430,3319,2451,3328,2475,3341,2479,3353,2469,3345,2477,3350,2495,3358,2493,3369,2510,3390,2502,3389,2510,3411,2510,3370,2515,3382,2540,3391,2541,3380,2550,3356,2506,3334,2492,3318,2495,3324,2515,3318,2503,3310,2498,3315,2488,3299,2467,3305,2435,3296,2430,3299,2420,3289,2427,3269,2463,3277,2460,3282,2481,3268,2466,3259,2491,3248,2537,3260,2547,3251,2543,3247,2555,3245,2543,3231,2579,3214,2595,3197,2630,3206,2627,3203,2639,3177,2701,3135,2759,3116,2805,3104,2876,3111,2884,3138,2885,3148,2820,3144,2798,3154,2834,3141,2892,3154,2875,3169,2870,3157,2851,3165,2826,3177,2824,3170,2813,3178,2799,3202,2789,3213,2794,3189,2797,3178,2816,3193,2826,3175,2830,3171,2848,3186,2880,3193,2859,3205,2853,3193,2869,3203,2878,3201,2904,3188,2906,3175,2883,3165,2900,3154,2884,3150,2905,3183,2933,3193,2924,3216,2933,3202,2943,3200,2962,3207,2972,3205,2988,3223,3007,3194,2987,3195,2998,3229,3061,3243,3129,3240,3182,3258,3195,3250,3204,3241,3199,3247,3212,3215,3281,3073,3283,3071,3283,3032,3283,3004,3303,2976,3371,2979,3405,2970,3445,2943,3481,2943,3494,2922,3493,2951,3507,2939,3508,2932,3528,2947,3520,2931,3530,2940,3549,2920,3528,2880,3594,2860,3665,2858,3698,2867,3707,2847,3750,2857,3750,2848,3751,2853,3863,2876,3855,2854,3866,2849,3917,2820,3998,2821,4035,2842,4044,2856,3991,2890,3967,2918,3973,2908,3941,2912,3906,2919,3946,2924,3926,2930,3937,2923,3962,2932,3957,2923,3972,2951,3940,2928,3836,2933,3820,2922,3857,2923,3835,2907,3828,2904,3812,2922,3826,2936,3790,2926,3778,2918,3784,2914,3758,2900,3761,2915,3749,2907,3715,2914,3700,2922,3762,2935,3749,2929,3727,2956,3736,2955,3712,2969,3763,2988,3763,2992,3722,2979,3716,2979,3701,2998,3681,2975,3653,2959,3649,2946,3662,2958,3641,2953,3631,2933,3642,2929,3631,2939,3625,2934,3609,2945,3617,2918,3606,2932,3599,2923,3593,2938,3593,2941,3601,2952,3594,2955,3613,2963,3616,2954,3620,2969,3621,2980,3627,2979,3638,2985,3630,3000,3642,3000,3622,2983,3621,2994,3612,2975,3584,2985,3592,2984,3572,2995,3591,3002,3551,2993,3527,3007,3553,3006,3601,3016,3595,3040,3577,3017,3529,3032,3527,3036,3554,3058,3554,3047,3564,3045,3587,3036,3598,3019,3614,3026,3645,3036,3653,3034,3663,3025,3658,3027,3687,3019,3682,3007,3691,3014,3715,3033,3724,3043,3800,3059,3796,3041,3737,3057,3689,3051,3680,3059,3680,3067,3675,3061,3654,3073,3642,3073,3663,3077,3637,3073,3628,3065,3625,3064,3605,3073,3622,3081,3621,3085,3612,3090,3571,3093,3607,3075,3651,3079,3671,3102,3651,3086,3674,3097,3669,3123,3640,3124,3651,3138,3647,3125,3661,3152,3732,3161,3721,3169,3736,3171,3723,3188,3727,3186,3706,3159,3700,3148,3665,3161,3677,3165,3664,3176,3660,3173,3649,3181,3644,3170,3634,3181,3632,3181,3622,3172,3625,3176,3598,3161,3609,3148,3604,3144,3623,3132,3611,3109,3614,3120,3605,3113,3574,3121,3580,3125,3606,3141,3601,3139,3592,3158,3598,3153,3573,3143,3572,3139,3563,3158,3566,3161,3576,3175,3567,3183,3546,3194,3557,3190,3545,3179,3542,3190,3543,3191,3533,3177,3532,3191,3531,3191,3513,3204,3506,3211,3538,3206,3526,3197,3546,3205,3561,3217,3558,3224,3568,3212,3573,3222,3576,3230,3566,3250,3562,3251,3576,3260,3569,3265,3578,3264,3589,3255,3590,3259,3600,3270,3601,3274,3592,3293,3596,3278,3596,3269,3609,3273,3620,3261,3620,3264,3611,3248,3614,3230,3590,3230,3648,3253,3651,3258,3631,3268,3627,3277,3626,3294,3644,3302,3633,3308,3658,3296,3662,3295,3683,3318,3690,3318,3675,3318,3685,3331,3685,3318,3691,3326,3713,3318,3749,3322,3774,3320,3830,3332,3821,3331,3794,3341,3772,3340,3814,3348,3806,3367,3807,3374,3794,3368,3767,3378,3753,3370,3729,3382,3741,3388,3718,3385,3692,3392,3701,3394,3688,3396,3736,3378,3764,3377,3804,3370,3816,3341,3823,3313,3975,3340,4009,3347,4053,3375,4064,3358,4069,3352,4090,3363,4085,3363,4095,3363,4097,3351,4097,3336,4132,3339,4140,3347,4136,3338,4143,3333,4172,3343,4187,3350,4178,3342,4153,3358,4157,3364,4144,3376,4143,3370,4133,3382,4134,3382,4126,3397,4133,3412,4121,3411,4107,3426,4095,3447,4079,3434,4095,3422,4108,3430,4116,3415,4123,3432,4132,3381,4147,3388,4166,3375,4160,3354,4196,3357,4209,3374,4204,3370,4224,3394,4224,3407,4205,3415,4210,3423,4197,3440,4196,3436,4184,3446,4195,3462,4189,3471,4195,3431,4202,3426,4213,3407,4224,3492,4224,3492,4214,3504,4219,3519,4197,3519,4205,3534,4208,3540,4194,3554,4190,3555,4177,3543,4181,3542,4146,3532,4145,3547,4138,3541,4097,3542,4085,3529,4075,3539,4068,3538,4079,3546,4082,3571,4062,3595,4025,3604,4025,3622,3995,3611,4014,3613,4022,3593,4031,3578,4058,3585,4067,3577,4064,3550,4085,3555,4097,3563,4098,3556,4120,3574,4111,3556,4126,3558,4139,3550,4148,3563,4173,3586,4157,3586,4140,3593,4151,3603,4135,3609,4145,3635,4134,3588,4160,3565,4189,3570,4199,3645,4193,3605,4203,3608,4214,3591,4201,3586,4215,3573,4206,3563,4209,3563,4201,3553,4204,3540,4221,3546,4224,3275,4224,3266,4212,3279,4218,3289,4199,3274,4194,3279,4180,3261,4189,3271,4177,3266,4168,3263,4158,3287,4177,3299,4162,3252,4108,3248,4128,3238,4106,3246,4101,3220,4105,3228,4123,3206,4134,3212,4120,3194,4119,3201,4110,3191,4095,3179,4089,3186,4069,3171,4059,3165,4072,3161,4085,3159,4075,3149,4081,3145,4068,3157,4065,3148,4061,3167,4049,3164,4029,3156,4017,3151,4027,3152,4035,3137,4038,3137,4057,3132,4040,3124,4037,3136,4030,3128,4014,3140,4016,3140,3987,3180,3967,3175,3949,3100,4026,3096,4037,3108,4063,3091,4065,3079,4085,3071,4081,3056,4084,3047,4074,3033,4097,3018,4123,3013,4192,2988,4224,3027,4224,3044,4223,3040,4206,3046,4219,3051,4224,3074,4224,3074,4216,3076,4224,3116,4224,3111,4198,3098,4192,3094,4178,3075,4180,3069,4127,3080,4145,3084,4173,3089,4165,3100,4169,3124,4202,3132,4190,3125,4181,3134,4185,3139,4173,3127,4143,3138,4148,3157,4136,3154,4122,3144,4124,3155,4117,3153,4109,3166,4134,3140,4155,3146,4172,3131,4214,3133,4224,3161,4224,3164,4180,3176,4203,3203,4177,3199,4162,3213,4155,3207,4166,3216,4186,3208,4187,3205,4199,3189,4197,3188,4215,3170,4221,3169,4224,4224,4224,4224,4224,4224,-128,4224,-128,4224,4224,2293,4224,2681,3125,2665,3123,2657,3113,2655,3124,2640,3119,2663,3099,2642,3105,2640,3089,2618,3108,2622,3138,2622,3153,2653,3192,2652,3210,2685,3144,2681,3125,2681,3125,3189,3788,3205,3783,3206,3763,3193,3756,3189,3788,3189,3788,2264,3287,2274,3283,2269,3270,2264,3287,2264,3287,2436,3801,2448,3809,2446,3798,2462,3796,2473,3772,2449,3781,2436,3801,2436,3801,3142,2365,3155,2362,3162,2350,3157,2333,3137,2341,3122,2401,3142,2382,3142,2365,3142,2365,2761,2561,2769,2563,2780,2549,2761,2561,2761,2561,2923,2209,2910,2200,2893,2208,2898,2222,2888,2211,2896,2176,2880,2194,2862,2195,2864,2218,2876,2232,2865,2227,2886,2247,2879,2258,2884,2266,2892,2260,2894,2239,2912,2246,2917,2236,2916,2251,2907,2248,2924,2290,2934,2286,2922,2272,2928,2254,2955,2248,2946,2241,2942,2214,2923,2209,2923,2209,2823,2539,2896,2498,2911,2465,2876,2449,2805,2496,2788,2496,2792,2523,2823,2539,2823,2539,3675,1790,3740,1742,3708,1651,3683,1646,3674,1634,3638,1646,3652,1647,3661,1664,3670,1660,3649,1717,3641,1722,3647,1736,3635,1756,3653,1759,3655,1741,3666,1743,3674,1731,3662,1730,3661,1711,3670,1711,3674,1691,3678,1695,3678,1649,3688,1650,3692,1665,3684,1671,3686,1698,3696,1689,3696,1708,3707,1709,3696,1719,3707,1731,3719,1729,3702,1729,3696,1741,3688,1759,3676,1769,3675,1790,3675,1790], [2397,2413,2419,2424,2432,2441,2446,2475,2484]]
};
var TriangulationContext = require('../src/util/Triangulation');
var triangulation = new TriangulationContext();
var Benchmark = require('benchmark');
global.__DEV__ = false;
for (var name in samples) {
var vertices = samples[name][0];
var holes = samples[name][1];
if (holes) {
var newHoles = [];
for (var i = 0; i < holes.length; i++) {
var startIdx = holes[i];
var endIdx = holes[i + 1] || vertices.length;
newHoles.push(vertices.slice(startIdx * 2, endIdx * 2));
}
vertices = vertices.slice(0, holes[0] * 2);
holes = newHoles;
}
else {
holes = [];
}
new Benchmark.Suite()
.add(name + ' (' + (vertices.length / 2) + ' vertices):', function () {
triangulation.triangulate(vertices, holes);
})
.on('error', function (e) {
console.log(e);
})
.on('cycle', logCycle)
.run();
}
function logCycle(event) {
console.log(String(event.target));
}