Welcome, Guest. Please login or register. Did you miss your activation email?

Author Topic: Determining whether a point lies within a non-rectangle shape  (Read 183 times)

0 Members and 1 Guest are viewing this topic.

It_Helped_Me

  • Newbie
  • *
  • Posts: 2
    • View Profile
Determining whether a point lies within a non-rectangle shape
« on: November 30, 2023, 04:35:51 am »
Hello everyone, hope you're doing well. I've been using SFML for school a few months now, and I'm working on a grid-based strategy role-playing game (like Fire Emblem, Shining Force, etc.) for my class. If you've played such a game, you know that when choosing to move, attack, etc. it highlights the tiles within a certain star-shaped radius (see attached example). I'm trying to implement a function that does this.

In my current approach, I made a square RectangleShape the size of the other squares in the grid, times the desired radius, plus a very small amount. I then set the origin of this square to the position of the character and rotate it 45 degrees. I've drawn it out on graph paper, and the resulting diamond will include the top left of every square I'd want to highlight.

I have a function that uses the getGlobalBounds() of the diamond to highlight every square on the grid whose position is within the diamond. But it highlights a large square around the character, not the shape I'm aiming for. I know this is because getGlobalBounds() returns the bounding rectangle of the shape, but I thought the bounding rectangle would rotate with the shape, which I now see is not the case.

So is there a way to do what I'm actually trying to do, which is: check if certain coordinates are within a non-rectangle shape?

Any help would be greatly appreciated. Thank you for reading.


eXpl0it3r

  • SFML Team
  • Hero Member
  • *****
  • Posts: 10784
    • View Profile
    • development blog
    • Email
Re: Determining whether a point lies within a non-rectangle shape
« Reply #1 on: November 30, 2023, 02:29:01 pm »
SFML only provides some function to check point in axis-aligned (AA) rectangle or axis-aligned bounding boxes (AABB), for other "collision" checks, you'll have to find alternative algorithms.
Not sure I fully understood your setup. I guess on the "extrem" end you could implement SAT (separate axis theorem), but maybe there are simpler checks that could be done in between.
Official FAQ: https://www.sfml-dev.org/faq.php
Official Discord Server: https://discord.gg/nr4X7Fh
——————————————————————
Dev Blog: https://duerrenberger.dev/blog/

Hapax

  • Hero Member
  • *****
  • Posts: 3339
  • My number of posts is shown in hexadecimal.
    • View Profile
    • Links
Re: Determining whether a point lies within a non-rectangle shape
« Reply #2 on: December 02, 2023, 03:37:56 pm »
Any sf::Transformable such as sf::RectangleShape uses a transform (sf::Transform) to convert all of the local co-ordinates of the shape to be in it is final position: the global co-ordinates. You can access this transform, for example, by rectangle.getTransform().

However, your "global" co-ordinates have already been transformed. What you could then use is a way to undo this transform and... there is a way! You can also get the "inverse transform" from an sf::Transformable like this: rectangle.getInverseTransform().

You can use this inverse transform to transform all global co-ordinates into local co-ordinates, which means that you can convert one object's global co-ordinates into another object's local co-ordinates. This means that you can work within axis-aligned boxes in the local space. This is useful for points where you can see if a point is inside a rotated rectangle.

This could be enough but if you need to compare two rectangles directly, you'll need SAT or similar.



With all that being said, I've made a function that can test collision between 2 rectangles that is on the SFML Wiki:
https://github.com/SFML/SFML/wiki/Source%3A-Rectangular-Boundary-Collision
It tests using increasing complexity until it is sure of the answer so it'll test using the usual basic AABB test, then using the method I mentioned above using transforms and points, and then, finally will test using a customised SAT calculation designed for just this exact task (and it re-uses a lot of the calculations from the previous test as well!).

So, if you have 2 rectangle shapes and want to see if they collide, that free function is the easiest way.
Selba Ward -SFML drawables
Cheese Map -Drawable Layered Tile Map
Kairos -Timing Library
Grambol
 *Hapaxia Links*