先月、急に結び目不変量を求めるUIを作りたくなり、思い立ってプロトタイプを作ってみました。

この記事で紹介すること

Vue.js (+ vue-cli)とCanvasでの線分衝突判定付きお絵かき機能の設計、実装

歴が浅いのでトンチンカンなことを言っているかもしれませんが、ご容赦ください。

対象とする人

これからVue.jsを始めようとする方、結び目理論の未解決問題にチャレンジしたい方など、どなたでも
なんでもコメントいただけると嬉しいです。

作成物のデモ

一筆書きの自己交叉するループを書くと、結び目を作ってくれます。

ソース(github)
サーバサイドの紹介は別記事にあります。

ちょっと機能を付けてデプロイしました（リバースプロキシの都合でもっさりします...）！https://t.co/1B41FS6QCz
内容薄いですが、記事も書きます pic.twitter.com/4hUFYG7iJ6
— penpenpen (@ayanamizuta) September 1, 2019

設計

1.線分描画機能
という基本的な機能に加えて
2.描画をやめても途中から続きを描ける機能
3.一筆書きが終わったかどうかを判定する機能
4.線分の交差を判定する機能
5.線分の交差の手前・奥を入れ替える機能
などを実装します。

今回は1の機能を1つのvue component（Canvas.vue）に任せます。
もう一つvue component（DrawManager.vue）を作り

2,3を実現するために描画の状態を管理する
4,5のために常にのCanvas上のマウスの位置を覚える
といった機能を任せることにします。

App.vue (バックエンドへデータを送るための機構)
|
DrawManager.vue
|
Canvas.vue

実装

Canvas.vue

描画といえばCanvasだ！という浅い意思の下Canvasの使用を決断しました。
マウスの軌跡で曲線を描こうと思うと、ドットを数ms毎に打つ方針だと離散的になってしまうので、線分を補完する必要があります。

vueのコンポーネントにまとめると以下のようになるでしょう
マウスを動かす度に位置を求めるには、mousemoveイベントで指定するとよいです。

Canvas.vue

<template>
  <canvas width="600" height="400" class="canvas"
   @mousedown="draw_activate()"
   @mousemove="get_current_position($event)"
   @mouseup="draw_deactivate()"
   ></canvas>
</template>
〜中略〜
methods: {
　　 draw_activate(){
      document.addEventListener("mousemove", this.draw);
    },
    draw_deactivate(){
      document.removeEventListener("mousemove", this.draw);
    },
    get_current_position(event){
      var newx = event.offsetX;
      var newy = event.offsetY;
      this.current_x = newx;
      this.current_y = newy;
    },
    draw() {
      if(this.draw_enable){
        if(this.last_draw_x == null || this.last_draw_y == null){
          this.last_draw_x = this.current_x;
          this.last_draw_y = this.current_y;
        }else{
          this.draw_core(this.last_draw_x, this.last_draw_y,this.current_x,this.current_y);
          this.last_draw_x = this.current_x;
          this.last_draw_y = this.current_y;
        }
      }
    },
    draw_core(x,y,nx,ny) {
      this.ctx.beginPath();
      this.ctx.moveTo(x, y);
      this.ctx.lineTo(nx, ny);
      this.ctx.stroke();
    }
}

DrawManager.vue

このコンポーネントでは大きく3つやりたいことがあります

描画状態の管理
マウスの軌跡の記録
描画した線分同士が交点を持つかの判定

viewは以下のように用意します。

DrawManager.vue

<template>
  <div @mouseup="suspend()" @mousedown="resume()" @click="intersection_parity_change()">
    <Canvas ref="canvas"/>
    <h3 v-if="state=='Done'">You've made a link diagram! congrats!</h3>
    <button @click="configure_link()" v-if="state=='Done'">configure a link!</button>
    <h3 v-if="state=='Configured'">You can submit this link and get the Kauffman bracket!</h3>
  </div>
</template>

状態管理は以下のように実装します（お気持ちのみ）。

DrawManager.vue

  data: function() {
    return {
      //代数的データ型が欲しいけど、諦める
      // state      = Ready | Draw | Suspend | Done | Configured
      // state_sub  = DrawUnTerminable | DrawTerminable
      state: 'Ready',
      state_sub: 'DrawUnTerminable',
      initial_place: null,
      intersection_pairs:      [],
      trajectory:              []
    }
  }

軌跡の記録は以下のように子コンポーネントをwatchして実装できます。

Canvas.vue

  mounted(){
    this.$watch(
      "$refs.canvas.last_draw_x",
      function(){
        var newx = this.$refs.canvas.last_draw_x;
        var newy = this.$refs.canvas.last_draw_y;
        this.trajectory.push([newx,newy]);
        〜中略〜
      }
    );
  }

交点判定は高校数学で行うような「直線の式に点の値を代入して符号を吟味する」実装をすればよいです。
なお、ナイーブに交点判定を全探索すると計算量が線分の数に対して2乗のオーダーになります。しかし実際に描いてみると線分の数が100もいかなかったのでそうしてます。
交点判定の該当部分は以下の通りです

DrawManager.vue

    //2つのLineが交差するかどうか
    is_intersect(idx,idy){
      var l1_from  = this.trajectory[idx];
      var l1_to    = this.trajectory[idx+1];
      var l2_from  = this.trajectory[idy];
      var l2_to    = this.trajectory[idy+1];
      var line_formula = function(l){
        return l[1]-l1_from[1]-(l[0]-l1_from[0])*(l1_to[1]-l1_from[1])/(l1_to[0]-l1_from[0]);
      }
      return line_formula(l2_from)*line_formula(l2_to)<0;
    }

デプロイ

vue-cliでbuildする。
静的ページができるので、今回はそれをサーバ側にmvして（サーバーサイド込みの）アプリ自体は完成です。

参考にさせていただいた記事・実装

canvasでお絵かき機能を作る際の雛形。サンプル点をlineToで繋ぐ。
https://github.com/ics-creative/tutorial-createjs/blob/gh-pages/samples/paint_step2.html

子コンポーネントのwatch
https://stackoverflow.com/questions/51225378/how-to-watch-child-properties-changes-from-parent-component

既存のバグ

linkのconfigure時、交点を認識しない時がしばしばある。

これは恐らく格子点で2つの線分が交わる場合、浮動小数の丸め誤差で交点と認識されない時があるのだと予想してます。