詳しい人求む！

最適な撮影位置を求めるアルゴリズム

解決済

質問者：usa3usa
質問日時：2022/03/18 07:52
回答数：4件

数学かプログラミングかどちらのカテゴリーに質問したらよいか迷いましたが、とりあえずここに質問します

台形ABCDの領域を撮影できるカメラとサンプル(xi,yi) i=0,1000が分布している板がある
板をy方向に移動させてより多くのサンプルが撮影範囲に入るようにしたい

最適な移動量Y0を求めるアルゴリズムをC言語で記述したいです。

なお、サンプルは(xi,yi)、台形ABCDは A(X1,Y3),B(X1,Y2),C(X2,Y1),D(X2,Y4) で与えられています（X1<X2,Y1<Y2<Y3<Y4)。
板の上のサンプルは(xi,yi)は撮影時には(xi,yi+Y0)となります。

移動量yと撮影範囲に入るサンプル数f(y)の関数（対応表）を定義して、
移動量としては、「（xi,yi)が辺BC上に来る移動量y」の１０００か所として
f(y)の最大値のY0=yを見つければ良いことはわかりますが、馬鹿正直にそのままプログラミングするのでは効率が悪い気がしています

賢いアルゴリスム、アドバイスお願いします。

通報する

この質問への回答は締め切られました。

質問の本文を隠す

回答 (4件)

ベストアンサー優先
最新から表示
回答順に表示

No.2ベストアンサー

回答者： Tacosan
回答日時：2022/03/19 05:40

サンプルごとに「撮影範囲に『入る』移動量」「撮影範囲から『出る』移動量」を計算して, それを (全サンプルで) ソートしたあと移動

量を変えながら「撮影範囲に入っているサンプル数」を計算していく.

- 0
- 件

通報する

この回答へのお礼

賢いアルゴリスムのアドバイスの回答ありがとうございます

実は私も今朝、撮影範囲の入出状況に着目したアルゴリズムを思いついたところです。

