多角形の内外判定(javascriptでの実装を添えて)
アノテーションツールでセグメンテーション用に多角形での範囲選択を実装しようとしている。 四角形の場合には簡単に内外判定ができるが、多角形だとそう簡単にはいかない。 今回実装にあたって多角形の内外判定を勉強した。
TL;DR
- Winding Number Algorithmは割と楽に実装できる
- 実装するときは角度の符号の計算を忘れない
はじめに参考資料
理論だったり詳しい実装のポイントは以下の資料を見てください。 この資料を見て理解できればこの記事は読まなくて大丈夫です。
Winding Number Algorighmとは
多角形の角2つと対象となる点が成す角度を順番に計算していき、それらの和が360°以上であれば(一周以上するのであれば)点は多角形内部にある。 一方で和が0であれば、点は多角形外部にある。
最初角度の和が0になればってどういうこと?と悩んだが、角度を符号つきで計算すると外部にあるときは角度同士がキャンセルしあって和は0になるよ、と理解すれば良さそうだ。
「360°以上」というところは自己交差領域があると和が一周以上になる場合が出てくる(上記のNTTの資料参考)。あまり数学的なところは理解できないが他にありえるのだろうか。
実装する上での注意点
角度を符号付きで計算することを忘れなければ実装はかなり簡単。符号の計算を忘れるとうまく動かなくて沼にハマる。 角度の絶対値はベクトルの内積を使えば簡単に計算できる。符号は外積を計算して、その符号だけを取ればOK。
javascriptでの実装
コメントを多めに入れたので長くなったが、やっていることは非常に簡単。 バグがあれば教えてください。
/** * 指定した点が多角形の中に含まれるかどうかを判定する * * @param {Array} polygon 多角形を構成する点(X, Y)の配列. 多角形を一周するように並んでいる必要がある. * @param {Number} x 判定する点のX座標 * @param {Number} y 判定する点のY座標 * @returns {Boolean} 点が多角形に含まれていればtrue */ function hit(polygon, x, y) { let thetaSum = 0; const n = polygon.length; // i-1 => 指定された点 => i の成す角度の和をthetaSumに足し込んでいく for (let i = 1; i < n; i++) { if (polygon[i][0] === x && polygon[i][1] === y) { // 指定された点が多角形の角の場合うまく角度が計算できないので、判明した時点でtrueを返す return true; } const v1x = polygon[i - 1][0] - x; const v1y = polygon[i - 1][1] - y; const v2x = polygon[i][0] - x; const v2y = polygon[i][1] - y; thetaSum += computeDegree(v1x, v1y, v2x, v2y); } // 0とN番目の成す角度 if (polygon[0][0] === x && polygon[0][1] === y) { return true; } const v1x = polygon[n - 1][0] - x; const v1y = polygon[n - 1][1] - y; const v2x = polygon[0][0] - x; const v2y = polygon[0][1] - y; thetaSum += computeDegree(v1x, v1y, v2x, v2y); thetaSum = Math.abs(thetaSum); if (thetaSum >= 0.1) { return true; } return false; } /** * 2つのベクトルの成す角度を符号付きで計算する * 角度の絶対値の計算には内積を、符号の計算には外戚を利用する * * @param {Number} x1 * @param {Number} y1 * @param {Number} x2 * @param {Number} y2 */ function computeDegree(x1, y1, x2, y2) { const abs1 = Math.sqrt(x1*x1+y1*y1); const abs2 = Math.sqrt(x2*x2+y2*y2); let theta = Math.acos((x1*x2+y1*y2)/(abs1*abs2)); // 内積を使って角度を計算 let sign = Math.sign(x1*y2-y1*x2); // 外積を使って符号を計算 theta *= sign; return theta } function main() { const pol1 = [[0, 0], [100, 20], [100, 120], [0, 100]]; // 通常の判定 console.log(hit(pol1, 50, 50)); // true console.log(hit(pol1, 101, 50)); // false console.log(hit(pol1, 100, 121)); // false // コーナーケース(多角形の辺上の場合) console.log(hit(pol1, 50, 10)); // true console.log(hit(pol1, 100, 60)); // true // コーナーケース(多角形の角上の場合) console.log(hit(pol1, 0, 0)); // true console.log(hit(pol1, 100, 20)); // true } main();
anntを大きくリファクタした
前公開したanntをちまちま改修してたのでリリース
前:
後:
主な改修内容は
- Google Drive対応
- 内部のリファクタリング
- デザインの変更
の3点
Google Drive対応
Google DriveはDropboxと違って、階層構造のファイルシステムじゃないので実装が手探りになってしまった。 Google Driveは普段使い慣れているWindowsやMacみたいにパスでファイルやフォルダを指定できない。(フラットファイルシステムというらしい) 各ファイルが親フォルダの情報を持っているので、SQLのSELECT~WHERE文みたいなイメージで指定したフォルダを親とするファイルをリストアップする。
深いパスのファイルを取得しようとすると階層分だけAPIを呼び出さないといけないので、余計なオーバーヘッドが発生している気がする。 Dropboxに比べて遅いのと、若干バグが多いのでここは今後の課題。 あとプライバシーポリシー作ってないので、OAuthの認証画面でやばいですよアピールされるのも課題
内部的なリファクタリング
リファクタリングをやって大分今後の改修がしやすくなった。 今後多角形のアノテーションの実装を検討しているが、以前までの絶望感が無い。 この調子なら割とすぐに実装できそうなので、次の課題にしてみようと思う。
デザイン的な変更
デザインの変更は前からの課題だったので、割と大きく直したつもりでいる。 前回のデザインをださいださいと思ってて直したが、直しても相変わらずしょっぱい気がしている。 バウンディングボックスがすごい見ずらいのでこれもどうにかしたい。
小さな改善点としてはタブ操作だけでタグを選択できるようになった点。 Vue使えばかんたんなインクリメントサーチを本当に楽に実装できる。 公式チュートリアルに例があるので、興味ある型はそちらを参照。
今後もちまちま直していこうと思う。
twitterはじめました ⇒ @toritoritori29
Google Drive APIでファイルをアップロード - Multipart/Related
前回に引き続きGoogleDriveAPIのお話です。 今回はファイルの新規アップロードについてです。
createエンドポイント
ファイルを新規にアップロードするにはcreateエンドポイントを使用します。
https://developers.google.com/drive/api/v3/reference/files/create
このエンドポイントが曲者で、アップロード時に3つのアップロードタイプから一つを選んで明示的に指定する必要があります。
現実問題としてメタデータ無しでファイルをアップロードしたいという局面は殆ど無いと思われます。Google Driveではフォルダの階層構造をファイルのメタデータで管理しているため、メタデータ抜きでは親ディレクトリの指定すらできません。
ということで多くの場合においてアップロードタイプとしてmultipartかresumableを指定することになるでしょう。複数回リクエストを投げるよりは一回のリクエストで片付けてしまいたいので、自分の中でmultipartを使ってみようということになりました。ところがこのmultipart、RFC 2387というプロトコルに則ってリクエストを作成する必要があります。日本語の文献もほぼ無いということで素直にRFCを流し読みしました。
RFC 2387 The MIME Multipart/Related Content-type
複数の異なるMimeTypeのデータをまとめてアップロードするための「Multipart/Related」というMimeTypeについてまとめてたものです。あまりしっかりと読めているわけではないですが、要点は以下の通りとなっています。
- Content-TypeでMultipart/Relatedを指定し、同時にBoundary(境界文字列)も指定する。
- リクエストボディは"--"+Boundaryで区切って、異なるデータのリクエストボディを指定する。
- リクエストの終わりは"--"+Boundary+"--"で締める
これだけだと抽象的で少し分かりづらいですが、RFCの原本に載っている例がわかりやすいです。
Content-Type: Multipart/Related; boundary=example-1 start="950120.aaCC@XIson.com"; type="Application/X-FixedRecord" start-info="-o ps"
--example-1 Content-Type: Application/X-FixedRecord Content-ID: <950120.aaCC@XIson.com> 25 10 34 10 25 21 26 10 --example-1 Content-Type: Application/octet-stream Content-Description: The fixed length records Content-Transfer-Encoding: base64 Content-ID: <950120.aaCB@XIson.com> T2xkIE1hY0RvbmFsZCBoYWQgYSBmYXJtCkUgSS BFIEkgTwpBbmQgb24gaGlzIGZhcm0gaGUgaGFk IHNvbWUgZHVja3MKRSBJIEUgSSBPCldpdGggYS BxdWFjayBxdWFjayBoZXJlLAphIHF1YWNrIHF1 YWNrIHRoZXJlLApldmVyeSB3aGVyZSBhIHF1YW NrIHF1YWNrCkUgSSBFIEkgTwo= --example-1--
HTTP本体のリクエストヘッダにはMultipart/Relatedを指定しています。startなどはどのデータから読み込めばいいかを示す情報のようです(それっぽいことが書いてありましたが良く理解できませんでした)。リクエストボディの各セクションでは、それぞれのデータに対して改めてヘッダを定義しています。
javascriptでの実装
Multipart/Relatedのリクエストボディを生成する関数を作成した。この関数でエンコードした文字列をリクエストボディにして、リクエストヘッダにはMultipart/Relatedを指定すれば
/** * 引数で指定したオブジェクトをMultipart/Relatedのリクエストボディに変換 * 以下のような配列を第一引数として指定する必要がある * e.g) * let objects = [ * { header: ['Content-Type': 'text/plane'], body: '内容1' }, * { header: ['Content-Type': 'text/plane'], body: '内容2' }, * ] * * @param {Array} エンコードしたいオブジェクトのリスト * @param {String} 境界文字列 * @returns {String} エンコード済みの文字列 */ function encodeMutipart(objects, separator) { let encoded = ''; for (let o of objects) { encoded += `--${separator}`; encoded += '\n'; Object.keys(o.headers).forEach((key) => { encoded += key; encoded += ': '; encoded += o.headers[key]; encoded += '\n'; }); encoded += '\n'; if (typeof o.body === 'object') { encoded += JSON.stringify(o.body); } else if (typeof o.body === 'string') { encoded += o.body; } encoded += '\n'; } encoded += `--${separator}--`; return encoded; }
Google Drive APIでパスを指定してファイル一覧を取得する
Google Drive APIで心が折れた
指定したパスのファイルが存在するか知りたいだけだった。Google Drive Api V3のリファレンスを読んでもあまりファイルパスに関する記述が殆ど見当たらない。クラウドストレージサービスのリファレンスでそんなことあるかと思って調べた。
Try to stop thinking in terms of file paths. Google Drive is a flat filesystem, where "parent" is simply an attribute, a bit like a tag. A file can have many parents, and so could be on many paths.
Google Driveはフラットファイルシステムなので、ファイルパスで考えるのはやめましょう。"親フォルダ"は単なるタグのような属性です。ファイルは複数の親フォルダを持つ可能性がありますし、複数のパスを持つ可能性があります。
Flat Filesystemって何や...って調べてみると英語版ウィキペディアの項目に小さくFlat Filesystemという項目がある。単純に階層構造の無いファイルシステムのようだけど何かしらのメリットがあるのだろうか... Amazon S3も同様の仕組みって書いてあるので大規模クラウドストレージ特有の問題に対応しやすいということだろうか。
要するに指定したパスにファイルが存在するかどうか確認したい場合には再帰的にパスをたどっていくしか無さそう。
listエンドポイント
https://developers.google.com/drive/api/v3/reference/files/list
ファイルのリストを取得するためにはlistエンドポイントを仕様する。
パスで指定するのではなく、qとfiledsパラメータを駆使して全てのファイルの中から必要なデータをフィルターするイメージ
qパラメータ
取得したファイル一覧をフィルタリングするためのクエリです。サポートしている文法を確認するためには"Search for files"を確認してください。
fieldsパラメータ
レスポンスに含まれるパスとフィールドを指定します。指定されなければレスポンスはこのメソッドのデフォルトの集合を返します。開発の際にはすべてのフィールドを返す記号*を使えますが、必要なフィールドだけを指定した方がパフォーマンスが優れています。
qで取得するファイルをフィルターして、fieldsで取得する項目(ファイル名、更新日等々)の情報を絞り込む。
javascriptで指定したディレクトリのファイル一覧を取得
javascriptで指定したディレクトリのファイル一覧を取得する。予め何らかの方法でGoogleのOauth2トークンを取得しておく必要がある。 __listDirは補助関数で本体はlistDir関数となっている。
const axios = require('axios'); const API_KEY = '---- Your API Key -----'; const MIMETYPE_FOLDER = 'application/vnd.google-apps.folder' /** * GoogleDriveからファイルのリストを取得する(補助関数) * * @param {String} token * @param {String} parent - 上位フォルダのID * @returns {Object} Google Drive APIからのレスポンス */ async function __listFiles(token, parentId) { const url = 'https://www.googleapis.com/drive/v3/files'; const options = { headers: { Authorization: `Bearer ${token}`, Accept: 'application/json', }, params: { key: API_KEY, fields: 'files(id, name, mimeType)', q: `"${parentId}" in parents`, }, }; let resp = null; try { resp = await axios.get(url, options); return resp.data.files; } catch (error) { throw error; }; } /** * GoogleDriveからファイルのリストを取得する * * @param {String} token - OAuth2トークン * @param {String} path - ディレクトリのパス * @returns {Object} 指定したディレクトリ内のファイル一覧 */ async function listFiles(token, path) { const sepPath = path.split('/'); let files = null; try { files = await __listFiles(token, 'root'); } catch(error) { throw error; } for (let i=0; i < sepPath.length; i++) { let nextId = null; for (let e of files) { if (sepPath[i] === e.name && e.mimeType === MIMETYPE_FOLDER) { nextId = e.id; break; } } if (nextId) { try { files = await await __listFiles(token, nextId); } catch (error) { throw error; } } } return files; }
一個のファイルの情報を確認するためだけに数回のリクエストが必要になる。可能な限り過去のリクエストをキャッシュして通信回数を減らすのがいいのか。
Google Technical Writing Part 1を読み始めた
英語で技術よりの文書が書けるようになりたくて、Google Technical WrtingのPart 1を読み始めた。
内容は英語で技術文書を書くためのエッセンスを詰め込んだものになっている。読んでいてあたりまえじゃん!って思ったが、実際に過去に自分が書いた文章を見ていると全然出来てなくて驚く。
今のところ「Technical Writing One」〜 「Short Sentence」まで読んだので各章のメモ。
Word(単語)
色々なトピックに関して触れていたので箇条書きで。
- 文章内で単語の一貫性を保つ
- 単語を明確に定義する
- よく知られるものであれば単語の定義のリンクを貼る
- そうでないなら明確に定義する。量が多いなら用語集を作る。
- 略称を使う場合には初回だけ正式名称(略称)という表現を使う
- そもそも略称を使うべきか判断する(長さと頻度を判断基準に)
- 代名詞は混乱を招くので使用を控える
- 代名詞を使うのであれば明確な場合にのみ使う
メモ
英語だけでなく日本語で書く場合にも使える普遍的な内容だと思う。一貫性、定義、略称は混乱のもとなので普段から気を付けたい。 代名詞は日本語だと英語に比べて使用頻度が低い気がするが気を付けるに越したことはないと思う。
Active Voice(能動態)
能動態と受動態どちらを使うべきかという話。可能な限り能動態を使うべきという結論だった。理由としては
- 読者は暗黙的に脳内で能動態に変換している。
- 能動態に比べて読みづらい。能動態のほうが直接的に表現している。
- 短い
- 主語が抜ける場合があって明瞭性に欠ける
メモ
なるほどという感じだった。英語力が低くて逃げの受動態を使っていたが、載ってる例などを見ていると能動態のほうが圧倒的にわかりやすい。
日本語の場合だとどうなんだろうと考えてみた。あまり普段から能動態と受動態を意識したことが無いが、やはり能動態で書いた方がわかりやすいことが多いのかなと思う。日本語は能動態、受動態に関わらず主語が抜けることがあるので、そこが注意するべき点ではないだろうか。
Clear Sentences(明快な文章)
あまり読み込めていないが主なトピックは以下の通り。
- 強い動詞を使わない
- Thereを使わない
- あいまいな形容詞・副詞を使わない
強い動詞というのはhappenやoccurなどの普遍的で使いやすい単語を使うのではなくて、triggerやgenerateなどの使われる場面が限られている=情報量が多い動詞を使うべきと理解した。
メモ
強い動詞を使うという主張は理解しているが、語彙力が無くて普遍的な単語しか使えないという悲哀。Thereは長くて退屈だから使うなという主張のようだ。There文は単純に後ろにある文章を前に持ってくるか、主語をYouに変えて文章書き直せば簡単に直せるよという有り難いアドバイスが書いてあるので活用しようと思う。
Short Sentences(短い文章)
短いコードが読みやすいようにドキュメントも短く簡潔にという内容。
- 1文には一つのアイディアに留める
- andで繋いで長くなった文章は、リストに切り出すことを考える。
- 無駄に長い言い回しを避ける。
- whichとthatの使い分け(関係代名詞)
メモ
言葉にすれば簡単だが実践するのは難易度が高い内容だと思う。気がつけば長文が出来上がっている。この章の内容も日本語でも積極的に使いたい内容だった。特に日本語は無駄に長い言い回しをするのが得意な言語だと思うので、そこは直していきたい。
whichとthatは完全に同じ意味だと思っていたがそうではないらしい。少なくともアメリカでは。whichは無くても文意が通る場合に使い、thatは無いと文意が通らない場合に使うとのこと。豆知識を得てしまった。
まとめ
まだ前半しか読んでないが有意義な内容だった。長くてやってらんねーよ!という方はトピックを訳している記事があるのでそちらだけでも。
vue.js+vue-routerで自作サービスの多言語対応 Part.1
以前作ったWebサービスの多言語対応を行った。 anntはvue-routerで動くSPAだったが、URLに応じて適切な言語で表示するように改修した。
多言語対応の方法
初期段階で多言語対応ってそもそもどうやるんだろうと思いながらWeb検索をしていると、だいたいどこのサイトでも以下の3通りがメジャーですよと教えてくれた。
4 Key SEO Tips for Your Multilingual Website in 2020
グローバルドメイン .jpや.frなどの国固有のドメインを購入して、ドメイン名によって言語を切り替える。 カッコいいとは思うがクソほどお金がかかるのでパス。
サブドメイン jp.example.comのように新たにサブドメインを作成して、サブドメインによって言語を切り替える。 1つのドメインにサブドメインを設定していくだけなので、追加コストは0。 ただ余り見慣れないURLな気がして少し違和感を感じた+ドメイン周りの設定いじるのがめんどくさいという理由でスキップ
サブディレクトリ 冒頭に示した"https://annt.ai/ja"のような形式で、パスの先頭の値によって言語を切り替える。 ルーティングの設定だけで言語を切り替えられるので、楽+追加コスト無しということでこれを採用した。
当初は実装面の簡便さの観点からサブディレクトリ方式を選んだが、それ以外の要素ってどうなんだろうと思って調べてみるとSEO的にもサブディレクトリが良さそう。
In these cases, you should almost always use subfolders. Subdomains lose a lot of power in terms of SEO, which makes a huge different with regards to marketing and search visibility. Moz has done repeated tests over the years and has determined that using subfolders is simply better SEO practice.
ほとんどの場合サブフォルダーを使用する必要があります。サブドメインはSEOに関して多くの力を失い、マーケティングと検索の可視性に関して大きな違いをもたらします。Mozは何年にもわたって繰り返しテストを行っており、サブフォルダを使用するほうがSEOの実践として優れていると判断しました。
どれだけ信頼のおける情報かは分からないが、個人での検証のしようが無いので信じてみようと思う。
Vue.jsでの実装
言語の切り替え
Vue I18nという多言語対応用のライブラリが存在している。どうもi18nはinternationalizationの略語として使われているようだ。(国際化と地域化 - Wikipediaを参考:Wikipediaは何でも乗っていて本当にすごい。)
ライブラリを調べてみたは良いが使い方調べるのが面倒臭くなって、結局ライブラリは使わず言語の切り替えは自分で実装した。国際化という意味だと言語以外の要素(日にちの表現など)を本来は対応する必要があるのかなと思ったが、用途的に別に使わないと考えてjsonに記載したテキストデータから現在の言語に応じて適切なデータを取得する仕組みを作った。
イメージは↓みたいな感じで、各ページのcreatedのタイミングでURLに応じて言語を切り替えるための初期化処理(initLocale)を呼び出す。初期化後はmsgプロパティから現在の言語のテキストが取れるような仕組み。どのページでも使うのでmixinにしてある。当然タイトルなども変える必要があるので初期化後に書き換える。
// ページが読み込まれた際の初期化処理 created() { try { // messagesは各言語での文章が書かれたjsonデータを読み込んだもの this.initLocale(messages); } catch { // Force to redirect route. this.$router.push('/'); } common.SetTitle(this.msg.page_title); common.SetDescription(this.msg.page_description); },
肝心な初期化処理が割と長くなったので記載はしないが、URLのパスに応じてスイッチ文で切り替えるだけなので実装は非常に簡単。 あとはルーティングの設定やhreflangなどについても諸々変更したが、長くなったのでまた次回。
pythonで色を連続的に変化させる方法
色をシームレスに変化させたい。虹色みたいに。ただそれだけ。
と思っても、実は色についてほとんど知識が無いことに気がつく。RGBは分かるが、それを使ってどう変化させればいいかわからない。RGBのRの値だけを変えても色の赤みが薄くなるか濃くなるかだけで、虹色みたいに変化させるのは難しいのではと思った。
困ったときのウィキペディア。世の中には皆がよく知るRGB以外にも色を表現する方法はあるようだ。というかペイントとかでお世話になっていた。 RGBは赤・緑・青の原色を混ぜ合わせることで色を表現する方法だが、HSV色空間は、Hue(色相)、Saturation(彩度)、Value(明度)の3つのパラメータで表現する方法だ。ウィキペディアを見て、色を連続的に変化させたい = 色相を変化させたい、とやりたいことを明確に言語化できた。
ウィキペディアを見るとHSVからRGBの変換方法まで記載されていたので、そのままhsvからRGBの変換関数を作成してみた。
def hsv_to_rgb(h, s, v): """ Convert hsv color code to rgb color code. Naive implementation of Wikipedia method. See https://ja.wikipedia.org/wiki/HSV%E8%89%B2%E7%A9%BA%E9%96%93 Args: h (int): Hue 0 ~ 360 s (int): Saturation 0 ~ 1 v (int): Value 0 ~ 1 """ if s < 0 or 1 < s: raise ValueError("Saturation must be between 0 and 1") if v < 0 or 1 < v: raise ValueError("Value must be between 0 and 1") c = v * s h_dash = h / 60 x = c * (1 - abs(h_dash % 2 - 1)) rgb_dict = { 0: (c, x, 0), 1: (x, c, 0), 2: (0, c, x), 3: (0, x, c), 4: (x, 0, c), 5: (c, 0, x), } default = (0, 0, 0) rgb = [0, 0, 0] for i in range(len(rgb)): rgb[i] = (v - c + rgb_dict.get(int(h_dash), default)[i]) * 255 rgb = map(int, rgb) return tuple(rgb)
あとはhを0~360までfor文で変化させたものをgifにすればトップの色が変化していく画像ができあがる。
for i in range(60): color = hsv_to_rgb(i*6, 1, 1) img = Image.new('RGB', (width, width), (0, 0, 0)) draw = ImageDraw.Draw(img) draw.rectangle((0, 0, width, width), fill=color) images.append(img) images[0].save("./color.gif", save_all=True, append_images=images[1:], optimize=False, duration=5, loop=0)
せっかくだからグラデーションにでもすればもっと見目麗しい画像になった気がする。 あとpillowは簡単にgifが出来て便利。(小並感)