The business scenario

The company’s business needs to carry out point fetching on the THREE-DIMENSIONAL model, and support the function of line segment point fetching and area point fetching. Line segment point selection is to select two points on the model to form a line segment and select points at the same interval within the line segment. To pick a region of the model (irregular polygon) is to pick points evenly inside the polygon.

Since the points on the model can be converted into plane coordinates, this problem can be verified on canvas, where the functions of line segment point fetching and region point fetching are implemented. The effect is as follows :(Demo online debugging)

Line segment point:

Area pick point:

Line take

Implementation approach

It’s easy to pick a point on a line segment, and you can use trigonometric relations to figure out the p0 coordinate of the interval point

  1. So let’s figure out our starting point times x1, y1.And the end pointThe length c between (x2, y2)**, namely:SQRT ((x2-x1)² + (y2 - y1)²)
  2. According to the length of the interval between the pointsiTo find how many points to take on the line segmentn, that is:n = Math.floor(c / i)
  3. Find the coordinates of each interval point according to the trigonometric relations

Take the code

Function getLineSegmentPoint(lineSegment, lineSegment) interval) { try { if (interval && lineSegment && lineSegment.length === 2) { const point1 = lineSegment[0]; const point2 = lineSegment[1]; const a = point2.y - point1.y; const b = point2.x - point1.x; const c = Math.sqrt(Math.pow(a, 2) + Math.pow(b, 2)); const n = Math.floor(c / interval); const p = []; for (let i = 1; i <= n; i++) { const x = (b / c) * (interval * i) + point1.x; const y = (a / c) * (interval * i) + point1.y; p.push({ x, y }); } return p; } else {console.error(' lineSegment failed to get point ', lineSegment, interval); }} catch (error) {console.error(' line segment failed to fetch point ', error); }}Copy the code

Area take

Implementation approach

We can think about it, when a line goes through a polygon, it must produce a set of intersection points with the polygon. Since the polygon is a finite and closed graph, the line is infinite, so every time the line enters the polygon, it must go through the polygon once, so we can get the following conclusion:

For any line in the plane that passes through a polygon, the total number of points it intersects into or out of the polygon must be an even number, and the points entering or exiting the polygon must occur in consecutive pairs.

Here the definitions of entry and exit are:

Entry: A line from the outside of the polygon crosses the edge or vertex of the polygon into the inside of the polygon;

Out: A line from the inside of a polygon crosses the edge or vertex of a polygon to the outside of the polygon

If we put a polygon into a grid, the horizontal grid lines will intersect the polygon to form a number of intersectionsEnter theorWear aThe intersection points of the polygon are stored, and then the grid is taken between the two consecutive points, not to achieve uniform dot within the polygon.

A special case

The other thing to notice here is the definition of the intersection that goes in or out of the polygon, right? Combined with the following figure for analysis

  1. Line AIt coincides with the four vertices of the polygon, so do the four vertices count** enters or penetrates the intersection of ** polygonsA simple analysis shows that since the lines do not enter the polygon, there is no entry or exit.They are not intersections that enter or exit the polygon
  2. Line B has three contact points with the polygon, the first point (point 5) is a line from the outside of the polygon into the inside of the polygon, satisfies the condition; The second point (point 6) is tangent to the line, and the line does not pass from the inside to the outside of the polygon. The line is still inside the polygon, which does not satisfy the condition. The third point (point 7) is tangent to the line from the inside to the outside of the polygon, which satisfies the condition, so point 6 is not the intersection of the point entering or exiting the polygon
  3. Like line A, line D does not enter the polygon, so there is no entering or exiting the polygon. Point 10 is not the intersection of entering or exiting the polygon
  4. Line EThere are four points of contact with the polygonAt 12andSome 13Here,The outer or side of a polygonisExterior of polygonSo point 12 is going from the inside of the polygon to the outside of the polygon, point 13 is going from the outside of the polygon to the inside of the polygon,Points 12 and 13 are both intersections entering or exiting the polygon

Implementation details

The specific steps are as follows:

  1. Take the rectangle around the polygon, and start at the upper left corner of the rectangle to form aSome intervalIs the grid grid spacing
  2. Obtain the contact point of each grid line and polygon, and determine whether this point is the intersection of the polygon into or out of the polygon (see the special case analysis of the surface), if yes, save, not discard. The second grid line in the figure below contains four points [A,B,C,D].
  3. After the second step, each of the horizontal grid lines will result in an even set of intersections, and each pair of points will be a pair (one is the intersection into the polygon and one is the intersection out of the polygon).
  4. Take points between each pair of points at the intersection of the grid to ensure that they are equally spaced

