前提・実現したいこと
図のような複数の頂点からなるポリゴンの各辺をある一定の距離Lで法線方向に縮小することが目的です。
アルゴリズムとして各頂点の座標の配列と一定の距離Lを与えpythonなどで自動で行えるようにしたいと考えています。
発生している問題・エラーメッセージ
図形縮小後の頂点(P0',P1',...,Pn')は縮小前の頂点(P0,P1,...,Pn)を各直線の法線方向にLだけ平行移動させ移動後の2点([P0A,P0B],[P1A,P1B],...,[PnA,PnB])からなる各直線の交点を取ればよいという事はわかっています。
問題は頂点を移動させる際,図形を縮小させる方向の判断をどのように行えばよいかという事です。
各直線の法線はオレンジ矢印と緑矢印の2種類があり、オレンジ矢印の判断をどのように行えばよいかがわかりません。
どうぞよろしくお願い致します。
気になる質問をクリップする
クリップした質問は、後からいつでもMYページで確認できます。
またクリップした質問に回答があった際、通知やメールを受け取ることができます。
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2021/10/08 03:02
回答4件
0
(以下,例示されたデータを用いて記す)
与えられたデータから,
「P0→P1→P2→P3→P4→P0 と辿れば一周できる」ということは知ることができると思います.
↓
この方向でポリゴンの縁を辿るときに,
各頂点位置で曲がる角度を調べます.(角度:±180の範囲とする.例えば「右に曲がる方向を+,左に曲がる方向を-」のように)
全頂点位置での角度の総計値の符号から,この辿り方が 右回り or 左回り のどちらなのかが判別できます.
上記順序でポリゴンの縁を辿るときには,(右曲がりを+とするなら)総和は+となり,ポリゴンの内側は右手側にあることがわかります.
投稿2021/10/08 02:57
編集2021/10/08 04:23総合スコア11634
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2021/10/08 03:04 編集
2021/10/08 04:07
2021/10/08 04:28 編集
2021/10/08 04:22
2021/10/08 07:27 編集
0
とりあえず単純な方法としては,「2個の結果を作って一方を選ぶ」で.
「P0→P1→P2→P3→P4→P0 と辿れば一周できる」までが分かった時点で
各直線の法線はオレンジ矢印と緑矢印の2種類があり…
の{オレンジ側で作った結果,緑側で作った結果}の2つを作ることができるわけで,そしたらあとは
- より小さい方(面積が簡単に計算できる場合はこんな判定で)
- 他方に包括されている側:一方側の1個の頂点について,他方の図形の内外どっちにあるか?の判定を行えばよいかな.
(「他方」じゃなくて「元の図形」でもいいけど)
…みたいな判断で,元の図形の縮小版となる側を選べばよい,という.
投稿2021/10/09 09:56
編集2021/10/09 09:57総合スコア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
総合スコア38234
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2021/10/08 23:01
2021/10/10 03:40 編集
2021/10/10 08:34
2021/10/11 12:47
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
総合スコア24666
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2021/10/08 17:00
2021/10/08 22:53
2021/10/09 01:33 編集
2021/10/09 02:12 編集
2021/10/10 02:01
あなたの回答
tips
太字
斜体
打ち消し線
見出し
引用テキストの挿入
コードの挿入
リンクの挿入
リストの挿入
番号リストの挿入
表の挿入
水平線の挿入
プレビュー
質問の解決につながる回答をしましょう。 サンプルコードなど、より具体的な説明があると質問者の理解の助けになります。 また、読む側のことを考えた、分かりやすい文章を心がけましょう。