市町村単位でのボロノイ分割 C++バージョン

以前、Excelで、K-mean法で試した時のデータを使って、C++でプログラムを書いて、実行してみました.C++でもすべての場合について調べるには膨大な時間がかかるので、最適とは限りませんが.Excelの時とはちょっと違う結果になりました.元のデータは政令指定都市を区まで分割して、3200余りの自治体になっていた頃のデータを使っています.

単なるボロノイ分割ではなくて、地理的最適配置問題です.領域の重心とボロノイ分割の母点が一致する分割で、なおかつ、母点からの距離の二乗和が最小になるようにしてあります.なお、すべての人の位置はわからないので、自治体ごとに、自治体の住人の住所を市役所の位置で近似してあります.

８分割

ごくありきたりの分割です.7分割以下だと、近畿地方と中部地方がくっ付いてしまいます

重心に近い自治体	東経	北緯	人口	面積	人口の多い自治体
埼玉県志木市	139.6162062	35.82522217	45790846	54786.73	東京都世田谷区
大阪府大阪市西淀川区	135.4401848	34.71044823	22120718	32957	大阪府堺市
岐阜県可児郡御嵩町	137.1210417	35.39625119	17690526	45834.5	静岡県静岡市
熊本県山鹿市	130.6770522	33.04008283	14224915	43695.53	熊本県熊本市
山形県最上郡最上町	140.49021	38.7660707	10586804	65410.82	新潟県新潟市
広島県御調郡向島町	133.1613144	34.3623622	10041710	44984.13	岡山県岡山市
北海道夕張市	141.8893119	43.04523516	5775712	80574.98	北海道旭川市
沖縄県中頭郡嘉手納町	127.6720579	26.32134135	1476817	3513.4	沖縄県那覇市

35分割

現在の兵庫県の範囲が１つの区域になります.（淡路島が外れてしまいますが）

重心に近い自治体	東経	北緯	人口	面積	人口の多い自治体
神奈川県横浜市青葉区	139.5514335	35.57312872	18437070	5141.08	東京都世田谷区
千葉県松戸市	139.934922	35.77111886	13992019	6543.31	東京都江戸川区
大阪府大阪市東成区	135.5396186	34.66885386	12302628	5653.71	大阪府堺市
愛知県名古屋市北区	136.9344966	35.19414584	8499652	11335.01	岐阜県岐阜市
埼玉県大里郡妻沼町	139.3444922	36.19314402	5069054	9324.35	埼玉県川越市
佐賀県神埼郡三瀬村	130.3326866	33.44783209	4409521	7066.55	福岡県福岡市東区
滋賀県大津市	135.8434477	35.06770647	3811862	7759.93	滋賀県大津市
兵庫県小野市	134.9218501	34.83534555	3719104	9074.87	兵庫県姫路市

a10035g100713604.csv

79分割

播磨の範囲が１つの区域になります。都市圏の単位という気もします。

重心に近い自治体	東経	北緯	人口	面積	人口の多い自治体
東京都新宿区	139.7025171	35.70357353	9656812	807.25	東京都世田谷区
大阪府大阪市北区	135.5167096	34.71040398	8818691	1560.18	大阪府堺市
神奈川県横浜市戸塚区	139.5497332	35.40760446	6754717	2243.56	神奈川県横須賀市
東京都国立市	139.4338098	35.67828466	5880285	2192.73	神奈川県相模原市
愛知県名古屋市緑区	136.9880113	35.0674179	4996931	2905.88	愛知県豊田市
千葉県松戸市	139.9180134	35.78580966	4977967	1174.63	東京都江戸川区
埼玉県桶川市	139.5845241	36.02124194	3934389	2505.41	埼玉県川越市
岐阜県羽島郡川島町	136.8424391	35.33733399	3460717	5337.09	岐阜県岐阜市
京都府京都市山科区	135.8048257	34.96839562	3036797	3354.33	滋賀県大津市
福岡県福岡市博多区	130.4458486	33.58487106	2579792	1973.2	福岡県福岡市東区
北海道札幌市東区	141.3596607	43.07479737	2556216	8131.41	北海道札幌市北区
群馬県佐波郡玉村町	139.1495709	36.32297662	2495021	7009.13	群馬県前橋市
千葉県千葉市緑区	140.1693306	35.5734713	2472731	2610.43	千葉県市原市
奈良県北葛城郡河合町	135.7424962	34.57306561	2247961	3008.53	奈良県奈良市
広島県広島市西区	132.44911	34.4013326	2233520	6779.15	広島県広島市安佐南区
兵庫県神戸市長田区	135.1141704	34.68920334	2196901	1332.17	兵庫県明石市
福岡県北九州市小倉南区	130.8791575	33.83905373	2054996	2984.86	福岡県北九州市八幡西区
岡山県児島郡灘崎町	133.9226921	34.5726279	1972345	3580.31	岡山県岡山市
栃木県宇都宮市	139.890881	36.53106068	1912613	6524.55	栃木県宇都宮市
宮城県宮城郡利府町	140.9569796	38.32363215	1870735	4023.32	宮城県仙台市青葉区
静岡県引佐郡細江町	137.6199955	34.77635842	1826568	3781	静岡県浜松市
大阪府泉南市	135.2988195	34.31917419	1707499	2800.6	和歌山県和歌山市
長野県小県郡青木村	138.1583706	36.37697696	1679098	7382.02	長野県長野市
静岡県三島市	138.9162556	35.12693639	1663761	3678.19	静岡県富士市
熊本県熊本市	130.6930621	32.80112156	1584757	4359.09	熊本県熊本市
福岡県三潴郡三潴町	130.458502	33.23442877	1577995	3272.94	福岡県久留米市
茨城県稲敷郡江戸崎町	140.3700444	35.9441265	1550317	2905.62	茨城県つくば市
兵庫県姫路市	134.7240013	34.83275321	1463241	3178.46	兵庫県姫路市

