teratail
回答率
85.32%
teratail header banner
teratail header banner
質問するログイン新規登録
トップアルゴリズムに関する質問直線を書くアルゴリズムについて

編集履歴

回答編集履歴

3

GitHubリンク追記

2018/09/30 21:45

投稿

opyon
opyon

スコア1009

test CHANGED
@@ -16,6 +16,8 @@
16
16
 
17
17
 
18
18
 
19
+
20
+
19
21
  変更した判定条件式
20
22
 
21
23
  ```
@@ -245,3 +247,5 @@
245
247
  # plt.savefig('test.png')
246
248
 
247
249
  ```
250
+
251
+ [GitHub](https://github.com/opyon/public/blob/master/Python3/qa149396.ipynb)

2

条件式改修＋描画部分引用

2018/09/30 21:45

投稿

opyon
opyon

スコア1009

test CHANGED
@@ -2,17 +2,17 @@
2
2
 
3
3
 
4
4
 
5
- ~~検証していませんが、上記サンプルコードに線分と判定する座標を与えれば判定出来そうですね。~~
6
-
7
- ~~実装頑張ってみてください。~~
8
-
9
-
10
-
11
- 判定部分のみ実装してみました。
5
+ 判定部分は上記から引用し改修しました。
6
+
7
+ 描画部分は@tiitoiさんコードから引用し改修しました。
12
8
 
13
9
  上記参考コードをそのまま移植するだけでは判定出来ませんでした。
14
10
 
15
- 試行錯誤したところ、判定条件式　`a * p.x + b * p.y + c == 0` を変更することで欲しい結果が得られました。
11
+ 試行錯誤したところ、判定条件式　`a * p.x + b * p.y + c == 0` から下記のように変更することで欲しい結果が得られました。
12
+
13
+ @tiitoiさんの回答にある論文はさっぱり分かりませんが、引用したコードの条件式を手探りで発見し要件を満たす結果が得られたことはとても満足しています。
14
+
15
+ @tiitoiさんの描画部分のコードのおかげで試行錯誤とテストが捗りとても感謝しています。
16
16
 
17
17
 
18
18
 
@@ -20,24 +20,48 @@
20
20
 
21
21
  ```
22
22
 
23
- chk = a * p.x + b * p.y + c
23
+ chk = a * p.x + b * p.y + c
24
+
25
+
26
+
24
-
27
+ len_x = e.x - s.x
28
+
29
+ len_y = e.y - s.y
30
+
31
+ if len_x == len_y:
32
+
33
+ v = 0
34
+
35
+ else:
36
+
37
+ v = len_x // 2 + len_y // 2
38
+
39
+
40
+
25
- if chk >= -2 and chk <= 2:
41
+ if chk >= v * -1 and chk <= v:
42
+
43
+ return True
44
+
45
+ else:
46
+
47
+ return False
26
48
 
27
49
  ```
28
50
 
29
-
30
-
31
- 但し計算根拠に基づいた式を作ったわけではなく手探りで見つけただけなので正しいアルゴリズムかどうかは分かりません。
32
-
33
- 検証範囲も始点固定(0,0)で、終点(1,3)終点(2,3)終点(3,3)だけです。
51
+ ![イメージ説明](756cd83de567cf71865d4fcdbab735a3.png)
34
-
35
- この範囲なら要件通りの判定出来ています。
36
52
 
37
53
 
38
54
 
39
55
  ```Python3
40
56
 
57
+ import sys
58
+
59
+ import numpy as np
60
+
61
+ print(sys.version)
62
+
63
+
64
+
41
65
  class Point_():
42
66
 
43
67
 
@@ -50,7 +74,9 @@
50
74
 
51
75
 
52
76
 
77
+
78
+
53
- def chk(s,e,p):
79
+ def chk(s, e, p):
54
80
 
55
81
  if s.x <= p.x and p.x <= e.x:
56
82
 
@@ -74,82 +100,148 @@
74
100
 
75
101
 
76
102
 
103
+ #以下判定条件式を追加改修
104
+
77
105
  chk = a * p.x + b * p.y + c
78
106
 
107
+
108
+
109
+ len_x = e.x - s.x
110
+
111
+ len_y = e.y - s.y
112
+
113
+ if len_x == len_y:
114
+
115
+ v = 0
116
+
117
+ else:
118
+
119
+ v = len_x // 2 + len_y // 2
120
+
121
+
122
+
79
- if chk >= -2 and chk <= 2:
123
+ if chk >= v * -1 and chk <= v:
80
124
 
81
125
  return True
82
126
 
83
127
  else:
84
128
 
85
- pass
86
-
87
129
  return False
88
130
 
89
-
90
-
91
- s_x = 0
131
+ #追加改修以上
132
+
133
+
134
+
92
-
135
+ # 描画部分は@tiitoiさんコードから引用しコードに合わせて改修
136
+
137
+ import matplotlib.pyplot as plt
138
+
139
+ from matplotlib.lines import Line2D
140
+
141
+
142
+
143
+ def show_image(ax, img):
144
+
145
+ ax.imshow(img, interpolation='none')
146
+
147
+ ax.grid(which='minor', color='b', linestyle='-', linewidth=1)
148
+
149
+ # Major ticks
150
+
151
+ ax.set_xticks(np.arange(0, 10, 1))
152
+
153
+ ax.set_yticks(np.arange(0, 10, 1))
154
+
155
+ # Labels for major ticks
156
+
157
+ ax.set_xticklabels(np.arange(10))
158
+
159
+ ax.set_yticklabels(np.arange(10))
160
+
161
+ # Minor ticks
162
+
163
+ ax.set_xticks(np.arange(-.5, 10, 1), minor=True)
164
+
165
+ ax.set_yticks(np.arange(-.5, 10, 1), minor=True)
166
+
167
+
168
+
169
+ def draw_line(img, p1, p2, color=[255, 0, 0]):
170
+
93
- s_y = 0
171
+ x1, y1 = p1
94
-
172
+
95
- e_x = 2
173
+ x2, y2 = p2
174
+
175
+
176
+
96
-
177
+ slope = (y2 - y1) / (x2 - x1)
178
+
179
+
180
+
181
+ xs = np.arange(x1, x2 + 1, 0.01)
182
+
183
+ ys = y1 + slope * (xs - x1)
184
+
185
+ pts = np.vstack([xs, ys]).T
186
+
187
+ print(pts.shape)
188
+
189
+
190
+
191
+ pts = np.ceil(pts).astype(int) # 離散化する。
192
+
193
+ pts = np.unique(pts, axis=0) # 重複する点を削除
194
+
195
+
196
+
97
- e_y = 3
197
+ # 座標入力
98
-
99
-
100
-
198
+
101
- s = Point_(s_x, s_y)
199
+ s = Point_(1, 2)
102
-
200
+
103
- e = Point_(e_x, e_y)
201
+ e = Point_(8, 7)
104
-
105
-
106
-
202
+
203
+
204
+
107
- print(f'直線({s_x},{s_y})-({e_x},{e_y})')
205
+ print(f'直線({s.x},{s.y})-({e.x},{e.y})')
206
+
108
-
207
+ points = []
208
+
109
- for p_x in range(e_x+1):
209
+ for p_x in range(s.x,e.x+1,1):
110
-
210
+
111
- for p_y in range(e_y+1):
211
+ for p_y in range(s.y,e.y+1,1):
112
212
 
113
213
  p = Point_(p_x, p_y)
114
214
 
215
+ ret = chk(s,e,p)
216
+
217
+ if ret:
218
+
219
+ points.append([p_x,p_y])
220
+
221
+
222
+
223
+ points = np.array(points)
224
+
225
+
226
+
227
+ # 白紙の画像を作成する。
228
+
229
+ img = np.full((10, 10, 3), 255, dtype=np.uint8)
230
+
231
+
232
+
233
+ for x, y in points:
234
+
235
+ img[y, x] = [255, 0, 0] # 赤
236
+
237
+
238
+
239
+ fig, ax = plt.subplots(figsize=(8, 8), facecolor='w')
240
+
241
+ ax.add_line(Line2D([s.x, e.x], [s.y, e.y], color='g'))
242
+
243
+ show_image(ax, img)
244
+
115
- print(f'点({p_x},{p_y}) {chk(s,e,p)} ')
245
+ # plt.savefig('test.png')
116
-
117
-
118
246
 
119
247
  ```
120
-
121
-
122
-
123
- 出力例
124
-
125
- ```
126
-
127
- 3.7.0 (default, Jun 28 2018, 08:04:48) [MSC v.1912 64 bit (AMD64)]
128
-
129
- 直線(0,0)-(2,3)
130
-
131
- 点(0,0) True
132
-
133
- 点(0,1) True
134
-
135
- 点(0,2) False
136
-
137
- 点(0,3) False
138
-
139
- 点(1,0) False
140
-
141
- 点(1,1) True
142
-
143
- 点(1,2) True
144
-
145
- 点(1,3) False
146
-
147
- 点(2,0) False
148
-
149
- 点(2,1) False
150
-
151
- 点(2,2) True
152
-
153
- 点(2,3) True
154
-
155
- ```

1

実装してみた

2018/09/30 21:33

投稿

opyon
opyon

スコア1009

test CHANGED
@@ -2,6 +2,154 @@
2
2
 
3
3
 
4
4
 
5
- 検証していませんが、上記サンプルコードに線分と判定する座標を与えれば判定出来そうですね。
5
+ ~~検証していませんが、上記サンプルコードに線分と判定する座標を与えれば判定出来そうですね。~~
6
6
 
7
- 実装頑張ってみてください。
7
+ ~~実装頑張ってみてください。~~
8
+
9
+
10
+
11
+ 判定部分のみ実装してみました。
12
+
13
+ 上記参考コードをそのまま移植するだけでは判定出来ませんでした。
14
+
15
+ 試行錯誤したところ、判定条件式　`a * p.x + b * p.y + c == 0` を変更することで欲しい結果が得られました。
16
+
17
+
18
+
19
+ 変更した判定条件式
20
+
21
+ ```
22
+
23
+ chk = a * p.x + b * p.y + c
24
+
25
+ if chk >= -2 and chk <= 2:
26
+
27
+ ```
28
+
29
+
30
+
31
+ 但し計算根拠に基づいた式を作ったわけではなく手探りで見つけただけなので正しいアルゴリズムかどうかは分かりません。
32
+
33
+ 検証範囲も始点固定(0,0)で、終点(1,3)終点(2,3)終点(3,3)だけです。
34
+
35
+ この範囲なら要件通りの判定出来ています。
36
+
37
+
38
+
39
+ ```Python3
40
+
41
+ class Point_():
42
+
43
+
44
+
45
+ def __init__(self, x_init, y_init):
46
+
47
+ self.x = x_init
48
+
49
+ self.y = y_init
50
+
51
+
52
+
53
+ def chk(s,e,p):
54
+
55
+ if s.x <= p.x and p.x <= e.x:
56
+
57
+ if s.y <= e.y \
58
+
59
+ and (s.y <= p.y and p.y <= e.y) \
60
+
61
+ or s.y >= e.y \
62
+
63
+ and (s.y >= p.y \
64
+
65
+ and p.y >= e.y) \
66
+
67
+ :
68
+
69
+ a = e.y - s.y
70
+
71
+ b = s.x - e.x
72
+
73
+ c = s.x * (s.y - e.y) - s.y * (s.x - e.x)
74
+
75
+
76
+
77
+ chk = a * p.x + b * p.y + c
78
+
79
+ if chk >= -2 and chk <= 2:
80
+
81
+ return True
82
+
83
+ else:
84
+
85
+ pass
86
+
87
+ return False
88
+
89
+
90
+
91
+ s_x = 0
92
+
93
+ s_y = 0
94
+
95
+ e_x = 2
96
+
97
+ e_y = 3
98
+
99
+
100
+
101
+ s = Point_(s_x, s_y)
102
+
103
+ e = Point_(e_x, e_y)
104
+
105
+
106
+
107
+ print(f'直線({s_x},{s_y})-({e_x},{e_y})')
108
+
109
+ for p_x in range(e_x+1):
110
+
111
+ for p_y in range(e_y+1):
112
+
113
+ p = Point_(p_x, p_y)
114
+
115
+ print(f'点({p_x},{p_y}) {chk(s,e,p)} ')
116
+
117
+
118
+
119
+ ```
120
+
121
+
122
+
123
+ 出力例
124
+
125
+ ```
126
+
127
+ 3.7.0 (default, Jun 28 2018, 08:04:48) [MSC v.1912 64 bit (AMD64)]
128
+
129
+ 直線(0,0)-(2,3)
130
+
131
+ 点(0,0) True
132
+
133
+ 点(0,1) True
134
+
135
+ 点(0,2) False
136
+
137
+ 点(0,3) False
138
+
139
+ 点(1,0) False
140
+
141
+ 点(1,1) True
142
+
143
+ 点(1,2) True
144
+
145
+ 点(1,3) False
146
+
147
+ 点(2,0) False
148
+
149
+ 点(2,1) False
150
+
151
+ 点(2,2) True
152
+
153
+ 点(2,3) True
154
+
155
+ ```