Determine intersection with an Ovale shape

Question

I'm working with Java and I am trying to detect the intersection of an ovale with a rectangle.

I tough at first using Intersect would be sufficient :

Shape rect = new Rectangle2D.Double(ant.getPosX(), ant.getPosY(), 5, 5);
for (Shape obstacle : obstaclesShape) {
    if(obstacle.intersects(rect.getBounds())){
        System.out.println("Boom");
    }
}

obstaclesShape is an ArrayList of oval shape.

Shape oval = new Ellipse2D.Double(getRandomX(), getRandomY(), obstacle.getRandomWidth(), obstacle.
this.obstaclesShape.add(oval);

But using this method is not reliable enough. The event seems to be triggered almost randomly.

So I was asking myself wouldn't it be better to use mathematic and determine the position of the border of my ellipsis? Something which would be determine by the angle and height / width I guess.

The thing is how to determine it precisely? What is the formula for it? Or is there a better way?

I've got an oval shape, I know the position of the center of the shape and the position of the center of the point in the right corner. I know height and width of the oval and I'd like to determine the position of the red border. @xenteros — Baldráni, Jul 04 '17 at 08:57
[This is oval](https://en.wikipedia.org/wiki/Oval) and what you show looks like a random [Hazard](https://en.wikipedia.org/wiki/Hazard_(golf)) — xenteros, Jul 04 '17 at 08:58
first hit on google for "calculate point of oval" https://math.stackexchange.com/questions/22064/calculating-a-point-that-lies-on-an-ellipse-given-an-angle — Timothy Truckle, Jul 04 '17 at 08:59
Well, we don't know what you mean by "the event is triggered almost randomally". Of course, you have completely random ovals in your list of ovals. — RealSkeptic, Jul 04 '17 at 09:09
@RealSkeptic what I mean by that is that the event is trigger when there is collision between an oval and a rectangle but it is triggered too in some other case when there is no collision. As said in the [documentation](https://docs.oracle.com/javase/7/docs/api/java/awt/geom/Ellipse2D.html#intersects(double,%20double,%20double,%20double)) the method is not really accurate. — Baldráni, Jul 04 '17 at 09:15
@TimothyTruckle I admit having trouble translating this to a point position in an other position than 0,0. — Baldráni, Jul 04 '17 at 09:16
Note also in the documentation that it says that the reason for the imprecise calculation is that doing the exact calculation (the math) is going to be very expensive. Take this into account. As far as geometry is concerned, this is a very simple math problem. But if you need this to be fast to support a game, it's a different thing. — RealSkeptic, Jul 04 '17 at 09:31
*"I admit having trouble translating this to a point position in an other position"* Most likely you should not work with *display coordinates* within the *view layer*. You should create your own coordinate system with your own "obstacle" object types that do the collision detection. See this: https://stackoverflow.com/questions/44834930/is-there-a-way-to-check-if-one-method-draws-over-another-method-with-java-proces/44835925#44835925 — Timothy Truckle, Jul 04 '17 at 09:34
I see no rectangle ... also if you are really using ellipse instead of oval then you can rotate/scale the view so it become circle then compute intersections and then convert back to original scale ... That way is much easier to implement then to deal with ellipse ... it is unclear if you are using axis aligned shapes or not ... code suggest Yes image is unclear. The formula for this task is solution to system of equations (ellipse and set of rectangle edge lines or together) plus inside bbox check... — Spektre, Jul 04 '17 at 09:41
@TimothyTruckle interesting answer. Thank you for sharing :) — Baldráni, Jul 04 '17 at 09:50

score 1 · Answer 1 · answered Jul 04 '17 at 11:37

Yes, it is worth to apply some math and find whether your ellipse intersects rectangle.

Let rectangle has corners (x0,y0) and (x1,y1) and ellipse has center (cx, cy), horizontal semi-axis a, vertical sem-axis b.

At first we can make affine transformation to simplify calculations - we transform ellipse into origin-centered circle with radius 1. Rectangle will transform too, and intersection fact does not change.

With such transform  we apply shift by (-cx,-cy), scaling by `1/a` in OX direction and scaling by `1/b` in 0Y direction. After that rectangle will have coordinates

 xxx0 = (x0-cx) / a
 yyy0 = (y0-cy) / b
 xxx1 = (x1-cx) / a
 yyy1 = (y1-cy) / b

Now we can apply described here approach to find a distance between origin (circle center) and rectangle. If it less than 1, objects do intersect.

Slightly modified function (Delphi)

function RectDistanceToZeroLessThan1(RR: TRect): Boolean;
var
  wh, hh, dx, dy, t, SquaredDist: Double;
begin
  SquaredDist := 0;

  //width and height
  wh := RR.Right - RR.Left;
  hh := RR.Bottom - RR.Top;

  //doubled rectangle center coordinates
  dx :=  - (RR.Left + RR.Right);
  dy :=  - (RR.Top + RR.Bottom);

  //rectangle sides divide plane to 9 parts,
  t := dx + wh;
  if t < 0 then
    SquaredDist := t * t
  else begin
    t := dx - wh;
    if t > 0 then
      SquaredDist := t * t
  end;
  t := dy + hh;
  if t < 0 then
    SquaredDist := SquaredDist + t * t
  else begin
    t := dy - hh;
    if t > 0 then
      SquaredDist := SquaredDist + t * t
  end;

  Result = SquaredDist <= 4 // due to removed 0.5 coefficients
end;

Determine intersection with an Ovale shape

1 Answers1