Come determinare se l'insieme di coordinate ordinate forma una curva semplice?

Potresti argomentare che una curva è semplice se non ci sono due segmenti di linea tra i punti in modo tale che le linee si incrocino, il che significa che puoi verificare se una curva è semplice verificando l'assenza di questa condizione.

L'algoritmo sarebbe simile a:

for each p1, p2 in pointlist
  for each p3, p4 in pointlist
     if line_segment(p1, p2) intersects line_segment(p3, p4)
        return false
return true   

Si noti che p2 sarebbe il punto successivo dopo p1 e analogamente, p4 sarebbe il punto successivo dopo p3. Per evitare la ridondanza, i punti p3 e p4 potrebbero iniziare dopo i punti p1 e p2. Questo dovrebbe essere fatto facilmente in tempo O (n ^ 2). Fai attenzione al tuo controllo per l'intersezione poiché almeno una volta le linee saranno uguali (nessuna divisione per zero).

Se hai molti di questi punti, puoi saltare ogni altro punto e questo algoritmo sarà eseguito 4 volte più velocemente con il minimo rischio che una linea veramente intersecante non venga rilevata se la curva si avvicina a una tangente.

Puoi controllare ogni coppia di punti P[i],P[i+1] rispetto a ogni coppia di punti P[j],P[j+1]

Se uno qualsiasi dei segmenti di linea che creano si intersecano, la curva non è semplice.

Controlla in modo ingannevole ogni riga:

for(int i = 0; i < n-3; i++)
    for(int j = i+2; j < n-1; j++)
        if(doIntersect(new Line(P[i],P[i+1]), new Line(P[j],P[j+1]));

Salto il controllo di P[i],P[i+1] rispetto a P[i+1],P[i+2] perché si intersecano sempre sull'endpoint P[i+1]

Questo algoritmo può essere velocizzato ordinando l'elenco dei segmenti per x la maggior parte di sinistra e quindi solo le linee che hanno un punto finale a sinistra della x più a destra del segmento corrente.

Il concetto potrebbe essere semplice, ma ci sono molti dettagli diabolici.

Per cominciare, devi stabilire che i numeri che rappresentano i punti sono esatti, non approssimazioni ad alcune curve reali e che il contorno consiste di segmenti di retta, non di una curva attuale.

Secondo, le condizioni al contorno sono ovunque; se la linea AB tocca la linea DEF solo al punto E, conta come una croce o no? È necessario considerare la geometria complessiva del figura. Si consideri una figura a forma di "C" con uno pseudopodo che si estende dalla parte posteriore, intorno per entrare nella "bocca" del C, e ora gradualmente chiudere le fauci della C per incontrarsi in un singolo punto.