Maybe a problem with Rect intersections

[Tank]

Heya,

as I'm currently in war with sf::Rect, here's another thing that came up into my mind when using Rect intersections:

Code: [Select]


sf::Rect  a( 0, 0, 1, 1 );
sf::Rect  b( 1, 1, 2, 2 );
std::cout << a.Intersects( b ) << std::endl;


Matter of price: What do you expect gets printed? Two possibilities here:

1. Rects do NOT intersect because b is next to a.
2. Rects DO intersect because b shares the upper left point with the lower right point of a.

If a and b of the example above intersected by definition, it'd mean that there's an intersection rect = (1, 1, 1, 1). If NOT, then I think it should be impossible to have rects with a size of 1 either in width or height -- which would be bad in my opinion.

The current implementation of Intersects() uses method 1, which can lead to serious problem. Imagine this case:

Code: [Select]


sf::Rect  a( 1, 1, 1, 1 );
sf::Rect  b( 1, 1, 1, 1 );
std::cout << a.Intersects( b ) << std::endl;


a and b are still valid rects (with width and height of 1; at least that should be the case. SFML currently calculates wrong sizes, but a bugfix is already in the pipeline as stated by Laurent in another thread) and should therefore (or better: must!) intersect because they're at the exact same position.

So my proposal is to use method 2 for intersection checks.

Edit: Regarding to a fix: I think replacing

Code: [Select]


    return (overlapping.Left < overlapping.Right) && (overlapping.Top < overlapping.Bottom);


in sf::Rect<T>::Intersects() by

Code: [Select]


    return (overlapping.Left <= overlapping.Right) && (overlapping.Top <= overlapping.Bottom);


would fix it.

Thus a new problem appears in the Intersects() method accepting an additional parameter for actually getting the intersection rect:

Code: [Select]


        intersection = Rect<T>(0, 0, 0, 0);
        return false;


Intersects() returns false indicating that no intersection happened. But (0, 0, 0, 0) is wrong in this case, as it would define an intersection rect at (0, 0) with a width and height of 1.

[Laurent]

Maybe I should just rewrite sf::Rect from scratch :lol:

[Tank]

Nah, just fix it here and there.

[Nexus]

Hey, another question: Why is Intersects() a member function? I see absolutely no reason not to make it global. Concerning GetWidth() and GetHeight(), I can understand some people find it more intuitive to write Rect.GetWidth(), also because some other classes like sf::Window are handled the same way. Offset() and Contains() - hmm, controversial point. At least they needn't be members.

But Intersects()? As this function is symmetric regarding its arguments, what's wrong with a global function?

I find

Code: [Select]

Intersect(a, b)cleaner (maybe with a better identifier) than java-like

Code: [Select]

a.Intersects(b)because everytime I see such methods in C++, I think there is probably a difference between a.Intersects(b) and b.Intersects(a).

Generally, global functions can become part of the public interface as well. In many cases, they are the better option since they increase encapsulation (not relevant here, but in other classes it's mostly better to let only a few functions have direct access to private data) and allow genericity (for example as templates, which can be instantiated for multiple types performing the same action). Furthermore, adding member-functions is problematic while working with built-in types or already finished classes.

[Tank]

I like Nexus' approach.

[Laurent]

I like it too.

[Warfield]

What I'm about to say is based off of SFML 1.5, so if things have changed since that version please forgive me, but there seems to be some confusion about how rectangles should be represented by the sf::Rect object. Browsing through the code for the Rect class, I see conflicting uses. Here are the two options:

1) Inclusive Coordinates

The "right" and "bottom" members specify the bottom-right-most pixel that is included in the rectangle. So a Rect(0,0,1,1) would have a width of 2, and a height of 2, including four pixels, with the pixel at (1,1) being the bottom-right.

2) Exclusive Coordinates

The "right" and "bottom" members specify the bottom-right-most pixel that is outside the rectangle. So a Rect(0,0,1,1) would have a width of 1, a height of 1, and include only one pixel, (0,0).


