지도 웹앱 개발 좌표계 [최근접 이웃 알고리즘]

[최근접 이웃 알고리즘]

네이버와 공공데이터 API에서 제공하는 좌표 값이 서로 다를 경우, 이를 매칭하기 위해 유사한 좌표를 찾는 알고리즘을 JavaScript로 작성할 수 있습니다. 이를 위해 일반적으로 사용되는 알고리즘 중 하나는 "최근접 이웃" 알고리즘입니다. 아래는 JavaScript로 최근접 이웃 알고리즘을 구현하는 예시 코드입니다.

// 네이버 좌표
const naverCoords = { latitude: 37.12345, longitude: 127.67890 };

// 공공데이터 좌표 목록
const publicDataCoords = [
  { latitude: 37.23456, longitude: 127.78901 },
  { latitude: 37.34567, longitude: 127.89012 },
  // 여러 개의 좌표를 포함하는 배열
];

// 두 좌표 사이의 거리 계산 함수
function calculateDistance(coord1, coord2) {
  const radianFactor = Math.PI / 180;
  const lat1 = coord1.latitude * radianFactor;
  const lon1 = coord1.longitude * radianFactor;
  const lat2 = coord2.latitude * radianFactor;
  const lon2 = coord2.longitude * radianFactor;

  const deltaLat = lat2 - lat1;
  const deltaLon = lon2 - lon1;

  const a = Math.sin(deltaLat / 2) ** 2 + Math.cos(lat1) * Math.cos(lat2) * Math.sin(deltaLon / 2) ** 2;
  const c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));

  // 지구 반경 (미터)
  const radius = 6371e3;

  return radius * c;
}

// 가장 가까운 좌표 찾기
function findNearestCoordinate(targetCoord, coordinateList) {
  let nearestCoord = null;
  let minDistance = Infinity;

  for (const coord of coordinateList) {
    const distance = calculateDistance(targetCoord, coord);

    if (distance < minDistance) {
      minDistance = distance;
      nearestCoord = coord;
    }
  }

  return nearestCoord;
}

// 네이버 좌표를 가장 가까운 공공데이터 좌표와 매칭
const matchedCoord = findNearestCoordinate(naverCoords, publicDataCoords);

console.log("가장 가까운 공공데이터 좌표:", matchedCoord);

실제 적용 코드 

네이버 지역 검색 api 를 통해 받아온 데이터 입니다. 

크게 사용할 만한 건 좌표계입니다. 

현실적으로 해당 좌표계도 다른 공공데이터 좌표계와 동일하지 않습니다. 

이를 위해 위의 최근접 이웃 알고리즘을 사용해보겠습니다. 

$('#mapList').on('click', 'tr', function() {
     // 클릭된 행의 위도와 경도를 가져옴

    mySearchArea.setMap(null); 

    var trlatitude = $(this).find('td:nth-child(3)').text(); 

    var trlongitude = $(this).find('td:nth-child(4)').text(); 

    // 클릭한 마커로 이동 하는 함수
    filterTableByCoordinates(trlatitude, trlongitude); 


 });

해당 테이블 행을 클릭하면 좌표계를 가져와 

filterTableByCoordinates 해당 함수에서 사용합니다 . 

 

