overlapAreaMap 로직 분석

01역할

overlapAreaMap은 문서의 유효한 leaf 노드 쌍마다 bounding box 교집합 면적을 계산한다.

유휴 여백 지표는 leaf 박스의 합집합 면적만 보기 때문에 겹침을 직접 구별하지 못한다. 노드를 키우면서 다른 노드 위로 포개면 전체 점유율이 좋아진 것처럼 보일 수 있어, 신규 겹침을 별도의 게이트로 검사한다.

이 함수는 한 문서만 입력받는 자립 함수다. 현재 문서와 기준 문서에 동일한 규칙을 각각 적용한 뒤 결과 맵을 비교함으로써 신규 겹침을 판정한다.

02함수 계약

overlapAreaMap(
  doc: Doc,
  tight?: TightBoxMap,
): Map<string, number>

반환값의 key는 두 노드 ID를 사전순으로 정렬해 |로 연결한 문자열이다. 쌍에는 방향이 없으므로 A|B와 B|A를 같은 key로 만든다.

Map {
  'node-a|node-b' => 1250.5,
  'node-c|node-d' => 430,
}

면적은 반올림하지 않은 px² 값이다. computeLayoutMetrics가 최종 합계와 상세 결과를 만들 때 반올림한다.

03주요 상수와 타입

TEXT_CONTAINER_TYPES는 findTextContainer 분석에 정리된 그래픽 타입과 ExtendableShapeItem의 합집합이다.

04좌표와 판정 박스

모든 노드의 기본 절대 박스는 absBoxMap으로 만든다.

buildDocAbsBoxMap(doc, { preferRotated: false });

노드 종류와 tight 제공 여부에 따라 실제 교집합 계산에 사용할 박스가 달라진다.

tight box는 텍스트 프레임 원점 기준 상대좌표이므로 텍스트 절대 박스의 left, top을 더해 문서 절대좌표로 변환한다.

tight absolute left = text absolute left + tight.left
tight absolute top  = text absolute top  + tight.top

judgeBoxOf의 tight 상태별 처리는 다음과 같다.

rendered bounding box에는 오토핏 여백이 포함될 수 있어 실제 glyph가 닿지 않았는데도 겹침을 과대 보고할 수 있다. 정확한 시각적 겹침이 필요하면 tight box를 사용한다.

단, tight box를 사용해도 텍스트의 containerId는 rendered bounding box 기반의 findTextContainer로 찾는다.

051단계: 비교 아이템 구성

함수는 먼저 전체 노드를 순회해 실제 쌍 비교에 참여할 items 배열을 만든다.

{
  id: string;
  box: AbsBox;
  containerId: ContainerId;
  isContainerType: boolean;
}

처음부터 제외하는 노드

텍스트에는 findTextContainer를 호출해 containerId를 기록한다. 비텍스트 노드는 ROOT_CONTAINER를 기록한다.

isContainerType은 해당 노드가 TEXT_CONTAINER_TYPES인지 나타내며, 뒤의 포함 관계 판정에 사용한다.

062단계: 모든 leaf 쌍 비교

아이템이 n개면 i < j인 모든 쌍을 비교한다. 각 쌍은 다음 순서로 처리한다.

6.1 텍스트와 자기 컨테이너 제외

x.containerId !== ROOT_CONTAINER && x.containerId === y.id

도형 위에 텍스트가 놓이는 것은 정상적인 디자인이므로 겹침에서 제외한다. 방향과 무관하게 검사하기 위해 isOwnContainer(a, b)와 isOwnContainer(b, a)를 모두 확인한다.

ROOT_CONTAINER는 실제 부모로 취급하지 않는다. 페이지를 공통 컨테이너로 취급하면 배경 없는 텍스트끼리의 겹침이 모두 빠질 수 있기 때문이다.

컨테이너가 조상 노드라면 그 노드는 자식을 가진 그룹이므로 이미 leaf 필터에서 빠진다. isOwnContainer는 주로 텍스트와 형제 관계로 놓인 배경 도형을 제외하는 데 작동한다.

6.2 사각형 교집합 면적 계산

두 절대 박스의 겹친 폭과 높이를 계산한다.

overlapWidth  = min(a.right, b.right) - max(a.left, b.left)
overlapHeight = min(a.bottom, b.bottom) - max(a.top, b.top)

두 값이 모두 양수일 때만 다음 면적을 반환한다.

overlapArea = overlapWidth × overlapHeight

변만 공유하거나 모서리만 닿으면 면적은 0이다.

6.3 100px² 이하 제외

if (area <= OVERLAP_EPS) continue;

면적이 정확히 100px²인 경우도 제외된다. 이 임계는 부동소수 잡음뿐 아니라 모서리가 스치는 정도의 작은 접촉을 사고로 보지 않기 위한 정책이다.

6.4 포함 관계 제외

작은 요소가 큰 요소 안에 거의 완전히 들어가 있고 큰 요소가 배경 도형 타입이면 “충돌”이 아니라 “얹힌 배치”로 본다.

큰 요소가 TEXT_CONTAINER_TYPES
그리고
교집합 면적 / 작은 요소 면적 >= 0.95

예시는 다음과 같다.

• 카드 위의 칩
• 칩 위의 텍스트
• 패널 안에 거의 완전히 들어간 배지

이 판정은 containerId나 트리 관계를 보지 않는다. 임의의 두 판정 대상 사이에서 순수하게 박스 면적과 큰 노드의 타입만 본다. 그래서 findTextContainer가 자기 컨테이너로 고르지 않은 더 아래쪽 도형도 정상 포함 관계로 제외할 수 있다.

