벡터 함유 영역 (경계) 변환 래스터 맵 (픽셀 그리드)으로 변환

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

문제

세계지도의 국가와 같이 국경 (윤곽)으로 여러 지역으로 잘라낸지도가 있습니다. 각 지역에는 특정 표면 커스트 클래스가 있습니다 에스 (예 : 물의 경우 0, 잔디의 경우 0.03). 경계는 다음과 같이 정의됩니다.

  • 어떤 가치 에스 그것의 양쪽에 있습니다 (한쪽에는 0.03, 다른쪽에 0.0, 아래 예제에서)
  • 국경이 얼마나 많은 포인트로 만들어 졌습니까?N= 7 아래의 예에서 7) 및
  • N 좌표 쌍 (엑스, 와이).

이것은 하나의 예입니다. 

0.0300      0.0000           7
2660607.5   6332685.5   2660565.0   6332690.5   2660541.5   6332794.5 
2660621.7   6332860.5   2660673.8   6332770.5   2660669.0   6332709.5 
2660607.5   6332685.5

각 픽셀이 에스 픽셀의 중심이 떨어지는 영역에 해당합니다.

경계는 나타납니다 단계 변경 에스. 다양한 값 에스 개별 클래스 (예 : 잔디 나 물)를 나타내며 평균화 할 수있는 값이 아닙니다 (예 : 젖은 잔디 없음).

또한 모든 테두리가 위의 예와 같이 폐쇄 루프 인 것은 아닙니다. 이것은 국가 경계와 비슷합니다. 예를 들어 미국-캐나다 국경은 폐쇄 루프가 아니라 캐나다-해양과 미국-해양 "국경"이라는 두 개의 다른 국경과 함께 각 끝에 결합되는 선입니다. (폐 루프 경계 존재합니다 그럼에도 불구하고!)

누구 든지이 작업을 수행 할 수있는 알고리즘을 지적 할 수 있습니까? 나는 바퀴를 재창조하고 싶지 않다!

도움이 되었습니까?

해결책 5

내가 이것을 해결 한 방식은 다음과 같습니다.

  1. 각 세그먼트를 따라 행진; 정기적으로 중지하십시오 엘.
  2. 각 정거장에서 트레이서 지점을 즉시 왼쪽으로 그리고 세그먼트의 오른쪽에 놓습니다 (특정 작은 거리에서 디 세그먼트에서). 트레이서 포인트는 각각 왼쪽 및 오른쪽 S 값에 기인합니다.
  3. 가장 가까운 유명인 보간을하십시오. 래스터 그리드의 각 지점은 가장 가까운 트레이서 포인트의 S에 기인합니다.

이것은 맵의 가장자리에 폐쇄되지 않은 선이있을 때에도 작동합니다.

이것은 "완벽한"분석 알고리즘이 아닙니다. 두 가지 매개 변수가 있습니다. 엘 그리고 디. 알고리즘은 아름답게 작동합니다 디 << 엘. 그렇지 않으면 세그먼트 접합부 근처, 특히 급성 각도가있는 부정확성 (일반적으로 단일 픽셀)을 얻을 수 있습니다.

다른 팁

이러한 종류의 형상을 벡터 형태로 처리하는 일반적인 경우는 매우 어려울 수 있습니다. 특히 설명하는 구조에 대해서는 구조가 일관성이 필요하지 않기 때문입니다. 그러나 단지 래스터 화하려면 문제를 라인 세그먼트의 보로 노이 다이어그램으로 취급하는 것이 더 강력 할 수 있습니다.

Voronoi 다이어그램을 근사화하면 각 선 세그먼트를 텐트 모양을 만드는 한 쌍의 쿼드로 그리는 각 라인 세그먼트를 OpenGL에서 그래픽으로 수행 할 수 있습니다. Z- 버퍼는 가장 가까운 쿼드를 우선 순위로 삼는 데 사용되므로 가장 가까운 선을 기반으로 픽셀을 색칠합니다. 여기서 차이점은 선의 어떤면을 나타내는지를 기반으로 다각형을 색칠하고자하는 선이 대신 대신에 다각형을 채색하고 싶다는 것입니다. 비슷한 알고리즘을 논의하는 좋은 논문은 Hoff et al 's입니다. 그래픽 하드웨어를 사용하여 일반화 된 보로 노이 다이어그램의 빠른 계산

