## Introduction to the

Drawing irregular polygons by hand using Canvas. Click the points on the screen with the mouse as the vertices of the polygon, and connect the lines to form the polygon. In addition to hand drawing, but also added random generation and echo, detection of polygon crossing, concavity detection. Note: two points that are too close together will be considered the same point and ignored. To close the region, click the first point in the graph or click the close Graph button.

## Two Canvas layers

In order to realize the function of line following mouse movement, and the Canvas graph cannot clear a single drawing command, I used the absolute positioning of CSS to overlay two Canvas objects in the same area. A graph below, which indicates that the drawing has been completed, is called fixed Canvas; One sits on top and redraws the lines that follow the mouse every time the mouse moves, called a temporary Canvas. CanvasTemp is the temporary Canvas.

```
<template>
<div
class="canvas-box"
:style="{ width: canvasWidth + 'px', height: canvasHeight + 'px' }"
>
<canvas
ref="canvas"
:width="canvasWidth"
:height="canvasHeight"
class="canvas"
></canvas>
<canvas
ref="canvasTemp"
class="canvas"
:width="canvasWidth"
:height="canvasHeight"
@mousedown="draw"
></canvas>
</div>
</template>
<style lang="less" scoped>
.canvas-box {
margin: 5px auto;
background: #aaa;
position: relative;
.canvas {
position: absolute;
top: 0;
left: 0;
width: 100%;
height: 100%;
cursor: crosshair; }}</style>
Copy the code
```

## Drawing process

The painting process is briefly described as:

- Click the first point in the drawing area, then the line moves with the mouse.
- Then click the 2-nth points, each of which is the vertex of the polygon.
- Click the first point to close the graph, or click the button to automatically close the graph.

### Fixed Canvas drawing

The temporary Canvas receives the click event and gets the coordinate point of the current click.

- If it is the first point, clear the previous drawing area and move the position to the current point on the fixed Canvas.
- Otherwise, after checking the requirements, draw a line from the previous point to the current point in the fixed Canvas. If the condition is met, the graph is closed.
- Let the line follow the mouse.

```
draw(e) {
// Click the current point
let pointDown = {
x: e.offsetX,
y: e.offsetY,
};
// First point
if (this.pointList.length === 0 || this.closeStatus) {
this.clear();
this.canvasObj.beginPath();
this.canvasObj.moveTo(pointDown.x, pointDown.y);
} else {
// First check whether the generated points meet the requirements
const check = this.checkPoint(pointDown, this.pointList);
switch (check) {
case "closeFirst":
this.closeFigure();
return;
case false:
return;
case true:
break;
}
// It's already a little bit
this.canvasObj.lineTo(pointDown.x, pointDown.y);
this.canvasObj.stroke();
}
this.pointList.push({ ... pointDown, });// If the maximum number has been reached, close the graph directly
if (this.pointList.length >= this.maxPointNum) {
this.closeFigure();
return;
}
// Let the line follow the mouse as described in the next section
}
Copy the code
```

### The temporary Canvas moves with the mouse

After the mouse is released, monitor the mouse movement. Clear the temporary Canvas every time the mouse moves. Redraw a line from the clicked coordinate point to the current mouse position. Because the mouse position moves a lot, a simple anti-shake is added: after the next DOM update, only the last mouse position is drawn.

```
// Make the line follow the mouse
document.onmouseup = () = > {
document.onmousemove = (event) = > {
/ / image stabilization
if (this.timeout) {
clearTimeout(this.timeout);
}
this.timeout = setTimeout(() = > {
this.canvasTempObj.clearRect(
0.0.this.canvasWidth,
this.canvasHeight
);
this.canvasTempObj.beginPath();
this.canvasTempObj.moveTo(e.offsetX, e.offsetY);
this.canvasTempObj.lineTo(event.offsetX, event.offsetY);
this.canvasTempObj.stroke();
this.timeout = null;
});
};
};
Copy the code
```

### Initialization and drawing complete

Mounted to set the canvas object. At the end of drawing, the graph is closed directly after checking that the graph meets the requirements. Methods for checking compliance are described below.

