Finding which region contains a point based on coordinates.

Question

I have 4 points that form some quadrilateral. The lines can't cross or anything like that, it should be a square, rectangle, rhombus, parallelogram, etc.

The lines that connect them break the field into 9 regions. With a square, it would look like a tic-tac-toe board (#), but with other shapes the lines will be at angles.

A point falls randomly into this 9-region field. I know the coordinates of the random point, as well as the coordinates of the quadrilateral's 4 corners.

Is there any way I can find which field contains the point without using the equations of the lines?

I'm basically looking for something like

if(p.x > q1.x && p.x < q4.x && p.y < q3.y) {
    //It's in the top left region
}
etc

I'm thinking that this isn't possible when using sloped lines (rather than a square/rectangle) without solving the line equations. But I thought I'd run it by the math guys first. THANKS!

Answer 1

It may be equivalent to 'using the equations of the lines', but the obvious thing to do is to compute the affine transformation that takes your four points to the unit square (0,0), (0,1), (1,0), (1,1). To decide the location of a point, apply the transform to the point and compare the result against the unit square.

Answer 2

Anything you do is effectively "using the equations of the lines", so I'm not sure what to make of that condition. I assume you just want easy inequalities to check which region the random point (x,y) is in, so that's what I'll show you how to do.

From your question, it sounds like you always have a parallelogram, so let's assume that the points are (0,0), (a,b), (c,d), and (a+c,b+d), which makes the explanation a little easier to follow. To fix your mental picture, imagine that (a,b) is roughly "to the right" of (0,0) and (c,d) is roughly "above" (0,0). Then the equations for the "horizontal" lines are -bx+ay=0 and -bx+ay=-bc+ad, so you get three possibilities, depending on how -bx+cy compares to 0 and -bc+ad:

// Assuming -bc+ad is positive
-bx+ay < 0           // it's in the "bottom row"
0 < -bx+ay < -bc+ad // it's in the "middle row"
-bc+ad < -bx+ay     // it's in the "top row"

Similarly, the equations for the "vertical" lines are dx-cy=0 and dx-cy=da-bc, so the three possibilities, depending on how dx-cy compares to 0 and to da-cb:

// Still assuming ad-bc is positive
dx-cy < 0           // it's in the "left column"
0 < dx-cy < da-cb  // it's in the "middle column"
da-cb < dx-cy      // it's in the "right column"

Of course, if da-cb is negative, then the three possibilities in each case are "less than da-cb", "between da-cb and 0", and "greater than 0" instead. Finally, if equality ever holds, then the point (x,y) is actually on one of the lines rather than in one of the regions.