# Trace Code
###### tags: `2D-string`

### Point

//package squaretracing;
//定義Point  
public class Point {
    public static final int DIR_NORTH = 0; //方向
    public static final int DIR_EAST = 1;
    public static final int DIR_SOUTH = 2;
    public static final int DIR_WEST = 3;
    private int x; //x座標
    private int y; //y座標
    private int direction; //往哪個方向走
    
    //一開始的起始點, 預設方向是North
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
        this.direction = DIR_NORTH;
    }
    //有方向的Point
    public Point(int x, int y, int direction) {
        this.x = x;
        this.y = y;
        this.direction = direction;
    }
    //將point重設為refpoint
    public Point(Point refPoint) {
        this.x = refPoint.x;
        this.y = refPoint.y;
        this.direction = refPoint.direction;
    }
    //向右轉
    public void faceRight() {
        direction = (direction + 1) % 4;
    }
    //向左轉
    private void faceLeft() {
        if (direction == 0) {
            direction = 3; //如果方向剛好向北, 用直接指定的方式指定方向
        } else {
            direction--;
        }
    }
    //走一步
    private void goForward() {
        if (direction == DIR_NORTH) {
            y = y - 1;
        }
        if (direction == DIR_EAST) {
            x = x + 1;
        }
        if (direction == DIR_SOUTH) {
            y = y + 1;
        }
        if (direction == DIR_WEST) {
            x = x - 1;
        }
    }
    //向右走一步
    public void advanceToLeft() {
        faceLeft();
        goForward();
    }
    //向左走一步
    public void advanceToRight() {
        faceRight();
        goForward();
    }
    //複製point
    public Point getClone() {
        return new Point(this);
    }
    //回傳Point現在面對的方向
    public int getDirection() {
        return direction;
    }
    //回傳Point現在的x座標
    public int getX() {
        return x;
    }
    //回傳Point現在的y座標
    public int getY() {
        return y;
    }
    //判斷兩個Point是否在同一個位置
    //true代表在同一個位置
    @Override
    public boolean equals(Object obj) {
        if (obj == null) {
            return false;
        }
        if (getClass() != obj.getClass()) {
            return false;
        }
        final Point other = (Point) obj;
        if (this.x != other.x) {
            return false;
        }
        if (this.y != other.y) {
            return false;
        }
        return true;
    }
}

### SquareTracingService

import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
//Point.java

public class SquareTracingService {
    //getContourPoints(): 圈出有'1'的範圍
    //scrImage: 12*12
    //回傳List, 裡面裝被圈出的Point的x座標, y座標
    public List getContourPoints(int[][] scrImage) {
        int[][] image = scrImage.clone(); //複製
        clearBorder(image); //清除邊界
        
        List points = new LinkedList();//{x1, y1, x2, y2, ...}

        Point startingPoint = getStartingPoint(image); //找起始點
        Point currentPoint = startingPoint.getClone(); //圈出'1'(會移動)
        
        //走
        //currentPoint從startingPoint開始走, 
        //如果currentPoint和startingPoint不一樣, 就加到points, 
        //直到繞一圈走回startingPoint結束
        do {
            //如果該位置是1
            if (image[currentPoint.getX()][currentPoint.getY()] == 1) {
                points.add(currentPoint.getClone().getX());//x座標存入points
                points.add(currentPoint.getClone().getY());//y座標存入points
                currentPoint.advanceToLeft();
            } else {
                currentPoint.advanceToRight();
            }
        } while (!startingPoint.equals(currentPoint)); //用的是Point.equals() 

        return points;
    }
    //getStartingPoint(): 找起始點
    //一開始image已經被處理成只有0和1的[][], 1代表有東西
    private Point getStartingPoint(int[][] image) {
        //起始點從右下角開始找
        for(int y = image.length; y >= 0; y--) {
            for(int x = image[y].length;x >= 0; x--) {
                if(image[x][y] == 1) {
                    return new Point(x, y);
                }
            }
        }
        return null;
    }
    //clearBorder(): 清除邊界
    //邊界補0
    private void clearBorder(int[][] image) {
        for(int y = 0; y < image.length; y++) {
            for(int x = 0; x<image[y].length; x++) {
                if(y == 0 || x == 0 || y == image.length -1 || x == image[y].length - 1) {
                    image[x][y] = 0;
                }
            }
        }
    }
}