[FE] 구면좌표계 도입 여부?!

✅ 구면좌표계란?

• 지구처럼 구형인 표면 위의 위치를 나타내는 좌표계로, 위도(latitude)와 경도(longitude)를 사용한다.
• 일반적인 평면 좌표계와 달리, 두 점을 잇는 최단 경로는 직선이 아니다.

서비스에서 구면좌표계가 필요한 이유?

• 클라이언트에서 서버로 매우 많은 길 + 좌표를 생성 및 연산하여 전송한다.
• 연산 과정에서 거리 + 중점 + 내분점에 대한 계산이 자주 발생한다.

/** 구면 보간 없이 계산한 결과 */
export default function createSubNodes(polyLine: google.maps.Polyline): Coord[] {
	const paths = polyLine.getPath();
	const [startNode, endNode] = paths.getArray().map((el) => LatLngToLiteral(el));

	const length = distance(startNode, endNode);

	const subEdgesCount = Math.ceil(length / EDGE_LENGTH);

	const interval = {
		lat: (endNode.lat - startNode.lat) / subEdgesCount,
		lng: (endNode.lng - startNode.lng) / subEdgesCount,
	};

	const subNodes = [];

	for (let i = 0; i < subEdgesCount; i++) {
		const subNode: Coord = {
			lat: startNode.lat + interval.lat * i,
			lng: startNode.lng + interval.lng * i,
		};
		subNodes.push(subNode);
	}

	subNodes.push(endNode);

	return subNodes;
}

export default function centerCoordinate(point1: Coord, point2: Coord): Coord {
	return {
		lat: (point1.lat + point2.lat) / 2,
		lng: (point1.lng + point2.lng) / 2,
	};
}


/** 하버사인 공식 */
export default function distance(point1: google.maps.LatLngLiteral, point2: google.maps.LatLngLiteral): number {
	const { lat: lat1, lng: lng1 } = point1;
	const { lat: lat2, lng: lng2 } = point2;

	const R = 6371000;
	const toRad = (angle: number) => (angle * Math.PI) / 180;

	const dLat = toRad(lat2 - lat1);
	const dLon = toRad(lng2 - lng1);

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

	return R * c;
}

• 위의 기존 코드 는 중점 계산 + 내분점을 일반 유클리드 좌표계 연산을 통해 적용하고 있다.
• 거리 계산은 하버사인 공식 을 적용하고 있다.

유클리드 좌표계 연산 한계점

• 중점 + 내분점 계산을 구면좌표계가 아닌 일반 유클리드 연산을 적용한 결과, 길 생성 시 매우 삐뚤뺴뚤하게 그려진 것을 확인할 수 있었다.
• 이를 개선하고자 구글 구면 좌표계 를 도입하였다.

적용 이후 문제 상황

1. 구글 좌표계 도입 PR 을 도입하여 길을 생성한 결과, 기존 방식과 유사하게 길이 삐뚤빼뚤하게 생성된 것을 확인할 수 있었다.

2. 백엔드로부터 새로운 길 제보시 중복 포인트 삽입이 발생한다는 것을 인지하였습니다.

• 2~3m의 작은 길을 생성하여 샘플링 시, 중복포인트가 발생한다는 것을 확인하여 원인을 분석한 결과, #98 에서 도입한 구글 geometry 라이브러리에서 interpolate 시 발생하는 문제였습니다.

• @jpark0506 준혁님께서 비슷한 사례 Google Issue Tracker StackOverflow를 찾아주신 덕분에 짧은 거리에 대해 interpolate 시킬 경우, Google SDK에서 계산하는 로직으로는 좌표가 소수점 5번째 이하부터는 동작하지 않는 것을 확인하여 쉽게 해결할 수 있었습니다.

 Zt.interpolate = function(a, b, c) {
        a = _.Se(a);
        b = _.Se(b);
        var d = _.Pe(a)
          , e = _.Qe(a)
          , f = _.Pe(b)
          , g = _.Qe(b)
          , h = Math.cos(d)
          , k = Math.cos(f);
        b = Zt.Js(a, b);
        var l = Math.sin(b);
        if (1E-6 > l)
            return new _.Oe(a.lat(),a.lng());
        a = Math.sin((1 - c) * b) / l;
        c = Math.sin(c * b) / l;
        b = a * h * Math.cos(e) + c * k * Math.cos(g);
        e = a * h * Math.sin(e) + c * k * Math.sin(g);
        return new _.Oe(_.Wd(Math.atan2(a * Math.sin(d) + c * Math.sin(f), Math.sqrt(b * b + e * e))),_.Wd(Math.atan2(e, b)))
    }