// 장소명 클릭 시 -> 해당 marker 및 info open
// 위도와 경도를 기반으로 필터링된 테이블로 이동하는 함수
function filterTableByCoordinates(latitude, longitude) {
	
	// 좌표 값이 동일 한 건 찾기 어려울 수 있으니 유사 한 값을 찾는 알고리즘이 필요할까 ? 
    // 검색된 데이터 테이블의 모든 행을 순회하며 일치하는 값을 찾음
    
    const publicDataCoords = [];
    
    const naverCoords = { latitude, longitude }; // 네이버 지역 검색 api 정보 
    
    var matchingMarker = null;
    
    for (var i=0, ii=areaMarkers.length; i<ii; i++) {
    	
    	var lat_areaMarker =areaMarkers[i].position._lat.toString().slice(0,7);
    	var lng_areaMarker =areaMarkers[i].position._lng.toString().slice(0,8);
    	
    	const publicDataCoord = {lat_areaMarker, lng_areaMarker};
    	// 공공데이터 좌표 배열 생성 
    	publicDataCoords.push(publicDataCoord);
    	
    	
    	 if (lat_areaMarker === latitude && lng_areaMarker === longitude ) {
    		 
            matchingMarker = areaMarkers[i];
            infoWindow = areaInfoWindows[i];
            
            console.log(matchingMarker);
            console.log(infoWindow);
         
        }
    	
    	
    }
    
    if (!matchingMarker) {
        // 좌표가 정확하게 일치하지 않을 경우 가장 가까운 좌표를 찾음
        const matchedCoord = findNearestCoordinate(naverCoords, publicDataCoords);

        if (matchedCoord) {
            // 가장 가까운 좌표에 해당하는 마커와 인포윈도우를 표시
            for (var i = 0, ii = areaMarkers.length; i < ii; i++) {
                if (
                    areaMarkers[i].position._lat.toString().slice(0, 7) === matchedCoord.lat_areaMarker &&
                    areaMarkers[i].position._lng.toString().slice(0, 8) === matchedCoord.lng_areaMarker
                ) {
                    matchingMarker = areaMarkers[i];
                    infoWindow = areaInfoWindows[i];
                    console.log(matchingMarker);
                    console.log(infoWindow);
                    break;
                }
            }
        } else {
            alert('해당 충전소가 없습니다.');
        }
    }

    if (matchingMarker) {
        infoWindow.open(map, matchingMarker);
    }
  
}

쉽게 함수 인자로 가져오는 좌표를 네이버 좌표라고 하겠습니다. 

네이버 좌표는 naverCoords 변수에 객체 레터럴로  배정 됩니다. 

그리고 해당 좌표 계를 공공데이터 좌표계와 비교해야합니다. 

areaMarkers[i] 은 기존 공공데이터를 기반으로 지도에 셋업 한 마커 배열로 해당 배열에서

공공데이터 좌표계 값을 추출 가능합니다. 

publicDataCoords.push(publicDataCoord);

추출한 값을 다시 배열에 넣어주고 

1차적으로 

lat_areaMarker === latitude && lng_areaMarker === longitude

동일한 값이 있는지 조건문을 작성해줍니다. 

동일한 값이 있으면 해당 루프 구간에서의 

마커와 인포창을 띄워줍니다. 

하지만 매칭 되는 마커가 없다면 ! 

다시 

findNearestCoordinate 함수로 들어갑니다. 

// 가장 가까운 좌표 찾기
function findNearestCoordinate(targetCoord, coordinateList) {
  let nearestCoord = null;
  let minDistance = Infinity;

  for (const coord of coordinateList) {
    const distance = calculateDistance(targetCoord, coord);
    
	console.log(distance);
	
    if (distance < minDistance) {
      minDistance = distance;
      nearestCoord = coord;
    }
  }

  return nearestCoord;
}

여기서 targetCoord 은 네이버 좌표계 입니다. 

coordinateList 은 공공데이터 좌표계 배열 리스트입니다.

당연히 공공데이터 좌표계를 네이버 좌표계와 비교 계산을 해야합니다.  

여기서 calculateDistance 함수를 사용합니다. 

//두 좌표 사이의 거리 계산 함수
function calculateDistance(coord1, coord2) {
	
	console.log(coord1)
	console.log(coord2)
	
  const radianFactor = Math.PI / 180;
  // 네이버 검색 좌표	
  const lat1 = coord1.latitude * radianFactor;
  const lon1 = coord1.longitude * radianFactor;
  // 공공데이터 좌표
  const lat2 = coord2.lat_areaMarker * radianFactor;
  const lon2 = coord2.lng_areaMarker * radianFactor;
  // 두 좌표의 차이
  const deltaLat = lat2 - lat1;
  const deltaLon = lon2 - lon1;

  const a = Math.sin(deltaLat / 2) ** 2 + Math.cos(lat1) * Math.cos(lat2) * Math.sin(deltaLon / 2) ** 2;
  const c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));

  // 지구 반경 (미터)
  const radius = 6371e3;

  return radius * c;
}