```
/ / initialization
mounted() {
this.canvasObj = this.$refs.canvas.getContext("2d");
this.canvasObj.lineWidth = 2;
this.canvasObj.strokeStyle = "red";
this.canvasObj.fillStyle = "Rgba (128, 100, 162, 0.5)";
this.canvasTempObj = this.$refs.canvasTemp.getContext("2d");
this.canvasTempObj.lineWidth = 2;
this.canvasTempObj.strokeStyle = "red";
},
Copy the code
```

```
// Close the graph
closeFigure() {
// Check the section
if (!this.checkPointCross(this.pointList[0].this.pointList)) {
this.$message.error("Cross line occurred while closing graph, please redraw!");
this.clear();
return;
}
if (!this.checkPointConcave(this.pointList[0].this.pointList, true)) {
this.$message.error("Concave polygon appears when closing graph, please redraw!");
this.clear();
return;
}
if (this.pointList.length >= this.minPointNum && !this.closeStatus) {
// Meet the requirements
this.canvasTempObj.lineTo(this.pointList[0].x, this.pointList[0].y);
this.canvasObj.closePath();
this.canvasObj.stroke();
this.canvasObj.fill();
document.onmousemove = document.onmouseup = null;
this.canvasTempObj.clearRect(0.0.this.canvasWidth, this.canvasHeight);
this.closeStatus = true;
// After drawing, return data
this.$emit("drawFinished".this.pointList); }},// Clear the graph
clear() {
this.pointList = [];
document.onmousemove = document.onmouseup = null;
this.canvasTempObj.clearRect(0.0.this.canvasWidth, this.canvasHeight);
this.canvasObj.clearRect(0.0.this.canvasWidth, this.canvasHeight);
this.closeStatus = false;
},
Copy the code
```

## Randomly generate and echo graphics

Two integer points are randomly generated as xy coordinates to form polygon vertices to judge whether they meet the requirements. The list of vertices that meet the requirements is taken as polygons. If the requirements are met, the echo function is called.

### Randomly generated graph

You can see that the randomly generated graph has a while (1) loop and the if (j > num * 100) constraint. This is because it is a random generation point at present, and then judging whether it meets the requirements, random generation function is easy to fall into an infinite loop when it meets a more complex graph constraint, so the limit on the number of loop failures is added.

```
// Auxiliary function to get random points
getRandomPoint() {
const x = Math.floor(Math.random() * this.canvasWidth + 1);
const y = Math.floor(Math.random() * this.canvasHeight + 1);
return {
x,
y,
};
},
// Randomly generate points and draw graphs
randomRegion() {
while (1) {
const num = this.regionNum.min;
const pointList = [this.getRandomPoint()];
let i = 1;
let j = 0;
while (i < num) {
const point = this.getRandomPoint();
// Determine whether the generated point meets the requirements
if (this.$refs.canvasRegion.checkPoint(point, pointList) ! = =true) {
++j;
continue;
}
if (j > num * 100) break;
++i;
pointList.push(point);
}
// Determine whether the generated graph meets the requirements
if (
pointList.length < num ||
!this.$refs.canvasRegion.checkPointCross(pointList[0], pointList) ||
!this.$refs.canvasRegion.checkPointConcave(pointList[0], pointList, true)) {continue;
} else {
this.$refs.canvasRegion.handleForeignData(pointList);
break; }}},Copy the code
```

### The echo graphic

Draw directly on the fixed Canvas.

```
// Handle external data
handleForeignData(canvasData) {
this.clear();
if (
!canvasData ||
canvasData.length < this.minPointNum ||
canvasData.length > this.maxPointNum
) {
this.$message.error("The command output does not meet requirements!");
return;
}
this.pointList = canvasData;
this.echoFigure();
},
// The graph is displayed
echoFigure() {
this.canvasObj.beginPath();
this.canvasObj.moveTo(this.pointList[0].x, this.pointList[0].y);
for (let i = 1; i < this.pointList.length; ++i) {
this.canvasObj.lineTo(this.pointList[i].x, this.pointList[i].y);
}
this.canvasObj.stroke();
this.closeFigure();
},
Copy the code
```

