Jump to content
  • Advertisement
Sign in to follow this  
lawnjelly

For Loop Max Bug

This topic is 703 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

This particular 'off by one error' is something I've previously created bugs with, and I'm trying to think of an elegant way to solve it:

 

I have a bounding rectangle class, something like this (but not this exactly, this is just an example):

class MyRect
{
public:
void ExpandToIncludePoint(int x, int y)
{
if (x < left) left = x;
if (x > right) right = x;
if (y < top) top = y;
if (y > bottom) bottom = y;
}

int left, right, top, bottom;
}; 

Typically I'll be adding a load of points, and expanding the volume to contain them.

 

Then on iterating through the rectangle, I'll use a loop something like:

for (int x=left; x<right; x++)
{
....
}

Now, the potential problem is, upon adding a point with, e.g. x=10, right is set to 10.

 

But on iterating through, you never get to that point, because the iteration stops at 9 (as we are using a < expression in the for loop). So we could use a <= expression to get the for loop working. But typically we might have expressions to get the width of the rect, which would be right - left.

 

So we have to standardize somehow that the max edge of our rect is either the max INCLUSIVE, or EXCLUSIVE. I've so far standardized on exclusive, as it fits with all the rest of my code.

 

However, this means, that when adding points to the volume, I either have to ADD ONE to the maxes when adding points, or add one to the maxes AFTER adding all the points. Adding one to the maxes during the add is a needless extra computation (when you are dealing with thousands of points). But it is possible to FORGET to add one to the maxes after adding the points, leading to subtle bugs, which should be something I am detecting at compile time, rather than relying on remembering to deal with.

 

So I suspect I'm being a retard and there is probably some really obvious way of solving this conundrum, that I am missing. :D Is it standardization, or is there some way of enforcing the 'ADD ONE' after adding the points (perhaps an extra check in a debug build, or an accessor for range max with a plus one?)?

Edited by lawnjelly

Share this post


Link to post
Share on other sites
Advertisement

It is standardization that you are running into, in particular, lack of a clear meaning of the "left", "right", "top" and "bottom" variables.

 

If "right" is 10, what does that mean? Is x==10 part of the rectangle? You have to define something here.

Secondly, you should document that decision, so you can find it again if you need it, eg in Doxygen style:

int right; ///< Right most edge inside the rectangle.

I know it seems silly to do this when you write new code, I used to think that too. But believe me, your future you will be very happy and work faster if you can just read what a variable means, instead of having to deduce it from the code, in particular when some code says something else than other code. The biggest problem is that "future you" is 6 months or longer from now, so it seems not useful to do this for the first year or so.

 

Note that this makes having an empty rectangle somewhat fuzzy. You cannot give "right" a value that is inside an empty rectangle. If you do need empty rectangle, also define how to represent that in the variables (eg left > right). Don't forget to document it too.

 

With this definition, your "add point" code is correct. If I add (10, 10) as point, right becomes 10, ie the added point is inside the rectangle. Your "for (int x=left; x<right; x++)" is wrong, since x stops one before the end of the rectangle (as you already found). The solution here is thus to fix the for-loop to "for (int x=left; x<=right; x++)". There is the small issue that "right" must be less than max int, If you want to handle that, you need something else than a simple for-loop.

 

One alternative is to define

int right; ///< First X position outside the rectangle

This solves the "give right a value for an empty rectangle" nicely. Your "if (x > right) right = x;" code is however wrong now, as point (10, 10) makes right 10, which means the added point is not in the rectangle. Your test and assignment needs to change then. On the other hand, your "for" loop is correct now, x never gets the "right" value.

 

 

Do you see how the meaning of the variable drives correctness of the code?

 

 

Last but not least, you can also define a rectangle as

int x; ///< X position of the first column in the rectangle.
int y; ///< Y position of the first row in the rectangle.
int width; ///< Number of columns in the rectangle.
int height; ///< Number of rows in the rectangle.

This also can represent empty rectangles nicely.

 

 

I always use the relation width = (right - left) + 1 (left, right inclusive, so if left == right, there is 1 column in the rectangle), but ymmv. Define what each variable means, and fix your code according to that definition.

Edited by Alberth

Share this post


Link to post
Share on other sites

Upon googling, it seems this is a very common problem with incompatibilities between libraries having different standards for Rects and other structs. :blink:

 

Agree about commenting a clear standard into the header.

 

I can see why you went with inclusive, but I think in this case I will stick with exclusive as I have too much existing code that use my bounding volume classes. I suppose the problem is caused by the 'AddPoint' being an optimization (you know what they say about premature optimization being the root of all evil lol...) .. it is fast but it does break the consistency of the rect, and is not a 'self contained' routine. :ph34r:

 

So a possible semi-solution is to change it to have 2 add point routines, a standard one that maintains the exclusive consistency, and an explicit optimized version to remind me to add one to the maxes afterwards. Or an optimized routine 'AddPoints' that adds a bunch of points, then does the plus one as part of the routine, maintaining the consistency of the rect to the client code.

