たくみん成長日記

開発したアプリやプログラミングの備忘録を不定期に上げていきます。

トップ > アルゴリズム > 現在位置が特定の範囲内か範囲外か調べたい

現在位置が特定の範囲内か範囲外か調べたい

アルゴリズム JavaScript Angular

こんちか!!たくみんです。今日は、業務で使用した「ある点が特定の範囲(多角形)の内側か外側かを判定する機能」を実現するアルゴリズムとその実装について紹介します。

1. Crossing Number Algorithm

1-1. 概要

Crossing Number Algorithmは、ある点Pの右側から伸びる水平線と多角形の辺の交点の個数によって内側、外側を判定するアルゴリズムです。下図をみても分かる通り、偶数および0の場合は「外側」、奇数の場合は「内側」と判定します。

f:id:takuminv:20200426211713p:plain:w600

1-2. 自己交差している多角形に対する判定

このアルゴリズムは、下図のように自己交差している多角形に対し、うまく判定してくれません。点Pが多角形の内側にあるにも関わらず、交点の数が偶数となってしまうため、外側と判定されてしまいます。自己交差している多角形に対してもうまく判定してくれるアルゴリズムにWinding Number Algorithmがありますが、今回は割愛します。

f:id:takuminv:20200426213046p:plain:w150

1-3. 点が多角形の辺上に存在する場合

点が多角形の辺上に存在する場合人、内側とするか外側とするかを決めないといけません。一般的に左および下の辺にある場合は内側、右および上の辺にある場合は外側と判定するようです。 f:id:takuminv:20200427235255p:plain:w500

1-4. 判定方法

以上のことを踏まえると、以下のルールにより正しく判定することができます。

  • 下向きの辺は開始点を含まず、終点を含む
  • 上向きの辺は開始点を含め、終点を含まない
  • 水平となる辺は判定対象としない
  • 点Pの水平線と辺の交点は点pの右側にあること

2. 直線の方程式

点Pからのビル水平線と辺の交点のX座標を求めるために直線の方程式を使用します。 f:id:takuminv:20200428002602p:plain:w300

例として、以下の図で考えてみます。

f:id:takuminv:20200428001247p:plain:w150

交点のX座標を求めるために、①の式をXについて解きます。

f:id:takuminv:20200428002705p:plain:w300

次に、図をもとに②の式に以下を代入します。

f:id:takuminv:20200428003024p:plain:w100

f:id:takuminv:20200428003155p:plain:w300

よって、点Pから伸びる水平線と辺の交点のX座標は5であると求めることができました。Crossing Number Algorithmでは、ここで求めたX座標が点PのX座標より大きいか判定します。今回の場合だと求めたX座標が点PのX座標よりも大きいため、辺が点Pよりも右側にあると判定します。これを多角形を構成する全ての辺に対して行い、右側に存在する辺の個数が奇数であれば範囲内、偶数であれば範囲外とします。

f:id:takuminv:20200509213313p:plain:w300

3. 実装

以上の点を踏まえて、プログラムの実装を行います。最近仕事でAngularを使い始めたのでAngularで実装してみます。

3-1. バージョン

  • Angular 9.1.6
  • Angular CLI 9.1.5
  • Node 13.11.0

3-2. ディレクトリ構成(appディレクトリ下)

componentはCanvasComponentとTopPageComponentの2つで、サービスクラスはCrossingNumberAlgorithmServiceの1つです。

.
├── app-routing.module.ts
├── app.component.css
├── app.component.html
├── app.component.spec.ts
├── app.component.ts
├── app.module.ts
├── compoents
│   ├── Canvas // 点や図形を表示するcanvasを定義したcomponent
│   │   ├── Canvas.component.css
│   │   ├── Canvas.component.html
│   │   ├── Canvas.component.spec.ts
│   │   └── Canvas.component.ts
│   └── TopPage // CanvasComponentを表示するページのcomponent
│       ├── TopPage.component.css
│       ├── TopPage.component.html
│       ├── TopPage.component.spec.ts
│       └── TopPage.component.ts
└── service
    ├── CrossingNumberAlgorithm.service.spec.ts
    └── CrossingNumberAlgorithm.service.ts // アルゴリズムのロジック

3-3. TopPageComponent

3-3-1. HTML

CSSフレームワークとしてBulmaを使用しています。 CanvasComponentを子コンポーネントとして呼び出しているだけです。

<nav class="navbar is-dark" role="navigation" aria-label="main navigation">
</nav>
<app-Canvas></app-Canvas>

3-4. CanvasComponent

3-4-1. HTML

canvasタグにテンプレート参照変数と、クリックイベントを指定してます。 テンプレート参照変数を指定することで、canvasをTS側で参照できるようにします。 また、クリックイベントによりクリックした座標に点を配置するようにします。

<section>
  <div class="canvas">
    <canvas #crossingNumberAlgorithmCanvas (click)="onClickCanvas($event)" width="600" height="600">
    </canvas>
  </div>
</section>

3-4-2. CSS

CSSはただセンタリングしているだけです。

.canvas {
    text-align: center;
    padding: 20px;
  }
  .canvas canvas {
    border: 1px #000 solid;
    width: 600px;
    height: 600px;
  }

3-4-3. TS

@ViewChildはcomponentを描画した後に要素を取得するため、ngInit()ではなく、ngAfterViewInit()を使用します。 ngAfterViewInit()では、範囲判定の対象となる図形の表示を行います。図形の座標は、CrossingNumberAlgorithmService内で定義しています。

import { Component, OnInit, AfterViewInit, ViewChild } from '@angular/core';
import { CrossingNumberAlgorithmService } from 'src/app/service/CrossingNumberAlgorithm.service';

