효율적으로 선분을 루프로 정렬

Question

닫힌 다각형을 나타내는 선분 배열을 생성하는 라이브러리 (JavaScript-Voronoi)를 사용하고 있습니다. 이러한 세그먼트는 정렬되지 않은 순서로 나타나며 세그먼트가 나타나는 순서와 세그먼트의 각 끝에 대한 점의 순서가 모두 표시됩니다.

(편집 : 아래의 코멘트에서 언급 한 바와 같이, 내가 잘못했다 : 라이브러리 에서 세그먼트들이 잘 주문하지만, 질문은 서면으로 약자.의이 세그먼트가없는 것으로 가정하자 어떤 주문, 이것은 더 일반적으로 유용합니다으로) 예를 들어

:.

var p1 = {x:13.6,y:13.1}, p2 = {x:37.2,y:35.8}, p3 = {x:99.9,y:14.6}, 
    p4 = {x:99.9,y:45.5}, p5 = {x:33.7,y:66.7}; 
var segments = [ 
    { va:p1, vb:p2 }, 
    { va:p3, vb:p4 }, 
    { va:p5, vb:p4 }, 
    { va:p3, vb:p2 }, 
    { va:p1, vb:p5 } ]; 

공지 방법 마지막으로 첫 번째 세그먼트 연결합니다 (y는 공통점을 공유 함), 마지막에서 두 번째까지. 모든 세그먼트가 정확히 하나의 다른 세그먼트와 끝을 공유 함을 보장합니다.

내가 적절한 SVG 다각형을 생성하는 지점의 목록에이 변환하고자하는

:

console.log(orderedPoints(segments)); 
// [ 
// {"x":33.7,"y":66.7}, 
// {"x":13.6,"y":13.1}, 
// {"x":37.2,"y":35.8}, 
// {"x":99.9,"y":14.6}, 
// {"x":99.9,"y":45.5} 
// ] 

점은 시계 방향 또는 반 시계 방향으로 순서에 있는지 그것은 중요하지 않습니다.

다음 코드는 제가 생각해 냈습니다. 그러나 최악의 시나리오에서는 n^2+n 포인트 비교가 필요합니다. 이 모든 것을 함께 결합하는보다 효율적인 알고리즘이 있습니까?

function orderedPoints(segs){ 
    segs = segs.concat(); // make a mutable copy 
    var seg = segs.pop(), pts = [seg.va], link = seg.vb; 
    for (var ct=segs.length;ct--;){ 
    for (var i=segs.length;i--;){ 
     if (segs[i].va==link){ 
     seg = segs.splice(i,1)[0]; pts.push(seg.va); link = seg.vb; 
     break; 
     }else if (segs[i].vb==link){ 
     seg = segs.splice(i,1)[0]; pts.push(seg.vb); link = seg.va; 
     break; 
     } 
    } 
    } 
    return pts; 
} 

Answer 1

선형 시간에 (더블, 정렬되지 않은?) 연결리스트로 포인트를 설정 할 수 있어야한다 :

var prev = segments[0].va, 
    start = segments[0].vb, // start somewhere, in some direction 
    points = [], 
    cur = start; 
do { 
    points.push(cur); 
    var nexts = cur.nexts, 
     next = nexts[0] == prev ? nexts[1] : nexts[0]; 
    delete cur.nexts; // un-modify the object 
    prev = cur; 
    cur = next; 
} while (cur && cur != start) 
return points; 

:

for (var i=0; i<segments.length; i++) { 
    var a = segments[i].va, 
     b = segments[i].vb; 
    // nexts being the two adjacent points (in unknown order) 
    if (a.nexts) a.nexts.push(b); else a.nexts = [b]; 
    if (b.nexts) b.nexts.push(a); else b.nexts = [a]; 
} 

는 이제 배열을 구축하기를 반복 할 수

개체를 수정하지 않으려면 EcmaScript6 Map (개체 키 포함)을 사용하면 편리합니다. 이 문제를 해결하기 위해 점 좌표의 JSON 직렬화를 일반 객체의 키로 사용할 수는 있지만 좌표가 두 번 포함되지 않은 다각형으로 제한됩니다. 또는 라이브러리가 식별 할 수있는 꼭지점에 고유 한 voronoiId 속성을 사용하면됩니다.

Answer 2

다각형이 convex 인 경우 중간 선의 중점을 선택한 다음 convex hull 알고리즘을 사용하여 중간 항목으로 볼록한 다각형을 찾을 수 있습니다. 그 다음에는 가운데 정렬이 무엇인지 알 수 있으며 어느 중간인지 알기 때문에 어떤 세그먼트에 속해, 당신은 원래의 배열로 배열을 찾을 수 있습니다.

볼록 선체를 찾고 싶다면 볼록 선체 알고리즘을 직접 사용하십시오. O (n log n)이므로 충분히 빠르지 만 자바 스크립트 here에서 Quickhull 알고리즘을 찾을 수도 있습니다. quickhull도 O(n logn)에 있지만 평균적으로 최악의 경우는 O (n^2)이지만 덜 일정한 요인 때문에 빠릅니다.

세트 최초로 각각의 세그먼트의 일 단부, 및 (임의로) 제 등의 다른 쪽 끝

---

그러나 일반적인 알고리즘의 경우

. x 처음으로

를 정렬 세그먼트와 y 처음으로 같은 첫 x으로 배열 첫 번째 정렬 세그먼트에서 그 후 배열 First에 넣고 시작하고 같은있는 항목의 끝 위치에 저장하려면 구조로 두 개의 추가 int를 넣어 먼저 x.

두 번째 x 값으로 세그먼트를 다시 정렬하고 배열 second을 만듭니다.

위의 작업은 모두 O (n log n)에 있습니다.

지금 관련 부분 배열 (시작이 있고 항목의 끝 위치에서 자신의 y 값을 검색, 경우에 비슷한 값을 찾아 두 배열 First 및 second에서 두 번째 x 값을 검색, 배열 First에서 첫 번째 세그먼트를 선택 동일 x). 이 주문 (현재 세그먼트가 아님)이있는 세그먼트가 하나뿐이므로 다음 세그먼트를 찾는 데 O(log n)이 걸리며 다음 세그먼트가 모두 n-1이어서 O(n^2)보다 훨씬 빠른 O(n logn) (전처리)이 필요합니다.

Answer 3

볼록 다각형의 경우 측면 세그먼트를 알 필요조차 없습니다. 방금 정점이 필요합니다. 꼭짓점을 정렬하는 절차는 매우 간단합니다.

1. 모든 정점을 평균하여 다각형 내부의 한 점을 얻습니다. 이것이 중심 일 필요조차 없다는 것을주의하십시오. 그것은 단지 다각형 안에있는 점일 필요가 있습니다. 각 점 V [i]에 대해
2. 을 호출하고 V [i]에서 V [i] + (1,0)까지의 선분과 V [i] . 이것을 [i]라고 부르십시오.
3. 정점을 위성 데이터로 사용하여 정점 각도를 정렬합니다.

정렬 된 정점은 다각형 주위에 순서대로 있습니다. 제거 할 수있는 중복이 있습니다. 선형 시간에 1 회, 선형 시간에 2 회, n 로그 n에서 3 회 실행됩니다.