큰 쪽이 컨테이너 타입이어야 하므로 텍스트끼리는 95% 이상 포개져도 제외되지 않는다.

6.5 결과 저장

모든 제외 조건을 통과하면 정규화한 pair key와 교집합 면적을 맵에 저장한다.

out.set(pairKey(a.id, b.id), area);

결과적으로 맵에는 의도된 포함 관계가 아닌, 두 leaf 요소가 100px²를 초과해 부분적으로 포개진 관계가 남는다.

07전체 의사 코드

function overlapAreaMap(doc, tight?):
  abs = absolute boxes of doc
  items = []

  for node in doc.nodes:
    if node is non-leaf or decoration:
      continue
    if node box is missing, non-positive, or page backdrop:
      continue

    hitBox = tight box for text when supplied, otherwise absolute box
    if hitBox is unavailable:
      continue

    items.push({
      id,
      box: hitBox,
      containerId: findTextContainer(...) for text,
      isContainerType,
    })

  result = Map()

  for every unordered pair (a, b) in items:
    if a and b are text-own-container pair:
      continue

    area = intersectArea(a.box, b.box)
    if area <= 100:
      continue

    small, big = order by box area
    if big is container type and area / smallArea >= 0.95:
      continue

    result[pairKey(a.id, b.id)] = area

  return result

08computeLayoutMetrics의 전후 비교

computeLayoutMetrics는 채점 대상과 Expected에 각각 같은 함수를 적용한다.

const overlapNow = overlapAreaMap(doc, tight);
const overlapBase = overlapAreaMap(expected, expectedTight);

현재 문서에 존재하는 각 쌍에 대해 다음 차이를 계산한다.

delta = currentArea - expectedArea

delta > OVERLAP_EPS, 즉 100px²를 초과해 늘어난 경우 신규 겹침 지표에 포함한다.

newOverlapPairs += 1
newOverlapArea += delta

여기에는 두 종류가 모두 포함된다.

• Expected에 없던 쌍이 새로 생김: expectedArea = 0
• Expected에도 있던 쌍이 100px²를 초과해 더 많이 겹침

newOverlapPairs는 연속적인 품질 점수가 아니라 반드시 0이어야 하는 게이트다.

09재배치 method 1·2의 실행 중 게이트

method 1과 method 2도 overlapAreaMap을 사용하지만 최종 지표와 기준이 다르다.

기준 문서

• 최종 지표: Expected
• 실행 중 게이트: 재배치 입력 문서

판정 조건

실행 중 게이트는 면적 증가가 아니라 pair key의 신규 생성만 본다.

const baseline = overlapAreaMap(input);
const born = [...overlapAreaMap(trial).keys()].some(
  key => !baseline.has(key),
);

따라서 입력부터 존재하던 겹침 쌍의 면적이 커지는 것은 되돌림 사유가 아니다. 컨테이너를 확장하면 카드 위에 걸친 배지 같은 기존의 의도된 겹침이 필연적으로 커질 수 있어, 그것까지 막으면 컨테이너를 확장할 수 없기 때문이다.

10경계 조건과 알려진 한계

시간 복잡도

판정 아이템이 n개이면 모든 비순서 쌍을 비교하므로 시간 복잡도는 O(n²)다. 결과 맵의 공간 복잡도는 실제로 남은 겹침 쌍 수를 k라고 할 때 O(k)다.

isNested는 의미 관계를 확인하지 않는다

95% 포함 규칙은 트리, z-order, 실제 역할을 보지 않는 기하 휴리스틱이다. 따라서 우연히 큰 도형 안에 거의 완전히 들어간 실제 충돌도 정상적인 얹힘으로 제외할 수 있다. 코드에도 이 규칙을 일반적으로 사용할 수 있는지 확인이 필요하다는 TODO가 남아 있다.

동일 면적 쌍의 순서 의존성

두 박스 면적이 정확히 같으면 <= 비교에 따라 첫 번째 아이템을 small, 두 번째를 big으로 정한다. 둘 중 하나만 컨테이너 타입이라면 doc.nodes 순서가 isNested 결과에 영향을 줄 수 있다.

tight 누락 시 부분 결과가 된다

tight를 전달했는데 특정 텍스트의 결과가 없거나 실패하면 해당 텍스트는 모든 쌍 비교에서 빠진다. computeLayoutMetrics는 tightMissing으로 누락 수를 노출하지만 overlapAreaMap 단독 반환값에는 결과가 부분적이라는 표시가 없다.

rendered bounding box는 겹침을 과대 보고한다

tight를 제공하지 않으면 텍스트 프레임의 오토핏 여백까지 포함한다. 알고리즘 간 동일 조건 비교에는 쓸 수 있지만, 눈에 보이는 glyph 충돌과 정확히 일치해야 한다면 tight box를 구워서 전달해야 한다.

전용 단위 테스트가 없다

현재 method 1·2 테스트는 재배치 결과에서 입력에 없던 pair key가 생기지 않았는지를 검사한다. 하지만 다음 규칙을 각각 고립해 검증하는 overlapAreaMap 전용 단위 테스트는 없다.

• 장식 타입 제외
• 자기 컨테이너 제외
• 100px² 경계
• 95% 포함 경계
• tight 상태별 처리
• 동일 면적 쌍의 순서

정책 상수나 필터 순서를 변경한다면 위 경계 조건을 직접 고정하는 테스트를 추가하는 편이 안전하다.