How to draw an outline around a non-closed polygon

I. “Elementary my dear Watson”

 

Fig. 1

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)

                                                                                                                                                                                                                                                                                                                                                                  Fig.3

II. Line in Geometry

---

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.

 

                                                                                                               Fig. 5                                                                                                                                                                                                                       

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

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

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