이 코드는 두 개의 좌표 간의 거리를 계산하는 함수인 calculateDistance를 구현한 것입니다. 

두 좌표 (coord1와 coord2)를 입력으로 받습니다. 이때 coord1은 네이버 검색 좌표를, coord2는 공공데이터 좌표를 나타냅니다.

각 좌표의 위도(latitude)와 경도(longitude)를 라디안 단위로 변환합니다. 이 변환은 라디안과 도(degree) 간의 변환을 위해 Math.PI / 180을 곱하는 것으로, 삼각함수 연산을 위해 라디안 단위로 변환합니다.

각 좌표의 위도와 경도를 사용하여 두 좌표 사이의 차이를 계산합니다. deltaLat은 위도의 차이, deltaLon은 경도의 차이를 나타냅니다.

Haversine 공식을 사용하여 두 좌표 사이의 거리를 계산합니다. 이 공식은 구면 표면에서 두 지점 간의 최단 거리를 계산하는 데 사용되며, 구면 지구 모델에서 좌표 간의 거리를 정확하게 계산합니다.

마지막으로, 계산된 거리에 지구의 반지름을 곱하여 결과를 미터 단위로 반환합니다. radius는 지구의 평균 반지름인 약 6371 킬로미터를 미터로 변환한 것입니다.

이 함수는 두 좌표 간의 대략적인 거리를 미터 단위로 계산하며, 이를 통해 두 지점 간의 거리를 추정할 수 있습니다. 주로 지도와 위치 기반 애플리케이션에서 사용되며, 위치 기반 검색 및 라우팅에 활용됩니다.

 

다시 findNearestCoordinate 함수

// 가장 가까운 좌표 찾기
function findNearestCoordinate(targetCoord, coordinateList) {
  let nearestCoord = null;
  let minDistance = Infinity;

  for (const coord of coordinateList) {
    const distance = calculateDistance(targetCoord, coord);
    
	console.log(distance);
	
    if (distance < minDistance) {
      minDistance = distance;
      nearestCoord = coord;
    }
  }

  return nearestCoord;
}

let minDistance = Infinity;: 

이 부분은 가장 작은 거리를 나타내는 변수 minDistance를 초기화하는 부분입니다. 

Infinity는 JavaScript에서 무한대를 나타내는 특별한 값으로, 초기 거리 값을 무한대로 설정함으로써 처음에는 어떠한 거리보다도 큰 값을 가지도록 합니다.

 이렇게 초기화하면 이후에 찾은 거리 값들과 비교할 때 무조건 더 작은 거리 값이 나타날 것입니다.

 따라서 minDistance는 초기에는 가장 큰 값(무한대)을 가지고, 이후에는 실제 거리 값과 비교하여 더 작은 값으로 업데이트됩니다.

findNearestCoordinate 함수는 주어진 coordinateList 배열에서 targetCoord와 가장 가까운 좌표를 찾습니다.

 이를 위해 minDistance 변수를 사용하여 현재까지 찾은 가장 작은 거리를 추적하고, nearestCoord 변수를 사용하여 현재까지 가장 가까운 좌표를 추적합니다. 

함수는 for...of 루프를 사용하여 배열 내의 모든 좌표를 순회하며 각 좌표와 targetCoord 사이의 거리를 calculateDistance 함수를 통해 계산합니다.

 만약 현재 좌표의 거리가 현재까지의 최소 거리(minDistance)보다 작다면, minDistance를 해당 거리로 업데이트하고 nearestCoord를 현재 좌표로 업데이트합니다.

최종 결과: for...of 루프를 모두 순회한 후, nearestCoord에는 targetCoord와 가장 가까운 좌표가 저장되어 반환됩니다.

이렇게 minDistance를 사용하여 가장 작은 값을 추적하면서 최종적으로 가장 가까운 좌표를 찾게 됩니다.

 

최종

보면 네이버 검색 좌표와 공공데이터 좌표는 다릅니다. 

위의 알고리즘을 사용하여 거리가 가장 가까운 좌표를 리턴하여 

결과를 반영합니다.