Проверьте, если точка является частью квадратичной кривой Безье в Java

Question

Я хочу, чтобы проверить, если точка является частью квадратичной кривой Безье, определяемой точки p0, p1 и p2 ..

Это моя функция для получения точка на кривой с некоторым т:

public static final Point quadratic (Point p0, Point p1, Point p2, double t) { 
    double x = Math.pow(1-t, 2) * p0.x + 2 * (1-t) * t * p1.x + Math.pow(t, 2) * p2.x; 
    double y = Math.pow(1-t, 2) * p0.y + 2 * (1-t) * t * p1.y + Math.pow(t, 2) * p2.y; 

    return new Point((int)x, (int)y); 
} 

Учитывая, что точка в (т) в квадратичной кривой получается следующим образом:

в (Т) = (1 - т)^2 * p0 + 2 * t * (1 - t) * p1 + t^2 * p2

Я должен проверить, принадлежит ли точка P кривой, получая значение t для этой точки и сравнивая ее с точкой, полученной с использованием этого параметра t param, но в Java у меня возникают проблемы с точностью переменных ,

Моей функция для проверки точки является следующее:

public static final boolean belongsQuadratic (Point p, Point p0, Point p1, Point p2) { 
    double[] tx = obtainTs(p.x, p0, p1, p2); 
    double[] ty = obtainTs(p.y, p0, p1, p2); 

    if (tx[0] >= 0) { 
     if ((tx[0] >= ty[0] - ERROR && tx[0] <= ty[0] + ERROR) || (tx[0] >= ty[1] - ERROR && tx[0] <= ty[1] + ERROR)) { 
      return true; 
     } 
    } 

    if (tx[1] >= 0) { 
     if ((tx[1] >= ty[0] - ERROR && tx[1] <= ty[0] + ERROR) || (tx[1] >= ty[1] - ERROR && tx[1] <= ty[1] + ERROR)) { 
      return true; 
     } 
} 


    return false; 
} 

public static double[] obtainTs (int comp, Point p0, Point p1, Point p2) { 
    double a = p0.x - 2*p1.x + p2.x; 
    double b = 2*p1.x - 2*p0.x ; 
    double c = p0.x - comp; 

    double t1 = (-b + Math.sqrt(b*b - 4*a*c))/(2*a); 
    double t2 = (-b - Math.sqrt(b*b - 4*a*c))/(2*a); 

    return new double[] {t1, t2}; 
} 

Так что, если я запускаю код с этим значением:

Point p0 = new Point(320, 480); 
Point p1 = new Point(320, 240); 
Point p2 = new Point(0, 240); 
double t = 0.10f; 
Point p = Bezier.quadratic(p0, p1, p2, t); 
double[] ts = Bezier.obtainTs(p.x, p0, p1, p2); 

я получить следующий вывод:

For t=0.10000000149011612, java.awt.Point[x=316,y=434] 
For t1: -0.1118033988749895, java.awt.Point[x=316,y=536] 
For t2: 0.1118033988749895, java.awt.Point[x=316,y=429] 
java.awt.Point[x=316,y=434] belongs?: false 

Должен ли я использовать BigDecimal для выполнения операций? Есть ли другой способ проверить это? Благодаря

Answer 1

Существует ошибка здесь:

double[] ty = obtainTs(p.y, p0, p1, p2); 

потому что obtainTs() использует х -координаты из p0, p1, p2, чтобы найти т-параметр для у -координаты р.

Если изменить параметры метода в int (которые могут быть Х- или Y-координаты точки):

public static double[] obtainTs (int comp, int p0, int p1, int p2) { 
    double a = p0 - 2*p1 + p2; 
    double b = 2*p1 - 2*p0 ; 
    double c = p0 - comp; 

    double t1 = (-b + Math.sqrt(b*b - 4*a*c))/(2*a); 
    double t2 = (-b - Math.sqrt(b*b - 4*a*c))/(2*a); 

    return new double[] {t1, t2}; 
} 

и называем его

double[] tx = obtainTs(p.x, p0.x, p1.x, p2.x); 
double[] ty = obtainTs(p.y, p0.y, p1.y, p2.y); 

тогда ваш тестовый код будет return "true" (проверено с помощью ERROR = 0.02).

---

Обратите внимание, что если вы записать уравнение

B(t) = (1 - t)^2 * p0 + 2 * t * (1 - t) * p1 + t^2 * p2 

для обоих х- и у-координаты, то вы можете исключить т^2-Term и получить один линейное уравнение для т , Это дает следующий метод, который может быть немного проще и не использует квадратные корни:

public static final boolean belongsQuadratic2 (Point p, Point p0, Point p1, Point p2) { 
    double ax = p0.x - 2*p1.x + p2.x; 
    double bx = 2*p1.x - 2*p0.x ; 
    double cx = p0.x - p.x; 

    double ay = p0.y - 2*p1.y + p2.y; 
    double by = 2*p1.y - 2*p0.y ; 
    double cy = p0.y - p.y; 

    // "Candidate" for t: 
    double t = -(cx*ay - cy*ax)/(bx*ay - by*ax); 
    if (t < 0 || t > 1) 
     return false; 
    // Compute the point corresponding to this candidate value ... 
    Point q = Bezier.quadratic(p0, p1, p2, t); 
    // ... and check if it is near the given point p: 
    return Math.abs(q.x - p.x) <= 1 && Math.abs(q.y - p.y) <= 1; 
} 

Конечно, можно было бы проверить для особых случаев, таких как bx*ay - by*ax == 0.

Обратите внимание, что трудно решить точно, если точка лежит на кривой, потому что координаты точки округлены до целых чисел.

Answer 2

В качестве альтернативного ответа, чтобы обойти проблему, отмеченную Мартином R, вы можете просто построить таблицу поиска и разрешить координаты на кривой. Когда вы создаете кривую, создайте N-точечный массив координат для инкрементных значений t, а затем, когда вам нужно проверить, находится ли координата на кривой, найдите ближайшее значение значение этой координаты, проверив, координата находится в таблице поиска или «почти достаточно» координаты в таблице поиска. В коде:

point[] points = new point[100]; 
for(i=0; i<100; i++) { 
    t = i/100; 
    points[i] = new point(computeX(t), computeY(t)); 
} 

, а затем, когда вам нужно на-кривой тестирование:

for(i=0; i<points.length; i++) { 
    point = points[i]; 
    if(abs(point-coordinate)<3) { 
    // close enough to the curve to count, 
    // so we can use t value map(i,0,100,0,1) 
    } 
} 

строительство СПОИ практически ничего не стоит, так как мы должны построить этот LUT в любом случае, если мы хотим, чтобы нарисовать кривую в все, и вы не собираетесь запускать тест на кривой, не предварительно убедившись, что координата находится даже в ограничивающей рамке кривой.