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

Ответ 1

Я действительно нашел рабочее решение, которое использует встроенные функции 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

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

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

EDIT:

Я цитировал функцию квадратичной кривой, так что это кубическая:

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

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

Ответ 3

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

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

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

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

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

Ответ 4

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

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

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

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

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

Ответ 5

Здесь некоторый рекурсивный алгоритм из лекции Prof. Георг Умлауф

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.