• if 문에 의해 매우 짧은 거리일 경우, 첫 번째 좌표를 그대로 반환하는 문제가 존재하였습니다. 구글 문의
• 이로 인해, 짧은 길을 생성할 경우, 중복 포인트가 생성되는 것을 확인하여, 해당 interpolate함수를 분석하여 if문 없이 직접 구현하였습니다.

export function interpolate(point1: Coord, point2: Coord, fraction: number): Coord {
	const lat1 = toRad(point1.lat);
	const lng1 = toRad(point1.lng);

	const lat2 = toRad(point2.lat);
	const lng2 = toRad(point2.lng);

	const angle = Math.acos(Math.sin(lat1) * Math.sin(lat2) + Math.cos(lat1) * Math.cos(lat2) * Math.cos(lng2 - lng1));

	const sinAngle = Math.sin(angle);

	const A = Math.sin((1 - fraction) * angle) / sinAngle;
	const B = Math.sin(fraction * angle) / sinAngle;

	const x = A * Math.cos(lat1) * Math.cos(lng1) + B * Math.cos(lat2) * Math.cos(lng2);
	const y = A * Math.cos(lat1) * Math.sin(lng1) + B * Math.cos(lat2) * Math.sin(lng2);
	const z = A * Math.sin(lat1) + B * Math.sin(lat2);

	const interpolatedLat = Math.atan2(z, Math.sqrt(x * x + y * y));
	const interpolatedLng = Math.atan2(y, x);

	return {
		lat: toDeg(interpolatedLat),
		lng: toDeg(interpolatedLng),
	};
}

• interpolate를 직접 만들어서, google geometry 라이브러리를 import하는 주요 목적이 사라져 해당 라이브러리를 import하지 않기 위해 사용되던 computeLength 함수또한, SDK를 분석하였습니다.

distance 함수 구현

    Yda = function(a, b) {
        const c = _.dk(a);
        a = _.ek(a);
        const d = _.dk(b);
        b = _.ek(b);
        return 2 * Math.asin(Math.sqrt(Math.pow(Math.sin((c - d) / 2), 2) + Math.cos(c) * Math.cos(d) * Math.pow(Math.sin((a - b) / 2), 2)))
    }

• 위 함수를 분석한 결과, 제가 기존에 생성했던 #32 하버사인 공식과 유사한 것을 확인하고 기존의 로직을 수정하여 사용하기로 하였습니다.

import { Coord } from "../../data/types/coord";

/** 하버사인 공식 */
export default function distance(point1: Coord, point2: Coord): number {
	const R = 6378137;
	const { lat: lat_a, lng: lng_a } = point1;
	const { lat: lat_b, lng: lng_b } = point2;

	const rad_lat_a = toRad(lat_a);
	const rad_lng_a = toRad(lng_a);
	const rad_lat_b = toRad(lat_b);
	const rad_lng_b = toRad(lng_b);

	return (
		R *
		2 *
		Math.asin(
			Math.sqrt(
				Math.pow(Math.sin((rad_lat_a - rad_lat_b) / 2), 2) +
					Math.cos(rad_lat_a) * Math.cos(rad_lat_b) * Math.pow(Math.sin((rad_lng_a - rad_lng_b) / 2), 2),
			),
		)
	);
}

const toRad = (angle: number) => (angle * Math.PI) / 180;

• 내분점 + 거리 계산을 모두 구글에서 사용중인 함수로 변경하였습니다. 거리 계산의 경우 제가 적용했었던 하버사인과 동일하지만 지구 반지름 값을 변경하였습니다.
• 필요한 모든 기능을 직접 적용하여 구글 라이브러리 import를 제거했습니다.

• 구글 보정 시, 동일 값이 여러 번 생성된 것을 확인할 수 있고 직접 interpolate 함수를 사용한 결과 같은 경로에 대해서 모두 다른 점들을 생성한 결과를 확인할 수 있습니다.
• 이후 백엔드와 프론트엔드의 거리 계산이 달라서 이를 통일하였습니다.

PR

• 구글 구면좌표계 도입
• 구글 구면좌표계 제거 및 interpolate 함수 및 distance 함수 구현
• 백엔드 하버사인 적용