Как я могу выполнить геометрию расширенных операций по траекториям безье?

Question

У меня есть библиотека, которая рисует обычные фигуры траектории безье (сложные пути, образованные из множества точек безье), используя мидпойнт-аппроксимацию.

Я могу нарисовать их без проблем, но мне нужно добавить поддержку для расширенных операций геометрии: ближайшая точка кривой, пересечение, фигура содержит точку и, что более важно, комбинации путей: разность, пересечение, исключение или, союз, ...

Есть ли хороший источник, чтобы получить все это?

Благодаря

Answer 1

Я должен был выполнить некоторые из этих операций на кривых или замкнутых путей. В основном это сводится к линейным и многоугольным операциям. Несколько полезных концепций:

1. Контрольные точки образуют выпуклую оболочку вокруг пути Безье, что полезно для операций, связанных с пересечением коротких замыканий.
2. Ваше подразделение кривой должно быть адаптивным, останавливаясь, когда следующее подразделение не будет существенным различием, что означает, что каждая «половина» может разделиться на другую глубину.
3. Вы можете разделить кривую в любой точке, а не только на среднюю точку, которая полезна для создания субкуры Безье, заканчивающейся в найденной точке интереса.

Пример кода для произвольного разбиения:

static Point2D.Double[][] splitBezier(Point2D.Double[] p) { 
    return splitBezier(p, 0.5); 
} 

static Point2D.Double[][] splitBezier(Point2D.Double[] p, double t) { 
    Point2D.Double[][] parts = new Point2D.Double[2][4]; 
    Point2D.Double ab = interpolate(t, p[0], p[1]); 
    Point2D.Double bc = interpolate(t, p[1], p[2]); 
    Point2D.Double cd = interpolate(t, p[2], p[3]); 
    Point2D.Double abc = interpolate(t, ab, bc); 
    Point2D.Double bcd = interpolate(t, bc, cd); 
    Point2D.Double abcd = interpolate(t, abc, bcd); 
    parts[0][0] = p[0]; 
    parts[0][1] = ab; 
    parts[0][2] = abc; 
    parts[0][3] = abcd; 
    parts[1][0] = abcd; 
    parts[1][2] = bcd; 
    parts[1][2] = cd; 
    parts[1][3] = p[3]; 
    return parts; 
} 

static Point2D.Double interpolate(double t, Point2D.Double a, Point2D.Double b) { 
    return new Point2D.Double((1 - t) * a.getX() + t * b.getX(), 
           (1 - t) * a.getY() + t * b.getY()); 
} 

Некоторые полезные сайты:

• Details with applets
• Discussion of more advanced intersection methods (PDF)