기능 개선(랜덤 길찾기 알고리즘)

랜덤 길찾기 알고리즘을 발전시킬 것이다.
지금의 알고리즘은 단지 20km이내에 있는 관광지를 무작위적으로 추천해주는 알고리즘이다.
그 결과 T자, 8자등 만든 사람도 별로 내키지 않는 경로를 안내해준다.
경로 안내 알고리즘을 발전시키기 위해 3가지 방법을 생각해냈고, 각각의 알고리즘은 다음과 같다.

알고리즘 설명

직선거리 주변 경유지 탐색 알고리즘
원래 경로에서 크게 벗어나지 않는 경로를 원하거나,
짧은 경로 + 적은 경유지 상황에서 효과적이다.
큰 정사각형의 구간별 경유지 탐색 알고리즘
1번 보기보다 좀더 무작위적인 경로를 원하거나,
긴 경로 + 많은 경유지를 원할때 효과적인 방법이다.
순환형 드라이브 코스 추천 알고리즘
다른 보기와는 달리 집에서 출발해 집으로 돌아오는 알고리즘이다.
경로검색 한번으로 하루 드라이브 코스를 모두 정해줄 수 있다.

유틸리티 메서드

getRandomAngle
원하는 각도 범위를 주면 무작위 각도를 반환하는 메서드이다.
무작위 목적지를 반환하는 메서드와 순환형 드라이브 코스 추천 메서드에서 사용된다.

private double getRandomAngle(int angleRange) {
    Random random = new Random();
    // 0부터 3600 사이의 무작위 정수를 얻음
    int randomInt = random.nextInt(angleRange * 10 + 1); // 랜덤 각도 구해줌
    // 정수를 10으로 나누어 각도를 얻음 (0.1 단위로)
    double angle = randomInt / 10.0;
    // 점검용
    System.out.println("무작위 각도: " + angle);
    return angle;
}

calculateDistance
두 점 사이 거리를 계산해주는 메서드이다. 좌표값을 기준으로 구해줘서 '실제 거리 / 100'의 형태로 반환된다.

private double calculateDistance(double originY, double originX, double destinationY, double destinationX) {
    double deltaY = destinationY - originY;
    double deltaX = destinationX - originX;
    // 유클리드 거리 계산
    return Math.sqrt(deltaY * deltaY + deltaX * deltaX);
}

getRandomWayPoint
특정 좌표 주변 경유지를 골라주는 메서드이다. KakaoCategorySearchService의 기능을 이용한다.

private RandomDocumentDto getRandomWayPoint(double y, double x, double redius) {
    Random rd = new Random();
    KakaoApiResponseDto responses = kakaoCategorySearchService.requestPharmacyCategorySearch(y, x, redius);
    int randomLength = responses.getDocumentDtoList().size();
    if (randomLength == 0)
        return null;
    int wayPointCnt = rd.nextInt(randomLength);
    return new RandomDocumentDto(responses.getDocumentDtoList().get(wayPointCnt));
}

주요 메서드

무작위 목적지 구해주기
출발지에서 무작위 각도, distance만큼 떨어진 곳의 주변 2km 이내의 관광지를 목적지로 설정해준다.
우리나라의 3면이 바다이고, 산지도 꽤 많은것을 고려하면 해당 지점에 아무것도 없을 수 있다.
만일 해당 지점에 아무것도 없다면, 목적지로부터 출발지에 대칭인 곳 주변에서 목적지를 찾는다.
그래도 없다면, x좌표 대칭점, 또 그래도 없다면 y좌표 대칭점 주변에서 목적지를 구해준다.

