iOS - Come disegnare un CGPath specifico con CGPoints non ordinate

Question

Considerate questo disegno ASCII:

A _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ D 
|        | 
|        | 
|        | 
|        | 
|        | 
|        | 
|        | 
|        | 
|        | 
|        | 
|        | 
|        | 
|_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _| 
B         C 

punti A, B, C, e D sono noti CGPoints all'interno di un NSMutableArray e sono stati utilizzati per creare un riempito CGPath . Ora consideriamo questo disegno:

A _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ D 
|        | 
|        | 
|        | 
|        | 
|   H _ _ _ I   | 
|    |  |   | 
|    |  |   | 
|  F _ _ _|  |   | 
|  |  G |   | 
|  |   |_ _ _ K | 
|  |   J  |  | 
|  |     |  | 
|_ _ _ _| _ _ _ _ _ _ _ _ |_ _ _| 
B   E    L  C 

CGPoints E, F, G, H, I, J, K e L sono noti e sono stati aggiunti alla fine della NSMutableArray.

La questione

Come posso riorganizzare tutti i punti all'interno della matrice per creare un CGPath che si presenta come il disegno sottostante?

A _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ D 
|        | 
|        | 
|        | 
|        | 
|   H _ _ _ I   | 
|    |  |   | 
|    |  |   | 
|  F _ _ _|  |   | 
|  |  G |   | 
|  |   |_ _ _ K | 
|  |   J  |  | 
|  |     |  | 
|_ _ _ _|     |_ _ _| 
B   E    L  C 

Attualmente non ho problemi a creare un CGPath - se conosco l'ordine del CGpoints - da loop attraverso di loro:

CGPoint firstPoint = [[points objectAtIndex:0] CGPointValue]; 
CGMutablePathRef path = CGPathCreateMutable(); 
CGPathMoveToPoint(path, NULL, firstPoint.x, firstPoint.y); 
for (int i = 0; i < [points count]; i++) 
{ 
    CGPathAddLineToPoint(path, NULL, [[points objectAtIndex:i] CGPointValue].x, [[points objectAtIndex:i] CGPointValue].y); 
} 
CGPathCloseSubpath(path); 

... ma questo presuppone che un linea dovrebbe essere disegnata da ogni punto nell'array i al seguente punto i + 1. Nel disegno sopra, le linee dovrebbero essere disegnate da A → B, B → E, E → F ... K → L, L → C, C → D. Se E non è dopo B e C non è dopo L nell'array (che non saranno), ovviamente questo non verrà disegnato correttamente.

Ulteriori informazioni

