0

I have a square of 10x10 pixels. The square can be moved. I want to make sure that this square does not come out of the shape in the photo. This will be checked every 17 milliseconds. So, I want to check in the most optimized way whether this square is inside this rectangular shape.
I couldn't find a method like rectangle.intersects ().

So how can i do that?

Shape: shape image

Lajos Arpad
  • 64,414
  • 37
  • 100
  • 175
kralarmerlin
  • 35
  • 6
  • Is the quadrilateral's shape fixed? If so, you can just write a few simple inequalities by hand. Otherwise search for "point in polygon" algorithms. – kaya3 Apr 21 '21 at 10:44
  • @kaya3 Yes its fixed. only the slope of the upper and lower edges can change. And the length of the 4 sides. Okey thanks I will try to write a class for this spesific quadrilateral shape. – kralarmerlin Apr 21 '21 at 11:00
  • You can store your quadrilateral as a `Path2D quadrilateral` and your rectangle as a Rectangle2D then run, [quardrilateral.contains](https://docs.oracle.com/en/java/javase/11/docs/api/java.desktop/java/awt/geom/Path2D.html#contains(java.awt.geom.Rectangle2D)) – matt Apr 21 '21 at 11:11
  • Why do you ask about point in quad, when you really need square? What point of square you want to test? – MBo Apr 21 '21 at 16:51
  • Doesn't is suffice to check insideness of the four vertices ? (16 comparisons) –  Apr 21 '21 at 19:04

3 Answers3

0

This seems like polygon union testing to me. Maybe something like the Clipper library could help you. See also https://math.stackexchange.com/questions/15815/how-to-union-many-polygons-efficiently.

wilx
  • 17,697
  • 6
  • 59
  • 114
0

If both of your rectangles have their sides parallel with OX and OY vectors, respectively, then assuming that (x1, y1) is the left-top corner, while (x2, y2) is the right-bottom corner, then your solution for intersection is:

(p2.x1 >= p1.x1) && (p2.x2 <= p1.x2) && (p2.y1 >= p2.y1) && (p2.x2 <= p1.x1)

while if you need to determine intersection, then you will need to check whether rectangle1 is completely to the left, right, top or bottom in comparison to rectangle2:

!((p2.x2 < p1.x1) || (p2.x1 > p1.x2) || (p2.y2 < p1.y1) || (p2.y1 > p1.y2))

So, if the negation above is true, then the rectangles intersect.

However, if any of the rectangles may be rotated in comparison to the OX and OY vectors, then it is slightly more complex, see here: How to check intersection between 2 rotated rectangles?

EDIT

Whatever the polynom you have, each side has a chunk of a line. You can define the equation of the line, see here: https://www.mathsisfun.com/equation_of_line.html

That defines all the points on the line. However, you will need to use an inequality of the line, using the > or the < relation, depending on which side of the line your trapezoid is. Since you have four sides, this describes four inequalities. Having two trapezoids, you have 8 inequalities in total. https://courses.lumenlearning.com/suny-beginalgebra/chapter/solve-compound-inequalities/

Do this on paper for a few examples and after that the algorithm for the trapezoids will be easy.

In short: do the comparison with rectangles that you draw on your trapezoid and contains all the points of the trapezoid. If these wrapper rectangles don't intersect, then the trapezoids will not intersect either. If the rectangles intersect, then see whether the lines of the trapezoid's given sides intersect. If the outer rectangles intersect, but the trapezoid lines are not, then see whether one of the inner recangle intersects the other's outer rectangle.

Lajos Arpad
  • 64,414
  • 37
  • 100
  • 175
0

By convexity, the quadrilateral is wholly inside the rectangle if its four corners are.

In the most obvious way, this takes 4 x 4 comparisons (=16).

You can also get the smallest/largest abscissa/ordinate among the corners, using 2 x 4 comparisons, and compare to the corresponding rectangle sides with 4 more comparisons (=12).