본문 바로가기

전체 글154

지도 위의 영역 병합하기 3 - 건물 사이 채우기 1편: 지도 위의 영역 병합하기 1 - SAT와 DP 2편: 지도 위의 영역 병합하기 2 - 모서리 둥글게, 건물 크기 줄이기 위 링크는 앞선 글들이다.기존 방처럼, 지도의 그룹 바운더리를 늘리는 방식을 고집하기에는, 완벽한 건물이 나오지 않는다는 것을 깨달았다.사각형의 동서남북을 gap 만큼 늘리는 방향이 아닌, 필요한 방향만 늘리는 방식은 어떨까? 도형의 변을 gap만큼 밀어서 이웃과 닿으면 그만큼 늘리는 방식이다. 수정하기에는 비교적 쉽지만, 이웃이 없는 부분까지 같이 부풀어 올라서(폭이 넓은 층 아래에 좁은 층이 붙은 경우처럼) 완벽한 건물을 만들기에는 역부족이라고 생각했다. 지금 만들고 있는 Map은 하나의 Map에 수백, 수천개의 건물이 들어서고, 해당 건물들을 병합해야 하는것이 아닌, 많으면.. 2026. 10. 4.
지도 위의 영역 병합하기 2 - 모서리 둥글게, 건물 크기 줄이기 1편: 지도 위의 영역 병합하기 1 - SAT와 DP 앞 글에서 겹쳐 그리기로 테두리를 해결한 뒤에도 손볼 곳이 남아 있었다. 모서리가 각져 있었고, 건물 크기도 마음에 걸렸다.gap은 처음부터 층 사이가 살짝 떨어진 건물을 같은 건물로 묶으려고 넣은 값이었다. 도형을 gap만큼 부풀려서 겹침을 판정하면 떨어진 건물도 하나로 묶였다. 그런데 그 부푼 도형을 그대로 화면에도 그리고 있었다. 1. 모서리 둥글게 하기div 하나하나에 border-radius를 주면, 건물이 여러 조각이라 맞닿은 안쪽 모서리까지 둥글게 깎였다. 그래서 그룹마다 SVG를 하나 만들고, 그 안에 polygon을 두 겹으로 쌓는 방식으로 바꿨다.더보기 ... ... r은 모서리 둥글기, .. 2026. 10. 4.
지도 위의 영역 병합하기 - 경계선 추출(실수) 가장 오래 걸린 문제, 가장 허무했던 결말SAT로 겹치는 사각형끼리 그룹을 묶는 데는 성공했다. 그런데 그 다음 문제가 생각보다 훨씬 오래 발목을 잡았다. "겹쳐진 사각형 여러 개를, 안쪽 이음새 없이 바깥 경계선만 딱 떨어지게 그리려면 어떻게 해야 할까?" 이 글은 그 답을 찾기까지 겪은 시행착오 기록이다. 참고로 이 글에서 소개하는 방식은 나중에 훨씬 단순한 방법으로 대체됐다. (앞 글 참고) 그래도 그 과정에서 배운 게 많아서, 부끄럽지만 기록으로 남긴다. 1. 코드 흐름① 그룹 안의 모든 사각형에 대해, 각 변을 다른 사각형들과 대조한다② 겹쳐서 "가려지는 부분"을 계산하고, 그걸 뺀 "노출된 부분"만 남긴다③ 노출된 부분만 좌표로 변환해서 선분으로 저장한다④ 그 선분들을 SVG로 그린다 fn_g.. 2026. 9. 25.
SAT(분리축 정리)란? 지도 위의 회전된 사각형끼리 겹치는지 판정해야 했다. 회전이 없었다면 X좌표 범위와 Y좌표 범위가 겹치는지만 보면 끝나는 간단한 문제였겠지만, 회전이 섞이면서 이야기가 복잡해졌다. 이때 쓴 게 SAT(Separating Axis Theorem, 분리축 정리)였다.핵심 아이디어두 도형이 겹치지 않는다면, 두 도형을 완전히 분리하는 축(방향)이 반드시 존재한다.말로 풀면 이렇다. "겹치는지 증명"하려고 애쓰는 대신, "안 겹치는 방향이 하나라도 있는지" 찾는 방식이다. 방향을 하나 정해서 그쪽에서 두 도형을 바라봤을 때, 완전히 떨어져 보인다면 그 즉시 "안 겹친다"고 결론 낼 수 있다.가장 쉬운 예 — 회전이 없을 때두 사각형이 회전 없이 놓여 있다고 하자. 이 경우엔 X축 하나만 봐도 충분하다. A의 X.. 2026. 9. 25.