private DocumentDto getDestination(double originY, double originX, double distance) {
        double radians = Math.toRadians(getRandomAngle(360));

        double randomY = originY + distance * Math.sin(radians);
        double randomX = originX + distance * Math.cos(radians);

        double tempY = randomY; // 임시 Y 좌표
        double tempX = randomX; // 임시 X 좌표

        // 목적지 값을 반경으로 계산해서 가져오는 메소드
        KakaoApiResponseDto responses = kakaoCategorySearchService.requestPharmacyCategorySearch(randomY, randomX, 2);

        // 랜덤으로 다중 목적지와 경유지 만들기 알고리즘
        int randomLength = responses.getDocumentDtoList().size();

        // 만일 찍은 좌표 주변에 아무것도 없다면..?
        if (randomLength == 0) { // 출발지 좌표를 기준으로 대칭되는 곳의 좌표를 목적지 좌표로 수정
            randomX -= 2 * (randomX - originX);
            randomY -= 2 * (randomY - originY);
            responses = kakaoCategorySearchService.requestPharmacyCategorySearch(randomY, randomX, 2);
            randomLength = responses.getDocumentDtoList().size();
            if (randomLength == 0) { // 출발지 좌표를 기준으로 Y좌표가 대칭되는 곳의 좌표를 목적지 좌표로 수정
                randomX = tempX;
                responses = kakaoCategorySearchService.requestPharmacyCategorySearch(randomY, randomX, 2);
                randomLength = responses.getDocumentDtoList().size();
                if (randomLength == 0) { // 출발지 좌표를 기준으로 X좌표가 대칭되는 곳의 좌표를 목적지 좌표로 수정
                    randomX -= 2 * (randomX - originX);
                    randomY = tempY;
                    responses = kakaoCategorySearchService.requestPharmacyCategorySearch(randomY, randomX, 2);
                }
            }
        }
        Random rd = new Random();
        int destinationCnt = rd.nextInt(randomLength);
        DocumentDto destination = responses.getDocumentDtoList().get(destinationCnt);
        return destination;
    }

직선거리 주변 경유지 탐색 메서드
처음 설명한대로, 직선거리 주변의 경유지를 추천해준다.
직선거리 / 경유지수와 20 중 더 작은 값으로 주변의 경유지를 탐색하는 범위를 결정한다.

private List<RandomDocumentDto> getWayPointsAroundLine(double originY, double originX, double destinationY, double destinationX, Integer count) {
        double distance = calculateDistance(originY, originX, destinationY, destinationX);
        double realDistance = distance * 100;
        List<RandomDocumentDto> wayPoints = new ArrayList<>();
        for (int i = 1; i <= count; i++) {
            double tempY = originY + (destinationY - originY) * i / count;
            double tempX = originX + (destinationX - originX) * i / count;
            double redius = Math.min(realDistance/count, 20);
            RandomDocumentDto wayPoint = getRandomWayPoint(tempY, tempX, redius);
            wayPoints.add(wayPoint);
        }
        return wayPoints;
    }

큰 정사각형의 구간별 경유지 탐색 알고리즘
1. 출발지, 목적지 좌표를 이용해 middleX, middleY(중점)를 구해준다.
2. 출발지, 목적지 좌표를 이용해 둘의 X좌표 차이(distanceX), Y좌표 차이(distanceY) 를 구해준다.
만일 distanceX가 더 크다면 출발지와 목적지는 정사각형의 x 좌표 양쪽 끝, 반대라면 y좌표 양쪽 끝에 위치한다.
3. 만일 distanceX가 더 크다고 치자,
originX가 middleX보다 크다면 X좌표를 점점 줄이는 방향으로 경유지를 선정해야 하고,
originX가 middleX보다 작다면 X좌표를 점점 증가시키는 방향으로 경유지를 선정해야 한다.
distanceY가 distanceX보다 클 때는 X를 Y로 바꾸기만 하면 된다.
4. X좌표가 점점 줄어들 때마다, Y좌표는 랜덤 알고리즘을 이용해 구해준다.
그 결과 원하는 개수의 경유지만큼의 경유지가 생성될 것이다.

