MKPolyline detect self-intersecting line OBJECTIVE C

Question

How can I detect if an MKPolyline intersects itself? I tried researching this but only found problems that has two or more lines. How can I detect if I only have one line/one stroke? I want to detect it after the user releases the touch.

I currently have this code in touchEnded function.

            CGPoint location = [touch locationInView:self.mapView];
            CLLocationCoordinate2D coordinate = [self.mapView convertPoint:location toCoordinateFromView:self.mapView];
            [self.coordinates addObject:[NSValue valueWithMKCoordinate:coordinate]];
            NSInteger numberOfPoints = [self.coordinates count];

            if(numberOfPoints > 2)
            {
                [self setLineLength:[self getLengthArea]];
                if([self lineLength] < 401)
                {
                    if (numberOfPoints > 2)
                    {
                        CLLocationCoordinate2D points[numberOfPoints];
                        for (NSInteger i = 0; i < numberOfPoints; i++) {
                            points[i] = [self.coordinates[i] MKCoordinateValue];
                        }
                        [self.mapView addOverlay:[MKPolyline polylineWithCoordinates:points count:numberOfPoints]];
                    }

                    PCAnnotation *ann = [[PCAnnotation alloc] init];
                    [ann setCoordinate:coordinate];
                    ann.title = @"End";
                    [self.mapView addAnnotation:ann];
                }
                else
                {
                    NSArray *overlayItems = [self.mapView overlays];
                    NSArray *annotations = [self.mapView annotations];
                    [self.mapView removeOverlays:overlayItems];
                    [self.mapView removeAnnotations:annotations];
                }

            }

Answer 1

MKPolyline inherits form MKMultiPoint which has a - (MKMapPoint *)points; method,

You could try to check for intersections between all line segments.

"The points are connected end-to-end in the order they are provided."

So you can make your own line segments between each 2 points, and after you have an Array of line segments you can check for their intersections.

Here is a C++ code snippet for checking the intersections: It can be easily translated to Objective-C and whatever else.

public static bool LineSegmentsCross(Vector2 a, Vector2 b, Vector2 c,     Vector2 d)
{
     float denominator = ((b.X - a.X) * (d.Y - c.Y)) - ((b.Y - a.Y) * (d.X - c.X));

     if (denominator == 0)
     {
          return false;
     }

     float numerator1 = ((a.Y - c.Y) * (d.X - c.X)) - ((a.X - c.X) * (d.Y - c.Y));

     float numerator2 = ((a.Y - c.Y) * (b.X - a.X)) - ((a.X - c.X) * (b.Y - a.Y));

     if (numerator1 == 0 || numerator2 == 0)
     {
          return false;
     }

     float r = numerator1 / denominator;
     float s = numerator2 / denominator;

     return (r > 0 && r < 1) && (s > 0 && s < 1);
}

Answer 2

MKPolyline inherits form MKMultiPoint which has a - (MKMapPoint *)points; method,

You could try to check for intersections between all line segments.

"The points are connected end-to-end in the order they are provided."

So you can make your own line segments between each 2 points, and after you have an Array of line segments you can check for their intersections.

Here is a C++ code snippet for checking the intersections: It can be easily translated to Objective-C and whatever else.

public static bool LineSegmentsCross(Vector2 a, Vector2 b, Vector2 c,     Vector2 d)
{
     float denominator = ((b.X - a.X) * (d.Y - c.Y)) - ((b.Y - a.Y) * (d.X - c.X));

     if (denominator == 0)
     {
          return false;
     }

     float numerator1 = ((a.Y - c.Y) * (d.X - c.X)) - ((a.X - c.X) * (d.Y - c.Y));

     float numerator2 = ((a.Y - c.Y) * (b.X - a.X)) - ((a.X - c.X) * (b.Y - a.Y));

     if (numerator1 == 0 || numerator2 == 0)
     {
          return false;
     }

     float r = numerator1 / denominator;
     float s = numerator2 / denominator;

     return (r > 0 && r < 1) && (s > 0 && s < 1);
}