Follow

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use
Contact

Off-by-one Error when partitioning rectangle

I am trying to split a Rectangle into same-sized buckets, if there is not enough space at the border, the bucket is resized.

To determine the amount of Buckets, I use

int partitionsX = Math.Max((textureWidth / PartitionSize),1);
int partitionsY = Math.Max((textureHeight / PartitionSize), 1);
SampleBucket[] buckets = new SampleBucket[(partitionsX * partitionsY)];
for(int x=0; x < partitionsX; ++x)
{
    for(int y = 0;y < partitionsY; ++y)
    {
        int idx = x + (y * partitionsX);
        var bucketX = x * PartitionSize;
        var bucketY = y * PartitionSize;
        var bucketWidth = PartitionSize;
        var bucketHeight = PartitionSize;
        bucketWidth = Math.Min(bucketX + bucketWidth, (int)textureWidth) - bucketX;
        bucketHeight = Math.Min(bucketY + bucketHeight, (int)textureHeight) - bucketY;
        Debug.Assert(bucketWidth > 0);
        Debug.Assert(bucketHeight > 0);
        buckets[idx] = new SampleBucket()
        {
            X = bucketX,
            Y = bucketY,
            W = bucketWidth,
            H = bucketHeight,
            SampleLocations = Enumerable.Repeat(new SampleLocation() { Index = NOOP}, bucketWidth * bucketHeight).ToArray()
        };
    }
}

The problem occurs when I try to fill the buckets with my data.

MEDevel.com: Open-source for Healthcare and Education

Collecting and validating open-source software for healthcare, education, enterprise, development, medical imaging, medical records, and digital pathology.

Visit Medevel

foreach(var l in sampleLocations)
{
    int bucketX = (int)(l.PixelX / PartitionSize); // PixelX/PixelY is absolute within the original texture/rectangle
    int bucketY = (int)(l.PixelY / PartitionSize);
    int bucketIdx = bucketX + bucketY * partitionsX;
    Debug.Assert(bucketIdx < buckets.Length);
    var bucket = buckets[bucketIdx]; // OOB occurs here, but I don't know where my mistake is
    var locations = bucket.SampleLocations;
    var sampleX = l.PixelX - bucket.X;
    var sampleY = l.PixelY - bucket.Y;
    var sampleIdx = sampleX + sampleY * bucket.W;
    Debug.Assert(sampleIdx < locations.Length);
    locations[sampleIdx] = l;
}

with textureWidth = 416, textureHeight = 452 and a SampleLocation at PixelX = 51 and PixelY = 448 I receive an Out of Bounds Bucket, when the PartitionSize is 32.
I triple checked the math but for the love of god I can’t find where my mistake is.

Demo with Use case that crashes:
https://dotnetfiddle.net/VKYvpP

>Solution :

The lines where you determine the partitions X and Y is using integer math. This results in less buckets than required when the (would be) decimal part is below 0.5.

To resolve the issue, take the ceiling of size / partitionSize.

int partitionsX = Math.Max((int)Math.Ceiling(textureWidth / (float)PartitionSize),1);
int partitionsY = Math.Max((int)Math.Ceiling(textureHeight / (float)PartitionSize), 1);
Add a comment

Leave a Reply

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use

Discover more from Dev solutions

Subscribe now to keep reading and get access to the full archive.

Continue reading