It is currently Thu Mar 28, 2024 11:50 pm



Reply to topic  [ 1 post ] 
Intersection of two segments in euclidean plane 
Author Message
Emperor
User avatar

Joined: Wed Apr 16, 2003 1:25 am
Posts: 2560
Reply with quote
Post Intersection of two segments in euclidean plane
I had some talk on this topic lately and thought it might come handy in to put it here. So, when two line segments in euclidean plane intersects each other? Definition: the two given line segments AB and CD intersect each other if points A and B are from the different sides of the line determined with CD as well as the points C and D are from the different sides of the line determined with AB. Or if one of points A and B belong to CD and other not; The same for points C and D and AB. Both C and D may both belong to AB (or A and B belong CD) too.

In example, two points in euclidean plane, A and B, are from different sides of the line determined with CD, if the following works:

sgn((CD x CA)*(0,0,1)) != sgn((CD x CB)*(0,0,1))

If all the signums are nulls, it is the special case that both segments lie on the same line. In that case the distance of two most distant points on the line must be less or equal with summ of lengths of segments. Otherwise AB and CD do not intersect.

So now I will give an simple and non-optimizes piece of code that represents on solution of this problem. Piece of code is wrote in pure C and not optimized for fastest working, but for best showing what is going on in there. As well, for those who aren't quite sure about the concept of structures or classes, arguments are eight real numbers which are coordinates of four points. Function returns 0 when there is no intersection and 1 when there is.

There will be written four more helping functions. The signum, taking an real number and returning an integer. Function that quadriple value, i.e. f(x) = x*x, taking one real number and returning another. Function that calculates the third coordinate of vector porduct of two given vectors in plane, taking four real values and returning one. Function that calculates distance between two points in euclidean plane.

Code:
int signum(float x)
{
   if(x > 0) return 1;
   if(x < 0) return -1;
   return 0;
}

float qua(float x)
{ return x*x; }

float vectorproductz(float px,float py,float qx,float qy)
{ return px*qy - py*qx; }

float distance(float px,float py,float qx,float qy)
{ return (float) sqrt(qua(qx-px)+qua(qy-py)); }


int segmeninplanetintersect(
   float ax,float ay,
   float bx,float by,
   float cx,float cy,
   float dx,float dy
)
{
   // vector AB
   float abx = bx - ax, aby = by - ay;
   
   // vector CD
   float cdx = dx - cx, cdy = dy - cy;

   // sgn (AB x AC) * (0,0,1)
   int abac = signum( vectorproductz(abx,aby,cx-ax,cy-ay) );

   // sgn (AB x AD) * (0,0,1)
   int abad = signum( vectorproductz(abx,aby,dx-ax,dy-ay) );

   // sgn (CD x CA) * (0,0,1)
   int cdca = signum( vectorproductz(cdx,cdy,ax-cx,ay-cy) );

   // sgn (CD x CB) * (0,0,1)
   int cdcb = signum( vectorproductz(cdx,cdy,bx-cx,by-cy) );

   // buffers for the maximal and current distance
   float distmax,dist;

   if(abac == 0 && abad == 0 && cdca == 0 && cdcb == 0)
   {
      distmax = distance(ax,ay,cx,cy);

      dist = distance(ax,ay,dx,dy);
      if(dist > distmax) distmax = dist;

      dist = distance(bx,by,cx,cy);
      if(dist > distmax) distmax = dist;

      dist = distance(bx,by,dx,dy);
      if(dist > distmax) distmax = dist;

      return distance(0,0,abx,aby) + distance(0,0,cdx,cdy) >= distmax;
   }

   return abac != abad && cdca != cdcb;
}

Note: the signum can be written in few more ways.
Code:
int signum(float x)
{ return x<0?-1:x>0?1:0; }
Code:
int signum(float x)
{ return x<0?-1:!!x; }

The first one is universal model for all the programming languages that root from C. The second is C/C++ specific.

The condition abac == 0 && abad == 0 && cdca == 0 && cdcb == 0 in C/C++ can be writen in the following way too:
Code:
!(abac|abad|cdca|cdcb)

_________________
++


Tue Oct 17, 2006 12:30 am
Profile WWW
Display posts from previous:  Sort by  
Reply to topic   [ 1 post ] 

Who is online

Users browsing this forum: No registered users and 8 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Jump to:  
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group.
Designed by STSoftware.