## Point position constraint

In order to prevent the user from creating many vertices by clicking the mouse multiple times in the same position, we added the position limit of point. The method is simple:

- Click the mouse, to the graph in the existing each vertex cycle, each point to judge the distance with the current position of the mouse. If the distance is less than required, vertices cannot be generated.
- If the position is less than required from the first vertex (the starting point) in the graph, the user is considered to be trying to close the graph.

```
// Is the checkpoint too close to the current point? If it is too close, it is not considered a point
checkPointClose(point, pointList) {
let i;
for (i = 0; i < pointList.length; ++i) {
const distance = Math.sqrt(
Math.abs(pointList[i].x - point.x) +
Math.abs(pointList[i].y - point.y)
);
if (distance > 3) {
continue;
}
// If it is near the first point, it is considered an attempt to close the graph
if (pointList.length >= this.minPointNum && i === 0) {
return "closeFirst";
}
return false;
}
return true;
},
Copy the code
```

## The limit of intersecting lines

Intersecting lines represent the intersection of two sides of a polygon. If intersecting is allowed, the following strange pattern is produced:

This pattern obviously does not look like a normal polygon, so the intersecting lines are limited. So how do we know that two edges intersect?

### Primary school Mathematics practice

In elementary school math class, we all learned how to find the intersection of two lines.

Finally, determine whether the intersection point (x,y) belongs to the line segment formed by two vertices. Where, if a is equal to c, that means that the two lines have the same slope, that they’re parallel, that there’s no intersection. If b is equal to d at the same time, that means they’re on the same line. Finally, it is very simple to determine whether the intersection point is in the line segment. It only needs to determine whether the coordinate of the intersection point is between the two ends of the line segment. However, there is a big problem with this method: it involves division. Division is used to construct the equation of a line using points, as well as to solve the intersection of simultaneous equations. Floating-point numbers in computers are stored discretely and accurately if they are integers. If division is used, floating point numbers are generated, resulting in a loss of accuracy and misjudgment for partial boundary cases. Therefore, this method is not adopted.

### Vector cross product to determine direction

#### Vector cross-product

Vectors that start at (0,0) and end at (x1, y1) and (x2, y2) are called vectors a and b.

The cross product of two vectors is defined as:

If the cross product is positive, then b is counterclockwise to A. If it’s regular, it’s clockwise. If it’s 0, it means that a and B are collinear.

#### Use the cross product to determine the cross

Next, if you have two line segments called AB and CD, how do you tell if they cross?

Let’s take point A as the zero, AC and AD as the auxiliary vectors. And now we see that if these two lines are crossing, then C and D have to be on either side of the line. In other words, the cross product of the vectors AB and AC must be different from the cross product of the vectors AB and AD. What about the following case?

AC and AD do cross on both sides of AB, but the line segments do not cross. At this point, we take the endpoint D of the other line segment as the zero point, and again we find the same sign. Therefore, judging twice guarantees crossover. When judging, every time we click a point, we connect it with the last point in the original picture into a line, and then judge whether it intersects with all points in the original picture.

