質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

Q&A

解決済

4回答

3756閲覧

【アルゴリズム】図形縮小のための頂点の座標移動の方向の判定

takes.it.easy

総合スコア18

Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

1グッド

1クリップ

投稿2021/10/08 02:42

前提・実現したいこと

図のような複数の頂点からなるポリゴンの各辺をある一定の距離Lで法線方向に縮小することが目的です。
アルゴリズムとして各頂点の座標の配列と一定の距離Lを与えpythonなどで自動で行えるようにしたいと考えています。
イメージ説明

発生している問題・エラーメッセージ

図形縮小後の頂点(P0',P1',...,Pn')は縮小前の頂点(P0,P1,...,Pn)を各直線の法線方向にLだけ平行移動させ移動後の2点([P0A,P0B],[P1A,P1B],...,[PnA,PnB])からなる各直線の交点を取ればよいという事はわかっています。

問題は頂点を移動させる際,図形を縮小させる方向の判断をどのように行えばよいかという事です。
各直線の法線はオレンジ矢印と緑矢印の2種類があり、オレンジ矢印の判断をどのように行えばよいかがわかりません。

どうぞよろしくお願い致します。

can110👍を押しています

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

fana

2021/10/08 02:48

前提として > 縮小前の頂点(P0,P1,...,Pn) なるデータの順序は不明であるという話なのでしょうか? すなわち, ・頂点群の座標:順序不明 ・辺群のデータ:各辺の2端点がどの頂点なのか みたいな形でしかデータが無いような?
takes.it.easy

2021/10/08 03:02

頂点群の座標の順序は決まっています。プログラムとして実装する際にはポリゴンを形成する頂点を配列で与えることを想定しています。 辺を結ぶ2点は[(P0, P1),(P1,P2),...,(Pn, P0)]というように表されます。
guest

回答4

0

(以下,例示されたデータを用いて記す)

与えられたデータから,
「P0→P1→P2→P3→P4→P0 と辿れば一周できる」ということは知ることができると思います.

この方向でポリゴンの縁を辿るときに,
各頂点位置で曲がる角度を調べます.(角度:±180の範囲とする.例えば「右に曲がる方向を+,左に曲がる方向を-」のように)
全頂点位置での角度の総計値の符号から,この辿り方が 右回り or 左回り のどちらなのかが判別できます.

上記順序でポリゴンの縁を辿るときには,(右曲がりを+とするなら)総和は+となり,ポリゴンの内側は右手側にあることがわかります.

投稿2021/10/08 02:57

編集2021/10/08 04:23
fana

総合スコア11634

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

fana

2021/10/08 03:04 編集

※入力時点で頂点データが「右回り or 左回り の順になっているぞ」みたいな話になっているのであれば, そもそもこのように「調べる」必要はないのですが. (どの直線同士の交点を取ればいいのか?というのを把握できている時点で,必要な情報はほとんど既知なんじゃないか?とか想像しますが)
can110

2021/10/08 04:07

曲がり回数ではなく、左右それぞれの曲がり角度の積算値の大きい方を選ぶべきかと。 たとえばP3,4,0のように凹んだ(左曲がりの)部分がより滑らか(多数の点で構成)されているケースが考えられます。
fana

2021/10/08 04:28 編集

ご指摘感謝. 全面的にその通りですね. (ちょっと前に,これ系で「直角にしか曲がらない話」があり,そのときの記憶を引きずってしまった感)
fana

2021/10/08 04:22

頂いたコメント内容を鑑みて,内容を修正しました. (一部分だけに取り消し線を引いて文言修正するような形にはできなかったので,全体的に修正.)
fana

2021/10/08 07:27 編集

ところで,(この回答内容とは全然関係ないのだけども) 全ての頂点の座標を k(<1.0) 倍したものの位置を適切にオフセットさせることによって,本件が求めている結果を得る…ような方向はないのかなぁ? オフセットについては,ある頂点の二等分線方向だけに限定できそうな気がするから,未知数は{倍率k, オフセット量}という2個になりそうだけど…? (探索にならずに,こう,えいや!で解析解が得られるものだろうか?)
guest

0

とりあえず単純な方法としては,「2個の結果を作って一方を選ぶ」で.

「P0→P1→P2→P3→P4→P0 と辿れば一周できる」までが分かった時点で

各直線の法線はオレンジ矢印と緑矢印の2種類があり…

の{オレンジ側で作った結果,緑側で作った結果}の2つを作ることができるわけで,そしたらあとは

  • より小さい方(面積が簡単に計算できる場合はこんな判定で)
  • 他方に包括されている側:一方側の1個の頂点について,他方の図形の内外どっちにあるか?の判定を行えばよいかな.

(「他方」じゃなくて「元の図形」でもいいけど)

…みたいな判断で,元の図形の縮小版となる側を選べばよい,という.

投稿2021/10/09 09:56

編集2021/10/09 09:57
fana

総合スコア11634

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

ベストアンサー

質問で提示された手順をそのまま順番に行ってみたコードを示します。うまくできているようです。
法線の向きの決定方法はfanaさんの回答を参考にしました。
ただし、縮小方向の距離を大きくしすぎると、ポリゴンが「潰れて」意図しない結果になります。

Python

1import numpy as np 2import matplotlib.pyplot as plt 3 4# 単位ベクトルを返す 5def norm(v): 6 return v / np.linalg.norm(v) 7 8# 法線ベクトルを求める 9# is_right : 始点→終点から見て右の法線を返す 10def norm_v(v, is_right=False): 11 v = norm(v) 12 v = np.array([[0,-1],[1,0]]) @ v 13 if is_right: 14 v *= -1 15 return v 16 17# ポリゴンの内側の方向(左右)を返す 18def calc_dir(points, lines): 19 # 前後左右の判定 20 # http://taustation.com/math-vector-directyon-discriminaion/ 21 22 is_right = 0 23 NL = lines.shape[0] 24 for i in range(NL): 25 l1, l2 = lines[i], lines[(i+1)%NL] 26 p1, p2, p3 = points[l1[0]], points[l1[1]], points[l2[1]] 27 v1, v2 = p2 - p1, p3 - p2 28 29 # 方向ベクトルvを90度回転させた上で上記の前後判定を行うことで左右判定が可能になる。 30 v2 = norm_v(v2) 31 is_right += v1@v2 # 積算。内積値のままでいいだろう 32 33 is_right = is_right > 0 34 return is_right 35 36# 線分ABと線分CDの交点を求める関数 37def calc_cross_point(A, B, C, D): 38 # 【python】線分ABと線分CDの交点(2つの直線の交点)を計算する 39 # https://rikoubou.hatenablog.com/entry/2019/04/03/163751 40 41 cross_ = (0,0) 42 bunbo = (B[0] - A[0]) * (D[1] - C[1]) - (B[1] - A[1]) * (D[0] - C[0]) 43 44 vAC = ((C[0] - A[0]), (C[1] - A[1])) 45 r = ((D[1] - C[1]) * vAC[0] - (D[0] - C[0]) * vAC[1]) / bunbo 46 s = ((B[1] - A[1]) * vAC[0] - (B[0] - A[0]) * vAC[1]) / bunbo 47 48 # rを使った計算の場合 49 distance = ((B[0] - A[0]) * r, (B[1] - A[1]) * r) 50 return (A[0] + distance[0], A[1] + distance[1]) 51 52# 描画用の点群を返す 53def get_draw_points(points): 54 return zip(*(np.vstack([points, points[0]]))) 55 56 57 58L = 1 # 縮小する距離 負値=拡大 59points = [[10,10],[20,10],[20,20],[10,20],[15,15]] 60NP = len(points) 61lines = [[i,(i+1)%NP] for i in range(NP)] 62points = np.array(points) 63lines = np.array(lines) 64 65# ポリゴンの内側を判定するための「向き」を得る 66is_right = calc_dir(points, lines) 67 68# 移動後の点を求める 69new_points = [] 70NL = lines.shape[0] 71for i in range(NL): 72 # 2つの線分をなす始点、中点、終点 73 l1, l2 = lines[i], lines[(i+1)%NL] 74 p1, p2, p3 = points[l1[0]], points[l1[1]], points[l2[1]] 75 76 # 2つの線分をそれぞれ法線方向にLだけ内側に移動した線分の交点を求める 77 v1, v2 = norm_v(p2 - p1, is_right) * L, norm_v(p3 - p2, is_right) * L 78 p = calc_cross_point(p1 + v1, p2 + v1, p2 + v2, p3 + v2) 79 new_points.append(p) 80 81new_points = np.array(new_points) 82 83# 描画 84xs, ys = get_draw_points(points) 85plt.plot(xs,ys, c='black') 86xs, ys = get_draw_points(new_points) 87plt.plot(xs,ys, c='orange') 88plt.show()

イメージ説明

投稿2021/10/08 14:43

can110

総合スコア38234

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

takes.it.easy

2021/10/08 23:01

回答ありがとうございます。自分でもコードを考えていたのですが、法線の向きの部分でどうすれば良いか考えていたところでしたので、とても参考になります。 縮小距離を大きくし過ぎると「潰れて」しまうのは致し方なしと思います。もともと大きく縮小する予定はないので、その心配はないかとも思います。
takes.it.easy

2021/10/10 03:40 編集

何点か質問させていただきます。 ①lines[(i+1)%NL]の%演算子はどういう意図で使われているものでしょうか(lines[i+1]では問題あり?)。 ②コードを実行すると『RuntimeWarning: invalid value encountered in true_divide return v / np.linalg.norm(v)』のエラーが出ます。単位ベクトルを返す関数で発生しています。原因はおそらく、私が用意したポリゴンの頂点座標に原点(0,0)が含まれているからだと思います。解決法としては原点を避けるように座標を設定するほかないでしょうか。 訂正(2021/10/10 12:34):②エラーの原因は頂点座標に原点が含まれるためではないようです。私が用意した頂点座標の一番最初の点と最後の点が重複していたのが原因でした。修正し、エラーは出なくなったので②は回答していただかなくても大丈夫です。すみませんでした。 よろしくお願い致します。
can110

2021/10/10 08:34

①についてですが、lines[i] と lines[(i+1)%NL]の値をprintしてみればすぐに分かるかと思います。 またはlines[i+1]と修正して実行してみてもよいです。
takes.it.easy

2021/10/11 12:47

理解しました。lines[i]のインデックスが最後の値をとるときlines[i+1]のインデックスはNLと等しくなるのでlines[(i+1)%NL]とすることでlines[0]が得られるという事ですね。同じような処理を行うとき、私はわざわざif文を用意してましたが、この方法ではそれが必要なくなりますね。勉強になります。ありがとうございます。
guest

0

  • 全ての頂点の座標を k(<1.0) 倍したものの位置を適切にオフセットさせることによって,本件が求めている結果を得る…ような方向はないのかなぁ?

以下のように、重点をオフセットにすればできます。

python

1import matplotlib.pyplot as plt 2import cv2 3 4def barycenter(x, y): 5 mu = cv2.moments(np.stack([x,y]).T) 6 return int(mu["m10"]/mu["m00"]) , int(mu["m01"]/mu["m00"]) 7 8r = 0.8 9x1 = np.array([ 56, 500, 3384, 3128, 1592, 56]) 10y1 = np.array([333, 896, 768, 384, 512, 333]) 11x2 = (x1 * r).astype(int) 12y2 = (y1 * r).astype(int) 13gx1, gy1 = barycenter(x1, y1) 14gx2, gy2 = barycenter(x2, y2) 15x3 = x2 + gx1 - gx2 16y3 = y2 + gy1 - gy2 17plt.plot(x1, y1) 18plt.plot(x2, y2) 19plt.plot(x3, y3) 20plt.show() 21

実行結果です。
青の図形を0.8倍にしたのがオレンジの図形です。
それを重心の差だけ、x軸y軸ずらしたものが緑の図形で、これが求めるものになります。

重心移動

投稿2021/10/08 12:25

ppaul

総合スコア24666

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

yudedako67

2021/10/08 17:00

縮小した場合各辺を一定距離動かしたものにはならないので、質問内容と同じ結果にはならないようです。 尤もこちらのほうが本当に必要な結果だった可能性はありますが
takes.it.easy

2021/10/08 22:53

回答ありがとうございます。 私の目的としては各辺が一定距離を保つ必要があり、こちらではそれが満たせていないかなと思います。 しかしながら、別のアプローチの仕方としてはとても参考になるところが多く、とても勉強になりました。ありがとうございます。
fana

2021/10/09 01:33 編集

ある頂点(例えば一番左下にあるやつ)を原点とした座標系でk倍し, その原点にした頂点の角の二等分線方向にsだけオフセットするとき, 目的の図形を得られる(k,s)の組があるだろうか? …と考えたのですが…… よく考えたら,目的の図形は元の図形の相似ではないのですね. なんか,すみません.
fana

2021/10/09 02:12 編集

あーでも,この図での緑みたいな,「元の図形の内側に入った縮小図形」を簡単に求める方法があったとしたら,それを > オレンジ矢印の判断 に使えないかな? (元の図形の頂点→縮小図形の頂点 というベクトルがヒントになるのでは.単純には内積の符号を見るとかそういう.)
takes.it.easy

2021/10/10 02:01

たしかに目的の図形は元の図形の相似ではありません。その部分は私の説明不足でした。申し訳ないです。 fana様が投稿してくださった『どちらを内側を判断するか』『2つの結果を作って面積の小さい方を内側の図形とする』というご回答は大変参考になる考え方であります。感謝いたします。 また元の図形の頂点と縮小した図形の頂点での内積の符号で内外を判断するというのも私が今制作しているプログラムの別の部分にも役に立ちそうなご意見です。重ねて感謝いたします。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問