need help checking if any bool in a rotated rectangle is true

let's get right down to business i have a 2d bool array and i need to find out if any bool within a rotated rectangle is true. i don't need to know which bool is true just if any are true.

currently the way i was planning on doing this is to loop through a rectangle that contains the rotated rectangle checking each bool if it is inside(using is left method) and then checking to see if the bool is true. but i was wondering if there is a more efficient way of doing this.

 

Why don't you show us your approach? Your description is quite vage, and makes very little sense (I assume that you regard the array of bools to be something akin to an Array of Pixels.

But:

• is the 'rectangle' the same size (with, height) as the dimensions as the Array?
• how are bools to be interpreted that are inside a part of the rectangle that lies 'outside' the dimensions of the Array?
• how to treat parts of the rectangel that - due to rotation and Offset are exactly between two bools in the Array? Interpolate the value? How do you Lerp between true and false?

Perhaps going straight down to Business was a bit premature. Explain what you want to do, and why, then Show us the code you already have. I'm sure lots of people will be willing to help once we understand that.

 

i have yet to actually code this but i was gonna use something similar to this

float isLeft( Point P0, Point P1, Point P2 )

{

   return ( (P1.x - P0.x) * (P2.y - P0.y) - (P2.x - P0.x) * (P1.y - P0.y) );

}

bool PointInRectangle(Vector2 X, Vector2 Y, Vector2 Z, Vector2 W, Vector2 P)

{

   return (isLeft(X, Y, P) > 0 && isLeft(Y, Z, P) > 0 && isLeft(Z, W, P) > 0 && isLeft(W, X, p) > 0);

}

wasn't quite gonna be this but i haven't actually coded this part because i'm currently working on other code. this is one of the last complex things that i have to do for my game but the way i was thinking of doing this would be rather slow.

as for your points

• no the rectangle is a tank that is on the map, the map is constantly changing so i can't use colliders i was gonna use this method to detect collisions, 2d raycasts also won't really work because of a glow effect that i am applying to everything.
  
• i was gonna go though a for loop that goes from the highest to lowest x and y on the rotated rectangle and then passing each point in the loop through the code above and then checking if the bool is true.
• since currently i was just gonna go though a loop it was always gonna come out as an integar number

so this was roughly gonna be my approach but i don't actually need to find out what bool is true i only wanted to find out if any pixel in the entire rectangle was true so i was wondering if there was a decent way to do this

edited for clarity

i was planning to do something similar to how i'm dealing with my bullet collisions but with rectangles instead of circles

for (int x = 0; x <= circleRadius + circleRadius; x++)

{

            for (int y = 0; y <= circleRadius + circleRadius; y++)

            {

                if (isSolid[l][sZ + x + ((sW + y) * 324)] == true)

                {

                    if (new Vector2(x, y).SqrMagnitude() <= circleRadius * circleRadius)

                    {

                        DamageTerrain(new Vector2Int(sZ, sW), bulletPool[p, i].explosionRad, l);

                        bulletPool[p, i].gameObject.SetActive(false);

                        bulletPool[p, i].Active = false;

                        return;

                    }

                }

            }

}

edited to provide example from bullet collisions

 

Whoa. That's pretty cryptic code - comments are your friend if you ever want someone else to have a look. Let me see if I correctly interpret this riddling code:

In isLeft, you have three points and calculate their cross product in order to determine the normal, interpreting the sign as winding: the result being negative or positive (the direction of the normal (z) vector) is interpreted as right or left winding. I hope I'm OK so far.

You then try to determine if a Point P is inside a rectangle (actually an assumedly convex polygon) defined by the Points x, y, z, w (very, very unfortunate naming here, if you ask me), with the implied assumption by me that they are also given in clockwise orientation.The assumption seems to be that the point is inside the polygon if all triangles you construct with two Points from the polygon and the Point p also return the same winding/normal z value (above Zero)

The result of the winding test is highly dependent on the order, and I don't know how (what order) you are passing in the rotated rectangle's points. But if XYZW are always in clockwise order this should work.

How this applies to your game is difficult to see. If your array of bools represens some kind of map (occupied/free tile), and your tank can only occupy integer positions, and you can correctly convert the tank's location to an index into the Array, well, that could work. To optimize (i.e. not iterate over all bools), find the bounding box (that is aligned with the axes) of your tank, and only test those bools inside that bounding box against the rotated.

 

ok yeah i was talking to other people and they say that what i have is roughly the most efficient way so i guess i'll just be doing that

 

