Я бы сказал, что самый простой и, вероятно, самый быстрый ответ - это разделить их на очень маленькие линии и найти точки, где кривые пересекаются, если они на самом деле.
public static void towardsCubic(double[] xy, double x0, double y0, double x1, double y1, double x2, double y2, double x3, double y3, double t) {
double x, y;
x = (1 - t) * (1 - t) * (1 - t) * x0 + 3 * (1 - t) * (1 - t) * t * x1 + 3 * (1 - t) * t * t * x2 + t * t * t * x3;
y = (1 - t) * (1 - t) * (1 - t) * y0 + 3 * (1 - t) * (1 - t) * t * y1 + 3 * (1 - t) * t * t * y2 + t * t * t * y3;
xy[0] = x;
xy[1] = y;
}
public static void towardsQuad(double[] xy, double x0, double y0, double x1, double y1, double x2, double y2, double t) {
double x, y;
x = (1 - t) * (1 - t) * x0 + 2 * (1 - t) * t * x1 + t * t * x2;
y = (1 - t) * (1 - t) * y0 + 2 * (1 - t) * t * y1 + t * t * y2;
xy[0] = x;
xy[1] = y;
}
Очевидно, что грубая сила ответаплохой Смотрите ответ bo {4}, и есть много линейной геометрии и обнаружение столкновений, которые действительно очень помогут.
Выберите количество срезов, которое вы хотите для кривых.Что-то вроде 100 должно быть здорово.
Мы берем все сегменты и сортируем их по наибольшему значению y, которое они имеют.Затем мы добавляем второй флаг в список для наименьшего значения y для этого сегмента.
Мы сохраняем список активных ребер.
Перебираем отсортированный по y список сегментов, когда мы сталкиваемся с ведущим сегментом, мы добавляем его в активный список.Когда мы нажимаем на значение, помеченное маленьким-y, мы удаляем этот сегмент из активного списка.
Затем мы можем просто перебрать весь набор сегментов с тем, что составляет строку сканирования, монотонно увеличивая наш y по мере того, как мыпросто повторить список.Мы перебираем значения в нашем отсортированном списке, который обычно удаляет один сегмент и добавляет новый сегмент (или для узлов разделения и слияния, добавление двух сегментов или удаление двух сегментов).Таким образом, ведется активный список соответствующих сегментов.
Мы запускаем быструю проверку пересечения при сбое, так как добавляем новый активный сегмент в список активных сегментов только для этого сегмента и для текущих активных сегментов.
Таким образом, мы всегда точно знаем, какие отрезки линий являются релевантными, поскольку мы повторяем выборочные сегменты наших кривых.Мы знаем, что эти сегменты частично совпадают в координатах y.Мы можем быстро потерпеть неудачу в любом новом сегменте, который не перекрывается в отношении его x-координат.В том редком случае, когда они перекрываются в x-координатах, мы затем проверяем, пересекаются ли эти отрезки.
Это, вероятно, уменьшит количество проверок пересечения линий в основном до количества пересечений.
foreach(segment in sortedSegmentList) {
if (segment.isLeading()) {
checkAgainstActives(segment);
actives.add(segment);
}
else actives.remove(segment)
}
checkAgainstActive () просто проверит, перекрывают ли этот сегмент и какой-либо сегмент в активном списке свои x-координаты, если они это сделают, затем запустит проверку пересечения строк и предпримет соответствующее действие.
Также обратите внимание, что это будет работать для любого количества кривых, любого типа кривых, любого порядка кривых, в любой смеси.И если мы переберем весь список сегментов, он найдет все пересечения.Он обнаружит, что каждая точка Безье пересекает окружность или каждое пересечение, которое дюжина квадратичных кривых Безье имеет друг с другом (или с собой), и все в одну и ту же долю секунды.
Часто цитируемое Глава 7документ отмечает, для алгоритма подразделения:
"После того, как пара кривых была разделена настолько, что каждая из них может быть аппроксимирована отрезком линии с точностью до допуска"
Мы можембуквально просто пропустить посредника.Мы можем сделать это достаточно быстро, чтобы просто сравнить отрезки с допустимым количеством ошибок на кривой.В конце концов, это то, что делает типичный ответ.
Во-вторых, обратите внимание, что основная часть скорости увеличивается здесь для обнаружения столкновений, а именно упорядоченный список сегментов, отсортированных по их наибольшему y подобавить к активному списку, а наименьший у удалить из активного списка, можно также сделать непосредственно для многоугольников оболочки кривой Безье.Наш отрезок прямой - это просто многоугольник порядка 2, но мы можем сделать любое количество точек так же тривиально, и отметив ограничивающий прямоугольник всех контрольных точек в любом порядке кривой, с которой мы имеем дело.Таким образом, вместо списка активных сегментов, у нас будет список точек активных полигонов корпуса.Мы могли бы просто использовать алгоритм Де Кастельжау, чтобы разделить кривые, таким образом выбирая их как подразделяемые кривые, а не отрезки.Таким образом, вместо 2 баллов у нас было бы 4 или 7 или еще много чего, и мы выполняем ту же самую процедуру, будучи весьма склонными к быстрому провалу.
Добавление соответствующей группы точек в точке max y, удаление ее в точке min y и сравнение только активного списка. Таким образом, мы можем быстрее и лучше реализовать алгоритм подразделения Безье. Просто найдя перекрывающие рамки, затем разделив те кривые, которые перекрываются, и удалив те, которые не попали. Как, опять же, мы можем сделать любое количество кривых, даже те, которые подразделяются на кривые в предыдущей итерации. И, как в нашем приближении сегмента, очень быстро решить для каждой позиции пересечения сотни различных кривых (даже разных порядков). Просто проверьте все кривые, чтобы увидеть, перекрывают ли ограничивающие рамки, если они есть, мы подразделяем их до тех пор, пока наши кривые не станут достаточно маленькими или у нас не закончились