Fortune 알고리즘의 중단점 수렴

Question

저는 Voronoi 다이어그램을 계산하기 위해 Fortune의 스윕라인 알고리즘을 구현하고 있습니다.나의 주요 참고자료는 "계산 기하학:알고리즘 및 응용 프로그램"(de Berg et al.), 주제에 대한 내용은 매우 명확하지만 제가 스스로 해결하는 데 어려움을 겪었던 몇 가지 작지만 중요한 세부 사항을 전달합니다.나는 도움을 얻기 위해 웹을 검색했지만 다른 웹사이트는 교과서보다 더 높은 수준의 개요를 제공하거나 책에서 제공하는 것과 똑같은 유사 코드를 제공합니다.

다가오는 원 이벤트를 감지하려면 해변 선의 세 개의 호에 의해 결정된 한 쌍의 중단점이 수렴 또는 발산하는지 확인하는 방법이 필요합니다.결정을 내리려면 Fortune의 알고리즘이 진행됨에 따라 중단점이 추적되는 Voronoi 셀 가장자리의 모양에 대한 지식이 필요한 것 같습니다.예를 들어 중단점에 의해 추적된 가장자리의 기울기를 찾을 수 있다면 중단점에 의해 형성된 두 선과 각각의 경사가 교차하는 위치를 계산하고 그 결과에 따라 수렴되는지 여부를 결정할 수 있습니다.그러나 경사면에 대한 정보를 얻는 방법은 전혀 모르고 중단점의 현재 위치만 알 수 있습니다.

제가 작업해야 하는 유일한 정보는 세 사이트의 x,y 위치와 스윕라인의 현재 y 좌표입니다(저는 수평 스윕라인을 사용하고 있습니다).

사실, 나에게는 수렴을 결정하는 한 가지 아이디어가 있습니다.두 개의 사이트가 주어지면 그들이 정의하는 해변선의 두 섹션 사이의 중단점은 스윕 라인의 현재 위치에 의해서만 제어됩니다.두 중단점의 위치를 ​​기록하고, 일시적으로 스윕 라인을 약간 전진시키고, 새로운 위치를 기록하는 방법을 생각했습니다.일반적인 보로노이 다이어그램의 모서리는 곡선이 아니기 때문에 새 중단점 쌍 사이의 거리가 이전 쌍 사이의 거리보다 작으면 중단점이 수렴됩니다.그렇지 않으면 갈라집니다.그러나 이것은 위험하고(항상 작동하는지 잘 모르겠습니다) 추악해 보입니다.분명히 더 나은 방법이 있을 것입니다.

어떤 아이디어라도 높이 평가될 것이며 의사 코드(가능한 경우 C#과 유사한 구문)는 특히 그렇습니다.또한 보로노이 다이어그램을 얻는 데 사용할 수 있는 계산 기하학 라이브러리가 있다는 것을 알고 있지만 이것은 개인적인 학습 연습이므로 알고리즘의 모든 부분을 직접 구현하고 싶습니다.

Answer 1

드레이크를 환영합니다.저는 중단점이 스윕라인 위치의 '가상' 증분으로 원 중심에 물리적으로 수렴하는지 확인하여 이를 구현했습니다.어떤 경우에는 원 중심이 거의 또는 정확하게 스윕라인 위치에 있을 수 있기 때문에 이는 실제로 약간 복잡합니다. 따라서 스윕라인 증분은 현재 스윕라인 위치와 권장하는 대로 생성된 원 중심 간의 차이에 비례해야 합니다.

말하다:

1. currentSweeplineY = 1.0f; circleCenterY = 0.5f (그리고 우리는 아래쪽으로 이동하고 있습니다.감소하는 y 방향으로).

2. Set sweepYIncrement = (circleCenterY - currentSweepLineY) / 10.0f (10.0f 제수는 임의로 선택됩니다.)

3. Check new breakpoint positions at new sweepline position.

4. Check distance to circle center.

5. If both distances are less than current distances, the breakpoints converge.

중단점 위치를 여러 번 계산해야 하기 때문에 비용이 매우 많이 든다는 것을 알고 있지만 가능한 모든 경우를 처리한다고 확신합니다.

어쨌든 알고리즘의 다른 곳에서 부동 소수점 정밀도 오류와 관련된 심각한 문제를 발견했습니다.처음에 생각했던 것만큼 간단하지는 않습니다.

Answer 2

그래서 이것은 다소 당황스럽습니다. 그러나 문제에 대해 잠을 자고 나면 대답은 분명해 보입니다.앞으로 저와 같은 질문을 하는 학생들에게 도움이 되었으면 하는 마음으로 이 글을 씁니다.

두 사이트 사이의 보로노이 가장자리는 사이트를 연결하는 (가상) 선분을 수직으로 이등분합니다.연결 선분의 기울기의 수직을 취한 다음 두 모서리에 대한 선 교차 테스트를 수행하여 모서리의 기울기를 도출할 수 있지만 훨씬 더 쉬운 방법이 있습니다.

3개 사이트만 있으면 동일선상에 있지 않음, 이면 사이트 사이의 세그먼트를 수직으로 이등분하는 모서리도 세 사이트를 모두 포함하는 모서리의 원에 접합니다.따라서 세 개의 사이트로 정의된 원의 중심이 가운데 "앞"과 "뒤"는 선택한 좌표계와 스윕라인 정렬에 따라 달라집니다.

내 경우에는 최소 y에서 최대 y로 이동하는 수평 스윕라인이 있으므로 원 중심의 y 좌표가 중간 사이트의 y 좌표보다 크면 중단점이 수렴하고 그렇지 않으면 분기됩니다. .

편집하다:Kristian D'Amato는 위의 알고리즘이 일부 수렴 사례를 놓치고 있음을 정당하게 지적합니다.내가 사용한 최종 알고리즘은 다음과 같습니다.물론, 100% 정확하다고 확신할 수는 없지만, 제가 시도한 모든 경우에 효과가 있는 것 같습니다.

Given left, middle, right sites
    if they are collinear, return false
    center = ComputeCircleCenterDefinedBy3Points(left, middle, right)
    return IsRightOfLine(left, middle, center) && IsRightOfLine(middle, right, center)

IsRightOfLine(start, end, point)
    ((end.X - start.X) * (point.Y - start.Y) - (end.Y - start.Y) * (point.X - start.X)) <= 0

Answer 3

사이트가 원 중심을 중심으로 시계 방향으로 정렬되면 호가 수렴됩니다.원의 중심을 중심으로 시계 반대 방향으로 정렬되면 호가 발산됩니다.(또는 구현에 따라 그 반대).cw 또는 ccw 테스트는 원의 중심을 찾는 데 사용하는 코드에서 제외됩니다.

다음은 점 a,b,c의 외심 d를 계산하기 위한 C# 코드 조각입니다.

        Vector2 ba = b - a;
        Vector2 ca = c - a;     
        float baLength = (ba.x * ba.x) + (ba.y * ba.y);
        float caLength = (ca.x * ca.x) + (ca.y * ca.y); 
        float denominator = 2f * (ba.x * ca.y - ba.y * ca.x);   
        if (denominator <= 0f ) { // Equals 0 for colinear points.  Less than zero if points are ccw and arc is diverging.
            return false;  // Don't use this circle event!
        };
        d.x = a.x + (ca.y * baLength - ba.y * caLength) / denominator ;
        d.y = a.y + (ba.x * caLength - ca.x * baLength) / denominator ;