Собственно цель в названии вопроса. У меня имеются координаты верхнего левого угла и нижнего правого угла ограничивающего прямоугольника для эллипса (другими словами эллипс вписан в этот прямоугольник). Также, имеются две точки прямой. Координатная система - левый верхний угол окна 0;0, y направлена вниз, x направлена вправо. Как пытался решить:
Вот уравнение эллипса с центром x0;y0
(мой случай):
Вот уравнение прямой:
Взял уравнение эллипса и прямой, упростил, выразил из них X. Через дискриминант получаю:
- если
D < 0
- корней нет, прямая не пересекает эллипс; - если
D == 0
- корень один, прямая является касательной к эллипсу (могу быть не прав); - если
D > 0
- корней два, как раз точки пересечения прямой эллипса.
И еще один исключительный случай: если у прямой x2 - x1
очень близко к нулю, то формула меняется, и через дискриминант мы уже выражаем y
, а x
будет равен x1 || x2
(так как они совпадают, в моем случае координаты приходят целочисленные).
Я проверил этот способ, он отлично работает с эллипсом который является окружностью. Однако, как только у эллипса a != b
- алгоритм ошибается, и я никак не могу найти проблему. Ниже прикладываю подробный код (специально расписал длиннее, чтобы было легче найти проблему), в котором заложен вышеописанный алгоритм + исключительной случай, когда x2 - x1
очень близко к нулю:
private void calculatePointsIntersectBlock(Rectangle rect, Point pt1, Point pt2){
Rectangle rectCoordinate = new Rectangle(rect.x, rect.y, rect.x+ rect.width, rect.y+ rect.height);// координаты эллипса
double _a = rect.width / 2.0; // полуось эллипса a
double _b = rect.height / 2.0; // полуось эллипса b
double x0 = (rectCoordinate.x + rectCoordinate.width) /2.0; // x центр эллипса
double y0 = (rectCoordinate.y + rectCoordinate.height) /2.0; // y центр эллипса
// уравнение прямой
double k = (pt2.y - pt1.y) / (double)(pt2.x - pt1.x);
double b = pt1.y - k * pt1.x;
// уравнение эллипса
double v = (_a*_a)*(_b*_b);
double s = b - y0;
// собранное квадратное уравнение
double A = -1;
double B = -1;
double C = -1;
if(pt2.x - pt1.x != 0) {
A = (_a * _a) + (_b * _b) * (k * k);
B = 2 * ((_a * _a) * k * s - (_b * _b) * x0);
C = (_a * _a) * (x0 * x0) + (_b * _b) * (s * s) - v;
}else{ // исключительная ситуация x2 - x1 близко к нулю
double w = (1 - (Math.pow(pt1.x - x0, 2) / (_a*_a))) * (_b*_b);
A = 1;
B = -2 * y0;
C = (y0 * y0) - w;
}
// решаем и выводим два корня
double D = (B * B) - 4*A*C;
// подставляем и находим x и y
if(pt2.x - pt1.x != 0) {
// одна точка пересечения
if (D < 0) {
return; // точек пересечения нет
} else if (D == 0) {
double x1 = (-B * 2) / (2 * A);
Point single = new Point((int) x1, (int) (k * x1 + b)); // единственная точка
} else {
// две точки
double x1 = (-B - Math.sqrt(D)) / (2 * A);
double x2 = (-B + Math.sqrt(D)) / (2 * A);
double y1 = k * x1 + b;
double y2 = k * x2 + b;
Point first = new Point((int) x1, (int) y1); // первая точка
Point second = new Point((int) x2, (int) y2); // вторая точка
}
}else{ // исключительная ситуация x2 - x1 близко к нулю
if (D < 0) {
return; // точек пересечения нет
} else if (D == 0) {
// одна точка
double y1 = (-B * 2) / (2 * A);
Point single = new Point((int) 0, (int) y1); // единственная точка
} else {
// две точки
double y1 = (-B - Math.sqrt(D)) / (2 * A);
double y2 = (-B + Math.sqrt(D)) / (2 * A);
double x1 = pt1.x;
double x2 = pt1.x;
Point first = new Point((int) x1, (int) y1); // первая точка
Point second = new Point((int) x2, (int) y2); // вторая точка
}
}
}
Помогите найти ошибку. Проверял на бумаге, но никак не могу найти, вроде бы всё сходится.
A = (_a * _a) + (_b * _b) * (k * k);
->A = (_b * _b) + (_a * _a) * (k * k);
double x0 = (rectCoordinate.x + rectCoordinate.width) /2.0;
->double x0 = rectCoordinate.x + rectCoordinate.width /2.0;