a10079g100255592.csv

136分割

播磨が東西に分かれます。この方法では、姫路は東側に分類されました。

重心に近い自治体	東経	北緯	人口	面積	人口の多い自治体
東京都渋谷区	139.6813152	35.67766608	6352841	471.47	東京都世田谷区
東京都江戸川区	139.8713883	35.73719158	5003030	565.21	東京都江戸川区
神奈川県横浜市都筑区	139.5819621	35.52584397	4120416	518.15	東京都町田市
東京都立川市	139.4093219	35.68766504	4058227	1559.46	神奈川県相模原市
埼玉県さいたま市緑区	139.6823018	35.90121175	3815369	949.32	埼玉県川口市
大阪府門真市	135.5991027	34.74994002	3721061	664.31	大阪府東大阪市
愛知県名古屋市東区	136.9303667	35.16845061	3552457	1018.83	愛知県春日井市
大阪府大阪市住吉区	135.5300208	34.59317212	3401083	640.38	大阪府堺市
兵庫県伊丹市	135.3970416	34.76309798	2960433	966.19	兵庫県尼崎市
京都府京都市南区	135.7537184	34.97294498	2459519	2291.92	滋賀県大津市
神奈川県横浜市栄区	139.5815216	35.3477094	2450676	436.92	神奈川県横須賀市
千葉県千葉市若葉区	140.172794	35.62045072	2374389	1773.64	千葉県市原市
福岡県福岡市博多区	130.4183861	33.57766082	2260570	1315.15	福岡県福岡市東区
北海道札幌市東区	141.3836299	43.05935686	2141353	2217.65	北海道札幌市北区
愛知県安城市	137.0539564	34.96777708	2097888	1687.73	愛知県豊田市
岐阜県羽島郡柳津町	136.7481446	35.35870927	1868536	2464.22	岐阜県岐阜市
広島県安芸郡府中町	132.4955545	34.37781085	1823789	2529.2	広島県広島市安佐南区
神奈川県伊勢原市	139.3161884	35.37201955	1790891	1280.09	神奈川県平塚市
兵庫県神戸市須磨区	135.0830063	34.67053015	1760627	1038.16	兵庫県明石市
福岡県北九州市八幡西区	130.7903261	33.79711876	1690091	1798.15	福岡県北九州市八幡西区
埼玉県鶴ヶ島市	139.4091961	35.93196204	1634718	1845.28	埼玉県川越市
宮城県仙台市若林区	140.8938333	38.25103725	1530985	2083.05	宮城県仙台市青葉区
奈良県天理市	135.8134555	34.58625056	1480623	3042.47	奈良県奈良市
福岡県三潴郡三潴町	130.4622061	33.24337317	1457815	2486.29	福岡県久留米市
群馬県前橋市	139.0449049	36.37581822	1456352	5021.37	群馬県前橋市
茨城県取手市	140.0611139	35.92077497	1431143	1340.06	千葉県柏市
埼玉県大里郡妻沼町	139.3695708	36.23878332	1426652	1448	栃木県足利市
岡山県都窪郡早島町	133.8676321	34.62796362	1389844	1855.71	岡山県岡山市
静岡県浜北市	137.8176099	34.76615215	1261229	2600.09	静岡県浜松市
熊本県熊本市	130.7387162	32.8571457	1223691	3456.48	熊本県熊本市
兵庫県高砂市	134.786005	34.82345715	1200686	1670.11	兵庫県姫路市

