Line Drawing + Intersection of that line with self and also detect CCSprites inside that drawn Line

Question

I am drawing the line using following code, it works just amazing,

http://www.merowing.info/2012/04/drawing-smooth-lines-with-cocos2d-ios-inspired-by-paper/

Now I want to.....

1> Detect if the line Intersect with itself. 2) Detect if CCSprite is inside this closed line or not.

While searching I came across many logics for LineIntersection but none of them are accurate. I am giving one of them which detects an intersection, but it also detects it when there is no intersection of line.

1. First Method

   - (BOOL) lineIntersectOccured:(CGPoint)t1 pointEnd:(CGPoint)t2
   {
       BOOL result = NO;
       int pointsCount = [arrlinePoints count];
   
       CGPoint cp1;
       CGPoint cp2;
   
       for(int i = 0, j = 1; j < pointsCount; i++,j++)
       {
           [[arrlinePoints objectAtIndex:i] getValue:&cp1];
           [[arrlinePoints objectAtIndex:j] getValue:&cp2];
   
           // lines connected do not need to be included.
           if((cp2.x == t1.x && cp2.y == t1.y) || (cp1.x == t2.x && cp1.y == t2.y))
           {
               continue;
           }
   
           CGPoint diffLA = CGPointMake(cp2.x - cp1.x,cp2.y - cp1.y);
           CGPoint diffLB = CGPointMake(t2.x - t1.x, t2.y - t1.y);
   
           float compA = diffLA.x*cp1.y - diffLA.y * cp1.x;
           float compB = diffLB.x*t1.y - diffLB.y*t1.x;
   
           BOOL compA1 = (diffLA.x*t1.y - diffLA.y*t1.x) < compA;
           BOOL compA2 = (diffLA.x*t2.y - diffLA.y*t2.x) < compA;
           BOOL compB1 = (diffLB.x*cp1.y - diffLB.y*cp1.x) < compB;
           BOOL compB2 = (diffLB.x*cp2.y - diffLB.y*cp2.x) < compB;
   
           if(((!compA1 && compA2) || (compA1 && !compA2)) && ((!compB1 && compB2) || (compB1 && !compB2)))
           {
               result = YES;
           }
       }
       return result;
   }
   

And this is how I call this method, I have stored my points in the arrLinePoints from pangesture recognizer method

  if ([self lineIntersectOccured:[[arrlinePoints objectAtIndex:0] CGPointValue] pointEnd:[[arrlinePoints objectAtIndex:[arrlinePoints count] - 1] CGPointValue]] )
  {
      NSLog(@"Line Intersected");
  }

This gives me true even with the Following Situation

I also have tried the same Functionality with different Approach by adding view into CCDirector's view

UIBezierPath intersect

But this is giving performance issues , my fps reduced to almost 3 to 6. And also that intersection issue remains the same.

The Perfect Situation for Intersection is

Please help as soon as possible! Thanks for all Support.

Answer 1

As you construct the path yourself, it should not be necessary to test pixels. Instead use the points used to create the path.

It shouldn't be too hard to find a good line segment intersection algorithm. It seems the top answer of this question has a good method: Determining if two line segments intersect?

Once you've found a hit, use that exact hit point and the history of points to construct a polygon.

From there you should be able to perform a "point in polygon" test.

A few tips for performance:

1. In search for the intersection, only check the newest line segment for collision with the others (all lines that did not intersect previously will not intersect with each other this time around)
2. You might skip segments when you can conclude that both points are on one extreme of the line segment, for example you could skip foreign if: current.a.x < current.b.x && (foreign.a.x < current.a.x && foreign.b.x < current.a.x)

I hope this helps you along.