1. Tutte le linee vengono disegnate perpendicolari tra loro, in modo che tutti CGPoints dovrebbero condividere un x o y coordinata con la CGPoint prima e dopo di loro.
2. (Un'estensione di # 1) Un punto sarà sempre ad angolo retto rispetto ai punti prima e dopo di esso.
3. Non è possibile prevedere dove si verificheranno i punti all'interno del quadrato e la nuova serie di punti potrebbe essere o meno in ordine quando aggiunta alla fine dell'array.
4. ...

altri layout possibili

A _ _ _ _ _ _ _ K   P _ _ _ D 
|    |   |  | 
|    |   |  | 
|    | N _ _ _|  | 
|    |  |  O | 
|    |_ _ _|   | 
|   L  M   | 
|        | 
|   F _ _ _ G   | 
|    |  |   | 
|    |  |_ _ _ I | 
|    | H  |  | 
|    |   |  | 
|_ _ _ _ _ _ _|   |_ _ _| 
B    E   J  C 


A _ _ _ _ _ _ _ _ _ _ M 
|     |   
|     |   
|     |_ _ _ _ _ _ O 
|     N   | 
|   H _ _ _ I   | 
|    |  |   | 
|    |  |   | 
|  F _ _ _|  |   | 
|  |  G |   | 
|  |   |_ _ _ K | 
|  |   J  |  | 
|  |     |  | 
|_ _ _ _|     |_ _ _| 
B   E    L  C 

Answer 1

Penso che questo potrebbe farlo. L'ho provato con un paio di serie di numeri e sembrava funzionare. Fondamentalmente, comincio con il punto all'indice 0 (qualsiasi punto di partenza dovrebbe funzionare), aggiungilo alla matrice arrangedPoints e poi cerca il punto più vicino con lo stesso valore y - quel punto viene aggiunto a arrangedPoints e cancellato dai punti casuali originali array. Quindi faccio la stessa cosa nella direzione x e ripeto fino a quando rimane un solo punto nell'array di randomPoints, e lo aggiungo alla fine di arrangedPoints.

-(void)arrangePoints:(NSMutableArray *) randomPoints { 
    NSMutableArray *arrangedPoints = [NSMutableArray array]; 
    [arrangedPoints addObject:[randomPoints objectAtIndex:0]]; 
    [randomPoints removeObjectAtIndex:0]; 

    while (randomPoints.count > 1) { 
     //Look for the closest point that has the same y value 
     int yValueOfknownPoint = [[arrangedPoints lastObject] CGPointValue].y; 
     int xValueOfknownPoint = [[arrangedPoints lastObject] CGPointValue].x; 
     NSIndexSet *indSet = [randomPoints indexesOfObjectsPassingTest:^BOOL(id obj, NSUInteger idx, BOOL *stop){ 
      return yValueOfknownPoint == [obj CGPointValue].y; 
     }]; 
     NSLog(@"%d",indSet.count); 

     if (indSet.count == 1) { 
      [arrangedPoints addObject:[randomPoints objectAtIndex:indSet.firstIndex]]; 
      [randomPoints removeObjectAtIndex:indSet.firstIndex]; 
     }else{ 
      __block int min = 10000000; 
      __block int foundIndex; 
      [indSet enumerateIndexesUsingBlock:^(NSUInteger idx, BOOL *stop) { 
       int posibleMin = fabs(xValueOfknownPoint - [[randomPoints objectAtIndex:idx]CGPointValue].x); 
       if (posibleMin < min) { 
        min = posibleMin; 
        foundIndex = idx; 
       } 
      }]; 
      [arrangedPoints addObject:[randomPoints objectAtIndex:foundIndex]]; 
      [randomPoints removeObjectAtIndex:foundIndex]; 
     } 

     //Look for the closest point that has the same x value 
     xValueOfknownPoint = [[arrangedPoints lastObject] CGPointValue].x; 
     yValueOfknownPoint = [[arrangedPoints lastObject] CGPointValue].y; 
     indSet = [randomPoints indexesOfObjectsPassingTest:^BOOL(id obj, NSUInteger idx, BOOL *stop){ 
      return xValueOfknownPoint == [obj CGPointValue].x; 
     }]; 

     if (indSet.count == 1) { 
      [arrangedPoints addObject:[randomPoints objectAtIndex:indSet.firstIndex]]; 
      [randomPoints removeObjectAtIndex:indSet.firstIndex]; 
     }else{ 
      __block int min = 10000000; 
      __block int foundIndex; 
      [indSet enumerateIndexesUsingBlock:^(NSUInteger idx, BOOL *stop) { 
       int posibleMin = fabs(yValueOfknownPoint - [[randomPoints objectAtIndex:idx]CGPointValue].y); 
       if (posibleMin < min) { 
        min = posibleMin; 
        foundIndex = idx; 
       } 
      }]; 
      [arrangedPoints addObject:[randomPoints objectAtIndex:foundIndex]]; 
      [randomPoints removeObjectAtIndex:foundIndex]; 
     } 
    } 
    [arrangedPoints addObject:randomPoints.lastObject]; 
    NSLog(@"%@",arrangedPoints); 

} 

Alcuni punti aggiunti per affrontare i problemi noti:

Per far fronte a punti equidistanti come G e M da N, penso che vorrei mantenere i set di punti separano - piuttosto che mettere ogni cosa in uno array, manterrei il rettangolo originale e ogni nuova serie di punti che vengono separati. Poi, mentre stavo costruendo i percorsi, guardavo solo il punto all'interno del mio insieme di punti o del rettangolo originale, ma non in nessun altro insieme di punti.

Per risolvere il problema di inwit up, di raddoppiarsi su se stesso, penso che si dovrebbe determinare se un insieme di punti interseca un lato o un angolo - penso che solo gli angoli presenterebbero quel problema. Si può verificare per un angolo vedendo che 2 dei punti cadono su 2 diverse linee del rettangolo originale (piuttosto che sulla stessa linea). Dovresti quindi calcolare il punto mancante (un punto putativo nel tuo ultimo esempio sopra) e vedere a quale punto del rettangolo originale è identico, e quindi eliminare quel punto dal percorso. Penso che il mio algoritmo funzionerebbe correttamente.

Answer 2

Va bene, questo può sembrare un algoritmo molto complicato (ed è tutt'altro che ottimale), ma mi piacerebbe avvicinano come questo.

1. Find the point(s) with lowest X-value 

2. Of those points find point P (using a loop) such that: 
    - P has a nabour N with the same X-value 
    - There exists no other point that vertically lies between P and its nabour N with the same Y value 
    (if no P exists with a nabour, the algorithm has ended, after joining P with its horizontally aligned point) 

3. If there exists a point with the same X value as P (horizontally aligned), join that point and P with a line. 

4. Now join point P with its nabour N 

5. Find all points with the same X-value as N (horizontally aligned) 

6. Goto 2 

Spero che funzioni (non l'ho testato).

Answer 3

Ecco un approccio (in pseudocodice) se tutto quello che ci interessa è riempimenti e non colpi:

1. creare un percorso mutevole vuoto utilizzando CGPathCreateMutable().

2. Aggiungere la figura rettangolare originale al percorso mutabile come un anello chiuso.

3. Uno per uno, aggiungere ciascuna delle figure irregolari aggiuntive al percorso mutabile, separatamente, come un anello chiuso.

4. Utilizzare la funzione CGContextEOFillPath() per riempire la figura eroso utilizzando il pari-dispari regola di riempimento.

La regola di riempimento pari-dispari è descritta nella sezione Filling a Path nel Quartz 2D Programming Guide.

Potreste anche essere interessati a this