Method 2 is commonly accepted as the standard way of representing a rectangle. Using this method simplifies things such as iterating over the points in a rectangle, or calculating its width or height. For this, all that needs to be done is to subtract the right from the left. If using inclusive coordinates, the width of the rect is (right-left+1), which is considered counter-intuitive. Using exclusive coordinates also makes SFML's intersect code work correctly. For your example, the rect (0,0,1,1) would encompass only one pixel at (0,0). The second rect (1,1,2,2) would also encompass only one pixel, at (1,1). These do not intersect, even though they at first appear to share a pixel. In reality, they do not share any pixels, because the bottom-right pixel of the first rect is not actually inside that rectangle. If the rectangles do not overlap, returning a Rect(0,0,0,0) would be correct with exlusive coordinates, since this rectangle would have a width and height of zero, and thus contain no pixels and be invalid.

In the sf::Rect class, GetWidth(), GetHeight(), and Intersects() all operate as if the rectangle is expressed in exclusive coordinates. However, Contains() appears to operate as if the rectangle is using inclusive coordinates. Instead of this:

Code: [Select]

return (X >= Left) && (X <= Right) && (Y >= Top) && (Y <= Bottom);
I believe it should be this:

Code: [Select]

return (X >= Left) && (X < Right) && (Y >= Top) && (Y < Bottom);

I strongly recommend that SFML continue to use exclusive coordinates, they make life easy. Either way, the class needs to be consistent in the method it uses to do calculations. I am also in favor of having a global Intersects() function, but I would also like to see the class continue to have its own Intersects() method as well.

[Warfield]

The current implementation of Intersects() uses method 1, which can lead to serious problem. Imagine this case:

Code: [Select]


sf::Rect  a( 1, 1, 1, 1 );
sf::Rect  b( 1, 1, 1, 1 );
std::cout << a.Intersects( b ) << std::endl;


a and b are still valid rects (with width and height of 1; at least that should be the case. SFML currently calculates wrong sizes, but a bugfix is already in the pipeline as stated by Laurent in another thread) and should therefore (or better: must!) intersect because they're at the exact same position.

Just for clarity, if using exclusive coordinates, the intersect function should not return true if you pass it these rectangles. These rectangles would have a width and height of zero, and thus be invalid. Since they are invalid, they should not intersect because they have no area.

I also just noticed that the issue I found with Contains() was mentioned in another topic not too long ago, by Tank! So this is a known issue, but I believe the fix mentioned in that thread should be to change Contains(), not GetWidth() or GetHeight().

[Tank]

The fix would be exactly for what you're talking about: inclusive coordinates. Laurent has to decide which method is about to be used in SFML.

Currently both methods are mixed: Width and height are returning the width and height using inclusive coordinates, Intersects() uses exclusive coordinates and Contains() (AFAIR) uses also inclusive coordinates.

I'm fine with both methods, but not both mixed.

[Nexus]

I would prefer exclusive coordinates, too. I think copying the concept from the STL iterator ranges isn't bad. As Warfield stated, exclusive arithmetic makes life a lot easier. Just today, I saw this (not concerning SFML-rects, but in general): I wrote a tokenizer algorithm, and to my surprise, all the offsets and indices were calculated right at the first attempt. I didn't need any +1 or -1, everything was so straightforward, thanks to the STL end() iterators.

Also, I am glad to hear you appreciate a global Intersection() function. But Warfield, why do you want to keep the Intersects() method? For backward compatibility? I think SFML 2 is the opportunity to make progress and redesign some essential parts of the library. We should not make the mistake to allow multiple solutions for every task just to make everybody happy.

[Warfield]

Well, I was on the fence last night, but now that I've thought about it more, I suppose I am of the opinion that all of the functionality of a class should be contained within that class, if possible. Of course ultimately it's up to Laurent how he'd like to structure his API, but I was under the impression that one of the main selling points of SFML was its object-oriented nature. Having a bunch of global functions, even if they're templated, seems like a step backwards from that. I personally don't have any issue with symmetric methods, but a global function could be symmetric as well. Intersect(a, b) vs. Intersect(b, a), for example. When faced with the question of whether these should be equivalent, it should be obvious that they are just by the definition of an intersection. Same with a.Intersects(b) vs. b.Intersects(a).

