中值，最适合网格骨架的线
Median, best fit of line from mesh skeleton
我得到了一个网格骨架，它需要确定网格的方向，所以我可以自动在 3d space 中正确定位它。
我真的不知道如何获得最合适的线，所以我可以根据点集自动定位它。
下面是它的外观示例以及示例数据集。
//skeleton vertices
vertices = [ 2.06104, 318.734, -149.29;
4.2207, 212.092, -145.141;
4.23213, 200.135, -144.811;
4.16573, 95.1567, -133.954;
4.7053, 126.626, -138.59;
4.16915, 171.645, -143.646;
4.18659, 183.173, -144.185;
4.17842, 179.964, -144.008;
2.76537, 288.063, -147.215;
-1.71817, 61.155, -124.25;
-0.492168, 66.2098, -127.702;
2.07608, 79.5012, -131.886;
4.03249, 238.699, -146.141;
4.23595, 206.822, -145.001;
4.23623, 203.704, -144.908;
4.17145, 220.543, -145.415;
4.12453, 228.514, -145.761;
2.41377, 301.021, -147.804;
4.03098, 236.064, -145.985;
2.48681, 298.432, -147.685;
4.68192, 129.093, -138.873;
2.65048, 292.424, -147.406;
4.54555, 104.737, -135.116;
-4.23707, 53.6538, -113;
1.93508, 317.106, -148.755;
-4.98045, 51.9036, -109.052;
-5.87157, 49.9703, -104.104;
-11.2433, 41.1865, -71.6569;
-15.1283, 30.7528, -33.5845;
-14.6647, 26.7291, -17.9213;
-13.1176, 23.9812, -5.55431;
-8.27057, 20.6161, 13.9826;
-4.49387, 19.0295, 25.4537;
4.5645, 139.344, -140.275;
-3.3737, 56.0265, -117.133;
4.21667, 192.056, -144.576;
3.99948, 93.2911, -133.447;
4.22894, 209.986, -145.081;
4.17824, 167.633, -143.406;
3.94993, 243.303, -146.26;
4.20391, 188.412, -144.431;
4.20673, 214.944, -145.239;
3.82056, 248.85, -146.382;
3.75634, 252.761, -146.523;
3.46093, 268.466, -147.033;
4.11554, 230.181, -145.836;
4.44799, 147.962, -141.303;
4.205, 165.551, -143.138;
4.7514, 117.603, -137.34;
4.25931, 161.613, -142.739;
4.15939, 222.571, -145.502;
4.38497, 152.519, -141.797;
3.12906, 279.268, -147.181;
3.05571, 282.333, -147.279;
-8.35374, 45.7208, -89.6802;
-6.43016, 19.7295, 20.0489;
3.51218, 265.85, -146.95;
4.22735, 196.569, -144.716;
3.60114, 261.275, -146.806;
3.87527, 245.264, -146.243;
3.70115, 255.948, -146.633;
3.33032, 273.433, -147.142;
4.14712, 224.649, -145.592;
4.11102, 231.178, -145.882;
4.17545, 177.258, -143.86;
4.07209, 234.491, -145.985;
4.13698, 226.37, -145.667;
4.50243, 144.003, -140.851;
4.74996, 120.215, -137.661;
3.00397, 283.765, -147.29;
4.22263, 164.279, -143.008;
4.19542, 216.684, -145.284;
4.74419, 122.387, -138.079;
4.24362, 162.754, -142.854;
4.1921, 217.204, -145.299;
3.1988, 276.954, -147.144;
2.24673, 307.266, -148.14;
4.70408, 113.726, -136.704;
1.55558, 75.9859, -131.562;
4.66136, 131.166, -139.157;
3.69856, 90.4963, -133.113;
4.42481, 149.643, -141.489;
2.02224, 313.586, -148.445;
3.39344, 270.742, -147.067;
-11.4507, 40.824, -70.2682;
-12.6325, 23.3651, -2.57932;
-7.10479, 20.0528, 17.8335;
-5.64725, 19.4808, 22.078;
-4.64392, 19.0822, 25.039;
2.02817, 318.148, -149.125;
2.33964, 303.688, -147.933;
3.66401, 257.998, -146.701;
4.63971, 109.538, -135.974;
1.92836, 315.331, -148.48;
-14.1808, 25.5312, -12.8091;
-9.41149, 21.1265, 10.4194;
-4.95978, 19.1884, 24.1908;
2.59159, 294.625, -147.508;
2.13575, 310.184, -148.256;
2.70921, 290.146, -147.303;
4.27225, 160.675, -142.644;
4.26101, 97.2627, -134.029;
4.48821, 103.188, -134.891;
4.49926, 103.485, -134.935;
-7.047, 47.7435, -97.5736;
-6.3594, 48.9598, -101.483;
-9.77383, 43.5659, -81.0321;
-8.9763, 44.7772, -85.911;
-10.8234, 41.8961, -74.4074;
-13.9937, 35.5167, -50.7962;
-14.3038, 34.7247, -47.9571;
-14.8257, 32.9699, -41.6747;
-14.6745, 33.5497, -43.7501;
-11.2159, 22.148, 3.98751;
-11.8022, 22.5945, 1.47664;
-8.85457, 20.8696, 12.1895;
-10.131, 21.5096, 7.94287;
4.63046, 134.052, -139.576;
-10.0719, 43.1032, -79.1781;
-10.7667, 21.8667, 5.68727;
-12.6587, 38.5085, -61.6436;
3.95535, 241.725, -146.174;
-15.1097, 31.1952, -35.2305;
-14.9267, 27.8269, -22.3608;
-15.0656, 31.6803, -37.016;
-9.86649, 21.3662, 8.86292;
4.58261, 106.635, -135.457;
-13.3958, 36.9225, -55.8701;
-14.8467, 27.4234, -20.75;
-9.26049, 44.3478, -84.1828;
-9.51023, 43.9693, -82.6548;
-13.9657, 25.1136, -10.9592;
-14.4925, 34.1899, -46.0425;
-10.5672, 42.3162, -76.0544;
-11.5984, 40.5562, -69.2552;
-0.993421, 64.013, -126.478;
0.765767, 72.1493, -130.141;
-2.1096, 59.7809, -122.798;
-12.1454, 39.5104, -65.3578;
-13.062, 37.65, -58.5144;
-6.68714, 48.3172, -99.7383;
4.33504, 156.127, -142.176;
4.39741, 100.816, -134.536;
2.55245, 82.6571, -132.286;
-14.4223, 26.1384, -15.3963;
-1.22434, 63.1015, -125.766;
-4.58353, 52.82, -111.184;
-5.20508, 51.4016, -107.822;
1.17634, 74.0686, -130.953;
-7.37625, 47.2239, -95.5894;
-14.9706, 32.2558, -39.1074;
-15.1378, 29.7063, -29.6614;
-13.3868, 24.326, -7.21636;
-2.6613, 58.1303, -120.338;
-5.48993, 50.7878, -106.232;
-15.0685, 28.7501, -25.9925;
-13.7052, 36.2122, -53.3032;
0.437576, 70.5848, -129.527;
];
//skeleton lines
lines = [
93, 24;
56, 44;
0, 89;
42, 59;
7, 64;
17, 90;
62, 50;
39, 59;
48, 77;
3, 36;
13, 14;
10, 157;
20, 79;
19, 17;
43, 60;
76, 90;
157, 136;
4, 72;
79, 117;
14, 2;
7, 6;
40, 6;
62, 66;
135, 10;
49, 73;
38, 5;
61, 75;
137, 153;
78, 148;
2, 57;
38, 47;
117, 33;
61, 83;
35, 40;
9, 137;
58, 56;
153, 34;
1, 41;
9, 145;
39, 121;
82, 98;
25, 147;
25, 146;
23, 34;
8, 99;
23, 146;
60, 91;
149, 54;
108, 27;
156, 127;
139, 120;
112, 132;
109, 110;
150, 111;
124, 122;
151, 28;
150, 124;
155, 123;
151, 155;
29, 144;
128, 123;
114, 85;
30, 85;
114, 113;
95, 115;
115, 31;
116, 125;
95, 125;
31, 86;
55, 86;
87, 96;
88, 96;
52, 53;
1, 37;
58, 91;
70, 47;
8, 69;
5, 64;
53, 69;
126, 22;
15, 50;
45, 16;
65, 63;
45, 63;
13, 37;
141, 51;
57, 35;
15, 74;
71, 74;
48, 68;
72, 68;
46, 67;
20, 4;
70, 73;
141, 100;
16, 66;
18, 12;
52, 75;
18, 65;
46, 81;
42, 43;
121, 12;
41, 71;
24, 89;
22, 103;
77, 92;
21, 97;
36, 80;
126, 92;
21, 99;
33, 67;
102, 103;
44, 83;
76, 98;
118, 133;
87, 55;
101, 3;
51, 81;
49, 100;
136, 148;
78, 11;
142, 101;
82, 93;
19, 97;
104, 140;
140, 105;
104, 149;
106, 118;
129, 107;
106, 130;
129, 130;
134, 84;
27, 84;
138, 134;
138, 120;
132, 110;
112, 111;
116, 119;
26, 105;
131, 94;
154, 147;
54, 107;
108, 133;
88, 32;
156, 109;
135, 145;
127, 139;
29, 128;
113, 119;
28, 122;
143, 80;
152, 30;
142, 102;
144, 94;
131, 152;
143, 11;
26, 154;
];
我会：
将网格划分为单独的折线
并分别处理。所以你需要重新排序点 pnt[] 以便它们处于相同的拓扑顺序（只是点序列没有 line[] 结构）。
计算|pnt[i]-sliding_average(pnt[i])|
该值会给出与滑动平均值的距离，因此将其设置为阈值...如果太大，请划分折线。
您的数据的滑动平均值（平均之前 10 个点和之后 10 个点）如下所示（红色）：
作为我使用的阈值距离 sqrt(20) 所以这里检测到的各个多段线的起始端点（黄色）：
回归线
在 #2 之后，您的集合应该包含单独的线段。要提高精度，请忽略角点（多段线的边缘附近），因为它可能包含来自 next/previous 线段的点。
我选择忽略开头的10点和结尾的10点。我计算了内部点的平均位置。作为方向，我使用重新调整为外部端点大小的内部端点之间的差异。由此回归线只是平均位置+/-半方向向量。
您可以根据您想要获得的结果的属性来选择您想要的线的拟合或回归。
计算相邻线之间的交点
重构网格
这里是简单的 C++ 代码（抱歉我不使用 Matlab），用于您的数据覆盖 #1,#2,#3 没有递归细分（多段线的分支），这样你就可以看到事情是如何完成的，以防上面的描述不够。
//---------------------------------------------------------------------------
//skeleton vertices
double pnt[]=
{
2.06104, 318.734, -149.29,
4.2207, 212.092, -145.141,
4.23213, 200.135, -144.811,
4.16573, 95.1567, -133.954,
4.7053, 126.626, -138.59,
4.16915, 171.645, -143.646,
4.18659, 183.173, -144.185,
4.17842, 179.964, -144.008,
2.76537, 288.063, -147.215,
-1.71817, 61.155, -124.25,
-0.492168, 66.2098, -127.702,
2.07608, 79.5012, -131.886,
4.03249, 238.699, -146.141,
4.23595, 206.822, -145.001,
4.23623, 203.704, -144.908,
4.17145, 220.543, -145.415,
4.12453, 228.514, -145.761,
2.41377, 301.021, -147.804,
4.03098, 236.064, -145.985,
2.48681, 298.432, -147.685,
4.68192, 129.093, -138.873,
2.65048, 292.424, -147.406,
4.54555, 104.737, -135.116,
-4.23707, 53.6538, -113,
1.93508, 317.106, -148.755,
-4.98045, 51.9036, -109.052,
-5.87157, 49.9703, -104.104,
-11.2433, 41.1865, -71.6569,
-15.1283, 30.7528, -33.5845,
-14.6647, 26.7291, -17.9213,
-13.1176, 23.9812, -5.55431,
-8.27057, 20.6161, 13.9826,
-4.49387, 19.0295, 25.4537,
4.5645, 139.344, -140.275,
-3.3737, 56.0265, -117.133,
4.21667, 192.056, -144.576,
3.99948, 93.2911, -133.447,
4.22894, 209.986, -145.081,
4.17824, 167.633, -143.406,
3.94993, 243.303, -146.26,
4.20391, 188.412, -144.431,
4.20673, 214.944, -145.239,
3.82056, 248.85, -146.382,
3.75634, 252.761, -146.523,
3.46093, 268.466, -147.033,
4.11554, 230.181, -145.836,
4.44799, 147.962, -141.303,
4.205, 165.551, -143.138,
4.7514, 117.603, -137.34,
4.25931, 161.613, -142.739,
4.15939, 222.571, -145.502,
4.38497, 152.519, -141.797,
3.12906, 279.268, -147.181,
3.05571, 282.333, -147.279,
-8.35374, 45.7208, -89.6802,
-6.43016, 19.7295, 20.0489,
3.51218, 265.85, -146.95,
4.22735, 196.569, -144.716,
3.60114, 261.275, -146.806,
3.87527, 245.264, -146.243,
3.70115, 255.948, -146.633,
3.33032, 273.433, -147.142,
4.14712, 224.649, -145.592,
4.11102, 231.178, -145.882,
4.17545, 177.258, -143.86,
4.07209, 234.491, -145.985,
4.13698, 226.37, -145.667,
4.50243, 144.003, -140.851,
4.74996, 120.215, -137.661,
3.00397, 283.765, -147.29,
4.22263, 164.279, -143.008,
4.19542, 216.684, -145.284,
4.74419, 122.387, -138.079,
4.24362, 162.754, -142.854,
4.1921, 217.204, -145.299,
3.1988, 276.954, -147.144,
2.24673, 307.266, -148.14,
4.70408, 113.726, -136.704,
1.55558, 75.9859, -131.562,
4.66136, 131.166, -139.157,
3.69856, 90.4963, -133.113,
4.42481, 149.643, -141.489,
2.02224, 313.586, -148.445,
3.39344, 270.742, -147.067,
-11.4507, 40.824, -70.2682,
-12.6325, 23.3651, -2.57932,
-7.10479, 20.0528, 17.8335,
-5.64725, 19.4808, 22.078,
-4.64392, 19.0822, 25.039,
2.02817, 318.148, -149.125,
2.33964, 303.688, -147.933,
3.66401, 257.998, -146.701,
4.63971, 109.538, -135.974,
1.92836, 315.331, -148.48,
-14.1808, 25.5312, -12.8091,
-9.41149, 21.1265, 10.4194,
-4.95978, 19.1884, 24.1908,
2.59159, 294.625, -147.508,
2.13575, 310.184, -148.256,
2.70921, 290.146, -147.303,
4.27225, 160.675, -142.644,
4.26101, 97.2627, -134.029,
4.48821, 103.188, -134.891,
4.49926, 103.485, -134.935,
-7.047, 47.7435, -97.5736,
-6.3594, 48.9598, -101.483,
-9.77383, 43.5659, -81.0321,
-8.9763, 44.7772, -85.911,
-10.8234, 41.8961, -74.4074,
-13.9937, 35.5167, -50.7962,
-14.3038, 34.7247, -47.9571,
-14.8257, 32.9699, -41.6747,
-14.6745, 33.5497, -43.7501,
-11.2159, 22.148, 3.98751,
-11.8022, 22.5945, 1.47664,
-8.85457, 20.8696, 12.1895,
-10.131, 21.5096, 7.94287,
4.63046, 134.052, -139.576,
-10.0719, 43.1032, -79.1781,
-10.7667, 21.8667, 5.68727,
-12.6587, 38.5085, -61.6436,
3.95535, 241.725, -146.174,
-15.1097, 31.1952, -35.2305,
-14.9267, 27.8269, -22.3608,
-15.0656, 31.6803, -37.016,
-9.86649, 21.3662, 8.86292,
4.58261, 106.635, -135.457,
-13.3958, 36.9225, -55.8701,
-14.8467, 27.4234, -20.75,
-9.26049, 44.3478, -84.1828,
-9.51023, 43.9693, -82.6548,
-13.9657, 25.1136, -10.9592,
-14.4925, 34.1899, -46.0425,
-10.5672, 42.3162, -76.0544,
-11.5984, 40.5562, -69.2552,
-0.993421, 64.013, -126.478,
0.765767, 72.1493, -130.141,
-2.1096, 59.7809, -122.798,
-12.1454, 39.5104, -65.3578,
-13.062, 37.65, -58.5144,
-6.68714, 48.3172, -99.7383,
4.33504, 156.127, -142.176,
4.39741, 100.816, -134.536,
2.55245, 82.6571, -132.286,
-14.4223, 26.1384, -15.3963,
-1.22434, 63.1015, -125.766,
-4.58353, 52.82, -111.184,
-5.20508, 51.4016, -107.822,
1.17634, 74.0686, -130.953,
-7.37625, 47.2239, -95.5894,
-14.9706, 32.2558, -39.1074,
-15.1378, 29.7063, -29.6614,
-13.3868, 24.326, -7.21636,
-2.6613, 58.1303, -120.338,
-5.48993, 50.7878, -106.232,
-15.0685, 28.7501, -25.9925,
-13.7052, 36.2122, -53.3032,
0.437576, 70.5848, -129.527,
};
const int pnts3=sizeof(pnt)/sizeof(pnt[1]); // number of points * 3
const int pnts=pnts3/3; // number of points
//skeleton lines
int lin[]=
{
93, 24,
56, 44,
0, 89,
42, 59,
7, 64,
17, 90,
62, 50,
39, 59,
48, 77,
3, 36,
13, 14,
10, 157,
20, 79,
19, 17,
43, 60,
76, 90,
157, 136,
4, 72,
79, 117,
14, 2,
7, 6,
40, 6,
62, 66,
135, 10,
49, 73,
38, 5,
61, 75,
137, 153,
78, 148,
2, 57,
38, 47,
117, 33,
61, 83,
35, 40,
9, 137,
58, 56,
153, 34,
1, 41,
9, 145,
39, 121,
82, 98,
25, 147,
25, 146,
23, 34,
8, 99,
23, 146,
60, 91,
149, 54,
108, 27,
156, 127,
139, 120,
112, 132,
109, 110,
150, 111,
124, 122,
151, 28,
150, 124,
155, 123,
151, 155,
29, 144,
128, 123,
114, 85,
30, 85,
114, 113,
95, 115,
115, 31,
116, 125,
95, 125,
31, 86,
55, 86,
87, 96,
88, 96,
52, 53,
1, 37,
58, 91,
70, 47,
8, 69,
5, 64,
53, 69,
126, 22,
15, 50,
45, 16,
65, 63,
45, 63,
13, 37,
141, 51,
57, 35,
15, 74,
71, 74,
48, 68,
72, 68,
46, 67,
20, 4,
70, 73,
141, 100,
16, 66,
18, 12,
52, 75,
18, 65,
46, 81,
42, 43,
121, 12,
41, 71,
24, 89,
22, 103,
77, 92,
21, 97,
36, 80,
126, 92,
21, 99,
33, 67,
102, 103,
44, 83,
76, 98,
118, 133,
87, 55,
101, 3,
51, 81,
49, 100,
136, 148,
78, 11,
142, 101,
82, 93,
19, 97,
104, 140,
140, 105,
104, 149,
106, 118,
129, 107,
106, 130,
129, 130,
134, 84,
27, 84,
138, 134,
138, 120,
132, 110,
112, 111,
116, 119,
26, 105,
131, 94,
154, 147,
54, 107,
108, 133,
88, 32,
156, 109,
135, 145,
127, 139,
29, 128,
113, 119,
28, 122,
143, 80,
152, 30,
142, 102,
144, 94,
131, 152,
143, 11,
26, 154,
};
const int lins2=sizeof(lin)/sizeof(lin[1]); // number of lines * 2
const int lins=lins2/2; // number of lines
//---------------------------------------------------------------------------
int pol[pnts],pols=0; // polyline
double avg[pnts3]; // sliding average
//---------------------------------------------------------------------------
const int _mesh=100;
double mesh[_mesh*3];
int meshs=0,meshs3=0;
//---------------------------------------------------------------------------
void compute()
{
int i,j,e,n,i0,i1;
int his[pnts];
int used[lins];
double x,y,z,w,rr,ll;
//--- compute polyline pol[pols] ----------------------------------------
// histogram of point usagge
for (i=0;i<pnts;i++) his[i]=0;
for (i=0;i<lins2;i++) his[lin[i]]++;
// clear tables
for (i=0;i<pnts;i++) pol[i]=-1; pols=0;
for (i=0;i<lins;i++) used[i]=0;
// find start point (his[i]!=2)
for (e=1,i=0;i<pnts;i++)
if ((his[i])&&(his[i]!=2))
{ e=0; break; }
if (e) return; // stop if none found
// add start point to polyline
pol[pols]=i; pols++;
// process polyline
for (e=1;e;)
for (e=0,j=0;j<lins;j++)
if (!used[j]) // ignore used lines
{
// is point i in line j ?
if (lin[j+j+0]==i) i=lin[j+j+1];
else if (lin[j+j+1]==i) i=lin[j+j+0];
else continue;
// add next point to polyline
pol[pols]=i; pols++;
used[j]=1;
if (his[i]==2) e=1; // loop if not end of polyline
break;
}
//--- compute sliding average -------------------------------------------
n=10; // sliding average half interval [poins]
w=1+n+n; w=1.0/w;
for (i=0;i<pols;i++)
{
e=3*pol[i];
x=pnt[e]; e++;
y=pnt[e]; e++;
z=pnt[e]; e++;
for (j=1;j<=n;j++)
{
e=i+j; if (e>=pols) e=pols-1;
e=3*pol[e];
x+=pnt[e]; e++;
y+=pnt[e]; e++;
z+=pnt[e]; e++;
e=i-j; if (e<0) e=0;
e=3*pol[e];
x+=pnt[e]; e++;
y+=pnt[e]; e++;
z+=pnt[e]; e++;
}
e=3*i;
avg[e]=x*w; e++;
avg[e]=y*w; e++;
avg[e]=z*w; e++;
}
//--- regress lines -----------------------------------------------------
meshs=0; meshs3=0;
ll=20.0;
for (e=0,i=0;i<pols;i++)
{
// distance to sliding average
j=3*pol[i];
x=pnt[j]; j++;
y=pnt[j]; j++;
z=pnt[j]; j++;
j=3*i;
x-=avg[j]; j++; x*=x;
y-=avg[j]; j++; y*=y;
z-=avg[j]; j++; z*=z;
rr=x+y+z;
if ((e==0)&&(rr<=ll)){ i0=i; e++; }// find start point
else if ((e==1)&&(rr> ll)) // find end point
{
i1=i-1; e=0; if (i0==i1) continue;
// regress line from pol[i0..i1]
int j0,j1;
double dx,dy,dz;
// ignore n edge points
n=10; while ((i1-i0)<(n<<2)) n--;
j0=i0+n;
j1=i1-n;
// direction
j=3*pol[j1];
dx=pnt[j]; j++;
dy=pnt[j]; j++;
dz=pnt[j]; j++;
j=3*pol[j0];
dx-=pnt[j]; j++;
dy-=pnt[j]; j++;
dz-=pnt[j]; j++;
// original line size
j=3*pol[i1];
x=pnt[j]; j++;
y=pnt[j]; j++;
z=pnt[j]; j++;
j=3*pol[i0];
x-=pnt[j]; j++;
y-=pnt[j]; j++;
z-=pnt[j]; j++;
// rescale direction to match original half size
rr=sqrt((x*x)+(y*y)+(z*z));
rr=divide(rr,sqrt((dx*dx)+(dy*dy)+(dz*dz)));
rr*=0.5;
dx*=rr;
dy*=rr;
dz*=rr;
// avg position
for (x=y=z=0.0,n=0,i=j0;i<=j1;i++)
{
j=3*pol[i];
x+=pnt[j]; j++;
y+=pnt[j]; j++;
z+=pnt[j]; j++;
n++;
}
x/=n;
y/=n;
z/=n;
// line is avg+/-half direction
mesh[meshs3]=x-dx; meshs3++; meshs++;
mesh[meshs3]=y-dy; meshs3++;
mesh[meshs3]=z-dz; meshs3++;
mesh[meshs3]=x+dx; meshs3++; meshs++;
mesh[meshs3]=y+dy; meshs3++;
mesh[meshs3]=z+dz; meshs3++;
// restore main loop
i=i1+1; e=0;
}
}
i=0;
}
//---------------------------------------------------------------------------
mesh[meshs3] 保存结果折线的 3D 点坐标（每条线 2 个点）meshs 是点数，所以 num_of_lines=meshs/2
我得到了一个网格骨架，它需要确定网格的方向，所以我可以自动在 3d space 中正确定位它。
我真的不知道如何获得最合适的线，所以我可以根据点集自动定位它。 下面是它的外观示例以及示例数据集。
//skeleton vertices
vertices = [ 2.06104, 318.734, -149.29;
4.2207, 212.092, -145.141;
4.23213, 200.135, -144.811;
4.16573, 95.1567, -133.954;
4.7053, 126.626, -138.59;
4.16915, 171.645, -143.646;
4.18659, 183.173, -144.185;
4.17842, 179.964, -144.008;
2.76537, 288.063, -147.215;
-1.71817, 61.155, -124.25;
-0.492168, 66.2098, -127.702;
2.07608, 79.5012, -131.886;
4.03249, 238.699, -146.141;
4.23595, 206.822, -145.001;
4.23623, 203.704, -144.908;
4.17145, 220.543, -145.415;
4.12453, 228.514, -145.761;
2.41377, 301.021, -147.804;
4.03098, 236.064, -145.985;
2.48681, 298.432, -147.685;
4.68192, 129.093, -138.873;
2.65048, 292.424, -147.406;
4.54555, 104.737, -135.116;
-4.23707, 53.6538, -113;
1.93508, 317.106, -148.755;
-4.98045, 51.9036, -109.052;
-5.87157, 49.9703, -104.104;
-11.2433, 41.1865, -71.6569;
-15.1283, 30.7528, -33.5845;
-14.6647, 26.7291, -17.9213;
-13.1176, 23.9812, -5.55431;
-8.27057, 20.6161, 13.9826;
-4.49387, 19.0295, 25.4537;
4.5645, 139.344, -140.275;
-3.3737, 56.0265, -117.133;
4.21667, 192.056, -144.576;
3.99948, 93.2911, -133.447;
4.22894, 209.986, -145.081;
4.17824, 167.633, -143.406;
3.94993, 243.303, -146.26;
4.20391, 188.412, -144.431;
4.20673, 214.944, -145.239;
3.82056, 248.85, -146.382;
3.75634, 252.761, -146.523;
3.46093, 268.466, -147.033;
4.11554, 230.181, -145.836;
4.44799, 147.962, -141.303;
4.205, 165.551, -143.138;
4.7514, 117.603, -137.34;
4.25931, 161.613, -142.739;
4.15939, 222.571, -145.502;
4.38497, 152.519, -141.797;
3.12906, 279.268, -147.181;
3.05571, 282.333, -147.279;
-8.35374, 45.7208, -89.6802;
-6.43016, 19.7295, 20.0489;
3.51218, 265.85, -146.95;
4.22735, 196.569, -144.716;
3.60114, 261.275, -146.806;
3.87527, 245.264, -146.243;
3.70115, 255.948, -146.633;
3.33032, 273.433, -147.142;
4.14712, 224.649, -145.592;
4.11102, 231.178, -145.882;
4.17545, 177.258, -143.86;
4.07209, 234.491, -145.985;
4.13698, 226.37, -145.667;
4.50243, 144.003, -140.851;
4.74996, 120.215, -137.661;
3.00397, 283.765, -147.29;
4.22263, 164.279, -143.008;
4.19542, 216.684, -145.284;
4.74419, 122.387, -138.079;
4.24362, 162.754, -142.854;
4.1921, 217.204, -145.299;
3.1988, 276.954, -147.144;
2.24673, 307.266, -148.14;
4.70408, 113.726, -136.704;
1.55558, 75.9859, -131.562;
4.66136, 131.166, -139.157;
3.69856, 90.4963, -133.113;
4.42481, 149.643, -141.489;
2.02224, 313.586, -148.445;
3.39344, 270.742, -147.067;
-11.4507, 40.824, -70.2682;
-12.6325, 23.3651, -2.57932;
-7.10479, 20.0528, 17.8335;
-5.64725, 19.4808, 22.078;
-4.64392, 19.0822, 25.039;
2.02817, 318.148, -149.125;
2.33964, 303.688, -147.933;
3.66401, 257.998, -146.701;
4.63971, 109.538, -135.974;
1.92836, 315.331, -148.48;
-14.1808, 25.5312, -12.8091;
-9.41149, 21.1265, 10.4194;
-4.95978, 19.1884, 24.1908;
2.59159, 294.625, -147.508;
2.13575, 310.184, -148.256;
2.70921, 290.146, -147.303;
4.27225, 160.675, -142.644;
4.26101, 97.2627, -134.029;
4.48821, 103.188, -134.891;
4.49926, 103.485, -134.935;
-7.047, 47.7435, -97.5736;
-6.3594, 48.9598, -101.483;
-9.77383, 43.5659, -81.0321;
-8.9763, 44.7772, -85.911;
-10.8234, 41.8961, -74.4074;
-13.9937, 35.5167, -50.7962;
-14.3038, 34.7247, -47.9571;
-14.8257, 32.9699, -41.6747;
-14.6745, 33.5497, -43.7501;
-11.2159, 22.148, 3.98751;
-11.8022, 22.5945, 1.47664;
-8.85457, 20.8696, 12.1895;
-10.131, 21.5096, 7.94287;
4.63046, 134.052, -139.576;
-10.0719, 43.1032, -79.1781;
-10.7667, 21.8667, 5.68727;
-12.6587, 38.5085, -61.6436;
3.95535, 241.725, -146.174;
-15.1097, 31.1952, -35.2305;
-14.9267, 27.8269, -22.3608;
-15.0656, 31.6803, -37.016;
-9.86649, 21.3662, 8.86292;
4.58261, 106.635, -135.457;
-13.3958, 36.9225, -55.8701;
-14.8467, 27.4234, -20.75;
-9.26049, 44.3478, -84.1828;
-9.51023, 43.9693, -82.6548;
-13.9657, 25.1136, -10.9592;
-14.4925, 34.1899, -46.0425;
-10.5672, 42.3162, -76.0544;
-11.5984, 40.5562, -69.2552;
-0.993421, 64.013, -126.478;
0.765767, 72.1493, -130.141;
-2.1096, 59.7809, -122.798;
-12.1454, 39.5104, -65.3578;
-13.062, 37.65, -58.5144;
-6.68714, 48.3172, -99.7383;
4.33504, 156.127, -142.176;
4.39741, 100.816, -134.536;
2.55245, 82.6571, -132.286;
-14.4223, 26.1384, -15.3963;
-1.22434, 63.1015, -125.766;
-4.58353, 52.82, -111.184;
-5.20508, 51.4016, -107.822;
1.17634, 74.0686, -130.953;
-7.37625, 47.2239, -95.5894;
-14.9706, 32.2558, -39.1074;
-15.1378, 29.7063, -29.6614;
-13.3868, 24.326, -7.21636;
-2.6613, 58.1303, -120.338;
-5.48993, 50.7878, -106.232;
-15.0685, 28.7501, -25.9925;
-13.7052, 36.2122, -53.3032;
0.437576, 70.5848, -129.527;
];
//skeleton lines
lines = [
93, 24;
56, 44;
0, 89;
42, 59;
7, 64;
17, 90;
62, 50;
39, 59;
48, 77;
3, 36;
13, 14;
10, 157;
20, 79;
19, 17;
43, 60;
76, 90;
157, 136;
4, 72;
79, 117;
14, 2;
7, 6;
40, 6;
62, 66;
135, 10;
49, 73;
38, 5;
61, 75;
137, 153;
78, 148;
2, 57;
38, 47;
117, 33;
61, 83;
35, 40;
9, 137;
58, 56;
153, 34;
1, 41;
9, 145;
39, 121;
82, 98;
25, 147;
25, 146;
23, 34;
8, 99;
23, 146;
60, 91;
149, 54;
108, 27;
156, 127;
139, 120;
112, 132;
109, 110;
150, 111;
124, 122;
151, 28;
150, 124;
155, 123;
151, 155;
29, 144;
128, 123;
114, 85;
30, 85;
114, 113;
95, 115;
115, 31;
116, 125;
95, 125;
31, 86;
55, 86;
87, 96;
88, 96;
52, 53;
1, 37;
58, 91;
70, 47;
8, 69;
5, 64;
53, 69;
126, 22;
15, 50;
45, 16;
65, 63;
45, 63;
13, 37;
141, 51;
57, 35;
15, 74;
71, 74;
48, 68;
72, 68;
46, 67;
20, 4;
70, 73;
141, 100;
16, 66;
18, 12;
52, 75;
18, 65;
46, 81;
42, 43;
121, 12;
41, 71;
24, 89;
22, 103;
77, 92;
21, 97;
36, 80;
126, 92;
21, 99;
33, 67;
102, 103;
44, 83;
76, 98;
118, 133;
87, 55;
101, 3;
51, 81;
49, 100;
136, 148;
78, 11;
142, 101;
82, 93;
19, 97;
104, 140;
140, 105;
104, 149;
106, 118;
129, 107;
106, 130;
129, 130;
134, 84;
27, 84;
138, 134;
138, 120;
132, 110;
112, 111;
116, 119;
26, 105;
131, 94;
154, 147;
54, 107;
108, 133;
88, 32;
156, 109;
135, 145;
127, 139;
29, 128;
113, 119;
28, 122;
143, 80;
152, 30;
142, 102;
144, 94;
131, 152;
143, 11;
26, 154;
];
我会：
将网格划分为单独的折线
并分别处理。所以你需要重新排序点
pnt[]以便它们处于相同的拓扑顺序（只是点序列没有line[]结构）。计算
|pnt[i]-sliding_average(pnt[i])|该值会给出与滑动平均值的距离，因此将其设置为阈值...如果太大，请划分折线。
您的数据的滑动平均值（平均之前 10 个点和之后 10 个点）如下所示（红色）：
作为我使用的阈值距离
sqrt(20)所以这里检测到的各个多段线的起始端点（黄色）：回归线
在 #2 之后，您的集合应该包含单独的线段。要提高精度，请忽略角点（多段线的边缘附近），因为它可能包含来自 next/previous 线段的点。
我选择忽略开头的10点和结尾的10点。我计算了内部点的平均位置。作为方向，我使用重新调整为外部端点大小的内部端点之间的差异。由此回归线只是平均位置+/-半方向向量。
您可以根据您想要获得的结果的属性来选择您想要的线的拟合或回归。
计算相邻线之间的交点
重构网格
这里是简单的 C++ 代码（抱歉我不使用 Matlab），用于您的数据覆盖 #1,#2,#3 没有递归细分（多段线的分支），这样你就可以看到事情是如何完成的，以防上面的描述不够。
//---------------------------------------------------------------------------
//skeleton vertices
double pnt[]=
{
2.06104, 318.734, -149.29,
4.2207, 212.092, -145.141,
4.23213, 200.135, -144.811,
4.16573, 95.1567, -133.954,
4.7053, 126.626, -138.59,
4.16915, 171.645, -143.646,
4.18659, 183.173, -144.185,
4.17842, 179.964, -144.008,
2.76537, 288.063, -147.215,
-1.71817, 61.155, -124.25,
-0.492168, 66.2098, -127.702,
2.07608, 79.5012, -131.886,
4.03249, 238.699, -146.141,
4.23595, 206.822, -145.001,
4.23623, 203.704, -144.908,
4.17145, 220.543, -145.415,
4.12453, 228.514, -145.761,
2.41377, 301.021, -147.804,
4.03098, 236.064, -145.985,
2.48681, 298.432, -147.685,
4.68192, 129.093, -138.873,
2.65048, 292.424, -147.406,
4.54555, 104.737, -135.116,
-4.23707, 53.6538, -113,
1.93508, 317.106, -148.755,
-4.98045, 51.9036, -109.052,
-5.87157, 49.9703, -104.104,
-11.2433, 41.1865, -71.6569,
-15.1283, 30.7528, -33.5845,
-14.6647, 26.7291, -17.9213,
-13.1176, 23.9812, -5.55431,
-8.27057, 20.6161, 13.9826,
-4.49387, 19.0295, 25.4537,
4.5645, 139.344, -140.275,
-3.3737, 56.0265, -117.133,
4.21667, 192.056, -144.576,
3.99948, 93.2911, -133.447,
4.22894, 209.986, -145.081,
4.17824, 167.633, -143.406,
3.94993, 243.303, -146.26,
4.20391, 188.412, -144.431,
4.20673, 214.944, -145.239,
3.82056, 248.85, -146.382,
3.75634, 252.761, -146.523,
3.46093, 268.466, -147.033,
4.11554, 230.181, -145.836,
4.44799, 147.962, -141.303,
4.205, 165.551, -143.138,
4.7514, 117.603, -137.34,
4.25931, 161.613, -142.739,
4.15939, 222.571, -145.502,
4.38497, 152.519, -141.797,
3.12906, 279.268, -147.181,
3.05571, 282.333, -147.279,
-8.35374, 45.7208, -89.6802,
-6.43016, 19.7295, 20.0489,
3.51218, 265.85, -146.95,
4.22735, 196.569, -144.716,
3.60114, 261.275, -146.806,
3.87527, 245.264, -146.243,
3.70115, 255.948, -146.633,
3.33032, 273.433, -147.142,
4.14712, 224.649, -145.592,
4.11102, 231.178, -145.882,
4.17545, 177.258, -143.86,
4.07209, 234.491, -145.985,
4.13698, 226.37, -145.667,
4.50243, 144.003, -140.851,
4.74996, 120.215, -137.661,
3.00397, 283.765, -147.29,
4.22263, 164.279, -143.008,
4.19542, 216.684, -145.284,
4.74419, 122.387, -138.079,
4.24362, 162.754, -142.854,
4.1921, 217.204, -145.299,
3.1988, 276.954, -147.144,
2.24673, 307.266, -148.14,
4.70408, 113.726, -136.704,
1.55558, 75.9859, -131.562,
4.66136, 131.166, -139.157,
3.69856, 90.4963, -133.113,
4.42481, 149.643, -141.489,
2.02224, 313.586, -148.445,
3.39344, 270.742, -147.067,
-11.4507, 40.824, -70.2682,
-12.6325, 23.3651, -2.57932,
-7.10479, 20.0528, 17.8335,
-5.64725, 19.4808, 22.078,
-4.64392, 19.0822, 25.039,
2.02817, 318.148, -149.125,
2.33964, 303.688, -147.933,
3.66401, 257.998, -146.701,
4.63971, 109.538, -135.974,
1.92836, 315.331, -148.48,
-14.1808, 25.5312, -12.8091,
-9.41149, 21.1265, 10.4194,
-4.95978, 19.1884, 24.1908,
2.59159, 294.625, -147.508,
2.13575, 310.184, -148.256,
2.70921, 290.146, -147.303,
4.27225, 160.675, -142.644,
4.26101, 97.2627, -134.029,
4.48821, 103.188, -134.891,
4.49926, 103.485, -134.935,
-7.047, 47.7435, -97.5736,
-6.3594, 48.9598, -101.483,
-9.77383, 43.5659, -81.0321,
-8.9763, 44.7772, -85.911,
-10.8234, 41.8961, -74.4074,
-13.9937, 35.5167, -50.7962,
-14.3038, 34.7247, -47.9571,
-14.8257, 32.9699, -41.6747,
-14.6745, 33.5497, -43.7501,
-11.2159, 22.148, 3.98751,
-11.8022, 22.5945, 1.47664,
-8.85457, 20.8696, 12.1895,
-10.131, 21.5096, 7.94287,
4.63046, 134.052, -139.576,
-10.0719, 43.1032, -79.1781,
-10.7667, 21.8667, 5.68727,
-12.6587, 38.5085, -61.6436,
3.95535, 241.725, -146.174,
-15.1097, 31.1952, -35.2305,
-14.9267, 27.8269, -22.3608,
-15.0656, 31.6803, -37.016,
-9.86649, 21.3662, 8.86292,
4.58261, 106.635, -135.457,
-13.3958, 36.9225, -55.8701,
-14.8467, 27.4234, -20.75,
-9.26049, 44.3478, -84.1828,
-9.51023, 43.9693, -82.6548,
-13.9657, 25.1136, -10.9592,
-14.4925, 34.1899, -46.0425,
-10.5672, 42.3162, -76.0544,
-11.5984, 40.5562, -69.2552,
-0.993421, 64.013, -126.478,
0.765767, 72.1493, -130.141,
-2.1096, 59.7809, -122.798,
-12.1454, 39.5104, -65.3578,
-13.062, 37.65, -58.5144,
-6.68714, 48.3172, -99.7383,
4.33504, 156.127, -142.176,
4.39741, 100.816, -134.536,
2.55245, 82.6571, -132.286,
-14.4223, 26.1384, -15.3963,
-1.22434, 63.1015, -125.766,
-4.58353, 52.82, -111.184,
-5.20508, 51.4016, -107.822,
1.17634, 74.0686, -130.953,
-7.37625, 47.2239, -95.5894,
-14.9706, 32.2558, -39.1074,
-15.1378, 29.7063, -29.6614,
-13.3868, 24.326, -7.21636,
-2.6613, 58.1303, -120.338,
-5.48993, 50.7878, -106.232,
-15.0685, 28.7501, -25.9925,
-13.7052, 36.2122, -53.3032,
0.437576, 70.5848, -129.527,
};
const int pnts3=sizeof(pnt)/sizeof(pnt[1]); // number of points * 3
const int pnts=pnts3/3; // number of points
//skeleton lines
int lin[]=
{
93, 24,
56, 44,
0, 89,
42, 59,
7, 64,
17, 90,
62, 50,
39, 59,
48, 77,
3, 36,
13, 14,
10, 157,
20, 79,
19, 17,
43, 60,
76, 90,
157, 136,
4, 72,
79, 117,
14, 2,
7, 6,
40, 6,
62, 66,
135, 10,
49, 73,
38, 5,
61, 75,
137, 153,
78, 148,
2, 57,
38, 47,
117, 33,
61, 83,
35, 40,
9, 137,
58, 56,
153, 34,
1, 41,
9, 145,
39, 121,
82, 98,
25, 147,
25, 146,
23, 34,
8, 99,
23, 146,
60, 91,
149, 54,
108, 27,
156, 127,
139, 120,
112, 132,
109, 110,
150, 111,
124, 122,
151, 28,
150, 124,
155, 123,
151, 155,
29, 144,
128, 123,
114, 85,
30, 85,
114, 113,
95, 115,
115, 31,
116, 125,
95, 125,
31, 86,
55, 86,
87, 96,
88, 96,
52, 53,
1, 37,
58, 91,
70, 47,
8, 69,
5, 64,
53, 69,
126, 22,
15, 50,
45, 16,
65, 63,
45, 63,
13, 37,
141, 51,
57, 35,
15, 74,
71, 74,
48, 68,
72, 68,
46, 67,
20, 4,
70, 73,
141, 100,
16, 66,
18, 12,
52, 75,
18, 65,
46, 81,
42, 43,
121, 12,
41, 71,
24, 89,
22, 103,
77, 92,
21, 97,
36, 80,
126, 92,
21, 99,
33, 67,
102, 103,
44, 83,
76, 98,
118, 133,
87, 55,
101, 3,
51, 81,
49, 100,
136, 148,
78, 11,
142, 101,
82, 93,
19, 97,
104, 140,
140, 105,
104, 149,
106, 118,
129, 107,
106, 130,
129, 130,
134, 84,
27, 84,
138, 134,
138, 120,
132, 110,
112, 111,
116, 119,
26, 105,
131, 94,
154, 147,
54, 107,
108, 133,
88, 32,
156, 109,
135, 145,
127, 139,
29, 128,
113, 119,
28, 122,
143, 80,
152, 30,
142, 102,
144, 94,
131, 152,
143, 11,
26, 154,
};
const int lins2=sizeof(lin)/sizeof(lin[1]); // number of lines * 2
const int lins=lins2/2; // number of lines
//---------------------------------------------------------------------------
int pol[pnts],pols=0; // polyline
double avg[pnts3]; // sliding average
//---------------------------------------------------------------------------
const int _mesh=100;
double mesh[_mesh*3];
int meshs=0,meshs3=0;
//---------------------------------------------------------------------------
void compute()
{
int i,j,e,n,i0,i1;
int his[pnts];
int used[lins];
double x,y,z,w,rr,ll;
//--- compute polyline pol[pols] ----------------------------------------
// histogram of point usagge
for (i=0;i<pnts;i++) his[i]=0;
for (i=0;i<lins2;i++) his[lin[i]]++;
// clear tables
for (i=0;i<pnts;i++) pol[i]=-1; pols=0;
for (i=0;i<lins;i++) used[i]=0;
// find start point (his[i]!=2)
for (e=1,i=0;i<pnts;i++)
if ((his[i])&&(his[i]!=2))
{ e=0; break; }
if (e) return; // stop if none found
// add start point to polyline
pol[pols]=i; pols++;
// process polyline
for (e=1;e;)
for (e=0,j=0;j<lins;j++)
if (!used[j]) // ignore used lines
{
// is point i in line j ?
if (lin[j+j+0]==i) i=lin[j+j+1];
else if (lin[j+j+1]==i) i=lin[j+j+0];
else continue;
// add next point to polyline
pol[pols]=i; pols++;
used[j]=1;
if (his[i]==2) e=1; // loop if not end of polyline
break;
}
//--- compute sliding average -------------------------------------------
n=10; // sliding average half interval [poins]
w=1+n+n; w=1.0/w;
for (i=0;i<pols;i++)
{
e=3*pol[i];
x=pnt[e]; e++;
y=pnt[e]; e++;
z=pnt[e]; e++;
for (j=1;j<=n;j++)
{
e=i+j; if (e>=pols) e=pols-1;
e=3*pol[e];
x+=pnt[e]; e++;
y+=pnt[e]; e++;
z+=pnt[e]; e++;
e=i-j; if (e<0) e=0;
e=3*pol[e];
x+=pnt[e]; e++;
y+=pnt[e]; e++;
z+=pnt[e]; e++;
}
e=3*i;
avg[e]=x*w; e++;
avg[e]=y*w; e++;
avg[e]=z*w; e++;
}
//--- regress lines -----------------------------------------------------
meshs=0; meshs3=0;
ll=20.0;
for (e=0,i=0;i<pols;i++)
{
// distance to sliding average
j=3*pol[i];
x=pnt[j]; j++;
y=pnt[j]; j++;
z=pnt[j]; j++;
j=3*i;
x-=avg[j]; j++; x*=x;
y-=avg[j]; j++; y*=y;
z-=avg[j]; j++; z*=z;
rr=x+y+z;
if ((e==0)&&(rr<=ll)){ i0=i; e++; }// find start point
else if ((e==1)&&(rr> ll)) // find end point
{
i1=i-1; e=0; if (i0==i1) continue;
// regress line from pol[i0..i1]
int j0,j1;
double dx,dy,dz;
// ignore n edge points
n=10; while ((i1-i0)<(n<<2)) n--;
j0=i0+n;
j1=i1-n;
// direction
j=3*pol[j1];
dx=pnt[j]; j++;
dy=pnt[j]; j++;
dz=pnt[j]; j++;
j=3*pol[j0];
dx-=pnt[j]; j++;
dy-=pnt[j]; j++;
dz-=pnt[j]; j++;
// original line size
j=3*pol[i1];
x=pnt[j]; j++;
y=pnt[j]; j++;
z=pnt[j]; j++;
j=3*pol[i0];
x-=pnt[j]; j++;
y-=pnt[j]; j++;
z-=pnt[j]; j++;
// rescale direction to match original half size
rr=sqrt((x*x)+(y*y)+(z*z));
rr=divide(rr,sqrt((dx*dx)+(dy*dy)+(dz*dz)));
rr*=0.5;
dx*=rr;
dy*=rr;
dz*=rr;
// avg position
for (x=y=z=0.0,n=0,i=j0;i<=j1;i++)
{
j=3*pol[i];
x+=pnt[j]; j++;
y+=pnt[j]; j++;
z+=pnt[j]; j++;
n++;
}
x/=n;
y/=n;
z/=n;
// line is avg+/-half direction
mesh[meshs3]=x-dx; meshs3++; meshs++;
mesh[meshs3]=y-dy; meshs3++;
mesh[meshs3]=z-dz; meshs3++;
mesh[meshs3]=x+dx; meshs3++; meshs++;
mesh[meshs3]=y+dy; meshs3++;
mesh[meshs3]=z+dz; meshs3++;
// restore main loop
i=i1+1; e=0;
}
}
i=0;
}
//---------------------------------------------------------------------------
mesh[meshs3] 保存结果折线的 3D 点坐标（每条线 2 个点）meshs 是点数，所以 num_of_lines=meshs/2