How to draw an outline around a non-closed polygon | ASSIST Software Romania
get in touch

LIKE

SHARE

FOLLOW

https://cdnsite3.assist.ro/sites/default/files/promoted_images/blog/How%20to%20draw%20an%20outline%20around%20a%20non-closed%20polygon.Ionut%20Gradinaru%20ASSIST%20Software%202018%20promo.png
 
If you are a programmer who started using DirectX for drawing simple primitives and you have had to think about an algorithm for drawing an outline around a rectangle, circle, triangle, polygon etc., then you are going to enjoy reading this article.
I am going to describe the problem before going forward. So, if a user creates a non-closed polygon by pressing left mouse on the screen in several places, how can we create an outline for this polygon with a specific width?
Hundreds of swear words came out of my mouth in the last two days when I was searching on the web about a solution to my problem… I found nothing. After two days, I have figured it out. It was just a simple geometry problem.
 

I. “Elementary my dear Watson”

 

How to draw an outline around a non-closed polygon.Ionut Gradinaru ASSIST Software 2018

Fig. 1

How to draw an outline around a non-closed polygon.Ionut Gradinaru ASSIST Software 2018

Fig.2

 

So we have an arbitrary line made up of n points (Fig. 1), we want to draw an outline around this line, so we need to calculate the contour points of the surrounding line (Fig 2). 
The idea is: if you have the points of the line segments, you can easily create two parallel lines for each segment and calculate the connection point where they intersect with the next.

What we need is the equation of the line represented by two points, a series of transformations of each point (translate/ rotate/ scale). In this section, we are going to focus on the description of the line.

The equation of the line is defined by:

y = m * x + n,

where m is called slope or gradient which is a real number that describes the direction and steepness of the line, and n is called y-Intercept, also refers to the starting value of the line (Fig. 3).
If we have a point A (Xa, Ya), then a line which goes through A point is defined by :

y - Ya = m * (x - Xa)
y = m * x + (
Ya - m * Xa)

Also, the slope is equal to the rising value divided by run.

m = rise / run,

and if we know two points on the same line, the slope is also equaled with: 

m = (Yb - Ya) / (Xb - Xa)

How to draw an outline around a non-closed polygon.Ionut Gradinaru ASSIST Software 2018                                                                                                                                                                                                                                                                                                                                                                  Fig.3


“And then Satan said: <Let’s put the alphabet in the math>”...  so we got the description of the line if we know two points from it:

m = (Yb - Ya) / (Xb - Xa)
n = Ya - m *Xa
 

II. Line in Geometry

“Do not worry too much about your difficulty in mathematics, I can assure you that mine are still greater.” (Albert Einstein)
 
Let’s talk about the intersection of the lines
First, we need the equations of two lines. We are going to use slope-intercept form to describe an equation:
y = m1 * x + n1
y = m2 * x + n2
 
Then, since at the point of intersection, the two equations will have the same values of x and y, we set the two equations equal to each other (Fig 4). This gives an equation that we can solve for x:
m1 * x + n1 = m2 * x + n2
x = (n2 - n1) / (m1 - m2)
 
We substitute that x value in one of the line equations (it doesn't matter which) and find the y value:
y = m1 * x + n1
 
How to draw an outline around a non-closed polygon.Ionut Gradinaru ASSIST Software 2018                                                                                                                                                                                                                                                                                                                                                                Fig. 4 

Let’s talk about the 2D rotation around a point.

Imagine a point located at (x, y). If we want to rotate that point around the origin, the coordinates of the new point would be located at (x1, y1), you can see it in (Code sample 1).

x1 = x * cos(A) - y * sin(A)

y1 = y * cos(A) + x * sin(A)

where A is the angle of rotation.

 

How to draw an outline around a non-closed polygon.Ionut Gradinaru ASSIST Software 2018                                                                                                               Fig. 5                                                                                                                                                                                                                       


If you wanted to rotate the point around something other than the origin:

1. Translate the whole system so that the point of rotation is at the origin.
2. Perform the rotation. 
3. Undo the translation.
 
Having acquired all this information, we can proceed to write some code.
 

III. “Code is like humor. When you have to explain it, it’s bad.”

We will go to follow the next steps to achieve the result we want.
 
For each point having screen coordinates (exception for first/last point):
1. Calculate a new point at the distance width from the previous point applying the same rotation as previous and current point have.
2. Calculate the slope of linear equation defined by the previous and current point.
3. Calculate a new point at the distance width from the next point applying the same rotation as current and next point have.
4. Calculate the slope of the linear equation defined by the current and next point.
5. Calculate parameters from each line defined by the new points having in mind that two parallel lines have the same slope.
6. Having the slope and yIntercept value for each point, you can calculate the intersection point applying the formula we find earlier.
 
I know that it sounds a little hard to imagine all of the steps right now. We are going to write code. Stay tuned!
 
First of all, we will create a struct to define a point using screen coordinates (Code sample 1):
struct ScreenPoint
{
	float x;
	float y;
}

                                                                                                    Code sample 1


For the first and the last point from a non-closed polygon defined by a user, we do not have a previous/next point, so we just calculate the contour points for those points (Code sample 1) using the rotation from the consecutive points (first point - next point and previous point - last point).

void CreateFirstLastContourPoints(const std::vector<ScreenPoint> points, std::vector<ScreenPoint>& contourPoints)
{
	const int kPointsCount = points.size();
	const int kContourPointsCount = contourPoints.size();
	if (kContourPointsCount == 2 * kPointsCount)
	{
		// TODO: log error
		return;
	}

	const ScreenPoint kFirstScreenPoint = points[0];
	const ScreenPoint kLastScreenPoint = points[kPointsCount - 1];

	// Local variables for calculate the contour point
	ScreenPoint rightContourPoint = { 0.0f, 0.0f };
	ScreenPoint leftContourPoint = { 0.0f, 0.0f };

	float radAngleSlope = 0.0f;
	float cosValue = 0.0f;
	float sinValue = 0.0f;

	// Create contour points for the first point
	// Left point will be the symmetric point of the right
	radAngleSlope = atan2(points[1].y - kFirstScreenPoint.y, points[1].x - kFirstScreenPoint.x);
	cosValue = cos(radAngleSlope);
	sinValue = sin(radAngleSlope);

	rightContourPoint = { kFirstScreenPoint.x + kWidth * cosValue, kFirstScreenPoint.y - kWidth * sinValue };
	leftContourPoint = { -(rightContourPoint.x - kFirstScreenPoint.x) + kFirstScreenPoint.x, -(rightContourPoint.y - kFirstScreenPoint.y) + kFirstScreenPoint.y };

	contourPoints[0] = rightContourPoint;
	contourPoints[kContourPointsCount - 1] = leftContourPoint;

	// Create contour points for the last point
	// Left point will be the symmetric point of the right
	radAngleSlope = atan2(kLastScreenPoint.y - points[kPointsCount - 2].y, kLastScreenPoint.x - points[kPointsCount - 2].x);
	cosValue = cos(radAngleSlope);
	sinValue = sin(radAngleSlope);

	rightContourPoint = { kLastScreenPoint.x + kWidth * cosValue, kLastScreenPoint.y - kWidth * sinValue };
	leftContourPoint = { -(rightContourPoint.x - kLastScreenPoint.x) + kLastScreenPoint.x, -(rightContourPoint.y - kLastScreenPoint.y) + kLastScreenPoint.y };

	contourPoints[kPointsCount - 1] = rightContourPoint;
	contourPoints[kContourPointsCount - kControlPointsSize] = leftContourPoint;
}

                                                                                                   Code sample 2


For the rest of the points, we calculate the contour points using the intersection of the two lines:

void CreateContourPoints(const std::vector<ScreenPoint> points, std::vector<ScreenPoint>& contourPoints)
{
	const int kPointsCount = points.size();
	const int kContourPointsCount = contourPoints.size();
	if (kContourPointsCount == 2 * kPointsCount)
	{
		// TODO: log error
		return;
	}

	// Create contour points for the first/last point
	CreateFirstLastContourPoints(points, contourPoints);

	// Create contour points for the rest of the points
	// Local variables for calculate the contour point
	ScreenPoint rightContourPoint = { 0.0f, 0.0f };
	ScreenPoint leftContourPoint = { 0.0f, 0.0f };

	float radAngleSlope = 0.0f;
	float cosValue = 0.0f;
	float sinValue = 0.0f;

	// Each line is defined by y = m*x + n
	// To determine the intersection of two lines: m1*x + n1 = m2*x + n2
	// The point from intersection will have (x = [n1 - n2 / m2 - m2], y = m1*x + n1)
	for (auto i = 1; i < kPointsCount - 1; i++)
	{

	  	ScreenPoint previousPoint = points[i - 1];
	  	ScreenPoint currentPoint = points[i];
	  	ScreenPoint nextPoint = points[i + 1];

		// Line between (previous, current)
		// Calculate m1, n1 parameters
		radAngleSlope = atan2(currentPoint.y - previousPoint.y, currentPoint.x - previousPoint.x);
		cosValue = cos(radAngleSlope);
		sinValue = sin(radAngleSlope);

		ScreenPoint kPoint1 = { previousPoint.x + kWidth * cosValue, previousPoint.y - kWidth * sinValue };
		float m1 = ((currentPoint.y - previousPoint.y) / (currentPoint.x - previousPoint.x + FLT_EPSILON));
		float yIntercept1 = kPoint1.y - m1 * kPoint1.x;


		// Line between (current, next)
		// Calculate m2, n2 parameters
		radAngleSlope = atan2(nextPoint.y - currentPoint.y, nextPoint.x - currentPoint.x);
		cosValue = cos(radAngleSlope);
		sinValue = sin(radAngleSlope);

		ScreenPoint kPoint2 = { nextControlPoint.x + kWidth * cosValue, nextPoint.y - kWidth * sinValue };
		float m2 = ((nextPoint.y - currentPoint.y) / (nextPoint.x - currentPoint.x + FLT_EPSILON));
		float yIntercept2 = kPoint2.y - m2 * kPoint2.x;

		// The point from intersection
		// Lines defined by: y = slope1*x +yIntercept1 and y = slope2*x + yIntercept2
		float xIntersect = (yIntercept1 - yIntercept2) / (m2 - m1 + FLT_EPSILON);
		float yIntersect = m1 * xIntersect + yIntercept1;

		rightPoint = { yIntersect, yIntersect };
		leftPoint = { -(rightPoint.x - currentPoint.x) + currentPoint.x, -(rightPoint.y - currentControlPoint.y) + currentControlPoint.y };

		contourPoints[i] = rightPoint
		contourPoints[kContourPointsSize - i - 1] = leftPoint;
	}
}                                       
                                                                         

                                                                                                    Code sample 3


IV. Limitations

In this algorithm, there are some limitations, as I suppose you have already noticed. First of all, in the case of two non-parallel lines, the intersection will always be on the lines somewhere. When two lines are parallel, they do not intersect anywhere. They do not overlap, so they have no point of intersection.


If you enjoyed reading this, you can also check my previous article:

→ https://assist-software.net/snippets/how-create-simple-apps-using-unity-3d-and-parse-server

Ready to make it happen?

Drop us a line. We’d love to hear from you and see how we can help in solving your digital challenges. As one of the best software outsourcing companies in Romania, Eastern Europe, Europe and the world really, we are sure we can ASSIST.

GET IN TOUCH