```
// The auxiliary function gets the line with point1 as the origin
getPointLine(point1, point2) {
const p1 = {
x: point2.x - point1.x,
y: point2.y - point1.y,
};
return p1;
},
// The starting point of the auxiliary function must be the same
crossLine(point1, point2) {
return point1.x * point2.y - point2.x * point1.y;
},
// The auxiliary function checks whether the second line is to the left or right of the first line
isDirection(point1, point2, point3) {
// Assume that point1 is the origin
const p1 = this.getPointLine(point1, point2);
const p2 = this.getPointLine(point1, point3);
return this.crossLine(p1, p2);
},
// The auxiliary function checks whether two points are the same
isEuqalPoint(point1, point2) {
if (point1.x == point2.x && point1.y == point2.y) {
return true; }},// The auxiliary function checks whether two lines cross
isPointCross(line1P1, line1P2, line2P1, line2P2) {
const euqal =
this.isEuqalPoint(line1P1, line2P1) ||
this.isEuqalPoint(line1P1, line2P2) ||
this.isEuqalPoint(line1P2, line2P1) ||
this.isEuqalPoint(line1P2, line2P2);
const re1 = this.isDirection(line1P1, line1P2, line2P1);
const re2 = this.isDirection(line1P1, line1P2, line2P2);
const re3 = this.isDirection(line2P1, line2P2, line1P1);
const re4 = this.isDirection(line2P1, line2P2, line1P2);
const re11 = re1 * re2;
const re22 = re3 * re4;
if (re11 < 0 && re22 < 0) return true;
if (euqal) {
if (re1 === 0 && re2 === 0 && re3 === 0 && re4 === 0) return true;
} else {
if (re11 * re22 === 0) return true;
}
return false;
},
// Check whether the graph crosses
checkPointCross(point, pointList) {
if (this.crossAllow) return true;
let i;
if (pointList.length < 3) {
return true;
}
for (i = 0; i < pointList.length - 2; ++i) {
const re = this.isPointCross(
pointList[i],
pointList[i + 1],
pointList[pointList.length - 1],
point
);
if (re) {
return false; }}return true;
},
Copy the code
```

If the cross product is 0, it will be more complicated. It is necessary to first exclude the case of the adjacent sides of the polygon, and the rest should be divided into several cases to judge separately.

## Concave polygon restriction

Concave polygons are also determined using the cross product method above. And we know from above that the cross product can tell you whether the second vector is in the clockwise or counterclockwise direction of the first one. Let’s assume that A, B, and C are the three points that are drawn sequentially. Let’s call point A zero. Connect the AC. The cross product of AB and AC is greater than 0, which means counterclockwise.

And then let’s draw another point D on the graph. Let B be zero and connect BD. If the cross product is less than 0, it is clockwise. When this happens, it becomes obvious that there is a dent in the graph. If the cross product is greater than 0, it is counterclockwise, and the convex polygon can be guaranteed in this case. The condition for convex polygons, therefore, is that if the figures are connected sequentially, each line must be in the same clockwise direction.

Of course, there are some special cases, such as figure 1. Although each edge is counterclockwise in accordance with the rule, it is actually inrolled and cannot be closed at all without crossing the lines. Figure 2 is clearly a concave polygon, but there are so many points on the line in the middle of the discordant edges that it is impossible to tell the clockwise and counterclockwise of the front from the cross product of the adjacent edges. My solution: Forbid drawing such lines, even if the cross product of adjacent sides cannot be 0. There are several ways to solve this problem: 1. Record the direction of rotation of each edge in order. 2. Any endpoint in the graph can be connected to the last point in the current graph, and then compare the concavity with the three points currently drawn. If any inconsistency is found, it is not a convex polygon.

```
// The auxiliary function checks whether the three lines are convex or not
isPointConcave(point1, point2, point3, point4) {
const re1 = this.isDirection(point1, point2, point3);
const re2 = this.isDirection(point2, point3, point4);
if (re1 * re2 <= 0) return true;
return false;
},
// Check if it is concave
checkPointConcave(point, pointList, isEnd) {
if (this.concaveAllow) return true;
let i;
if (pointList.length < 3) {
return true;
}
if (
this.isPointConcave(
pointList[pointList.length - 3],
pointList[pointList.length - 2],
pointList[pointList.length - 1],
point
)
)
return false;
// If it is closed, point is the starting point, and we need to judge whether the last two lines and the first line form a concave shape
if (isEnd) {
if (
this.isPointConcave(
pointList[pointList.length - 2],
pointList[pointList.length - 1],
pointList[0],
pointList[1]))return false;
if (
this.isPointConcave(
pointList[pointList.length - 1],
pointList[0],
pointList[1],
pointList[2]))return false;
}
return true;
},
Copy the code
```

If it is the last closed graph, you need to judge the clockwise and counterclockwise of multiple lines near the closing point.

## reference

- Determine whether two line segments intersect – (vector cross-product) www.cnblogs.com/tuyang1129/…
- Cross product of line segment blog.csdn.net/m0_50089378…
- Convex polygon judgment [LeetCode] 469. Convex polygon blog.csdn.net/weixin_3991…