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

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());
 }

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

• Подробности с апплетами
• Обсуждение более продвинутых методов пересечения (PDF)