0
$\begingroup$

I'm working on a personal JavaFX project, and I need to check if two sprites overlap. Originally, I modelled them as ellipses. I was then able to then simplify the problem into checking the intersection of a circle and a non-rotated ellipse centered at the origin. For extra context, what I did was center one of the ellipses at the origin via a translation of $\mathbb{R}^2$, then applied a transformation $\begin{pmatrix}k&0\\0&1\end{pmatrix}$ so that the centered ellipse became a circle. I then translated once again so that the ellipse was centered, and the rotated the plane so that the ellipse was no longer rotated.

However, no matter what I tried (system of equations, checking which curve intersected a ray passing through the origin first, minimizing inequalities, etc.), I always ended up with a quartic equation, which is just not viable to solve. So, I decided to use some other curves to represent the sprites. I first thought of Bezier curves, but I don't think using degree 3 or higher polynomials would improve the situation.

My question is, is there a type of curve that is roughly ovular, where calculating the intersection of such curves is easier?

$\endgroup$
4
  • $\begingroup$ Case 1) If your sprites can be modelized as convex polygons , there exists an algorithm for the intersection of such polygons which is described in an answer of mine to this recent question. Case 2) If your sprites are polygonal but have concavities, decompose them into a union of (a few !) convex polygons $A_1 \cup A_2 \cup \cdots$ and $B_1 \cup B_2 \cup \cdots$ and apply case 1 to test whether one at least of intersections $A_p \cap B_q$ is nonvoid. $\endgroup$
    – Jean Marie
    Commented Oct 12, 2023 at 7:09
  • 1
    $\begingroup$ I don't think modelization of shapes by ellipses can lead to efficient procedures compared to modelization by polygons. $\endgroup$
    – Jean Marie
    Commented Oct 12, 2023 at 7:31
  • $\begingroup$ To exclude the most often occurring case to determine that the two sprites do not intersect, it is sufficient to consider enclosing rectangular boxes. Or if you want, circles, so you only need to check if the distance of the centers is greater than the sum of the radii. Then it is not that important how effective the test with more precise shape enclosures is. $\endgroup$
    – Lutz Lehmann
    Commented Oct 12, 2023 at 9:32
  • 1
    $\begingroup$ @JeanMarie Thanks for the quick response! I think using polygons would be a lot more viable. $\endgroup$
    – Ryan de Barros
    Commented Oct 12, 2023 at 13:31

1 Answer 1

Reset to default
1
$\begingroup$

There are a few options:

  1. Approximate your ellipses by polylines, as suggested by @JeanMarie.

  2. Approximate your ellipses by bi-arc curves. These are just strings of circular arcs, for which distance and overlap calculations are easy. For more details, you can either Google “biarc” or start with the answers to this question.

  3. Use bitmap representations of your ellipses. Then overlap checking is easy. You could even do it on the GPU, which would be extremely fast.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .