## 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

- 5
^{th} December, 2019: Initial version