좌표에서 첫 번째, 두 번째, 세 번째 이웃을 얻는 알고리즘

Question

각 픽셀의 비트 맵에서 비트 맵의 ​​끝까지 이웃의 첫 번째, 두 번째, 세 번째 ... 레벨을 얻으려고합니다. 그러나 내 솔루션 조금 천천히, 그래서 너희들 중 하나가이 작업을 수행 할 수있는 더 좋은 알고리즘 또는 방법이 있으면 알려 :

private IEnumerable<Point> getNeightboorsOfLevel(int level, Point startPos, Point[,] bitMap) 
{ 
    var maxX = bitMap.GetLength(0); 
    var maxY = bitMap.GetLength(1); 
    if (level > Math.Max(maxX, maxY)) yield break; 

    int startXpos = startPos.X - level; 
    int startYpos = startPos.Y - level; 
    int sizeXY = level * 2; 

    var plannedTour = new Rectangle(startXpos, startYpos, sizeXY, sizeXY); 
    var tourBoundaries = new Rectangle(0, 0, maxX, maxY); 

    for(int UpTour = plannedTour.X; UpTour<plannedTour.Width; UpTour++) 
     if (tourBoundaries.Contains(UpTour,plannedTour.Y)) 
      yield return bitMap[UpTour,plannedTour.Y]; 

    for(int RightTour = plannedTour.Y; RightTour<plannedTour.Height;RightTour++) 
     if (tourBoundaries.Contains(plannedTour.Right,RightTour)) 
      yield return bitMap[plannedTour.Right,RightTour]; 

    for(int DownTour = plannedTour.X; DownTour<plannedTour.Width;DownTour++) 
     if (tourBoundaries.Contains(DownTour,plannedTour.Bottom)) 
      yield return bitMap[DownTour,plannedTour.Bottom]; 

    for (int LeftTour = plannedTour.Y; LeftTour < plannedTour.Height; LeftTour++) 
     if (tourBoundaries.Contains(plannedTour.X,LeftTour)) 
      yield return bitMap[plannedTour.X,LeftTour]; 

} 

Answer 1

음,이 너무 느린 경우, 당신은 변경할 수 있습니다 당신의 접근.

예를 들어 비트 맵의 ​​각 색상에 해당 색상의 포인트 목록이있는 Dictionary<Color, List<Point>>을 생성하십시오. 그런 다음 점이 주어지면 색을 얻은 다음 점 목록을 통해 점에 가장 가까운 점을 찾습니다.

이것은 이미지에서 1 회 사전 계산 한 다음 동일한 색상의 포인트 수로 복잡성을 변경합니다. 나는 같은 색으로 점을 찾는 것이 거의 없기 때문에 많은 점을 봐야하기 때문에 현재 천천히 진행되고 있다고 가정하고 있습니다.

Answer 2

속도를 향상시키는 한 가지 방법은 사용자의 plannedTour에 경계를 포함시키는 것입니다. 예를 들면 다음과 같습니다.

var plannedTour = new Rectangle(
    Math.Max(0, startPos.X - level), 
    Math.Max(0, startPos.Y - level), 
    Math.Min(maxX, startPos.X + level), 
    Math.Min(maxY, startPos.Y + level)); 

미리 경계를 계산하고 모든 반복 반복을 검사하지 않아도됩니다. 예를 들어 Left 투어 전체를 저장할 수도 있습니다.

경계를 벗어나는 영역을 검사하지 않으려면 if 문이 필요합니다. 예를 들면 다음과 같습니다.

if (plannedTour.Y >= minY) 
{ 
    // do Up tour. 
} 
if (plannedTour.X <= maxX) 
{ 
    // do Right tour 
} 
if (plannedTour.Y <= maxY) 
{ 
    // do Down tour 
} 
if (plannedTour.X >= minX) 
{ 
    // do Left tour 
} 

미세 조정은 확인중인 4 개의 여분의 픽셀을 제거하는 것입니다. 네가 각 구석을 두 번 확인하는 것처럼 내게 보인다. 왼쪽 및 오른쪽 둘러보기를 시작하여 plannedTour.Y+1에서 시작하고 plannedTour.Bottom-1에서 끝내는 것을 방지 할 수 있습니다.

엄격한 왼쪽에서 오른쪽, 위에서 아래로의 확인을 사용하면 시간이 절약 될 수도 있지만, 아마도 작을 수도 있습니다. 즉, 위쪽 행을 확인한 다음 다음 행에서 왼쪽 및 오른쪽 픽셀을 확인하고 다음 행 등을 확인한 다음 마지막 행을 확인합니다. 이렇게하면 bitMap[x-level, y]과 bitmap[x+level, y]이 같은 캐시 라인에있을 가능성이 높기 때문에 더 나은 캐시 일관성을 제공하지만, bitmap[x-level, y]과 bitmap[x-level, y+1]은 동일한 캐시 라인에 존재할 가능성이 매우 낮습니다. 메모리 액세스를 통해 얻을 수있는 절약 효과는 코딩 복잡성을 가중시킬만한 가치가 없을 수도 있습니다.