4
\$\begingroup\$

I am wondering if there is a quick easy way to determine if a given vector is in a specified quadrant.

In the below image, I've define the ranges of the blue quadrants.

Quadrants

For example, if I am given a sample vector of -9.4,13.3 is there an easy way to figure out which of the four quadrants it is in (Q2)?

I'm looking to know if there is some vector math that can determine this relatively simply instead of doing a bunch of less than / greater than operators on a fixed range.

Considering that I could have more or less than 4 quadrants and they might not be at this nice 45 degree angle.

\$\endgroup\$
  • 1
    \$\begingroup\$ You could take the angle and use a lookup table. With a table, you could divide the table onto n widths for n quadrants. \$\endgroup\$ – Vaughan Hilts Mar 5 '15 at 0:35
  • 3
    \$\begingroup\$ Minor terminology issue here but quadrant implies exactly four regions. \$\endgroup\$ – Kelly Thomas Mar 5 '15 at 0:50
  • 1
    \$\begingroup\$ @KellyThomas Indeed; partition might be a better term. \$\endgroup\$ – bcrist Mar 5 '15 at 5:06
  • 1
    \$\begingroup\$ @bcrist Sector \$\endgroup\$ – congusbongus Mar 5 '15 at 5:38
  • 1
    \$\begingroup\$ Just FYI there are many ways to do this - but don't be afraid to use trig. You'd be surprised how much is done per frame in engines. Don't optimise it unless you need to (which you may well have to do - eventually) \$\endgroup\$ – Alec Teal Mar 5 '15 at 6:42
4
\$\begingroup\$

In this case, what is wrong with comparisons? It's (in this case) pretty easy, just

if(abs(x) > abs(y)
  if(x > 0) q = "q2"; else q = "q4";
else
  if(y > 0) q = "q1"; else q = "q3";

Alternatively, you could do something like (hopefully I'll get this right)

angle = atan2(y, x);
angle -= pi/4; // now (0,pi/2) is all Q1
quadrant = angle / (pi/2);
if(quadrant < 0) quadrant += 4;
quadrant++; // to make it 1 to 4. (not quite right for the numbering, but...)

This can be generalized for any evenly-spaced wedges. (They can be called "quadrants" when there's four of them.)

If the wedges aren't evenly spaced, you could still have a list of their angles, calculated when they change, also with atan2. Then it becomes a search problem, given the angle from the origin for a point of interest versus the wedge list. For a small number of wedges, a linear search is probably fine. If you have dozens, or thousands, a binary search might be nicer.

If it must be inside the circle, check the distance to origin first... Is there a reason it must be done "in vector math"?

\$\endgroup\$
  • \$\begingroup\$ But what if I had 5+ quadrants and they weren't at a nice 45 degree angle? So a quadrant could be defined as new Vector4(xMin, xMax, yMin, yMax) \$\endgroup\$ – test Mar 5 '15 at 0:23
  • 2
    \$\begingroup\$ In your question, you need to clarify what problem you want to solve. The problem you showed was exactly what it is; if the question is more general, you need to define how general it is. There's an infinite number of "but-what-ifs" for any situation; they can't all be answered. (Also, not sure how a (xmin,xmax,ymin,ymax) tuple or vec4 defines a pie wedge like in your picture?) Often, when you find exactly how to state your question, you may see the answer yourself more readily too. \$\endgroup\$ – david van brink Mar 5 '15 at 1:13
0
\$\begingroup\$

This is inspired by how OpenGL handles Cubemaps:

(Pseudocode)

vector = normalize(vector);
if(abs(vector.x) > abs(vector.y)){
  if(vector.x < 0)
    //Q1
  else
    //Q3
}else{
  if(vector.y < 0)
    //Q4
  else
    //Q2
}

(i hope you don't count this as "a bunch") Another way would be to calculate the angle which would involve a arctan and that should be a lot slower than my approach.

\$\endgroup\$
  • \$\begingroup\$ See edit regarding a variable amount of quadrants. \$\endgroup\$ – test Mar 5 '15 at 0:24
0
\$\begingroup\$

Yes.

First calculate the matrix for the transformation that maps your custom quadrants to the standard quadrants numbering CCW from +ve X and +ve Y.

Second apply this matrix to the point of interest (call it (x,y)) to get a mapped point in standard quadrant space (x',y'):.

Now apply this formula to the resulting vector (x',y'):

Quadrant = 1 + (1 - sign(y')) - ( sign(y') (1 - sign(x') ) / 2
\$\endgroup\$
0
\$\begingroup\$

Yes, you can perform simple binary search on region divisor vectors.
If you pre-process and sort your divisors ccw(and you probably should), it is sublinear log(n) complexity for n regions (oposed to other answers with linear complexity), moreover it doesnt rely on inaccurate and slow functions like atan, in addition your regions does not need to be quadrants or evenly spaced, it works for any number of any regions.
All you need is to determine if queried vecor lies to left or to right to the tested divisor(that is one vector operation) and apply this greater/lesser logic on same binary search like you already know. Code example(not tested):

Divisor findRegion(vec2 query_vec) {
return *(std::lower_bound(divisors.begin(), divisors.end(), query_vec, isLeft));
}

Please note you might need to implement additional logic if you allow regions greater than pi, but I assume you need use this for more smaller regions

\$\endgroup\$
0
\$\begingroup\$

If the sectors are of equal size then one approach would be to calculate the angle, divide by a full rotation and then multiply by the number or sectors:

rad = atan2(x, y)
normalised_angle = rad / (2 * pi)
sector = (int)(normalised_angle * sector_count)

For the example given in the question we would also require a π/4 offset to account for a quadrant straddling the zero angle. This offset also requires wrapping the angle value to ensure that it remains between 0 and

sector_count = 4
offset =  pi / 4

rad = atan2(x, y) + offset

while (rad < 0):
    rad += 2 * pi
while (rad > 2 * pi):
    rad -= 2 * pi

normalised_angle = rad / (2 * pi)
sector = (int)(normalised_angle * sector_count)
\$\endgroup\$
-1
\$\begingroup\$

Quadrant(1,2,3,4)=4-(1+sign(x))* (1-sign(y^2))-(2-sign(y))* (1-sign(x^2))

       -sign(x^2*y^2)*((1+sign(abs(x)-abs(y)))*(1+sign(x))/2

                      +(1-sign(abs(x)-abs(y)))*(1-sign(y)/2))   
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.