Here the difficult points in the second step, when the horizontal grid line and polygon intersection is just the polygon vertex, how to judge whether the vertex is entering or wear A polygon intersection, below we specific implementation for each specific situation analysis, the following figure line. A, B, C, D, E, and polygons generated 1-10 point of contact, Points 1, 2, 3, 4, 6, 10, 12 and 13 are not intersections of the polygon and need to be removed:

  1. Vertex 6 and 10 of the polygon are tangent to line B. We only need to determine whether the Y of the two points before and after the point is on the same side of line B
  2. Point 1, 2, 3, 4, 12, 13 is more special, is one of the line segment vertex connection with horizontal, at this time we need to determine whether the right and left sides of the point inside the polygon, if is not a straight line through the point will not enter the inside polygon, this point is not entered or wear a polygon intersection, need to discard.

But how do you tell if the point is inside the polygon?

Let’s think about it. Assuming point 1 is the starting point of the polygon, we have two ways to draw the polygon

  • Method 1:1→2→6… →1, then the right side of the side that makes up the polygon (line segments 1→2, 2→6) is inside the polygon
  • 1→5>8… →1, then the left side of the side that makes up the polygon (line segments 1→5, 5→8) is inside the polygon

So we need to first determine which side of each line segment is inside the polygon

*/ function getDirection() {for (let I = 0; i < points.length; i++) { const startIndex = i; const endIndex = i + 1 >= points.length ? 0 : i + 1; const lineStartPoint = points[startIndex]; const lineEndPoint = points[endIndex]; If (linestartPoint. y === lineendpoint. y) continue; const midPoint = { x: (lineStartPoint.x + lineEndPoint.x) / 2, y: (lineStartPoint.y + lineEndPoint.y) / 2, }; const midRightPoint = { ... X + 0.1,}; // const midLeftPoint = { // ... } const isRightInPoly = rayCasting(midPoint, points) === 'in'; // const isLeftPoint = rayCasting(midLeftPoint, If (lineendpoint-y < linestartPoint. y) {// Up return isRightInPoly? 'right' : 'left'; } else {return isRightInPoly? 'left' : 'right'; }}} ` ` `Copy the code

Then we determine whether the point should be removed according to whether the left and right sides of the point are inside the polygon.

  • Case 1: Point P and nextVertex are horizontal lines, and the right side of the polygon side is the interior of the polygon. If previousVertex is below P, both P and left are not inside the polygon and need to be removed. When previousVertex is above P, the left side of P is the interior of the polygon, which needs to be preserved

  • Case 2: Point P and nextVertex are horizontal lines, and the left side of the polygon side is the interior of the polygon. When previousVertex is below P, the left side of P is the interior of the polygon, which needs to be preserved. When previousVertex is above P, both P and left points are not inside the polygon and need to be removed

  • Case 3: The p points and perviousVertex are horizontal lines, and the right side of the polygon side is the interior of the polygon. When nextVertex is above P, the right side of P is the interior of the polygon, which needs to be preserved. If previousVertex is below P, both P and left are not inside the polygon and need to be removed.

  • Case 4: Point P and nextVertex are horizontal, and the left side of the polygon side is the interior of the polygon. If nextVertex is above point P, neither point P is inside the polygon and needs to be removed. When previousVertex is below P, the right side of P is the interior of the polygon, which needs to be preserved

3. In the last case, when the front and back lines of point P are both horizontal, the left and right sides of point P are not inside the polygon and need to be removed

*/ function checkPointNeedRemove(index, direction) {const {currentVertex: p, previousVertex, nextVertex, } = getNeighboringPoints(index); const isTangencyPoint = Math.sign(previousVertex.y - p.y) === Math.sign(nextVertex.y - p.y); If (isTangencyPoint) {return true; If (p.y === previousVertex. Y && p.y === nextVertex. Y) {return true; } let pointNeedRemove = false; If (p.x === previousVertex. Y) {if (p.x > previousVertex. X) {start ---->p // \ // \ if (p.x > previousVertex. (closingDirection === 'right' && nextVertex.y > p.y) || (closingDirection === 'left' && nextVertex.y < p.y) ) { pointNeedRemove = true; }} else {/ / line from right to left p < - start / / / / / / if ((closingDirection = = = 'right' && nextVertex. Y < p.y) | | (closingDirection === 'left' && nextVertex.y > p.y) ) { pointNeedRemove = true; }}} / / the second paragraph is the if horizontal (p.y. = = = nextVertex y) {if (p.x < nextVertex. X) {/ / line from left to right p -- -- -- - > end / / / / / / if ( (closingDirection === 'right' && previousVertex.y > p.y) || (closingDirection === 'left' && previousVertex.y < p.y) ) { pointNeedRemove = true; }} else {/ / line from right to left end < - p / / / / / / the if ((closingDirection = = = 'right' && previousVertex. Y < p.y) | | (closingDirection === 'left' && previousVertex.y > p.y) ) { pointNeedRemove = true; } } } return pointNeedRemove; }Copy the code

Online debugging

The full code is DrawDemo here.