プログラミングのお題スレ Part14

プログラミングのお題 ..

109:デフォルトの名無しさん
19/05/24 02:55:43.78 /EuQv4hQ.net
>>108 この凸包図を眺めてると、正解の正方形は左辺の一番長い線を1辺とした正方形になりそうだが、それをどうやって求めるのか。
How to find the minimum-area-rectangle (MAR) fitted on the given points?
URLﾘﾝｸ(gis.stackexchange.com)
最初に書いた人は、凸包を求めて重心を中心として1度ずつ回転させるやり方を考えたらしいが、下の方で良い解法のコメントが付いてた。
URLﾘﾝｸ(i.stack.imgur.com)
少しずつ回転させるのではなくて、長方形の1辺は必ず凸包の辺のどれかと重なってるはずだから、凸包の辺の角度だけをとって試せば良いとのこと。
これなら重心を求める必要もないし、時間はかからない。
長方形が求まったら、座標系の中に入る正方形にすれば良いがはみ出してたら、参考解かな。
このアルゴリズムは、
The algorithm you are looking for is known in polygon generalisation as "smallest surrounding rectangle".
凸包最小長方形の解法とでも言えば良いのかな。

次ページ

続きを表示

1を表示