One thing I don't understand is your comment about how global functions can become part of the public interface. Do you mean a global Intersects() function would be able to be called by saying a.Intersects(b)? I also don't think I understand how having global functions would increase encapsulation vs. member functions. It seems to me like that would violate encapsulation, by requiring those global functions to be able to access the private data of a class to which they don't belong. I agree with your argument about genericity, but I could see a situation where a general function works for 90% of classes, but special cases must be made for the other 10%, and it becomes a big confusing mess of "exceptions" to the "rules".

I guess I should also take this time to say hello to everyone, since these are my first few posts here. Great job on the library, Laurent. I am very excited about the possibilities that I will have by using SFML. You and everyone else who's contributed to this project has done an amazing job so far. Keep up the good work!

[K-Bal]

A static member function would be appropriate

[Laurent]

Of course ultimately it's up to Laurent how he'd like to structure his API, but I was under the impression that one of the main selling points of SFML was its object-oriented nature. Having a bunch of global functions, even if they're templated, seems like a step backwards from that

Objet oriented doesn't mean "put everything into classes". And the Intersect function is a very good example of a function that shouldn't be member. The whole STL API is another good example.

The most important thing in Intersect(x, y) is not x, it is "Intersect". x is a parameter, just like y, that's why x.Intersect(y) doesn't feel right. We could replace x with a circle z or a vector v, it's not really important we just want to perform an intersection test.

One thing I don't understand is your comment about how global functions can become part of the public interface. Do you mean a global Intersects() function would be able to be called by saying a.Intersects(b)?

No, it just means that a public interface is not only made of the member functions of a class. Non-member functions have to be taken in account as well (again, think about the STL).

I also don't think I understand how having global functions would increase encapsulation vs. member functions

Me too

It seems to me like that would violate encapsulation, by requiring those global functions to be able to access the private data of a class to which they don't belong

I think that a function should be non-member only if it uses the public interface of its parameters (except maybe operators). It's more an extension to the public API of the class, that doesn't require to modify the class itself.

I agree with your argument about genericity, but I could see a situation where a general function works for 90% of classes, but special cases must be made for the other 10%, and it becomes a big confusing mess of "exceptions" to the "rules".

Then you just have to write overloads for those types that require a specific implementation. Look at the STL (third time ).

I guess I should also take this time to say hello to everyone, since these are my first few posts here. Great job on the library, Laurent. I am very excited about the possibilities that I will have by using SFML. You and everyone else who's contributed to this project has done an amazing job so far. Keep up the good work!

Thanks

A static member function would be appropriate

I prefer a global
Imagine that I add intersection between vectors and rectangles, or a new Circle class and intersections between circles and rectangles? In which class would you put the Intersect function? It is perfectly symmetrical, so a global is better so that you can always call Intersect(a, b) whatever a and b are.

[Tank]

I also don't think I understand how having global functions would increase encapsulation vs. member functions

Easy: Every class function has access to private data of its surrounding class. So that data isn't encapsulated from the function.

When using a global Intersect() instead, it only has access to the data through the public methods of the class. So the data is completely encapsulated, which leads to safety and clarity, because you *know* that no side-effects can happen.

[Nexus]

Another feature request: I'd like it if the sf::Rect class template would provide a constructor taking two 2D vectors. Vectors are quite integrated into SFML, sf::Rect is one of the few exceptions.

Laurent, if you decide to leave the begin/end rectangles, something like this might be appropriate:

Code: [Select]

template <typename T>
Rect<T>::Rect(const sf::Vector2<T>& LeftUpper, const sf::Vector2<T>& RightLower)
: Left(LeftUpper.x)
, Top(LeftUpper.y)
, Right(RightLower.x)
, Bottom(RightLower.y)
{
}
The same applies if you want to change the semantics to begin/size rectangles:

Code: [Select]

template <typename T>
Rect<T>::Rect(const sf::Vector2<T>& LeftUpper, const sf::Vector2<T>& Size)
: Left(LeftUpper.x)
, Top(LeftUpper.y)
, Width(Size.x)
, Height(Size.y)
{
}
What do you think (other users as well)?