회사 프로젝트를 수행하면서 2천 건의 폴리곤(지리 데이터) 과 100만 건 이상의 Line을 비교해야하는 업무가 생겼다.
비교는 단순히 폴리곤 내에 Line 좌표가 포함되어있는지에 대한 비교였지만 모든 건수에 대해서 검사해야하는 만큼 소요 시간이 큰 작업이었다.
단순 계산 하였을 때 총 20억번의 연산이 필요하다.
처음 생각한 방법은 모든 폴리곤 데이터와 좌표 데이터를 Postgres Database 에 insert 한 후에 postgis 의 ST_CONTAINS 를 활용한 방법이었다.
select ST_Contains(
polygon,
lineString
);위와 같은 방식으로 진행하였을 때 속도는 10분 이상 걸렸다.
목표는 2분이내 연산완료... 단순 계산 해봤을 때, 20억 번의 연산을 2분이내 하는건 무리가 있었다.
그래서 서치한 방법이 jts 라이브러리의 STRtree 다.
STRtree는 내가 이해한 바에 따르면 일종의 tree 인데, 트리를 구성 할 때, 위치 정보를 그룹지어 트리를 만든다.
100개의 폴리곤이 존재한다고 가정해봤을 때, STRtree 에 100개의 폴리곤을 넣는다면, 가장 아래 리프 노드는 내가 넣은 100개의 폴리곤, 그 한 단계 위의 레벨은 지리적으로 가까운 폴리곤들을 합친 노드, 이렇게 재귀적으로 가다 보면 가장 초기 노드는 100개의 폴리곤을 합친 노드다.
더 쉽게 말하자면 부산, 대구, 인천, 서울 이렇게 4개의 폴리곤이 있다고 하자.
최상위 노드에는 4 지역을 합친 폴리곤이 있고,
그 아래 노드에는 인접한 지역인 {부산, 대구} / {인천,서울}
그 아래 노드인 리프 노드에는 {부산} , {대구} , {인천} , {서울} 이 위치한다.
{부산, 대구, 인천, 서울}
|
-----------|-----------
| |
{부산, 대구} {인천,서울}
-----|----- -----|-----
| | | |
{부산} {대구} {인천} {서울}
위 와 같은 트리가 생성되는 구조이다.
이렇게 생성된 트리에서 용산구가 포함된 폴리곤을 찾고 싶다면, 모든 폴리곤을 탐색하지 않아도 서울이라는 결과를 얻을 수 있게된다.
하지만 100프로 정확한 동작은 아닌거 같다. 공식문서를 확인해보면, 폴리곤이 주어졌을 때 폴리곤의 가장 외접점을 기준으로 사각형을 만들고 그 사각형의 겹침 여부를 판단하여 폴리곤 그룹을 만든다. 이렇게 만들어진 사각형은 내가 제공한 폴리곤이 아니기 때문에 STRtree 를 통해서 값을 구한 후 한번 더 검증이 필요하다.
이 방법을 이용해 실제 업무에서 2분안에 원하는 데이터를 얻을 수 있다.
아래는 간단하게 표현한 실제 코드다.
// GeoJson 의 feautres 를 전달하여 tree 생성
STRtree strTree = getStrTree(fetureList)
List<Result> res = dtoList.stream()
.filter(d -> {
// contains 가능성이 있는 featureList 도출
// 쿼리 시 반환 값은 insert 시 정해짐
List<Feature> potentialFeatureList = strTree.query(d.getLineString().getEnvelopeInternal());
return potentialFeatureList.stream()
// feature to polygon 함수
.filter(feautre -> getPolygon(feature).contains(d.getLineString()))
.map(feature - > Result.builder()
.feature(feature)
.dto(d)
.build()
);
}).collect(Collectors.toList());
public STRtree getStrTree(List<Feature> featureList) {
STRtree strTree = new STRtree();
featureList.foreach(f -> {
strTree.insert(getPolygon(f).getEnvelopeInternal(), f);
});
return strTree;
}
- 틀린 표현이나 , 다른 표현이 있다면 언제든 알려주시면 감사하겠습니다.