3D 지오메트리는 3 개의 빨간색/옐로우 세그먼트와 1 개의 파란색/녹색 세그먼트 로이 스케치와 같은 것으로 보입니다.

sketch of 3d geometry

이 절차는 폐쇄 루프로 아무것도 변환 할 필요가 없으며 멋진 형상 라이브러리가 필요하지 않습니다. 모든 것은 Z- 버퍼에 의해 처리되며 최신 그래픽 카드에서 실시간으로 실행할 수있을 정도로 빠르야합니다. 정제는 균질 한 좌표를 사용하여 기초 프로젝트를 무한대로 만드는 것입니다.

이 알고리즘을 파이썬 스크립트에서 구현했습니다 http://www.pasteall.org/9062/python. 흥미로운 경고 중 하나는 원뿔을 사용하여 선의 끝을 막는 것이 원뿔의 모양을 왜곡하지 않고 작동하지 않았다는 것입니다. 왜냐하면 세그먼트의 끝점을 나타내는 원뿔은 z- 싸움이기 때문입니다. 제공 한 샘플 형상의 경우 출력이 다음과 같습니다.

voronoi rendering output

다음과 같은 지오메트리 알고리즘 라이브러리를 사용하는 것이 좋습니다. cgal. 특히 두 번째 예 참조 설명서의 "2D 다각형"페이지에서 필요한 것을 제공해야합니다. 각 "테두리"를 다각형으로 정의하고 특정 지점이 다각형 내부에 있는지 확인할 수 있습니다. 기본적으로 그것은 같은 것입니다

for every y in raster grid
  for every x in raster grid
    for each defined polygon p
      if point(x,y) is inside polygon p
        pixel[X][Y] = inside_color[p]

외부 지역이 겹치기 때문에 외부 _color로 무엇을 해야할지 잘 모르겠습니다. 어쨌든, 당신의 예를 살펴보면, 모든 외부 지역은 물이 될 수 있으므로 결승전을 할 수 있습니다.

    if pixel[X][Y] still undefined then pixel[X][Y] = water_value

(또는 대안으로 다각형 목록을 반복하기 전에 픽셀 [x] [y]를 Water_value로 설정합니다)

  • 먼저, 모든 경계를 닫힌 루프 (아마도지도의 가장자리 포함)로 변환하고 내부 색상을 물리 치십시오. 이것은 가능해야합니다. 그렇지 않으면 데이터에 불일치가 있습니다.
  • Bresenham의 알고리즘을 사용하여 단일 사용되지 않은 색상으로지도의 모든 테두리 선을 그립니다.
    • 이 작업을 수행하는 모든 "테두리 픽셀"목록을 저장하십시오.
  • 그런 다음 각 국경에 대해
    • Triangulate It (Delaunay)
    • 중앙이 국경 안에있는 사람을 찾을 때까지 삼각형을 반복하십시오 (Point-in-Polygon 테스트)
    • 국경의 내부 색상에서 그 시점에서지도를 홍수 채우십시오.
  • 모든 내부 지역을 채우면 테두리 픽셀 목록을 반복하여 각 색상이 어떤 색이어야하는지 확인하십시오.
  • 마커 "빈"및 "테두리"로 사용되지 않은 두 가지 색상을 선택하십시오.
  • "빈"색상으로 모든 영역을 채우십시오
  • "테두리"색상으로 모든 지역 경계를 그립니다
  • "빈"색상으로 첫 번째를 찾기 위해 포인트를 반복
  • 그것이 속한 지역을 결정하십시오 (Google "Point Inside Polygon"은 Martin Demello가 제안한대로 국경을 닫아야 할 것입니다).
  • 이 시점부터 지역의 색상으로 홍수 요금 알고리즘을 수행하십시오.
  • 다음 "빈"포인트로 이동 (검색을 다시 시작할 필요 없음 - 계속 계속)
  • 그래서 "빈"포인트가 남아있을 때까지
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top