Обнаружение самопересечения в замкнутых кривых Безье - PullRequest
Новая
       78

Обнаружение самопересечения в замкнутых кривых Безье

10 голосов
/ 26 января 2010

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

Одна идея, которая у меня возникла, состояла в том, чтобы использовать FlatteningPathIterator, чтобы разложить фигуру на отрезки прямых линий, а затем определить, пересекается ли данный сегмент с другим, но мне было бы интересно узнать, есть ли лучший подход (поскольку иметь квадратичную производительность). Если я продолжу этот метод, существуют ли в Java библиотечные функции для определения перекрытия двух отрезков?

Спасибо.

Нет перехода

Нет кроссовера http://www.freeimagehosting.net/uploads/7ad585414d.png

Cross-Over

Кроссовер http://www.freeimagehosting.net/uploads/823748f8bb.png

Ответы [ 5 ]

4 голосов
/ 26 января 2010

Я действительно нашел рабочее решение, которое использует встроенные функции 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);
}
}
2 голосов
/ 26 января 2010

Что вы можете сделать, это взять векторную функцию для кривой Безье :

alt text

И сравните различные кривые Безье, которые составляют вашу кривую в парах, чтобы увидеть, есть ли решение в [0,1]. Конечно, это поможет в случае, когда части, которые перекрываются, являются частью разных кривых. Это не поможет в случае, когда одна кривая пересекает себя ...

РЕДАКТИРОВАТЬ:

Я процитировал функцию квадратичной кривой, так что это куб: alt text

И это действительно трудно решить уравнение. В качестве альтернативы я предлагаю использовать более свободный метод. То, что вы можете сделать, это «разбить» каждую кривую на n точек и рассчитать их положение, используя функцию выше. Затем для каждой из этих точек вы будете рассматривать диск произвольного радиуса (в зависимости от размеров кривых) и искать точки пересечения этих дисков. Вам нужно будет игнорировать пересечения последовательных дисков, поскольку они пересекаются только потому, что они лежат слишком близко друг к другу на одном сегменте кривой.

Этот метод должен быть очень быстрым, но вы можете потерять точность, если выберете «неправильные» параметры (размер n и радиус), но можете поэкспериментировать.

1 голос
/ 26 января 2010

Я думаю, что вы можете получить приличное приближение к

  • Использование FlatteningPathIterator для получения многоугольника, который приближается к BLOB-объекту.
  • Разделение пути вокруг многоугольника на подпути неубывающего y (то есть нисходящие пути - представьте, что вы рисуете многоугольник, используя только движения карандаша вниз).
  • Идти по нисходящим путям согласованно, сравнивая каждый отрезок линии только с отрезками, которые как минимум перекрываются в измерении y .

Это довольно просто и позволяет избежать производительности O ( n 2 ), о которой вы беспокоитесь. Для вашего среднего базового блоба, как и на вашем рисунке, есть только два нисходящих пути.

Вы можете еще больше сократить количество сравнений, сохранив нисходящие пути, отсортированные по горизонтали по ходу (возможно, TreeSet).

Другой способ сравнения только отрезков, которые перекрываются в измерении y , - это использование дерева интервалов .

1 голос
/ 26 января 2010

Я не уверен, поможет ли это, но это похоже на проблему в рендеринге полигонов, где для каждой строки сканирования Y имеется массив пар значений (X, флаг), где линии пересекают эту строку сканирования.

Следуйте за каждой кривой в форме, и где она пересекает каждую линию сканирования Y, запишите (X, флаг), где flag = 1, если "север", и flag = -1, если "юг".

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

Если все промежутки равны +1 или все промежутки равны -1, кривая не пересекает себя.

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

0 голосов
/ 27 января 2010

Вот некоторый рекурсивный алгоритм из лекции Проф. Георг Умлауф 

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.

...