1
최대로 서로 교차하는 세그먼트 범위가 있습니다. 이 세그먼트를 폴리선으로 병합하고 싶습니다.폴리 라인 범위에 세그먼트 범위를 병합/결합하는 알고리즘이 필요합니다.
여분의 저장소를 사용하지 않고 O(N_segments)에이 작업을 수행하는 알고리즘이 있습니까 (예 : 세그먼트 포인트에 대한 트리 또는 기타 공간 데이터 구조를 작성하지 않고 작업해야 함)?
내가 가지고있는 세그먼트 수는 O (10) 작습니다. 따라서 해쉬 테이블이나 맵 (적색 - 검은 색 트리)과 같은 동적 데이터 구조에 넣는다면 스택에 데이터 구조를 넣지 않고 메모리 할당을 피하기 만하면 끝 부분에서 루프보다 O(N^2) 루프가 더 비쌉니다. . (내가 사용 폴리 라인은 한 점의 수를 충분히 작은으로 할당을 피하는 small_vector 사용하여 현재 나는이 함께 왔어요
구현 :
polylines = []
// 1. Append each segment to a range of polylines, merging when possible:
for each segment in segments:
for each polyline in polylines:
merge_result = merge(segment, polyline)
if (not merge_result) continue
polyline = merge_result
goto done
// either polylines empty or no merge possible
polylines.append(segment)
done:
continue
// 2. Try to merge the polylines among themselves until no more merges are possible
// Pure brute force, quadratic
done = false
while not done:
for p1 in polylines:
for p2 in polylines[p1..end]:
merge_result = merge(p1, p2)
if not merge: continue
p1 = merge_result
polylines.remove(p2)
done = false
goto restart
restart: continue
을하지만 두 번째 루프 명확하게 2 차선이므로, 세그먼트 사이에 세그먼트 시퀀스를 병합/조인/결합하는 더 나은 알고리즘이 있는지 궁금합니다.
왜 데이터 구조가 생성되지 않습니까? 하나 이상의 세그먼트가 O (n) 시간에 끝점을 공유하는지 탐지하기 위해 세그먼트의 끝점 맵을 작성합니다. – MrSmith42
[관련 게시물] (http://stackoverflow.com/questions/1436091/joining-unordered-line-segments?rq=1)은 검색 속도를 높이기 위해 끝점의 해시를 계산할 것을 제안합니다. –
@ MrSmith42 나는 O (10) 세그먼트의 순서를 다루므로, 스택에서 맵을 생성하지 않으면 동적 맵 생성 비용이 최종 O (N^2) 루프 비용을 초과 할 가능성이 있습니다. 이것이 내가 여분의 데이터 구조없이 더 나은 알고리즘에 관심이 있었던 이유이다. 나는 그것을 스택에 맵으로 시험해보고 그것을 벤치 마크 할 것이다. 제안 해 주셔서 감사합니다. – gnzlbg