after much thought one thing that i came up with for this is i could make a jagged for loop i have yet to code it but i'll probably post it by tomorrow

edit: i came up with something more interesting so this will take me a bit longer

 

so here is what i came up with the first function just uses a bounding box and then checks each pixel if it is inside the rotated rectangle

the second function is my attempt at removing the pixels that aren't in the rotated rectangle while still handling the ones that are in it the second one isn't completely accurate yet i think there is a rounding error somewhere.

both functions have been split in three so if there is a problem somewhere it made it alot easier to find

Code (CSharp):

1. using UnityEngine;
2.  
3. public class rectangletest : MonoBehaviour
4. {
5.     Vector2 tempVector;
6.     Vector2 tempVector2;
7.     int i = 0;
8.     float xOffset = 40;
9.     float yOffset = 30;
10.     int maxX;
11.     int maxY;
12.     float highY;
13.     float highX;
14.  
15.     int minX;
16.     int minY;
17.     float riseTop;
18.     float riseBottom;
19.     float currentriseTop;
20.     float currentriseBottom;
21.     float xToSplit;
22.     bool FirstVectorMaxY = false;
23.  
24.     float heldFloat;
25.     float testfloat;
26.  
27.     int islefttest = 0;
28.     int jaggedtest = 0;
29.  
30.     int islefttest2 = 0;
31.     int jaggedtest2 = 0;
32.  
33.     int islefttest3 = 0;
34.     int jaggedtest3 = 0;
35.  
36.     private void Start()
37.     {
38.         //loop through 360 degrees to make sure the function works in all angles
39.         for (int i = -180; i < 180; i++)
40.         {
41.             islefttest = 0;
42.             jaggedtest = 0;
43.             islefttest2 = 0;
44.             jaggedtest2 = 0;
45.             islefttest3 = 0;
46.             jaggedtest3 = 0;
47.             testfloat = 0;
48.             tempVector = Quaternion.AngleAxis(i, Vector3.forward) * new Vector2(xOffset, yOffset);
49.             tempVector2 = Quaternion.AngleAxis(i, Vector3.forward) * new Vector2(xOffset, -yOffset);
50.  
51.             maxY = Mathf.FloorToInt(Mathf.Max(Mathf.Abs(tempVector.y), Mathf.Abs(tempVector2.y)));
52.             highY = Mathf.Max(Mathf.Abs(tempVector.y), Mathf.Abs(tempVector2.y));
53.             minX = -Mathf.FloorToInt(Mathf.Max(Mathf.Abs(tempVector.x), Mathf.Abs(tempVector2.x)));
54.             highX = Mathf.Max(Mathf.Abs(tempVector.x), Mathf.Abs(tempVector2.x));
55.             minY = -maxY;
56.             IsLeft();
57.             Jagged();
58.  
59.             if (jaggedtest != islefttest)
60.             {
61.                 Debug.Log("current rotation: " + i + ", jagged: " + jaggedtest + ", isleft: " + islefttest);
62.             }
63.  
64.             if (jaggedtest2 != islefttest2)
65.             {
66.                 Debug.Log("current rotation: " + i + ", jagged2: " + jaggedtest2 + ", isleft2: " + islefttest2);
67.             }
68.  
69.             if (jaggedtest3 != islefttest3)
70.             {
71.                 Debug.Log("current rotation: " + i + ", jagged3: " + jaggedtest3 + ", isleft3: " + islefttest3);
72.             }
73.         }
74.     }
75.  
76.     void IsLeft()
77.     {
78.         //xToSplit is used to split the function in three to make it easier to find problems
79.         if (Mathf.Abs(tempVector.y) > Mathf.Abs(tempVector2.y))
80.         {
81.             xToSplit = -Mathf.Abs(tempVector.x);
82.         }
83.         else
84.         {
85.             xToSplit = -Mathf.Abs(tempVector2.x);
86.         }
87.  
88.  
89.         for (int x = minX; x < Mathf.FloorToInt(xToSplit); x++)
90.         {
91.             for (int y = minY; y < maxY; y++)
92.             {
93.                 if (((tempVector2.x - tempVector.x) * (y - tempVector.y)) - ((x - tempVector.x) * (tempVector2.y - tempVector.y)) < 0 &&
94.                 ((-tempVector2.x + tempVector.x) * (y + tempVector.y)) - ((x + tempVector.x) * (-tempVector2.y + tempVector.y)) < 0 &&
95.                 ((-tempVector.x - tempVector2.x) * (y - tempVector2.y)) - ((x - tempVector2.x) * (-tempVector.y - tempVector2.y)) < 0 &&
96.                 ((tempVector.x + tempVector2.x) * (y + tempVector2.y)) - ((x + tempVector2.x) * (tempVector.y + tempVector2.y)) < 0)
97.                 {
98.                     //do stuff for (x, y) as well as (-x, -y)
99.                     islefttest++;
100.                 }
101.             }
102.         }
103.  
104.         for (int x = Mathf.FloorToInt(xToSplit); x < 0; x++)
105.         {
106.             for (int y = minY; y < maxY; y++)
107.             {
108.                 if (((tempVector2.x - tempVector.x) * (y - tempVector.y)) - ((x - tempVector.x) * (tempVector2.y - tempVector.y)) < 0 &&
109.                 ((-tempVector2.x + tempVector.x) * (y + tempVector.y)) - ((x + tempVector.x) * (-tempVector2.y + tempVector.y)) < 0 &&
110.                 ((-tempVector.x - tempVector2.x) * (y - tempVector2.y)) - ((x - tempVector2.x) * (-tempVector.y - tempVector2.y)) < 0 &&
111.                 ((tempVector.x + tempVector2.x) * (y + tempVector2.y)) - ((x + tempVector2.x) * (tempVector.y + tempVector2.y)) < 0)
112.                 {
113.                     //do stuff for (x, y) as well as (-x, -y)
114.                     islefttest2++;
115.                 }
116.             }
117.         }
118.  
119.         //x = 0
120.         for (int y = minY; y < maxY; y++)
121.         {
122.             if (((tempVector2.x - tempVector.x) * (y - tempVector.y)) - ((-tempVector.x) * (tempVector2.y - tempVector.y)) < 0 &&
123.             ((-tempVector2.x + tempVector.x) * (y + tempVector.y)) - ((tempVector.x) * (-tempVector2.y + tempVector.y)) < 0 &&
124.             ((-tempVector.x - tempVector2.x) * (y - tempVector2.y)) - ((-tempVector2.x) * (-tempVector.y - tempVector2.y)) < 0 &&
125.             ((tempVector.x + tempVector2.x) * (y + tempVector2.y)) - ((tempVector2.x) * (tempVector.y + tempVector2.y)) < 0)
126.             {
127.                 //do stuff for (x, y)
128.                 islefttest3++;
129.             }
130.         }
131.     }
132.  
133.     void Jagged()
134.     {
135.         //these if statements are used to find how much i need to go up or down each iteration
136.         if (Mathf.Abs(tempVector.y) > Mathf.Abs(tempVector2.y))
137.         {
138.             FirstVectorMaxY = true;
139.             xToSplit = -Mathf.Abs(tempVector.x);
140.             if (tempVector2.x < 0)
141.             {
142.                 //this means riseTop is line(tempvector2, -tempvector)
143.                 riseTop = Mathf.Abs(-tempVector.y - tempVector2.y) / Mathf.Abs(-tempVector.x - tempVector2.x);
144.                 //and riseBottom is line(tempvector2, tempvector)
145.                 riseBottom = Mathf.Abs(tempVector.y - tempVector2.y) / Mathf.Abs(tempVector.x - tempVector2.x);
146.                 currentriseTop = Mathf.Abs((tempVector2.x - Mathf.CeilToInt(tempVector2.x)) * riseTop) + tempVector2.y;
147.                 currentriseBottom = tempVector2.y - Mathf.Abs((tempVector2.x - Mathf.CeilToInt(tempVector2.x)) * riseBottom);
148.             }
149.             else
150.             {
151.                 //this means riseTop is line(-tempvector2, tempvector)
152.                 riseTop = Mathf.Abs(tempVector.y + tempVector2.y) / Mathf.Abs(tempVector.x + tempVector2.x);
153.                 //and riseBottom is line(-tempvector2, -tempvector)
154.                 riseBottom = Mathf.Abs(-tempVector.y + tempVector2.y) / Mathf.Abs(-tempVector.x + tempVector2.x);
155.                 currentriseTop = Mathf.Abs((-tempVector2.x - Mathf.CeilToInt(-tempVector2.x)) * riseTop) + -tempVector2.y;
156.                 currentriseBottom = -tempVector2.y - Mathf.Abs((-tempVector2.x - Mathf.CeilToInt(-tempVector2.x)) * riseBottom);
157.             }
158.         }
159.         else
160.         {
161.             FirstVectorMaxY = false;
162.             xToSplit = -Mathf.Abs(tempVector2.x);
163.             if (tempVector.x < 0)
164.             {
165.                 //this means riseBottom is line(tempvector, -tempvector2)
166.                 riseBottom = Mathf.Abs(-tempVector2.y - tempVector.y) / Mathf.Abs(-tempVector2.x - tempVector.x);
167.                 //and riseTop is line(tempvector, tempvector2)
168.                 riseTop = Mathf.Abs(tempVector2.y - tempVector.y) / Mathf.Abs(tempVector2.x - tempVector.x);
169.                 currentriseTop = Mathf.Abs((tempVector.x - Mathf.CeilToInt(tempVector.x)) * riseTop) + tempVector.y;
170.                 currentriseBottom = tempVector.y - Mathf.Abs((tempVector.x - Mathf.CeilToInt(tempVector.x)) * riseBottom);
171.             }
172.             else
173.             {
174.                 //this means riseBottom is line(-tempvector, tempvector2)
175.                 riseBottom = Mathf.Abs(tempVector2.y + tempVector.y) / Mathf.Abs(tempVector2.x + tempVector.x);
176.                 //and riseTop is line(-tempvector, -tempvector2)
177.                 riseTop = Mathf.Abs(-tempVector2.y + tempVector.y) / Mathf.Abs(-tempVector2.x + tempVector.x);
178.                 currentriseTop = Mathf.Abs((-tempVector.x - Mathf.CeilToInt(-tempVector.x)) * riseTop) + -tempVector.y;
179.                 currentriseBottom = -tempVector.y - Mathf.Abs((-tempVector.x - Mathf.CeilToInt(-tempVector.x)) * riseBottom);
180.             }
181.         }
182.  
183.         //i don't need to check if these pixels are inside th rotated rectangle because only the ones that are should be checked
184.         for (int x = minX; x < Mathf.FloorToInt(xToSplit); x++)
185.         {
186.             for (int y = Mathf.Max(Mathf.CeilToInt(currentriseBottom), -maxY); y <= Mathf.Min(Mathf.FloorToInt(currentriseTop), maxY); y++)
187.             {
188.                 //do stuff for (x, y) as well as (-x, -y)
189.                 //if (jaggedtest > 10000)
190.                 //{
191.                 //    Debug.Log("bottom: " + Mathf.CeilToInt(currentriseBottom) + ", Top: " + Mathf.FloorToInt(currentriseTop) + ", first half");
192.                 //    break;
193.                 //}
194.                 jaggedtest++;
195.             }
196.             currentriseTop += riseTop;
197.             currentriseBottom -= riseBottom;
198.         }
199.  
200.         //this small section is used to switch the rise over run of the corner that hit the top or bottom of the bounding box
201.         heldFloat = Mathf.Abs(xToSplit - Mathf.FloorToInt(xToSplit));
202.  
203.         currentriseTop += riseTop * heldFloat;
204.         currentriseBottom -= riseBottom * heldFloat;
205.  
206.         if (FirstVectorMaxY)
207.         {
208.             riseBottom = -riseTop;
209.         }
210.         else
211.         {
212.             riseTop = -riseBottom;
213.         }
214.  
215.         for (int x = Mathf.FloorToInt(xToSplit); x < 0; x++)
216.         {
217.             for (int y = Mathf.Max(Mathf.CeilToInt(currentriseBottom), -maxY); y <= Mathf.Min(Mathf.FloorToInt(currentriseTop), maxY); y++)
218.             {
219.                 //do stuff for (x, y) as well as (-x, -y)
220.                 //if (jaggedtest > 10000)
221.                 //{
222.                 //    Debug.Log("bottom: " + Mathf.CeilToInt(currentriseBottom) + ", Top: " + Mathf.FloorToInt(currentriseTop) + ", second half");
223.                 //    break;
224.                 //}
225.                 jaggedtest2++;
226.             }
227.             currentriseTop += riseTop;
228.             currentriseBottom -= riseBottom;
229.         }
230.  
231.         //for x = 0
232.         for (int y = Mathf.Max(Mathf.CeilToInt(currentriseBottom), -maxY); y <= Mathf.Min(Mathf.FloorToInt(currentriseTop), maxY); y++)
233.         {
234.             //do stuff
235.             //if (jaggedtest > 10000)
236.             //{
237.             //    Debug.Log("bottom: " + Mathf.CeilToInt(currentriseBottom) + ", Top: " + Mathf.FloorToInt(currentriseTop) + ", second half");
238.             //    break;
239.             //}
240.             jaggedtest3++;
241.         }
242.     }
243. }
244.  

if anyone can find where the second function goes wrong it would be greatly appreciated