2023.11.02
💻 개선 방향
- 카테고리에 맞는 정확한 지명과 주소의 매칭
- 효율적인 길찾기 경로 생성
- 도로교통 정보를 반영 -> 거리가 더 멀어지더라도 정체 -> 서행으로 드라이브를 할 수 있게
- 출발지 도착지 명확하게 표시
✅ 2. 효율적인 길찾기 경로 생성
- 경유지 리스트들 중 2개를 랜덤으로 뽑아서 경유지, 목적지로 설정 -> 중복된 경로가 발생
- 효율적인 경로 생성이 어려움 -> 중복된 경로가 생성되지 않고 이어지는 경로 생성
- 반경이 제한적인 상황
- 하나의 경유지가 아닌 다양한 경유지(관광 명소 카테고리)를 잡아서 다채로운 경로 생성
효율적 길찾기 -> 알고리즘을 직접 구현해서 길찾기가 가능할까?
- 효율적인 길찾기를 위해서 길찾기가 어떤 원리로 동작이 되는지 알 필요가 있다.
- 현재는 카카오 내부 길찾기 api를 활용해서 구현을 하고 있는데, 직접 데이터 모델링을 하고 그 그래프를 토대로 알고리즘을 적용해서 최적의 경로를 찾아내는 방식을 알아내면 더 효율적인 길찾기가 되지 않을까?
- 실제 도로 데이터를 가져오기에는 범위가 너무 커져서 일단 구현이 가능한지를 확인하기 위해 경유지를 노드로 잡고 그래프와 알고리즘을 통해 경로가 생성되는지 보자.
📟 기존 문제
- 효율적인 경로 생성 x -> 중복된 경로 생성
- 20km 제한적 반경
-> 중복된 경로 제한, 다음 경유지로 연결, 반경 확장 고려
💻 시도1
- 기존에 길찾기 알고리즘과 같이 데이터 모델링을 통해서 카카오 api 호출이 아닌, 직접 알고리즘을 먼저 적용해보면서 노드와 엣지를 통한 경로 생성 시도
- 도로 좌표의 데이터를 가지고 노드와 엣지를 만들어서 해야 하나, 일단은 카카오 api 에서 카테고리별 잡은 경유지 리스트를 가지고 경유지를 기반으로 루트 생성 시도
- 경유지 리스트 -> 노드로 만들기, 각 노드별 엣지를 연결 해서 최단 거리 구하기 -> 제일 먼 노드를 목적지로 설정 하고 중간 거리인 경유지 좌표를 통해 총 3개의 좌표 구하고 경로생성
서비스 로직
public RouteResult requestAllRandomWay(String originAddress, Integer radius) {
DocumentDto origin = kakaoAddressSearchService.requestAddressSearch(originAddress).getDocumentDtoList().get(0);
KakaoApiResponseDto tourResponses = kakaoCategorySearchService.requestAttractionCategorySearch(origin.getLatitude(), origin.getLongitude(), radius);
List<DocumentDto> waypoints = new ArrayList<>();
DocumentDto saveOrigin = new DocumentDto(origin);
waypoints.add(saveOrigin); // origin을 waypoints의 첫 번째 요소로 추가
waypoints.addAll(tourResponses.getDocumentDtoList());
logWaypointInfo("waypoints", waypoints);
logWaypointInfo("getDocumentDtoList placeNames", tourResponses.getDocumentDtoList());
logWaypointInfo("getDocumentDtoList addressNames", tourResponses.getDocumentDtoList());
Graph graph = buildGraphWithWaypoints(waypoints);
Nodes newOrigin = nodesRepository.findByName("출발지");
Map<Nodes, Nodes> predecessors = new HashMap<>();
DijkstraResult dijkstraResult = dijkstra(graph, newOrigin, predecessors);
List<Nodes> pathNodesList = dijkstraResult.getPathNodes();
log.info("최적 경로 : {}", pathNodesList.stream().map(Nodes::toString).collect(Collectors.joining(" -> ")));
return RouteResult.builder()
.start(origin)
.destination(pathNodesList.get(2).toDto()) // 마지막 노드 (목적지)
.waypoints(pathNodesList.get(1).toDto()) // 중간 경유지
.totalDistance(dijkstraResult.getTotalDistance())
.path(pathNodesList) // 모든 경로 노드들 (출발지, 중간 경유지, 목적지 포함)
.build();
}
- KakaoApiResponseDto tourResponses = kakaoCategorySearchService.requestAttractionCategorySearch(origin.getLatitude(), origin.getLongitude(), radius); -> 최초 사용자가 주소를 입력 -> 그 주변 반경의 경유지 리스트를 뽑아온다.
- 해당 경유지 리스트를 그래프로 만든다. (노드 + 엣지)
Graph graph = buildGraphWithWaypoints(waypoints);- 만든 그래프를 가지고 노드 들간의 최단 거리를 구하는 알고리즘에 적용한다.
DijkstraResult dijkstraResult = dijkstra(graph, newOrigin, predecessors);- 최종 3개의 좌표로 polyline을 만들어 본다.
-> 추후에 도로 좌표를 노드, 엣지로 만들어서 똑같은 개념으로 적용 가능.
⌨ 그래프 만들기
public Graph buildGraphWithWaypoints(List<DocumentDto> waypoints) {
Graph graph = new Graph();
Set<Edges> edgesSet = new HashSet<>();
List<Nodes> nodesList = waypoints.stream().map(Nodes::new).collect(Collectors.toList());
for (int i = 0; i < nodesList.size(); i++) {
for (int j = i + 1; j < nodesList.size(); j++) {
Nodes node1 = nodesList.get(i);
Nodes node2 = nodesList.get(j);
double distance = calculateDistance(
node1.getY(), node1.getX(),
node2.getY(), node2.getX());
Edges newEdge = new Edges(node1, node2, distance);
if(!edgesSet.contains(newEdge)) {
graph.addEdge(node1, node2, distance);
edgesSet.add(newEdge);
}
}
}
saveGraphToDatabase(graph);
log.info("그래프 : {}", graph );
return graph;
}
// haversine fomula 거리계산 알고리즘
private double calculateDistance(double lat1, double lon1, double lat2, double lon2) {
lat1 = Math.toRadians(lat1);
lon1 = Math.toRadians(lon1);
lat2 = Math.toRadians(lat2);
lon2 = Math.toRadians(lon2);
double earthRadius = 6371; //Kilometers
return earthRadius * Math.acos(Math.sin(lat1) * Math.sin(lat2) + Math.cos(lat1) * Math.cos(lat2) * Math.cos(lon1 - lon2));
- 경유지 리스트
- 경유지 리스트 각 각 -> 노드로
- 각 노드끼리의 거리계산을 통해 해당 거리를 엣지로 설정(현재 방향성 x, 중복 문제)
- 해당 로그 정보
만들어진 그래프를 토대로 알고리즘 진행
⌨ 알고리즘 적용하기
// Dijkstra 알고리즘
public DijkstraResult dijkstra(Graph graph, Nodes start, Map<Nodes, Nodes> predecessors) {
Map<Nodes, Double> shortestDistances = new HashMap<>();(Comparator.comparingDouble(shortestDistances::get));
PriorityQueue<Nodes> nodes = new PriorityQueue<>(Comparator.comparingDouble(node ->
shortestDistances.getOrDefault(node, Double.MAX_VALUE)));
nodes.add(start);
shortestDistances.put(start, 0.0);
while (!nodes.isEmpty()) {
Nodes currentNode = nodes.poll();
for (Edges edge : graph.getEdges(currentNode)) {
Nodes adjacentNode = (edge.getNode1().equals(currentNode)) ? edge.getNode2() : edge.getNode1();
double newDist = shortestDistances.get(currentNode) + edge.getWeight();
if (newDist < shortestDistances.getOrDefault(adjacentNode, Double.MAX_VALUE)) {
nodes.add(adjacentNode);
shortestDistances.put(adjacentNode, newDist);
predecessors.put(adjacentNode, currentNode); // 경로 추적을 위해 추가
}
}
}
log.info("알고리즘 : {}", shortestDistances);
// Map<Nodes, Double> 반환 타입 -> shortestDistances -> 출발지로부터 모든 노드의 경로를 계산한 값이 출력
Map.Entry<Nodes, Double> maxEntry = Collections.max(shortestDistances.entrySet(),
Map.Entry.comparingByValue());
Nodes farthestNode = maxEntry.getKey();
// 중간 거리의 노드 찾기
double halfDistance = maxEntry.getValue() / 2.0;
Nodes middleNode = null;
double minDifference = Double.MAX_VALUE;
for (Map.Entry<Nodes, Double> entry : shortestDistances.entrySet()) {
double difference = Math.abs(halfDistance - entry.getValue());
if (difference < minDifference) {
minDifference = difference;
middleNode = entry.getKey();
}
}
log.info("가장 먼 거리를 가진 노드: {}", farthestNode);
log.info("중간 거리를 가진 노드: {}", middleNode);
List<Nodes> pathNodes = new ArrayList<>();
pathNodes.add(start); // 출발지 추가
pathNodes.add(middleNode); // 중간 경유지 추가
pathNodes.add(farthestNode); // 목적지 추가
double distanceFromStartToMiddle = shortestDistances.get(middleNode);
double distanceFromMiddleToDestination = shortestDistances.get(farthestNode) - distanceFromStartToMiddle;
double totalDistance = distanceFromStartToMiddle + distanceFromMiddleToDestination;
log.info("출발지에서 중간지점까지의 거리: {}", distanceFromStartToMiddle);
log.info("중간지점에서 목적지까지의 거리: {}", distanceFromMiddleToDestination);
log.info("출발지에서 목적지까지의 총 거리: {}", totalDistance);
DijkstraResult result = new DijkstraResult();
result.setPathNodes(pathNodes);
result.setTotalDistance(totalDistance);
return result;
}
}
- 현재는 출발지 입력 -> 목적지, 경유지 설정 이후 경로 생성
- 현재의 출발지 node는 0의 거리를 가지고 있고, 각 노드와의 거리를 계산하는 로직
- 현재는 1~5번의 경유지가 있다면
(1,2), (1,3), (1,4), (1,5)이런식으로 노드의 최단 거리를 설정 -> 그러나 실제 길찾기에서는 일직선 상으로 연결될 수 없다. 중간에 도로와 사거리 등등의 노드를 통하고 통해서 갈 수 있어야 한다.(1,2,3,4,5) -> 1번 출발, 5번 목적지 , 2,3,4 도로의 노드를 통해서 길찾기
⌨ 간단한 테스트
- 출발지를 입력하면 해당 좌표를 받아서, 경유지 리스트를 만들고, 그 해당 리스트를 가지고 노드와 엣지를 만든다.
- 거리계산 알고리즘을 적용해서 출발지로부터 가장 먼 거리의 노드를 목적지로 설정한다. 그리고 중간지점의 거리를 경유지로 설정해서 3개의 노드를 가지고 경로를 생성한다.
- 카카오 길찾기 api를 활용하지 않고 직접 알고리즘을 적용해서 노드를 생성할 순 있었다. 경로 생성은 카카오 지도 api와 자바스크립트를 활용해서 표현했다.
<script>
const mapContainer = document.getElementById('map'),
mapOption = {
center: new kakao.maps.LatLng(37.566826, 126.9786567),
level: 7
};
const map = new kakao.maps.Map(mapContainer, mapOption);
// latitude -> y , longitude -> x
function searchRoute() {
const origin = document.getElementById("origin-input").value;
const radius = document.getElementById("radius-input").value;
// 백엔드에서 경로 정보 가져오기
fetch(`/getRoute?origin=${origin}&radius=${radius}`)
.then(response => response.json())
.then(data => {
const start = new kakao.maps.LatLng(data.start.y, data.start.x);
const waypoints = new kakao.maps.LatLng(data.waypoints.y, data.waypoints.x);
const destination = new kakao.maps.LatLng(data.destination.y, data.destination.x);
const linePath = [start, waypoints, destination];
const polyline = new kakao.maps.Polyline({
path: linePath,
strokeWeight: 5,
strokeColor: '#FF0000',
strokeOpacity: 0.7
});
polyline.setMap(map);
map.setCenter(start);
});
}
</script>💻 실제 길찾기 알고리즘 구현을 하려면
추후에 실제로 길찾기 기능처럼 구현을 하려면(현재는 말도 안되는 경로,도로를 통과해서 직선 생성) 모든 도로의 좌표들을 분류하여 노드로 만들고 도로의 길을 엣지처럼 만들어서 그 안에 가중치를 넣고, 출발지부터 목적지까지의 최적의 경로를 탐색하는 알고리즘 코드를 작성해야 한다. 이후에 해당 경로의 좌표들을 프론트에 넘겨주어서 그 경로를 프론트에 표시해 주어야 한다.
💻 효율적인 길찾기?
- 현재는 api를 효율적으로 활용하는 방법인 것 같다. -> 효율적으로 api를 호출해서 겹치지 않는 경로를 생성하는 추가적인 알고리즘을 결합하는 방식을 먼저 시도.
- 추후에 직접 데이터 그래프를 통해서 알고리즘을 적용해 보자.
디자인에서 개발자로