Share this post


Link to post
Share on other sites

So a possible semi-solution is to change it to have 2 add point routines, a standard one that maintains the exclusive consistency, and an explicit optimized version to remind me to add one to the maxes afterwards. Or an optimized routine 'AddPoints' that adds a bunch of points, then does the plus one as part of the routine, maintaining the consistency of the rect to the client code
I would definitely go for the second option, remembering to do things in a certain order is going to goof up somewhen in the future.

Share this post


Link to post
Share on other sites
Generally speaking I like semi-open ranges (where the end value is excluded), and the C++ standard library follows this convention. But whenever you can sidestep it entirely (eg. using "width" instead of "right"), do that. :)

Share this post


Link to post
Share on other sites

(1) The C and C++ language use half-open ranges (see an introductory college-level course on arithmetic for the theoretical background).  A half-open range, [s, t), includes its leftmost (usually smallest) value and everything up to but not including its rightmost (usually largest) value.  The for control structure in the C language is built on a half-open range, and the C++ standard library generally operates on half-open ranges.  You should too.

 

(2) A rectangle has { width, height } as properties, pretty much by definition.  Some implementations implement rectangles, especially bounding boxes, as things in a space so they would also have a { position } property.  A rule of thumb in programming is that you should never store a derived value since it can get out of synch with the properties it's derived from, so your AABB should have { position, width, height } as properties and use those properties to calculate things like the right, left, top, and bottom extents as needed.  For example for (x = this->x; x < (this->x + this->w); ++x) { ... ) to iterate over absolute positions of the box width.

 

Applying the above two longstanding and well-reasoned ideas would eliminate any and all ambiguity related to using intervals with your data structures.  Or not, your choice.

Share this post


Link to post
Share on other sites

(2) A rectangle has { width, height } as properties, pretty much by definition.  Some implementations implement rectangles, especially bounding boxes, as things in a space so they would also have a { position } property.  A rule of thumb in programming is that you should never store a derived value since it can get out of synch with the properties it's derived from, so your AABB should have { position, width, height } as properties and use those properties to calculate things like the right, left, top, and bottom extents as needed.  For example for (x = this->x; x < (this->x + this->w); ++x) { ... ) to iterate over absolute positions of the box width.

 

Well, to play devil's advocate, you could equally well argue that the width and height are derived from the min / max extents, it just depends how you look at it. In real world scenarios you may even find it useful to have libraries containing Rect classes stored as left, right, top, bottom AND classes that store as left, top, width, height (I have this, although I rarely use the latter). Or even left, bottom, width, height if you want to do things the ass about face opengl way lol. But certainly it is beneficial to write most stuff for a standard rect, to save writing the same routines twice.

 

In practice which is better must surely depend on the usage patterns, Although storing width / height can be more efficient for example, in moving rects, in many other cases storing min / max extents can be more efficient, many bounding volume tests for example, or the AddPoint routine in my example code, which is why many libraries store them in such a way, e.g.:

 

https://msdn.microsoft.com/en-us/library/windows/desktop/dd162897(v=vs.85).aspx

Edited by lawnjelly

Share this post


Link to post
Share on other sites
I think you can definitely see it both ways - which means, in my opinion, that the tie-breaker is this whole off-by-one issue. Having to write "left + width" everywhere is inconvenient but at least it's unambiguous that the value you get back is not inside the rectangle. :)

Share this post


Link to post
Share on other sites

This is part of the reason I wish C++ had syntactic sugar for implementing properties. A struct could store x, y, width, height, and then have properties for left, right, top, bottom. It would remove all the ambiguity.

 

In the meanwhile I did something different recently on a project where I had various functions that wanted rect arguments of both varieties. Primarily the API I was using wanted a LRTB rect and the code I was working on dealt primarily with XYWH rects, so I just wrote an XYWH struct and added automatic conversions to and from the API rect type. I was expecting it to throw up in a few places but it turned out to work pretty well.

Share this post


Link to post
Share on other sites

However, this means, that when adding points to the volume, I either have to ADD ONE to the maxes when adding points, or add one to the maxes AFTER adding all the points. Adding one to the maxes during the add is a needless extra computation (when you are dealing with thousands of points). But it is possible to FORGET to add one to the maxes after adding the points, leading to subtle bugs, which should be something I am detecting at compile time, rather than relying on remembering to deal with.

 

I'd recommend writing code primarily for readability and correctness, unless it involves a big sacrifice of performance to do so. You can always try to optimize any bottlenecks found by your profiler later on.

 

In that particular case there's a good chance that the compiler will work out that it can move the +1 outside of the loop anyway.

 

It sounds like you might also benefit from some unit tests, so that you can find out about things that get broken at compile time (assuming you run the tests at the end of each successful build).

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!