0

I am looking for a simple algorithm to detect if the area of an aabb overlaps with the area of an arc (closed by the cord) or a pie (closed through the circle's center).

I already found this answer: Intersection of rectangle and circle (or arc)

But it is not quite what I am looking for because I am not interested in the intersection points of the shapes' outlines but just want to know if the areas overlap.

Eg the case that a very small AABB contains only the center of the pie but the AABB's edges do not intersect the pie's circle would not be covered in the linked answer. Likewise the case that the arc completely contains the the AABB and the AABB's sides do not even intersect the cord would not be covered.

Now before I start reinventing the wheel I would like to ask if there is a known algorithm for such an overlap check.

One example of AABB-Sector:

example of four AABBs intersecting a two sectors

Community
  • 1
  • 1
Laszlo Korte
  • 1,179
  • 8
  • 17
  • possible duplicate of [How to test if a line segment intersects an axis-aligned rectange in 2D?](http://stackoverflow.com/questions/99353/how-to-test-if-a-line-segment-intersects-an-axis-aligned-rectange-in-2d) – Ben Sep 23 '15 at 16:09
  • This question is not about intersecting lines. As described in the question I am looking for overlapping shapes (pie and aabb) even in cases in which there is no line intersection at all – Laszlo Korte Sep 23 '15 at 16:11
  • You are correct, you want a circle-segment intersection not a line-segment intersection. – Ben Sep 23 '15 at 16:32

2 Answers2

1

This isn't such an easy problem given the variety of configurations.

You will make the problem simpler by splitting the sector with a cross through the center, so that an horizontal or vertical line will not meet the arc twice, and process the pieces separately.

Then consider one of the pieces and "inflate" it while you "deflate" the rectangle. More precisely, every point of the sector becomes the rectangle originating from it (upper-left corner), while the rectangle shrinks to its lower-right corner.

The shape that you obtain (green area) is a so-called Minkowski sum (aka dilation).

As you see, it has 5 straight edges and a curved one. You can easily predict the shapes for all sector orientations.

enter image description here

Now there is an intersection if the rectangle shrunk to a point lies inside this curvilinear hexagon. You check that the point belongs to the sector using polar coordinates (r < R and Θ' < Θ < Θ"), and you check insideness to the (straight) hexagon by a standard point-in-polygon test.

Similar reasoning works for the circular segment (chord).

enter image description here

This geometric transformation allows to use the "locus" approach, i.e. visualize the solution set as a geometric shape, to support reasoning. Given the nature of the domain (a convex hexagon), we can conclude that in the worst case 4 comparisons (involving linear or quadratic terms) are enough to get the answer by dichotomy !

0

The sector and segment cases are different.

For a segment:

  • Broadphase: If the AABB of the circle-segment doesn't intersect, then no.
  • If the chord intersects (or is within) the AABB the answer is yes. This is line-segment to rectangle test, which I assume you know how to do.
  • This leaves only the case where the AABB is within the circle-segment or intersects the arc. For this to be true at least part of one of the four sides must be within the segment (or the whole segment would be contained including the chord, and we would have found that at the previous step).
  • therefore treat rectangle as four lines, and for each line
    • calculate the line segment within the circle by intersection with the circle
    • if it exists check that either end of the line is on the inside of the circle-segment by comparing to the chord.

For a sector, you can either treat it as a segment plus a triangle, or:

  • If the AABB of the circle doesn't intersect, then no.
  • If either radial line intersects, then Yes.
  • Otherwise treat the rectangle as four line segments, and for each segment:
    • Calculate the line segment within the circle by intersection with the circle.
    • If it exists calculate the sub-segment which is on the correct side of the first radial line.
    • if it exists calculate the sub-segment which is on the correct side of the second radial line.
Ben
  • 34,935
  • 6
  • 74
  • 113
  • In the accepted answer you linked there is a note in the end "Note that it relies on the fact that the border of the rectangle can't intersect the border of the sector without also intersecting its circular part.". I do not get how the described algorithm covers all the cases. I have added a graphic to my question to highlight 3 cases for which I do not see how the are distinguished by the algorithm in the linked answer. – Laszlo Korte Sep 23 '15 at 17:01