a10136g100126806.csv

２７１分割

これは、政府が目標としていた300の基礎自治体というパターンに相当すると思います。姫路は加古川や高砂などと同じ分類でした。

重心に近い自治体	東経	北緯	人口	面積	人口の多い自治体
東京都目黒区	139.68894	35.6041075	3024422	250.39	東京都世田谷区
大阪府大阪市東成区	135.5576588	34.66794511	2961773	277.96	大阪府東大阪市
東京都中野区	139.6838365	35.72281138	2921382	181.77	東京都練馬区
東京都江戸川区	139.8712923	35.73883407	2772312	273.98	東京都江戸川区
神奈川県横浜市神奈川区	139.5971458	35.49036277	2404376	289.4	神奈川県横浜市港北区
大阪府豊中市	135.4608168	34.75763975	2349243	331.29	兵庫県尼崎市
東京都清瀬市	139.5228471	35.77230813	1853774	276.99	埼玉県所沢市
東京都稲城市	139.5220702	35.64489005	1778111	206.15	東京都府中市
神奈川県横浜市栄区	139.5524589	35.36549293	1682611	257.06	神奈川県藤沢市
北海道札幌市中央区	141.3481845	43.06343118	1671725	1154.9	北海道札幌市北区
愛知県名古屋市東区	136.9450857	35.19413201	1624831	293.09	愛知県春日井市
東京都昭島市	139.3340101	35.6953103	1535028	962.05	東京都八王子市
大阪府堺市	135.4810284	34.56261093	1531077	292.19	大阪府堺市
大阪府枚方市	135.6212445	34.80662667	1512979	365.17	大阪府枚方市
京都府京都市中京区	135.7726899	35.00441882	1476376	850.93	滋賀県大津市
福岡県福岡市城南区	130.3801097	33.58224374	1466033	540.34	福岡県福岡市東区
東京都墨田区	139.7884293	35.68887666	1444805	126.95	東京都江東区
東京都町田市	139.4087188	35.5401613	1437841	332.15	神奈川県相模原市
埼玉県さいたま市緑区	139.6816284	35.85084701	1408492	176.89	埼玉県川口市
広島県広島市西区	132.4559381	34.40702068	1341065	1836.32	広島県広島市安佐南区
千葉県習志野市	140.028455	35.69316761	1328854	234.49	千葉県船橋市
宮城県仙台市宮城野区	140.9060731	38.26871488	1305888	1028.25	宮城県仙台市青葉区
岡山県都窪郡早島町	133.857738	34.61830969	1272134	1336.08	岡山県岡山市
愛知県名古屋市緑区	136.9402792	35.07111703	1209942	319.73	愛知県名古屋市緑区
埼玉県吉川市	139.8363565	35.86671626	1144663	322.58	埼玉県越谷市
神奈川県高座郡寒川町	139.3750195	35.38080372	1086199	332.25	神奈川県平塚市
福岡県北九州市小倉北区	130.907955	33.89038075	1038961	782.42	山口県下関市
千葉県千葉市中央区	140.1461006	35.57790057	998623	677.64	千葉県市原市
熊本県熊本市	130.7359095	32.84831308	992796	1563.58	熊本県熊本市
静岡県浜松市	137.7465147	34.77923487	968851	2104.67	静岡県浜松市
岐阜県瑞穂市	136.6974562	35.3947093	965293	1677.84	岐阜県岐阜市
兵庫県西宮市	135.3294949	34.74378685	964628	250.59	兵庫県西宮市
埼玉県比企郡川島町	139.5344912	35.96096329	961605	351.98	埼玉県川越市
愛知県江南市	136.8537957	35.32463545	931609	404.89	愛知県一宮市
京都府久世郡久御山町	135.7570744	34.89575175	906848	368.96	京都府京都市伏見区
兵庫県高砂市	134.7467447	34.78958258	870977	500.66	兵庫県姫路市

a10271g100049069.csv