@Component({
  selector: 'app-Canvas',
  templateUrl: './Canvas.component.html',
  styleUrls: ['./Canvas.component.css']
})
export class CanvasComponent implements OnInit, AfterViewInit {

  /** canvasタグを特定する用 */
  @ViewChild('crossingNumberAlgorithmCanvas') crossingNumberAlgorithmCanvas;
  
  /** canvasタグ用 */
  public canvas: HTMLCanvasElement; 
  public ctx: CanvasRenderingContext2D;

  /** 範囲判定を行う図形は固定 */
  public lines = this.crossingNumberAlgorithmService.LINES;


  constructor(private crossingNumberAlgorithmService: CrossingNumberAlgorithmService) { }

  ngOnInit() {
  }

  /** viewChildが描画語でなければ参照できないいため使用 */
  ngAfterViewInit() {
    this.canvas = this.crossingNumberAlgorithmCanvas.nativeElement;
    this.ctx = this.canvas.getContext( '2d' );

    // 指定した座標に沿って線を引く
    for (let i = 0; i < this.lines.length - 1; i++) {
      this.ctx.beginPath();
      this.ctx.moveTo(this.lines[i].x, this.lines[i].y);
      this.ctx.lineTo(this.lines[i+1].x, this.lines[i+1].y);
      this.ctx.closePath();
      this.ctx.stroke();  
    }
  }
  
  /**
   * canvas内をクリック時
   * クリックした箇所に点をうつ
   * 範囲内であれば赤点、範囲外であれば青点とする
   * @param event 
   */
  onClickCanvas(event) {

    // canvasの左上を(0,0)とするために座標計算
    let rect = event.currentTarget.getBoundingClientRect();
    let x = event.x - rect.left;
    let y = event.y - rect.top;

    // 点をうつ
    this.drawPoint(x, y);
    }

    /**
     * 引数として与えられた座標に点をうつ
     * 範囲内であれば赤点、範囲外であれば青点とする
     * @param x 
     * @param y 
     */
    drawPoint(x: number, y: number) {
    // 点をうつ
    this.ctx.beginPath();
    this.ctx.arc( x, y, 1, 0, Math.PI*2, false ) ;

    // 範囲内: Styleを赤, 範囲外: Styleを青
    this.crossingNumberAlgorithmService.checkWithInPoint(x, y)? this.ctx.strokeStyle = "red" : this.ctx.strokeStyle = "blue" ;
    this.ctx.lineWidth = 1 ;
    this.ctx.stroke(); 
    }


}

3-5. CrossingNumberAlgorithmService

checkWithInPoint()内で　CrossnigNumberAlgorithmを実装しています。

import { Injectable } from '@angular/core';

@Injectable({
  providedIn: 'root'
})
export class CrossingNumberAlgorithmService {

  /** 範囲判定を行う図形(図形を構成する点の座標を配列として表す) */
  public LINES:{x: number, y: number}[] = [
    {
      x: 100,
      y: 100,
    },
    {
      x: 150,
      y: 150,
    },
    {
      x: 200,
      y: 150,
    },
    {
      x: 300,
      y: 200,
    },
    {
      x: 300,
      y: 50,
    },
    {
      x: 400,
      y: 50,
    },
    {
      x: 450,
      y: 200,
    },
    {
      x: 500,
      y: 200,
    },
    {
      x: 500,
      y: 300,
    },
    {
      x: 350,
      y: 500,
    },
    {
      x: 350,
      y: 300,
    },
    {
      x: 200,
      y: 400,
    },
    {
      x: 200,
      y: 500,
    },
    {
      x: 100,
      y: 300,
    },
    {
      x: 100,
      y: 100,
    },
  ]

  constructor() { }


  /**
   * 引数として渡された点が範囲内であるか判定する
   * @param pointX 
   * @param pointY 
   * @return true: 範囲内, false: 範囲外
   */
  checkWithInPoint(pointX: number, pointY: number): boolean {
    let withIncount: number = 0;

    for (let i = 0; i < this.LINES.length - 1; i++) {
      // 点のY座標が辺の始点と終点の間に存在するか(上向きの辺の場合)
      if( ((this.LINES[i].y <= pointY) && (this.LINES[i + 1].y > pointY))
      // 点のY座標が辺の始点と終点の間に存在するか(下向きの辺の場合)
      // このif文<figure class="figure-image figure-image-fotolife" title="実装結果">[f:id:takuminv:20200523162720g:plain]<figcaption>実装結果</figcaption></figure>により点の水平線(右側のみ)と交わることのない辺を除去
          || ((this.LINES[i].y > pointY) && (this.LINES[i + 1].y <= pointY))) {

            // 直線の方程式より、点の水平線(右側のみ)と辺の交点のX座標を求める
            let dx = (pointY - this.LINES[i]. y) * (this.LINES[i + 1].x - this.LINES[i].x) / (this.LINES[i + 1].y - this.LINES[i].y) + this.LINES[i].x; 

            if (pointX < dx) {
              withIncount++;
            }
          }
    }

    // 奇数: 範囲内, 偶数: 範囲外
    return withIncount % 2 !== 0 ? true : false; 
  }
}

4. 実装結果

ちょっと見えずらいですが、図形の範囲内の時は赤点、範囲外の時は青点になっていることがわかります。

実装結果

5. おわりに

このようにcanvasを使用したことで判定が正しくできていることが目に見えてわかるため、実装してよかったと思います。ではでは。

github.com

6. おまけ

点をcavas内の全ての座標に配置するようにしたら次のようになりました。きれい。

おまけ

7. 参考にしたサイト

www.nttpc.co.jp

qiita.com