Introduction
The people working around with some graphics code, very often run into the problem of clipping line segments. It is a well-known problem and there have been a lot of algorithms provided. However, it is still a boring procedure and I've searched around for some feasible algorithms and finally, I found out the compact ant simply vector formula. In this article, the sample of the completed codes of anyhow segments clipping in MFC have been provided.
The calculation of the intersection point of two line segments is based on the so-called wedge product of the two vectors; there are three performances of the wedge product of the two vectors completely interchanging:
The vector formula for the calculation of the intersection point of the two lines defined by the line segments:
The formula (1) is valid just in condition r1^r0≠0. Also, it is clear that in computer calculations, no “pure zero” maybe not obtained while working with the float and double values. Therefore, for programming codes, this condition should be performed as:
If the condition (2) is valid, the coordinates of the intersection point R of the two lines is defined by the line segments to be obtained by the formula (1). It is not clear yet if the segments intersected themselves. The intersection of the segments to be established with the scalar product of the vectors. Intersection condition of the segments has been demonstrated in figure 2:
If the condition (3) is not valid, the segments are not intersected. Nevertheless, the scalar product of the vectors may provide valuable information on the relative positions of the segments concerned:
The same for another segment:
And the condition when the lines defined by the segments do not intersect the segments themselves:
If condition (2) is not valid, the segments and the lines defined by them are collinear and there is nothing of the point of intersection if the segments lay not in one line. The condition of the collinear vectors not to be in one line is defined by wedge product in the formula (7) and represented in figure 6:
If conditions (2) and (7) are not valid, the segments are placed in one line and maybe overlapped in some areas. The conditions of overlapping may also be established by means of the scalar product and it is worth distinguishing different cases as the segments are collinear in the same direction(r1∙r0>0), or the contrary one(r1∙r0<0), figure 7 and figure 8:
Conditions of the collinear segments not overlapping have been provided in figure 9:
The above is a complete set to provide valuable information about the relative positions of the segments. Needless to say, this technology may be applied to any programming language. The main advantage of the formula (1) provided is that it can be used in the graphics programming almost in the same form as performed in this article. In order to check all the technology above, the author developed a computer program in Visual C++ MFC (Microsoft Foundation Classes) with anyhow segments randomly created, randomly rotating and randomly moving and clipping at arbitrary point of time, just press “Enter” button. The vectors' behavior has to be defined regarding edge product, scalar product, and some other special routine mathematical properties.
The demo project Segment2D has been created with the standard MFC App wizard. Vector performance is the same as class Polygon_2D and class Vector_2D in my former CodeProject article "Weiler-Atherton algorithm in MFC". The segments are randomly created and randomly moving and randomly rotating.
Before you start building the project provided, it is highly recommended to have a look at the demo presentation enclosed to get an idea of the output expected.
Demo Explanations
The executable Segment2D.exe has been built with MSVS-2015 pro using the instruments of MSVS-2010. Therefore the Segment2D.exe is valid even for Windows-XP (as opposed to my former CodeProject articles, no special *.dll files are required because of the RAM used only).
Some menu and some special Accelerator keys have been arranged in order to demonstrate the Segment2D project implementation:
- Menu File->Play - play/stop object rotation (also Ctrl+P click)
- Menu Edit->Reset Scene->Random - two somehow segments with the random rotation and moving rates created (also Space Bar click)
- Menu Edit->Reset Scene->Collinear - two somehow collinear segments with the random moving rates created (also Ctrl+Space Bar click)
- Menu Edit->Reset Scene->Overlapping - two somehow segments in line with the random moving rates created (also Alt+Space Bar click)
- Menu Edit->Start Clipping - stop segments rotation and moving and start clipping (also Enter click)
- Menu Edit->Next Scene - next scene of performance (if play stopped; also Right Arrow click)
- Menu Help->Help - show Help Dialog (also F1 click)
The Help Dialog is non-modal therefore you can use as menu and accelerator commands directly or press an OK button in the Help Dialog (or double click the item correspondence):
Building Notes
Solution configuration must be installed as Release and the platform to be x86.
The project provided has been developed with MSVS-2015 pro using the instruments of MSVS-2010. Therefore the EXE files are valid even for Windows-XP. If you do not need to run the application in Windows-XP, just change the instruments to MSVS-2015.
The default coding property is UNICODE; nevertheless MBCS coding is also available, just change the property.
Even if you are working for the first time with MSVS, just select menu Debug->Start without debugging and the program Segment2D.exe should start building and working.
Project Source and Data Storage
Standard source codes in Segment2Dproj path have been created with the standard MFC Application Wizard:
- Segment2D.cpp - defines the standard class behaviors for the application
- MainFrm.cpp - implementation of the standard
CMainFrame class - CChildView.cpp - implementation of the standard
CWnd class; messages handling procedures created by the author using standard MFC Application Wizard procedures - DlgHelp.cpp - non-modal implementation of the standard
CDialogEx class; messages handling procedures created by the author using standard MFC Application Wizard procedures - Segment2D.rc and resource.h - menu, dialog, accelerator resources created by the author using the standard Resource Wizard procedures
Special source codes in Segment2DProj\GlobUse path have been developed by the author based on the standard graphics and geometry routine procedures:
- Vector_2D.cpp, Poligon_2D.cpp - 2D object handling
Code Explanation
All the Menu and Accelerator Commands have been done with standard MFC AppWizard technologies. And this article has no purpose to explain Segment2D demo project. If required, you may refer to my former article "Weiler-Atherton algorithm in MFC" where the InitApplication and DrawScene Procedure has been described. The main idea of this article is to explain the use of the Magic Formula of the intersection point of two line segments.
While declaring class Vector_2D, the main operations with the vectors are to be predetermined:
class Vector_2D : public CObject
{
public:
double x,y;
Vector_2D ( const Vector_2D& v ){ x = v.x; y = v.y;};
Vector_2D(double vx, double vy) { x = vx; y = vy; };
friend Vector_2D operator + ( const Vector_2D&, const Vector_2D& );
friend Vector_2D operator - ( const Vector_2D&, const Vector_2D& );
friend double operator * ( const Vector_2D&, const Vector_2D& );
friend Vector_2D operator * ( double, const Vector_2D& );
friend Vector_2D operator * ( const Vector_2D&, double );
friend Vector_2D operator / ( const Vector_2D&, double );
friend Vector_2D operator / ( const Vector_2D&, const Vector_2D& );
friend Vector_2D operator & ( const Vector_2D& u, const Vector_2D& v )
{ return (u.x + v.x, u.y + v.y);};
friend double operator ^ ( const Vector_2D& u, const Vector_2D& v )
{return (u.x*v.y - u.y*v.x);};
friend double operator | ( const Vector_2D &u, const Vector_2D &v )
{ return (u.x * v.x + u.y * v.y );};
};
inline Vector_2D Normalize ( Vector_2D& v )
{ double vv = !v; return vv > GeomTreshold ? v /vv : Vector_2D(0); };
inline Vector_2D operator + ( const Vector_2D& u, const Vector_2D& v )
{ return Vector_2D( u.x + v.x, u.y + v.y );}
inline Vector_2D operator - ( const Vector_2D& u, const Vector_2D& v )
{ return Vector_2D( u.x - v.x, u.y - v.y );}
inline double operator * ( const Vector_2D& u, const Vector_2D& v )
{ return u.x * v.x + u.y * v.y;}
inline Vector_2D operator * ( const Vector_2D& u, double f )
{ return Vector_2D( u.x * f, u.y * f);}
inline Vector_2D operator * ( double f, const Vector_2D& u )
{return Vector_2D( f * u.x , f * u.y );}
inline Vector_2D operator / ( const Vector_2D& u, double f )
{ return Vector_2D( u.x / f, u.y / f );}
inline Vector_2D& Vector_2D::operator += ( const Vector_2D& v )
{ x += v.x; y += v.y; return * this;}
inline Vector_2D& Vector_2D::operator -= ( const Vector_2D& v )
{ x -= v.x; y -= v.y; return * this;}
inline Vector_2D& Vector_2D::operator *= ( double v ){ x *= v; y *= v; return * this;}
inline Vector_2D& Vector_2D::operator *= ( const Vector_2D& v )
{ x *= v.x; y *= v.y; return * this;}
inline Vector_2D& Vector_2D::operator /= ( double v ){ x /= v; y /= v; return * this;}
The intersection point of two lines is determined by segments to be calculated in one line:
Vector_2D R = (r0 * (R11^R10) - r1 *(R01^R00)) / (r1^r0);
And once the intersection point of two lines has been determined by the segments received, it is easy to estimate if the point belongs to the segments with the scalar product calculation as in the Background part of this article prescribed.
The overlapping conditions of the collinear segments in line calculated by the function followed:
BOOL isOverlapping(Vector_2D R00, Vector_2D R01, Vector_2D R10,
Vector_2D R11, Vector_2D * Q0, Vector_2D * Q1)
{
Vector_2D r0 = R01 - R00;
Vector_2D r1 = R11 - R10;
if (fabs(r1^r0 / (!r1 * !r0)) > GeomTreshold)
return FALSE;
if (fabs((R10 - R00) ^ r0 / (!(R10 - R00) * !r0)) > GeomTreshold)
return FALSE;
if(r0*r1 >0)
if ((R00 - R10)* (R00 - R11) <= 0)
{
*Q0 = R00;
if ((R01 - R10)* (R01 - R11) <= 0)
*Q1 = R01;
else
*Q1 = R11;
}
else
if ((R10 - R00)* (R10 - R01) < 0)
{
*Q0 = R10;
if ((R01 - R10)* (R01 - R11) <= 0)
*Q1 = R01;
else
*Q1 = R11;
}
else;
else
if ((R00 - R10)* (R00 - R11) <= 0)
{
*Q0 = R00;
if ((R01 - R10)* (R01 - R11) <= 0)
*Q1 = R01;
else
*Q1 = R10;
}
else
if ((R11 - R00)* (R11 - R01) < 0)
{
*Q0 = R11;
if ((R01 - R10)* (R01 - R11) <= 0)
*Q1 = R01;
else
*Q1 = R10;
}
else
return FALSE;
return TRUE;
}
}
Your Own Application Development Using the Project Provided
I hope that my explanations in the Background part of this article are quite clear so everybody can use this technology in any programming language.
You may pick up this entire project, rename it with the project of my former CodeProject article "MFC Project from Existing Code in One Click" and combine and improve the code as you like.
Or you may pick up the GlobUse directory from this project and include the special procedures contained in any of your own graphics projects with menu Project->Existing Item.
Your references to my code if any, should be highly appreciated.
Points of Interest
The main interest point is why I've not found this magic formula in any authoritative sources. It is easy to use even in the school level of geometry. Sure if we unpack this formula using the standard coordinate performance finally should be obtained as an enormous algorithm as provided a lot of on the internet. But I'm sure a few people should come back to the boring procedures after they use this formula.
I believe that this demo and code should be helpful for software people for segments clipping.
The project has been developed in the MFC platform. Nevertheless, everything developed in MFC may be converted to Win32 and vice versa.
The gif in the title of this article has been created with the program of my former CodeProject article "Your Own Avishop".
History
- 5th December, 2019: Initial version
