점 집합과 Delaunay 삼각측량을 고려하여 보로노이 다이어그램을 어떻게 도출합니까?

StackOverflow https://stackoverflow.com/questions/85275

문제

저는 지역(위험 또는 외교)의 무작위 지도를 만드는 게임을 작업 중입니다.해당 지도를 만들기 위해 먼저 일련의 반무작위 지점을 생성한 다음 해당 지점의 Delaunay 삼각측량을 계산합니다.

그 작업이 완료되면 이제 지방 경계의 시작점 역할을 할 지점의 보로노이 다이어그램을 만들려고 합니다.이 시점에서 내 데이터(말장난 의도 없음)는 원래 일련의 점과 Delaunay 삼각형 모음으로 구성됩니다.

웹에서 이를 수행하는 여러 가지 방법을 보았지만 대부분은 Delaunay가 파생된 방법과 묶여 있습니다.Delaunay에 통합할 필요는 없지만 데이터만으로 작동할 수 있는 것을 찾고 싶습니다.실패하면 최적의 속도가 아닌 상대 기하학 초보자가 이해할 수 있는 것을 찾고 있습니다.감사해요!

도움이 되었습니까?

해결책

보로노이 다이어그램은 들로네 삼각분할의 이중 그래프일 뿐입니다.

  • 따라서 보로노이 다이어그램의 가장자리는 Delaunay 삼각분할 가장자리의 수직 이등분선을 따르므로 해당 선을 계산합니다.
  • 그런 다음 인접한 모서리의 교차점을 찾아 보로노이 다이어그램의 꼭지점을 계산합니다.
  • 마지막으로 가장자리는 해당 정점 사이에 있는 계산된 선의 하위 집합입니다.

정확한 코드는 두 다이어그램에 사용하는 내부 표현에 따라 달라집니다.

다른 팁

최적의 속도를 고려하지 않는 경우 다음 의사 코드는 보로노이 다이어그램을 어려운 방법으로 생성합니다.

for yloop = 0 to height-1
  for xloop = 0 to width-1

    // Generate maximal value
    closest_distance = width * height

    for point = 0 to number_of_points-1
      // calls function to calc distance
      point_distance = distance(point, xloop, yloop)

      if point_distance < closest_distance
        closest_point = point
      end if
    next

  // place result in array of point types
  points[xloop, yloop] = point

  next
next

'포인트' 클래스나 구조가 있다고 가정하고 여기에 임의의 색상을 할당하면 출력을 표시할 때 익숙한 보로노이 패턴을 볼 수 있습니다.

이 스레드를 내 자신의 유사한 질문에 대한 답변의 소스로 사용하려고 시도한 후 Fortune의 알고리즘이 가장 인기 있고 가장 많이 문서화되어 있기 때문에 가장 이해하기 쉽다는 것을 알았습니다.

Fortune의 알고리즘에 관한 Wikipedia 기사 C, C# 및 Javascript의 소스 코드에 대한 새로운 링크를 유지합니다.그들 모두는 최고 수준이었고 아름다운 예를 가지고 있었습니다.

나는 '삼각형'이 확실하다 http://www.cs.cmu.edu/~quake/triangle.html 보로노이를 생성할 수 있다

각 Delaunay 삼각형에는 Voronoi 다이어그램의 단일 점이 포함되어 있습니다.

세 가지의 교차점을 찾아 이 점을 계산할 수 있습니다. 수직 이등분선 각 삼각형마다.

보로노이 다이어그램은 이 점 집합을 각각 가장 가까운 세 개의 이웃과 연결합니다.(각 이웃은 Delaunay 삼각형의 측면을 공유합니다)

엣지 케이스에 어떻게 접근할 계획인가요?

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top