頂点に誤差のある面積の最大値を求めるには？

15角形の各頂点に1㎝の誤差がある時、面積の最大値を求めるにはどうすればよいでしょうか？

X Y

160 51

167 67

184 102

190 122

185 133

171 136

153 138

115 122

85 103

54 64

66 45

87 34

122 43

133 46

160 51

Answer 1

[mizuki]

最大面積となる頂点は最適化計算で求めることができます。 多角形の面積は頂点 i, i+1, 中心 の三角形の面積の和ですので、それを目的関数とします。 ここで定義した目的関数を最大にするような15つの頂点を最適化で求めます。 制約条件として、それぞれの変数が定義されている数値±1になる点を定義します。

最適化の関数はたくさんありますが、 fmincon 関数が適切だと思います。

なお、多角形の面積は以下のように polyarea 関数で求めることができます。

area_poly = polyarea(A(:,1), A(:,2));

多角形ではなく直方体の面積最大化の課題ですが、似たような例を以下のvideoで解説していますので、目的関数と制約条件の設定の参考にしてください。

- 最適化による課題解決とパフォーマンス向上

https://jp.mathworks.com/videos/optimization-to-solve-problems-and-improve-performance-116782.html

[Tohru Kikawada]

mizukiさんの提示された方法で実装した例が下記のものです。

ご参考まで。

function verticesOptimized = findVerticesMaximizingArea
% 頂点を定義
vertices = [160 51
    167 67
    184 102
    190 122
    185 133
    171 136
    153 138
    115 122
    85 103
    54 64
    66 45
    87 34
    122 43
    133 46];

% 可視化
figure; patch(vertices(:,1),vertices(:,2),'b','FaceAlpha',.5);
axis equal;
hold on;
hopt = patch(vertices(:,1),vertices(:,2),'r','FaceAlpha',.5);
legend('x0','optimized');

% 非線形最適化問題として解く
x0 = reshape(vertices',[],1);
lb = x0-1;
ub = x0+1;
axis([min(lb(1:2:end-1)) max(ub(1:2:end-1)) ...
    min(lb(2:2:end)) max(ub(2:2:end))]);

% 面積の逆数を目的関数とする
% (許容誤差に対して相対的に小さくなりすぎないように1000倍)
fun = @(x) 1/polyarea(x(1:2:end-1), x(2:2:end))*1000;

% OutputFcnを指定して各反復毎の値をプロット
options = optimoptions('fmincon','Display','iter',...
    'PlotFcn',@optimplotfval,'OutputFcn',@outfun);

% 最適化を実行
verticesOptimized = fmincon(fun,x0,[],[],[],[],lb,ub,[],options);

      % 途中の値の可視化
      function stop = outfun(x,~,~)
          stop = false;
          set(hopt,{'XData','YData'},...
              {x(1:2:end-1),x(2:2:end)}); % パッチのアップデート
          pause(0.1); % 0.1ごとに表示
      end
  end

%