[2022 하계 모각코] 5회차 결과

목표

하나의 edge를 가진 그래프를 만들고 시각화 해보려 합니다.

 

결과

하나의 edge는 시작점과 끝점이 있어야하고, 방향을 나타내기 위해 화살표로 만들어야 합니다.

 

이때 시작점과 끝점은 시작 vertex의 중심에서 끝 vertex의 중심으로 향하는 직선 과, 두 vertex의 교점입니다.

 

이를 구현하기 위해 점을 회전시키는 함수를 만들어야했고, 이때 사용한 것은 회전 변환 행렬입니다.

 

export class Point {
  x: number;
  y: number;
  constructor(x: number, y: number) {
    this.x = x;
    this.y = y;
  }

  static getTanValue(centerPoint: Point, targetPoint: Point): number {
    let width = targetPoint.x - centerPoint.x;

    width = Math.max(Math.abs(width), 1e-4);

    if (targetPoint.x - centerPoint.x < 0) {
      width *= -1;
    }

    const height = targetPoint.y - centerPoint.y;

    return height / width;
  }

  static getAngle(centerPoint: Point, targetPoint: Point): number {
    const tanValue = this.getTanValue(centerPoint, targetPoint);
    let angle = Math.atan(tanValue);

    if (
      (tanValue < 0 && targetPoint.x - centerPoint.x < 0) ||
      (tanValue > 0 && targetPoint.y - centerPoint.y < 0)
    ) {
      angle += Math.PI;
    }

    if (Object.is(angle, -0)) {
      angle += Math.PI;
    }

    return angle;
  }

  static getRotatedPoint(targetPoint: Point, angle: number): Point {
    const rotatedX =
      Math.cos(angle) * targetPoint.x - Math.sin(angle) * targetPoint.y;
    const rotatedY =
      Math.sin(angle) * targetPoint.x + Math.cos(angle) * targetPoint.y;
    return new Point(rotatedX, rotatedY);
  }
}

 

따라서 시작점과 끝점을 구한 후 두 점을 이어주면 우선 edge를 이루는 선을 그릴 수 있게 됩니다.

 

다음으로 필요한 것은 화살표입니다.

 

화살표는 끝점에서 10px의 길이를 갖는 원 중, edge의 선으로부터 -30도 +30도를 한 두 점으로 이어주면 화살표를 그릴 수 있게 됩니다.

 

import { Point } from "./Point.js";
import { Vertex } from "./Vertex.js";

export class Edge {
  firstEdgePoint: Point;
  secondEdgePoint: Point;
  firstCenterPoint: Point;
  secondCenterPoint: Point;
  direction: boolean; // true: first to second, false: second to first

  constructor(
    firstEdgePoint: Point,
    secondEdgePoint: Point,
    firstCenterPoint: Point,
    secondCenterPoint: Point,
    direction: boolean
  ) {
    this.firstEdgePoint = firstEdgePoint;
    this.secondEdgePoint = secondEdgePoint;
    this.firstCenterPoint = firstCenterPoint;
    this.secondCenterPoint = secondCenterPoint;
    this.direction = direction;
  }

  static drawEdge(ctx: CanvasRenderingContext2D, edge: Edge) {
    let startEdgePoint: Point;
    let endEdgePoint: Point;
    let startCenterPoint: Point;
    let endCenterPoint: Point;

    if (edge.direction) {
      startEdgePoint = edge.firstEdgePoint;
      endEdgePoint = edge.secondEdgePoint;
      startCenterPoint = edge.firstCenterPoint;
      endCenterPoint = edge.secondCenterPoint;
    } else {
      startEdgePoint = edge.secondEdgePoint;
      endEdgePoint = edge.firstEdgePoint;
      startCenterPoint = edge.secondCenterPoint;
      endCenterPoint = edge.firstCenterPoint;
    }

    const startToEndAngle = Point.getAngle(startCenterPoint, endCenterPoint);
    const endToStartAngle = Point.getAngle(endCenterPoint, startCenterPoint);

    const rotatedStart = Point.getRotatedPoint(
      new Point(50, 0),
      startToEndAngle
    );
    const rotatedEnd = Point.getRotatedPoint(new Point(50, 0), endToStartAngle);

    startEdgePoint = new Point(
      rotatedStart.x + startCenterPoint.x,
      rotatedStart.y + startCenterPoint.y
    );
    endEdgePoint = new Point(
      rotatedEnd.x + endCenterPoint.x,
      rotatedEnd.y + endCenterPoint.y
    );

    ctx.beginPath();
    ctx.strokeStyle = "black";
    ctx.lineWidth = 3;
    ctx.moveTo(startEdgePoint.x, startEdgePoint.y);
    ctx.lineTo(endEdgePoint.x, endEdgePoint.y);
    ctx.stroke();

    this.getArrow(ctx, startEdgePoint, endEdgePoint);
  }

  private static getArrow(
    ctx: CanvasRenderingContext2D,
    controlPoint: Point,
    endPoint: Point
  ) {
    const ARROW_LENGTH = 15;
    const angle = Point.getAngle(endPoint, controlPoint);

    const arrowEndPoint = new Point(endPoint.x + ARROW_LENGTH, endPoint.y);

    const rightArrowEndPoint = Point.getRotatedPoint(
      new Point(arrowEndPoint.x - endPoint.x, arrowEndPoint.y - endPoint.y),
      angle + Math.PI / 6
    );

    const leftArrowEndPoint = Point.getRotatedPoint(
      new Point(arrowEndPoint.x - endPoint.x, arrowEndPoint.y - endPoint.y),
      angle - Math.PI / 6
    );

    rightArrowEndPoint.x += endPoint.x;
    rightArrowEndPoint.y += endPoint.y;

    leftArrowEndPoint.x += endPoint.x;
    leftArrowEndPoint.y += endPoint.y;

    ctx.beginPath();
    ctx.strokeStyle = "black";
    ctx.lineWidth = 3;
    ctx.lineCap = "round";
    ctx.moveTo(rightArrowEndPoint.x, rightArrowEndPoint.y);
    ctx.lineTo(endPoint.x, endPoint.y);
    ctx.moveTo(leftArrowEndPoint.x, leftArrowEndPoint.y);
    ctx.lineTo(endPoint.x, endPoint.y);
    ctx.stroke();
  }
}

이제 그려보겠습니다.

 

const app = new App();
app.addVertex("1", 100, 100);
app.addVertex("2", 400, 100);
app.addVertex("3", 100, 400);
app.addVertex("4", 400, 400);
app.addEdge(app.vertexSet[0], app.vertexSet[1]);
app.addEdge(app.vertexSet[2], app.vertexSet[0]);
app.addEdge(app.vertexSet[1], app.vertexSet[3]);
app.addEdge(app.vertexSet[2], app.vertexSet[3]);
app.addEdge(app.vertexSet[2], app.vertexSet[1]);

위와 같이 (100, 100), (400, 100), (100, 400), (400, 400) 에 순서대로 1~4라는 이름을 가진 반지름 50짜리 vertex 4개를 그린 후,

 

1 --> 2, 3 --> 1, 2 --> 4, 3 --> 4, 3 --> 2 와 같이 방향을 갖는 edge를 그렸고, 결과는 다음과 같습니다.

 

다음에는 edge에 가중치를 넣을 수 있게 만들어볼 생각입니다.