Rilevamento di autotransferimento in curve chiuse di Bezier

Question

Ho creato una forma "blob" rappezzando insieme le curve cubiche di Bezier (schermata seguente). Mi piacerebbe essere in grado di rilevare la situazione in cui una curva ha attraversato se stessa o un'altra curva e si chiedeva se c'è un approccio raccomandato o un algoritmo noto per farlo?

Un'idea che avevo era di usare uno FlatteningPathIterator per scomporre la forma in segmenti di linea retta e quindi rilevare se un dato segmento si incrocia con un altro, ma sarei interessato se c'è un approccio migliore (come questo avrà prestazione quadratica). Se seguo questo metodo ci sono funzioni di libreria in Java per rilevare se due segmenti di linea si sovrappongono?

Grazie.

No Cross-Over

No Crossover http://www.freeimagehosting.net/uploads/7ad585414d.png

Cross-Over

Crossover http://www.freeimagehosting.net/uploads/823748f8bb.png

Answer 1

ho effettivamente trovato una soluzione di lavoro che sta usando costruito nel funzioni Java2D ed è estremamente veloce ...

È sufficiente creare un Path2D dalle vostre curve, quindi creare una zona fuori della vostra Path2D e invocare il metodo Area.isSingular();

Funziona ... Vedere questo piccolo esempio.

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

Answer 2

Che cosa si può fare è prendere la funzione di vettore per il Bezier curve:

E uguaglia le diverse curve di bezier che formano la curva in coppie per vedere se esiste una soluzione in [0,1]. Naturalmente ciò aiuterebbe nel caso in cui le parti che si sovrappongono fanno parte di curve diverse. E non aiuterà nel caso in cui una curva stessa interseca ...

EDIT:

ho citato la funzione curva quadratica quindi questo è il cubo:

Ed è davvero difficile da risolvere l'equazione. In alternativa, propongo di utilizzare un metodo più libero. Quello che puoi fare è "dividere" ogni curva in n punti e calcolare la loro posizione usando la funzione sopra. Quindi per ognuno di questi punti considererai un disco di raggio arbitrario (a seconda delle dimensioni delle curve) e cercherai le intersezioni di questi dischi. Dovrai ignorare le intersezioni dei dischi sequenziali dall'intersezione solo perché si trovano troppo vicine l'una all'altra su un singolo segmento di curva.

Questo metodo deve essere molto veloce ma è possibile perdere la precisione se si selezionano i parametri "errati" (la dimensione n e il raggio) ma è possibile sperimentare.

Answer 3

Non sono sicuro se questo aiuti, ma è simile a un problema nel rendering di poligoni, dove si ha, per ogni linea di scansione Y, una matrice di coppie di valori (X, bandiera) dove le linee attraversano quella linea di scansione .

Seguire ogni curva nella forma e dove attraversa ogni linea di scansione Y, registrare (X, bandiera) dove flag = 1 se si va "nord" e flag = -1 se si va "sud".

Se su ciascuna linea di scansione si considerano le coppie in ordine X e si mantiene una somma parziale dei valori dell'indicatore, la somma tra uno span di due valori X sarà positiva se la curva è in senso orario e negativa se il la curva è in senso antiorario.

Se tutti gli intervalli sono +1 o tutti gli intervalli sono -1, la curva non si incrocia.

Modifica: questo richiede un tempo lineare nel numero di linee di scansione attraversate dalla figura. Quindi la struttura dati risultante può essere utilizzata per il rendering della figura.

Answer 4

penso che si può ottenere un'approssimazione decente

• Utilizzando FlatteningPathIterator per ottenere un poligono che approssima il blob.
• Divisione del tracciato attorno al poligono in sottotraccia di nondecrescimento y (ovvero, percorsi verso il basso — immaginare di disegnare il poligono usando solo tratti discendenti della matita).
• Camminando i percorsi verso il basso di concerto, confrontando ogni segmento di linea solo con segmenti di linea che si sovrappongono almeno nella dimensione y.

questo è abbastanza semplice ed evita la O (n ) prestazioni siete preoccupati. Per il tuo blob di base medio, come quelli nella tua illustrazione, ci sono solo due percorsi verso il basso.

È possibile ridurre ulteriormente il numero di confronti mantenendo i percorsi verso il basso ordinati orizzontalmente mentre si va (a TreeSet, forse).

Un altro modo per confrontare solo i segmenti di linea che si sovrappongono nella dimensione y consiste nell'utilizzare un interval tree.

Answer 5

Ecco qualche algoritmo ricorsivo da una conferenza di Prof. Georg Umlauf

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

dove delta^2(b_i) è definito come b_{i+2} - 2*b_{i+1} + b_i.