HYUNJUNGLEE
b9342f6726
S-CANVAS (Saman Corp.) — DXF + DEM + AI 기반 3D 조감도 생성 엔진. ~24k LOC Python (scanvas_maker.py 7072 LOC GUI + 구조물 파서/빌더 다수). 이 커밋은 7-iter cleanup이 적용된 상태로 import: - F821 8 + B023 6: 비동기 lambda + except/loop 변수 캡처 NameError (Py3.13에서 reproduce 확인된 진짜 버그) - RUF012 4 + RUF013 1: ClassVar / implicit Optional 명시화 - F811/B905/B904/F401/F841/W293/F541/UP/SIM/RUF/PLR 700+ cleanup/modernization 신규 파일: - ruff.toml: target=py313, Korean unicode/저자 스타일/도메인 복잡도 무력화 - requirements-py313.txt: pyproj>=3.7, scipy>=1.14, numpy>=2.0.2 (Py3.13 wheel) - .gitignore: gcp-key.json, 캐시, 백업, 생성 이미지 제외 검증: ruff 0 errors, py_compile 0 errors, import 33/33 OK on Py3.13.13. Co-Authored-By: Claude Opus 4.7 (1M context) <noreply@anthropic.com>
226 lines
8.0 KiB
Python
226 lines
8.0 KiB
Python
"""개방선(line-soup) 집합에서 폐합 폴리곤(면)을 복원하는 기하 유틸리티.
|
||
|
||
배경:
|
||
CAD 도면은 구조물 외곽이나 교각을 단일 폐합 폴리라인이 아닌 여러 개의 선분
|
||
(LINE + LWPOLYLINE의 인접 점 쌍 등)으로 그리는 경우가 많다. 이 모듈은
|
||
그런 "개방선 수프(line-soup)"에서 실제로 둘러싸인 영역(face)을 planar 그래프
|
||
face-enumeration 알고리즘으로 복원한다.
|
||
|
||
알고리즘:
|
||
1. 모든 선분 끝점을 공차(tol) 내에서 단일 vertex로 묶음 (그리드 해싱)
|
||
2. 무방향 인접 리스트(vertex → 이웃들) 구성
|
||
3. "Leftmost-turn traversal": 각 방향 간선 (u→v)에서 시작해, 다음 정점에서
|
||
들어온 방향 기준 **왼쪽으로 가장 많이 꺾는** 이웃을 선택, 시작점 복귀
|
||
시까지 반복. → 평면 그래프의 모든 face 순환 열거.
|
||
4. Dedup: 회전·반사로 동일한 face는 canonical form (최소 vertex id를
|
||
시작으로 하는 정방향/역방향 중 사전순 작은 것)으로 중복 제거.
|
||
5. 부호 있는 면적으로 외곽 면(가장 큰 면, 혹은 음의 signed area)은 caller가
|
||
선택해 제거 가능.
|
||
|
||
반환:
|
||
List[(polygon_pts, area_unsigned)], area 내림차순.
|
||
"""
|
||
from __future__ import annotations
|
||
|
||
import math
|
||
from collections.abc import Iterable
|
||
|
||
|
||
Point = tuple[float, float]
|
||
Segment = tuple[Point, Point]
|
||
|
||
|
||
def _grid_key(p: Point, grid: float) -> tuple[int, int]:
|
||
return (math.floor(p[0] / grid), math.floor(p[1] / grid))
|
||
|
||
|
||
class _VertexStore:
|
||
"""공차 내 점을 동일 vertex ID로 묶는 그리드 해시 기반 저장소."""
|
||
|
||
def __init__(self, tol: float):
|
||
self.tol = tol
|
||
self.tol_sq = tol * tol
|
||
self.grid = max(tol * 2.0, 1e-6)
|
||
self._grid: dict[tuple[int, int], list[int]] = {}
|
||
self.points: list[Point] = []
|
||
|
||
def get_or_add(self, p: Point) -> int:
|
||
key = _grid_key(p, self.grid)
|
||
# 주변 3x3 셀 검사
|
||
for dx in (-1, 0, 1):
|
||
for dy in (-1, 0, 1):
|
||
bucket = self._grid.get((key[0] + dx, key[1] + dy))
|
||
if bucket:
|
||
for vid in bucket:
|
||
q = self.points[vid]
|
||
if (q[0] - p[0]) ** 2 + (q[1] - p[1]) ** 2 <= self.tol_sq:
|
||
return vid
|
||
vid = len(self.points)
|
||
self.points.append(p)
|
||
self._grid.setdefault(key, []).append(vid)
|
||
return vid
|
||
|
||
|
||
def _signed_area(pts: list[Point]) -> float:
|
||
a = 0.0
|
||
n = len(pts)
|
||
for i in range(n):
|
||
x1, y1 = pts[i]
|
||
x2, y2 = pts[(i + 1) % n]
|
||
a += x1 * y2 - x2 * y1
|
||
return a * 0.5
|
||
|
||
|
||
def _canonical(face_ids: list[int]) -> tuple:
|
||
"""Face 순환을 rotation/reversal 무관하게 고유 식별하는 canonical tuple."""
|
||
n = len(face_ids)
|
||
if n == 0:
|
||
return ()
|
||
# 각 회전·반사 중 사전순 최소
|
||
best = None
|
||
for direction in (face_ids, list(reversed(face_ids))):
|
||
# 최소 시작 인덱스
|
||
min_id = min(direction)
|
||
start = direction.index(min_id)
|
||
rotated = tuple(direction[start:] + direction[:start])
|
||
if best is None or rotated < best:
|
||
best = rotated
|
||
return best
|
||
|
||
|
||
def reconstruct_polygons(segments: Iterable[Segment],
|
||
tol: float = 5.0,
|
||
min_area: float = 100.0,
|
||
max_faces: int = 5000) -> list[tuple[list[Point], float]]:
|
||
"""개방선 집합에서 폐합 폴리곤(면) 복원.
|
||
|
||
Args:
|
||
segments: [(p1, p2), ...] 각 선분
|
||
tol: 끝점 동일시 공차 (선분 단위와 동일; DXF mm면 mm 단위)
|
||
min_area: 이 값 이하의 면은 버림 (노이즈 억제)
|
||
max_faces: 안전 상한 (무한 루프 방지)
|
||
|
||
Returns:
|
||
[(polygon_pts, unsigned_area), ...] 면적 내림차순. polygon_pts는 닫히지
|
||
않은 형태 (끝점이 시작점과 중복되지 않음).
|
||
"""
|
||
# 1) Vertex 단일화
|
||
vs = _VertexStore(tol)
|
||
edges: set[tuple[int, int]] = set() # 무방향 간선 (u<v)
|
||
for p1, p2 in segments:
|
||
u = vs.get_or_add(p1)
|
||
v = vs.get_or_add(p2)
|
||
if u == v:
|
||
continue
|
||
if u > v:
|
||
u, v = v, u
|
||
edges.add((u, v))
|
||
|
||
if not edges:
|
||
return []
|
||
|
||
# 2) 인접 리스트 (각 vertex → 이웃 정렬 목록)
|
||
adj: dict[int, list[int]] = {}
|
||
for u, v in edges:
|
||
adj.setdefault(u, []).append(v)
|
||
adj.setdefault(v, []).append(u)
|
||
|
||
# 3) Leftmost-turn face enumeration
|
||
def _ang(a_id: int, b_id: int) -> float:
|
||
ax, ay = vs.points[a_id]
|
||
bx, by = vs.points[b_id]
|
||
return math.atan2(by - ay, bx - ax)
|
||
|
||
visited: set[tuple[int, int]] = set() # 방향 간선
|
||
canonical_faces: set[tuple] = set()
|
||
result_faces: list[list[int]] = []
|
||
|
||
# 각 방향 간선 (u→v)에 대해 한 번씩
|
||
for u in adj:
|
||
for v in adj[u]:
|
||
if (u, v) in visited:
|
||
continue
|
||
# 이 방향에서 face 한 개 추적
|
||
face = [u]
|
||
prev, curr = u, v
|
||
steps = 0
|
||
# 평면 그래프에서 face 길이 <= 전체 간선 수 × 2 안쪽
|
||
step_cap = len(edges) * 2 + 10
|
||
aborted = False
|
||
while steps < step_cap:
|
||
visited.add((prev, curr))
|
||
face.append(curr)
|
||
if curr == u:
|
||
break
|
||
# 다음 vertex: curr에서 prev로의 방향 기준 leftmost turn
|
||
# (2π 안쪽 가장 작은 양수 turn_angle 이웃 선택)
|
||
back_angle = _ang(curr, prev)
|
||
candidates = [n for n in adj[curr] if n != prev]
|
||
if not candidates:
|
||
aborted = True
|
||
break
|
||
best_n = None
|
||
best_t = None
|
||
for n in candidates:
|
||
out = _ang(curr, n)
|
||
t = (out - back_angle) % (2.0 * math.pi)
|
||
# 완전 역방향(동일 간선 되돌아가기, t≈0 또는 2π)은 마지막 수단
|
||
if t < 1e-9:
|
||
t = 2.0 * math.pi
|
||
if best_t is None or t < best_t:
|
||
best_t = t
|
||
best_n = n
|
||
prev, curr = curr, best_n
|
||
steps += 1
|
||
if len(result_faces) + len(canonical_faces) > max_faces:
|
||
aborted = True
|
||
break
|
||
if aborted or len(face) < 4:
|
||
continue
|
||
# 마지막 원소는 시작점 중복 → 제거
|
||
face_ids = face[:-1]
|
||
canon = _canonical(face_ids)
|
||
if canon in canonical_faces:
|
||
continue
|
||
canonical_faces.add(canon)
|
||
result_faces.append(face_ids)
|
||
|
||
# 4) 면적 계산 + 필터·정렬
|
||
polys: list[tuple[list[Point], float]] = []
|
||
for face_ids in result_faces:
|
||
pts = [vs.points[v] for v in face_ids]
|
||
area = abs(_signed_area(pts))
|
||
if area < min_area:
|
||
continue
|
||
polys.append((pts, area))
|
||
|
||
polys.sort(key=lambda t: -t[1])
|
||
return polys
|
||
|
||
|
||
def segments_from_lines(lines: Iterable[tuple[Point, Point]]) -> list[Segment]:
|
||
"""편의: LINE 엔티티들을 segment 리스트로 변환."""
|
||
return [(p1, p2) for p1, p2 in lines]
|
||
|
||
|
||
def segments_from_polyline(pts: list[Point]) -> list[Segment]:
|
||
"""LWPOLYLINE 점 목록 → 인접 segment 쌍."""
|
||
from itertools import pairwise
|
||
return list(pairwise(pts))
|
||
|
||
|
||
if __name__ == "__main__":
|
||
# 간단 스모크: 두 개의 겹친 사각형
|
||
segs = [
|
||
# 외곽 10x10
|
||
((0, 0), (10, 0)), ((10, 0), (10, 10)),
|
||
((10, 10), (0, 10)), ((0, 10), (0, 0)),
|
||
# 내부 사각형 2~5 x 2~5
|
||
((2, 2), (5, 2)), ((5, 2), (5, 5)),
|
||
((5, 5), (2, 5)), ((2, 5), (2, 2)),
|
||
]
|
||
polys = reconstruct_polygons(segs, tol=0.01, min_area=0.1)
|
||
print(f"found {len(polys)} polygons")
|
||
for i, (pts, area) in enumerate(polys):
|
||
print(f" #{i}: area={area:.2f}, pts={pts}")
|