private List<RandomDocumentDto> getWayPointsInBox(double originY, double originX, double destinationY, double destinationX, Integer count) {
        List<RandomDocumentDto> wayPoints = new ArrayList<>();
        double middleY = (originY + destinationY) / 2;
        double middleX = (originX + destinationX) / 2;
        double distanceY = Math.abs(originY - destinationY);
        double distanceX = Math.abs(originX - destinationX);
        double sideLength = Math.max(distanceY, distanceX);

        if (sideLength == distanceY) {
            if(originY > middleY) {
                for (int i = 0; i < count; i++) {
                    Random rd = new Random();
                    double randomY = originY - sideLength / count / 2  - sideLength / count * i;
                    double randomX = middleX - sideLength / 2 + sideLength / count * rd.nextInt(count);
                    double redius = Math.min(sideLength/count * 100, 20);
                    RandomDocumentDto wayPoint = getRandomWayPoint(randomY, randomX, redius);
                    wayPoints.add(wayPoint);
                }
            }
            else {
                for (int i = 0; i < count; i++) {
                    Random rd = new Random();
                    double randomY = originY + sideLength / count / 2  + sideLength / count * i;
                    double randomX = middleX - sideLength / 2 + sideLength / count * rd.nextInt(count);
                    double redius = Math.min(sideLength/count * 100, 20);
                    RandomDocumentDto wayPoint = getRandomWayPoint(randomY, randomX, redius);
                    wayPoints.add(wayPoint);
                }
            }
        }
        else {
            if(originX > middleX) {
                for (int i = 0; i < count; i++) {
                    Random rd = new Random();
                    double randomX = originX - sideLength / count / 2 - sideLength / count * i;
                    double randomY = middleY - sideLength / 2 + sideLength / count * rd.nextInt(count);
                    double redius = Math.min(sideLength/count * 100, 20);
                    RandomDocumentDto wayPoint = getRandomWayPoint(randomY, randomX, redius);
                    wayPoints.add(wayPoint);
                }
            }
            else {
                for (int i = 0; i < count; i++) {
                    Random rd = new Random();
                    double randomX = originX + sideLength / count / 2 + sideLength / count * i;
                    double randomY = middleY - sideLength / 2 + sideLength / count * rd.nextInt(count);
                    double redius = Math.min(sideLength/count * 100, 20);
                    RandomDocumentDto wayPoint = getRandomWayPoint(randomY, randomX, redius);
                    wayPoints.add(wayPoint);
                }
            }
        }
        return  wayPoints;
    }

순환형 드라이브 코스 경유지 추천 메서드
1. 출발지에서 무작위 각도, distance/2만큼 떨어진 곳의 좌표를 원의 중점을 잡는다.
이때 얻은 무작위 각도를 + 180 = 원의 중점에서 출발지의 각도이다.
2. 원하는 경유지의 개수 + 1 만큼 원을 쪼개줄 것이다. 이때 + 1은 출발지를 나타낸다.
3. 쪼개진 구간별로 랜덤한 각도를 계산한다.
4. 중점에서 구한 각도, distance/2만큼 떨어진 곳의 좌표 주변 2km 내에서 경유지를 찾아준다.

private List<RandomDocumentDto> getWayPointsCircular(double originY, double originX, double redius, Integer count) {
        List<RandomDocumentDto> wayPoints = new ArrayList<>();

        double degree = getRandomAngle(360);
        double radian = Math.toRadians(degree);
        double rediusY = originY + redius * Math.sin(radian);
        double rediusX = originX + redius * Math.cos(radian);
        System.out.println("중점 : " + rediusY + ", " + rediusX);
        int rangeDegree = 360 / (count + 1);

        for (int i = 0; i < count; i++) {
            double wayPointRadian = Math.toRadians(degree + 180 + getRandomAngle(rangeDegree)+ rangeDegree * i);
            System.out.println("각도 : " + wayPointRadian);
            double wayPointY = rediusY + redius * Math.sin(wayPointRadian);
            double wayPointX = rediusX + redius * Math.cos(wayPointRadian);
            System.out.println("정점" + (i+1) + " : " + wayPointY + ", " + wayPointX);
            RandomDocumentDto wayPoint = getRandomWayPoint(wayPointY, wayPointX, 2);
            if (wayPoint != null)
                wayPoints.add(wayPoint);
        }
        return wayPoints;
    }

주의할 점

2, 3번 기능은 너무 먼 거리를 설정할 경우 드라이브 코스로 생각할 수 없을만큼 오래 운전해야 하는 코스를 추천해준다.
3번은 최대 40km까지 2번은 최대 60km까지만 갈 수 있게 설정해놓자.

'프로젝트 > RanDrive' 카테고리의 다른 글

기능 개선(경유지를 가진 경로 이탈 시 처리) (0)	2023.11.01
기능 개선(JMeter) (0)	2023.10.30
https 배포 (0)	2023.10.28
Random-Drive-Project 기본 MVC 구현(프론트엔드 작업) (0)	2023.10.26
Random-Drive-Project 기본 MVC 구현(경로 조회, 상세조회) (1)	2023.10.18

HWK의 코딩 블로그

기능 개선(랜덤 길찾기 알고리즘)

알고리즘 설명

유틸리티 메서드

주요 메서드

주의할 점

'프로젝트 > RanDrive' 카테고리의 다른 글

티스토리툴바

기능 개선(랜덤 길찾기 알고리즘)

알고리즘 설명

유틸리티 메서드

주요 메서드

주의할 점

'프로젝트 > RanDrive' 카테고리의 다른 글

관련글

티스토리툴바