Обнаружение сам пересекающийся в закрытых кривых Безье
Я создал форму «капли», соединив кубические кривые Безье (скриншот ниже). Я хотел бы иметь возможность обнаружить ситуацию, где кривая пересекла или его или другую кривую и задавалась вопросом, есть ли рекомендуемый подход или известный алгоритм для того, чтобы сделать это?
Одна идея, которую я имел, состояла в том, чтобы использовать a FlatteningPathIterator разложить форму на сегменты прямой линии и затем обнаружить, пересекается ли данный сегмент с другим, но я интересовался бы тем, есть ли лучший подход (поскольку у этого будет квадратная работа). Если я действительно преследую этот метод, там функции библиотеки на Яве, чтобы обнаружить, накладываются ли два линейных сегмента?
Спасибо.
Никакой переход
Никакой переход http://www.freeimagehosting.net/uploads/7ad585414d.png
Переход
Переход http://www.freeimagehosting.net/uploads/823748f8bb.png
5 ответов
На самом деле я нашел рабочее решение, которое использует встроенные функции Java2D и является ЭКСТРЕМЕННО быстрым...
Просто создайте Path2D из кривых, затем создайте область из Path2D и вызовите метод Area.isSingular();
Он работает..... Смотрите этот небольшой пример.
import java.awt.Color;
import java.awt.Dimension;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.geom.Area;
import java.awt.geom.CubicCurve2D;
import java.awt.geom.Path2D;
import javax.swing.JFrame;
import javax.swing.JPanel;
public class Test {
@SuppressWarnings("serial")
public static void main(String[] args) {
JFrame f = new JFrame("Test");
JPanel c = new JPanel() {
Area a;
Path2D p;
{
p = new Path2D.Double();
p.append(new CubicCurve2D.Double(0, 0, 100, 0, 150, 50, 200, 100), true);
p.append(new CubicCurve2D.Double(200, 100, 200, 150, 150,0, 50, 100), true);
p.append(new CubicCurve2D.Double(100, 100, 100, 50, 50, 50, 0, 0), true);
a = new Area(p);
setPreferredSize(new Dimension(300, 300));
}
@Override
protected void paintComponent(Graphics g) {
g.setColor(Color.black);
((Graphics2D)g).fill(p);
System.out.println(a.isSingular());
}
};
f.setContentPane(c);
f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
f.pack();
f.setVisible(true);
}
}
Что вы можете сделать, это сделать векторную функцию для кривой Безье :
и приравнивайте различные кривые Bezier, которые составляют вашу кривую в пары, чтобы увидеть, если там есть это решение в [0,1]. Конечно, это поможет в том случае, если части, которые перекрываются, являются частью разных кривых. Он не поможет в том случае, когда одна кривая пересекается сама ...
Редактировать:
Я процитировал функцию квадратичной кривой, чтобы это кубическая:
И действительно трудно решить уравнение. В качестве альтернативы я предлагаю использовать более свободный метод. То, что вы можете сделать, это «разделить» каждую кривую в n указывает и рассчитать их положение с помощью функции выше. Затем для каждого из этих моментов вы рассмотрите диск произвольного радиуса (в зависимости от размеров кривых) и поиск пересечений этих дисков. Вам нужно будет игнорировать пересечения последовательных дисков, поскольку пересекаются только потому, что они лгут слишком близко друг к другу на одной кривой сегменте.
Этот метод должен быть очень быстрым, но вы можете потерять точность, если вы выберете «неправильные» параметры (размер n и радиус), но вы можете поэкспериментировать.
Я не уверен, что это поможет, но это похоже на проблему в рендеринге многоугольника, где у вас есть, для каждой линии сканирования Y, массивных пар (X, FLAG) где линии пересекают эту сканирующую линию.
Следуйте за каждой кривой в форме, и где она пересекает каждую строку сканирования y, запись (X, флаг), где флаг = 1, если идти «Север» и флаг = -1, если идти «Юг».
Если на каждой строке сканирования вы рассмотрите пары в X порядка, и сохраняйте работу значений флага, то сумма между диапазоном двух значений X будет положительной, если кривая по часовой стрелке, а отрицательная, если кривая против часовой стрелки.
Если все пробелы +1 или все промежутки -1, кривая не пересекается.
Править: Это требует времени линейного в количестве строк сканирования, пересекаемых на рисунке. Затем полученную структуру данных можно использовать для визуализации рисунка.
Я думаю, что вы можете получить приличное приближение
- , используя
с использованием, чтобы получить многоугольник, чтобы получить многоугольник, который приближается к BLOB. - Разделить путь вокруг многоугольника в подпункты недействия y (то есть нисходящих путей - представьте, рисуют многоугольник, используя только пониженные удары карандаша).
- Ходить по нисходящим путям на концерте, сравнивая каждую сегмент линии только с линейными сегментами, которые, по крайней мере, перекрываются в измерении Y .
Это довольно просто и позволяет избежать o ( n 2 ), вы беспокоитесь о. Для вашего среднего базового BLOB, вроде те на своей иллюстрации, есть только два потяжного пути.
Вы можете уменьшить количество сравнений, сохраняя отсортированные пути к горизонтально, когда вы идете (A Treet , возможно).
Другой способ сравнить только сегменты линии, которые перекрываются в измерении y - использовать интервальное дерево .
Здесь некоторые рекурсивный алгоритм от лекции проф. Георг Умлауф
INTERSECT(b_0,...,b_m;c_0,...,c_n, EPSILON)
if [min b_i, max b_i] AND [min c_i, max c_i] != EMPTY { // check bounding boxes
if m*(m-1)*max||delta^2(b_i)|| > EPSILON) { // check flatness
Calculate b'_0, ..., b'_2m over [0, 0.5, 1] with the deCasteljau algorithm;
INTERSECT(b'_0,...,b'_m;c_0,...,c_n;EPSILON);
INTERSECT(b'_m,...,b'_2m;c_0,...,c_n;EPSILON);
}
}
else {
if (n*n-1)*max||delta^2(c_i)|| > EPSILON then {
Calculate c'_0, ..., c'_2m over [0, 0.5, 1] with the deCasteljau algorithm;
INTERSECT(b_0,...,b_m;c'_0,...,c'_n;EPSILON);
INTERSECT(b_0,...,b_m;c'_n,...,c'_2n;EPSILON);
}
else {
Intersect line segments b_0b_m and c_0c_n;
}
}
, где DELTA ^ 2 (B_i) определяется как b_ {i + 2} - 2 * b_ {i + 1} + b_i .