Detección de aciertos al dibujar líneas en iOS

Question

Me gustaría permitir al usuario dibujar curvas de tal manera que ninguna línea pueda cruzar otra línea o incluso a sí misma. Dibujar las curvas no es un problema, e incluso descubrí que puedo crear una ruta que esté cerrada y que siga siendo bastante parecida a una línea, rastreando los nodos de la línea hacia delante y hacia atrás y luego cerrando la ruta.

Desafortunadamente, iOS solo proporciona una prueba de si un punto está contenido en una ruta cerrada (containsPoint: y CGPathContainsPoint). Desafortunadamente, un usuario puede mover sus dedos bastante rápido lo suficiente como para que los puntos de contacto aterricen en ambos lados de una ruta existente sin que en realidad estén contenidos en esa ruta, por lo que probar los puntos de contacto es bastante inútil.

No encuentro ningún método de "intersección" de caminos.

¿Alguna otra idea sobre cómo llevar a cabo esta tarea?

Answer 1

Bueno, se me ocurrió una forma de hacer esto. Es imperfecto, pero pensé que otros querrían ver la técnica, ya que esta pregunta se votó un par de veces. La técnica que utilicé dibuja todos los elementos para probar en un contexto de mapa de bits y luego dibuja el nuevo segmento de la línea progresiva en otro contexto de mapa de bits. Los datos en esos contextos se comparan utilizando operadores bit a bit y si se encuentra una superposición, se declara un acierto.

La idea detrás de esta técnica es probar cada segmento de una línea recién dibujada contra todas las líneas dibujadas anteriormente e incluso contra piezas anteriores de la misma línea. En otras palabras, esta técnica detectará cuándo una línea cruza otra línea y también cuándo cruza sobre sí misma.

Una aplicación de ejemplo que demuestra que la técnica está disponible: LineSample.zip.

El núcleo de las pruebas de detección se realiza en mi objeto LineView. Aquí hay dos métodos clave:

- (CGContextRef)newBitmapContext { 

    // creating b&w bitmaps to do hit testing 
    // based on: http://robnapier.net/blog/clipping-cgrect-cgpath-531 
    // see "Supported Pixel Formats" in Quartz 2D Programming Guide 
    CGContextRef bitmapContext = 
    CGBitmapContextCreate(NULL, // data automatically allocated 
          self.bounds.size.width, 
          self.bounds.size.height, 
          8, 
          self.bounds.size.width, 
          NULL, 
          kCGImageAlphaOnly); 
    CGContextSetShouldAntialias(bitmapContext, NO); 
    // use CGBitmapContextGetData to get at this data 

    return bitmapContext; 
} 


- (BOOL)line:(Line *)line canExtendToPoint:(CGPoint) newPoint { 

    // Lines are made up of segments that go from node to node. If we want to test for self-crossing, then we can't just test the whole in progress line against the completed line, we actually have to test each segment since one segment of the in progress line may cross another segment of the same line (think of a loop in the line). We also have to avoid checking the first point of the new segment against the last point of the previous segment (which is the same point). Luckily, a line cannot curve back on itself in just one segment (think about it, it takes at least two segments to reach yourself again). This means that we can both test progressive segments and avoid false hits by NOT drawing the last segment of the line into the test! So we will put everything up to the last segment into the hitProgressLayer, we will put the new segment into the segmentLayer, and then we will test for overlap among those two and the hitTestLayer. Any point that is in all three layers will indicate a hit, otherwise we are OK. 

    if (line.failed) { 
     // shortcut in case a failed line is retested 
     return NO; 
    } 
    BOOL ok = YES; // thinking positively 

    // set up a context to hold the new segment and stroke it in 
    CGContextRef segmentContext = [self newBitmapContext]; 
    CGContextSetLineWidth(segmentContext, 2); // bit thicker to facilitate hits 
    CGPoint lastPoint = [[[line nodes] lastObject] point]; 
    CGContextMoveToPoint(segmentContext, lastPoint.x, lastPoint.y); 
    CGContextAddLineToPoint(segmentContext, newPoint.x, newPoint.y); 
    CGContextStrokePath(segmentContext); 

    // now we actually test 
    // based on code from benzado: http://stackoverflow.com/questions/6515885/how-to-do-comparisons-of-bitmaps-in-ios/6515999#6515999 
    unsigned char *completedData = CGBitmapContextGetData(hitCompletedContext); 
    unsigned char *progressData = CGBitmapContextGetData(hitProgressContext); 
    unsigned char *segmentData = CGBitmapContextGetData(segmentContext); 

    size_t bytesPerRow = CGBitmapContextGetBytesPerRow(segmentContext); 
    size_t height = CGBitmapContextGetHeight(segmentContext); 
    size_t len = bytesPerRow * height; 

    for (int i = 0; i < len; i++) { 
     if ((completedData[i] | progressData[i]) & segmentData[i]) { 
      ok = NO; 
      break; 
     } 
    } 

    CGContextRelease(segmentContext); 

    if (ok) { 
     // now that we know we are good to go, 
     // we will add the last segment onto the hitProgressLayer 
     int numberOfSegments = [[line nodes] count] - 1; 
     if (numberOfSegments > 0) { 
      // but only if there is a segment there! 
      CGPoint secondToLastPoint = [[[line nodes] objectAtIndex:numberOfSegments-1] point]; 
      CGContextSetLineWidth(hitProgressContext, 1); // but thinner 
      CGContextMoveToPoint(hitProgressContext, secondToLastPoint.x, secondToLastPoint.y); 
      CGContextAddLineToPoint(hitProgressContext, lastPoint.x, lastPoint.y); 
      CGContextStrokePath(hitProgressContext); 
     } 
    } else { 
     line.failed = YES; 
     [linesFailed addObject:line]; 
    } 
    return ok; 
} 

Me encantaría escuchar sugerencias o ver mejoras. Por un lado, sería mucho más rápido comprobar únicamente el rectificador del nuevo segmento en lugar de verlo todo.