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.

Entrench

I want to detect Intersection of Same Line In Cocos2d. – Entrench

Not implemented though, I guess you can detect pixel value of the line drawn with the pixel value of your drawn line inside the touchesMoved method. – Logion

Have a look at scribus/lib2geom functionfind_self_intersections scribus.net/svn/Scribus/branches/ScribusOTF/scribus/plugins/… .It may be instructive – Brannon

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.

Charlottecharlottenburg

+1 for line segment suggestion and 2nd performance suggestion (1st however I think is rubbish). – Rie

I edited 1st suggestion clarify it, hopefully making it less rubbish. – Charlottecharlottenburg

Answer 2

Not implemented though, I guess you can detect pixel value of the line drawn with the pixel value of your drawn line inside the touchesMoved method. Or you can refer here for detailed approach. The same work has been done here.

Logion