確かに、馬鹿正直プログラムはオーダーo(n²)ですので、
この方法ならば、
　ソートがo(n log(n)）のオーダー
　移動量による変化はo(n)のオーダー
なので、トータルo(n log(n)）のオーダー計算できる、賢いアルゴリスムですね。

ありがとうございます。

通報する

お礼日時：2022/03/19 13:44

No.4

回答者： sukitaro
回答日時：2022/03/19 16:56

No3です。

すみません、質問を勘違いしていました。

for文の中の繰り返しをなくしました。
「// canvas描画」の直前のブロックを以下に差し替えてください。

// X1 < x < X2 以外不要
const inX12_dots = dots.filter(v => (X1 < v[0] && v[0] < X2));
// BC上最小値
const onBC_dots = inX12_dots.map(v => onBC(...v));
const onBC_min = Math.min(...onBC_dots);
// BC上最小値との差 onBC_dysは0以下にして、onAD_dysは正のみフィルタ
const onBC_dys = onBC_dots.map(v => onBC_min - v);
const onAD_dys = inX12_dots.map(v => onAD(...v) - onBC_min).filter(v => v >= 0);
// 配列を合体して絶対値でソート
const dys = [...onBC_dys, ...onAD_dys].sort((a,b)=> Math.abs(a) - Math.abs(b));
// ここからfor文
const Ns = dys.length;
let s = 1, // 正の時+1, 0と負の時-1を足す
s_max = 0, // sの最大値
y_best = 0; // s最大値の時のy0
for(let i = 0; i < Ns; i++){
s += (dys[i] > 0) ? 1 : -1;
if(s_max < s){
s_max = s;
y_best = onBC_min + dys[i];
}
}

- 0
- 件

通報する

この回答へのお礼

再度の回答ありがとうございます

＞すみません、質問を勘違いしていました。
こちらこそ、分りにくい質問をしてしまい、恐縮です。

＞// 配列を合体して絶対値でソート
＞const dys = [...onBC_dys, ...onAD_dys].sort((a,b)=> Math.abs(a) - Math.abs(b));

なるほど！

ここでo(n log(n)）のオーダー
最小値を求める　for(let i = 0; i < Ns; i++)　はo(n)のオーダー

で、トータルo(n log(n)）のオーダー計算できる、賢いアルゴリスムですね

ありがとうございます。

通報する

お礼日時：2022/03/19 23:03

No.3

回答者： sukitaro
回答日時：2022/03/19 12:04

C言語は分からないのでJSですが、こんなのはどうでしょうか。

<!DOCTYPE html>
<html lang="ja">
<head>
<meta charset="UTF-8">
<title>sample</title>
</head>
<body>
<canvas></canvas>
<script>
// canvas の幅と高さ
const width = 400,
height = 800;
// ABCDの頂点
const [X1, X2, Y1, Y2, Y3, Y4] = [100, 200, 50, 100, 150, 200];
const A = [X1, Y3],
B = [X1, Y2],
C = [X2, Y1],
D = [X2, Y4],
// [x, y - y0] が BC, AD上にあるときのy0を返す
onBC = (x, y) => y - Y2 - (Y1 - Y2) * (x - X1) / (X2 - X1),
onAD = (x, y) => y - Y3 - (Y4 - Y3) * (x - X1) / (X2 - X1);
// [xi, yi] を1000個用意する
const raw_dots = new Array(1000).fill(0);
const dots = raw_dots.map((v) => [Math.random() * width | 0, Math.random() * height | 0]);

// X1 < x < X2 以外不要
const inX12_dots = dots.filter(v => (X1 < v[0] && v[0] < X2));
// BC,AD上のy0
const onBC_dots = inX12_dots.map(v => onBC(...v)).sort((a,b) => a - b);
const onAD_dots = inX12_dots.map(v => onAD(...v));
// AD上最大値
const onAD_max = Math.max(...onAD_dots);
// ここから馬鹿正直
const Ns = onBC_dots.length;
let s_max = 0, y_best = 0;
for(let i = 0; i < Ns; i++ ){
let yi = onBC_dots[i];
let si = onAD_dots.filter(y => y < yi).length - i;
if(s_max < si) {
s_max = si;
y_best = yi;
}
if(yi > onAD_max) break;
}

// canvas描画
const canvas = document.querySelector('canvas');
canvas.width = width;
canvas.height = height;
const ctx = canvas.getContext('2d');
ctx.strokeStyle = 'red';
ctx.beginPath();
ctx.moveTo(X1, Y3 + y_best);
ctx.lineTo(X1, Y2 + y_best);
ctx.lineTo(X2, Y1 + y_best);
ctx.lineTo(X2, Y4 + y_best);
ctx.lineTo(X1, Y3 + y_best);
ctx.stroke();
ctx.strokeStyle = 'blue';
dots.forEach(d => {
ctx.beginPath();
ctx.arc(...d, 2, 0, 2 * Math.PI);
ctx.stroke();
});
</script>
</body>
</html>

- 0
- 件

通報する

この回答へのお礼

回答ありがとうございます

すいません、回答いただいたプログラム、賢いアルゴリスムの部分が読み取れません（汗；）。
解説いただければ幸いです。

私の理解：
回答いただいたプログラム拝見したところ、
for(let i = 0; i < Ns; i++ ){
でo(n)のオーダー
そこの中の
let si = onAD_dots.filter(y => y < yi).length - i;
の処理もo(n)のオーダーで
結果、全体でo(n²)のアルゴリズムのままの気がします。

通報する

お礼日時：2022/03/19 14:00

No.1

回答者： lv4u
回答日時：2022/03/18 08:01

まずは、馬鹿正直にそのままプログラミングしてみて、とりあえず動作するようになってから、アルゴリズムとか、プログラムの効率を改善して

みれば？

- 0
- 件

通報する

この回答へのお礼

回答ありがとうございます

賢いアルゴリスム、アドバイスお願いします。

ーー馬鹿正直プログラムーーーー
smax=0; ybest=0;
for(i=0; i<Ns; i++) {
　　yshift = getyOnBC(x[i],y[i],X1,Y2, X2,Y1);
　　s=0;
　　for(j=0; j<Ns; j++)
　　　　if( inABCD(x[j],y[j]+yshift, X1,X2, Y1,Y2,Y3,Y4) >0) s++;
　　if(s > smax) {
　　　smax=s; ybest = yshift;
　　}
}

通報する

お礼日時：2022/03/18 09:30

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう！