Let the two-dimensional vector P = (x 1, y 1) and Q = (x2, y2).

Then vector subtraction is defined as: P-Q = (x 1-x2, y 1-y2).

Obviously, it has the property of P-Q =-(Q-P).

Unless otherwise specified, the following points are regarded as vectors, and the subtraction of two points is vector subtraction;

2. Vector cross product

Let the vector P = (x 1, y 1) and Q = (x2, y2).

Then the vector cross product is defined as: P × Q = x 1*y2-x2*y 1, and the result is scalar.

Obviously, it has the property that P × Q =-(Q × P) P × (-Q) =-(P × Q).

Unless otherwise specified, all the following points are regarded as vectors, and the product of points is regarded as vector cross product;

Important properties of cross product:

& gt if P × Q > 0, then p is in the clockwise direction of q.

& gt if p × q

& gt if P × Q = 0, then p and q are * * * lines, but they may be in the same direction or in opposite directions.

3. The judgment point is on the line segment.

Set point is q, and line segment is P 1P2. The basis for judging the Q point on this line segment is:

(Q-P 1) × (P2-P 1) = 0, and q is in a rectangle with P 1 and P2 as diagonal vertices.

4. Judge whether two line segments intersect.

We determine whether two line segments intersect in two steps:

(1). Rapid rejection test

Let the rectangle with diagonal P 1P2 be R and the rectangle with diagonal Q 1Q2 be T. If

R and t do not intersect, obviously two line segments do not intersect;

(2). Upright test

If two line segments intersect, they must cross each other, as shown in figure 1. In the figure 1, P 1P2 spans.

Q 1Q2, then the vectors (P 1-Q 1) and (P2-Q 1) are located on both sides of the vector (Q2-Q 1), namely

(p 1-q 1)×(Q2-q 1)*(P2-q 1)×(Q2-q 1)& lt； 0

The above formula can be rewritten as

(p 1-q 1)×(Q2-q 1)*(Q2-q 1)×(P2-q 1)& gt； 0

When (p 1-q 1) × (Q2-q1) = 0, explain (p1-q1) and (Q2-q1) * *.

However, because it passed the fast elimination test, P 1 must be on the line Q 1Q2; Similarly,

(Q2-Q 1) ×( P2-Q 1) = 0 means that P2 must be on the line segment Q 1Q2.

Therefore, the basis for judging that P 1P2 crosses Q 1Q2 is:

(p 1-q 1)×(Q2-q 1)*(Q2-q 1)×(P2-q 1)≥0

Similarly, the basis for judging whether Q 1Q2 crosses P 1P2 is:

(q 1-p 1)×(P2-p 1)*(P2-p 1)×(Q2-p 1)≥0

At this point, the problem of judging whether the line segments intersect is completely solved.

5. Judge whether the line segment and the straight line intersect.

If the line segment P 1P2 intersects the straight line Q 1Q2, then P 1P2 crosses Q 1Q2, that is:

(p 1-q 1)×(Q2-q 1)*(Q2-q 1)×(P2-q 1)≥0

6. Determine whether the rectangle contains points.

It is only necessary to judge whether the abscissa and ordinate of the point are sandwiched between the left and right sides and the upper and lower sides of the rectangle.

6. Judge whether the line segment, polyline and polygon are in the rectangle.

Because the rectangle is a convex set, it is only necessary to judge whether all the endpoints are within the rectangle.

7. Judge whether the rectangle is inside the rectangle.

Just compare the left and right boundaries with the upper and lower boundaries.

8. Judge whether the circle is in the rectangle.

The necessary and sufficient condition for a circle in a rectangle is that the center of the circle is in the rectangle and the radius of the circle is less than or equal to the distance from the center of the circle to the four sides of the rectangle.

Minimum value of distance.

9. Determine whether a point is in a polygon.

Make the light l to the left with the point p as the endpoint. Because polygons are bounded, there must be many left ends of light L.

Outside the polygon, consider moving from left to right along L from infinity and meeting the first intersection of the polygon.

, entered the interior of the polygon, met the second intersection, left the polygon, ...

It is easy to see that when the intersection number c of L and polygon is odd, when P is in polygon, it is even.

P is outside the polygon.

But there are some special circumstances to consider. If l intersects the vertices of a polygon, in some cases, the intersection can only be

Count one, in some cases, the intersection does not need to be counted (just draw a picture yourself); If l and polygon

One side overlaps, and this side should be ignored. For the sake of unity, we are calculating the ray L and the multilateral

At the intersection of shapes, 1 does not consider the horizontal edges of polygons; 2。 For the vertex and L phase of a polygon

In the case of intersection, if the vertex is the vertex with large ordinate on its side, count it, otherwise ignore it;

3。 For the case that P is on the edge of a polygon, it can be directly judged that P belongs to a polyline. Thus, the pseudo code of the algorithm is obtained.

As follows:

1. Count ← 0;

2. Make a ray L from right to left with P as the endpoint;

3. Each side of a polygon.

4. If P is on the side, do it.

5. Then return true.

6. If S is not horizontal.

7. So if one endpoint of S is on L, and it is the endpoint with larger ordinate among the two endpoints of S..

9. Then count ← Count+1

10. Otherwise, if s and l intersect.

1 1. Then count ← count+1;

12. If the counting modulo 2 = 1

13. Then return true.

14. Otherwise, return false.

The method of making ray L is: Let the ordinate of P' be the same as P, and the abscissa be positive infinity (a big positive infinity).

Number), then P and p' determine the ray L, and the complexity of this algorithm is O(n).

10. Determines whether the line segment is within a polygon.

A necessary condition for a line segment to be in a polygon is that both endpoints of the line segment are in a polygon;

If a line segment intersects an edge of a polygon (intersection of two line segments means that the two line segments intersect and the intersection point is not on the two line segments)

Endpoint), because the left and right sides of the polygon belong to different parts inside and outside the polygon, there must be line segments.

Part of it is outside the polygon. So we get the second necessary condition of line segments in polygons: line segments and polygons.

All sides of the shape are not inscribed;

The intersection of a line segment and a polygon at both ends of the line segment does not affect whether the line segment is in a polygon; But if a polygon

When a vertex intersects a line segment, it is necessary to judge whether the line segment between two adjacent intersections contains the interior of a polygon.

So we can first find the vertices of all polygons that intersect the line segments, and then sort them according to the X-Y coordinates, so that,

Two adjacent points are the intersection points of two adjacent points on a line segment. If the midpoint of any adjacent two points is also within a polygon,

The line segment must be within a polygon. Proved as follows:

Proposition 1:

If the two adjacent intersections P 1 of the line segment and the polygon and the midpoint p' of P2 are also within the polygon, the value between P 1 and P2 is taken.

All the points are in a polygon.

Prove:

Suppose there is a point between P 1 and P2 that is not in the polygon. Let it be q, between P 1 and p', because it is multilateral.

The shape is a closed curve, so its inside and outside are bounded, while P 1 belongs to the inside of the multi-line and q belongs to the outside of the multi-line.

P' belongs to multilateralism, and P 1-Q-P' is completely continuous, so P 1Q and QP' must cross the boundaries of polygons, so

There are at least two intersections between p 1 and p', which contradicts that P 1P2 are adjacent to each other.

This proposal holds. Certificate of completion

It can be directly inferred from the proposition 1:

Inference 2:

Let the intersection of polygon and line segment PQ be P 1, P2, ... PN sequence, where Pi and Pi+ 1 are two adjacent intersections, and the line segment

The necessary and sufficient conditions for PQ to be in a polygon are: p, q are in a polygon and for I = 1, 2, ..., N- 1, Pi, Pi+ 1.

The midpoint of is also within the polygon.

In actual programming, it is not necessary to calculate all intersections. First of all, it is necessary to judge whether the line segment and the edge of the polygon intersect.

If a line segment intersects an edge of a polygon, then the line segment must be outside the polygon; If each line segment and polygon

If no edges intersect, the intersection of a line segment and a polygon must be the endpoint of the line segment or the vertex of the polygon.

It is enough to judge whether the point is on the line segment.

At this point, we get the following algorithm:

1. The endpoints of PQ at the end of the if line are not all within the polygon.

2. Then return false.

3.pointSet pointset is initialized to null;

4. Each side of a polygon.

5. the endpoint of 5.DOIF line segment is on S.

6. Then add the endpoint to the pointSet.

7. If S is on PQ, it is the endpoint of else.

8. Then add the endpoint to the pointSet.

9.else If S intersects the line PQ// at this time, it can be determined that it intersects.

10. Then return false.

1 1. Sorts the points in the point set according to the X-Y coordinates, with the smallest x coordinate in front.

For points with the same x coordinate, the point with the smaller y coordinate comes first;

12. For pointset [i], every two adjacent points in pointset [i+ 1].

13.Do if pointset [i], the midpoint of pointset [i+ 1] is not in the polygon.

14. Then return false.

15. Returns true.

The complexity of this algorithm is also O(n). Because the number of intersections is definitely much less than the number of vertices of a polygon.

N, so the complexity is constant at most and almost negligible.

1 1. Make sure the polyline is within the polygon.

It is only necessary to judge whether each line segment of the polyline is within a polygon. Let a broken line have m segments and a polygon have n segments.

Vertex with complexity O(m*n).

12. Determine whether the polygon is within the polygon.

It is only necessary to judge whether each edge of the polygon is within the polygon. Judge that a polygon with m vertices is

Not in a polygon with n vertices, the complexity is O(m*n).

13. Determine whether the rectangle is within the polygon.

Convert a rectangle into a polygon, and then determine whether it is within a polygon.

14. Determine whether the circle is within a polygon.

As long as the shortest distance from the center of the circle to each side of the polygon is calculated, if the distance is greater than or equal to the radius of the circle, the circle is in

Within a polygon. The algorithm for calculating the shortest distance from the center of the circle to each side of the polygon will be described later.

15. Determine whether the point is in the circle.

Calculate the distance from the center of the circle to the point. If it is less than or equal to the radius, the point is within the circle.

16. Determine whether a line segment, polyline, rectangle or polygon is in a circle.

Because a circle is a convex set, it is only necessary to judge whether each vertex is in the circle.

17. judge whether the circle is in the circle.

Let two circles be O 1, O2, and the radii are r 1, r2 respectively. It is necessary to judge whether O2 is within O 1. First, compare the sizes of r 1 and r2.

, if r 1 < R2, O2 can't be in o1; Otherwise, if the distance between the two centers is greater than r 1-r2, O2 does not exist.

Within O 1; Otherwise O2 is in the range of O 1.

18. Calculate the nearest point from point to line segment.

If the line segment is parallel to the X-axis (Y-axis), then the intersection point is the perpendicular of the line segment, and the vertical foot is very tolerant.

Easy to get, and then calculate the vertical foot, if the vertical foot is in a straight line, return to the vertical foot, otherwise return to the end point near the vertical foot.

Point;

If the line segment is not parallel to the X axis or the Y axis, the slope exists and is not 0. Let the two ends of the line segment be

Pt 1 and pt2, and the slope is:

k = ( pt2.y - pt 1。 y)/(pt2 . x-pt 1 . x)；

The linear equation is:

y = k *(x-pt 1 . x)+pt 1 . y

The slope of its vertical line is-1/k,

The vertical equation is:

Y = (- 1/k) * (x point x)+point y

Simultaneous solutions of two linear equations;

x =(k^2 * pt 1 . x+k *(point . y-pt 1 . y)+point . x)/(k^2+ 1)

y = k *(x-pt 1 . x)+pt 1 . y；

Then judging whether the vertical foot is on the line segment, and if it is on the line segment, returning the vertical foot; If not, two endpoints are calculated.

Distance to the vertical foot, select the endpoint closer to the vertical foot to be returned.

19. Calculate the nearest point from a point to a polyline, rectangle or polygon.

Just calculate the nearest point from this point to each line segment, record the nearest distance, and take the point with the smallest nearest distance.

Yes

20. Calculate the nearest distance from a point to a circle.

If the point is at the center of the circle, it returns UNDEFINED.

Connecting point P and center O, if PO is parallel to X axis, calculate the nearest point according to whether P is on the left or right of O.

The abscissa is centerPoint.x-radius or centerPoint.x+radius, as shown in Figure 4 (a);

If PO is parallel to the y axis, the ordinate of the nearest point is calculated according to whether p is above or below o.

CenterPoint.y+radius or centerPoint.y-radius, as shown in figure 4 (b).

If PO is not parallel to the x and y axes, the slope of PO exists and is not 0, as shown in fig. 4(c). At this time, straight Po.

The slope is

k = ( P.y - O.y )/ ( P.x - O.x)

The equation of the straight line PO is:

y = k * ( x - P.x) + P.y

Let the circle equation be:

(x - O.x ) ^2 + ( y - O.y ) ^2 = r ^2，

The intersection of a straight line PO and a circle can be solved by two simultaneous equations, and the intersection near point P is taken.

2 1. Calculate the intersection of line segments of two * * * lines.

For the line segments of two * * * lines, the positional relationship between them is as shown in Figure 5.

The two line segments in fig. 5(a) have no intersection; The two line segments in figs. 5 (b) and 5 (d) have infinite focal lengths; Figure 5 (c)

There is an intersection between two line segments. Let line 1 be a long line segment and line2 be a short line segment.

If line 1 contains two endpoints of line2, it is the case of fig. 5(d), and the two line segments have infinite intersections; such as

If line 1 contains only one endpoint of line 2, then if one endpoint of line 1 is equal to the endpoint contained by line 1.

The end point of line 2 is the situation in fig. 5(c), when there is only one intersection point between two line segments, otherwise it is.

In the case of fig. 5(c), two line segments also have infinite intersections; If the line 1 does not contain any endpoints of line 2,

This is the case in fig. 5(a), when two line segments have no intersection.

22. Calculate the intersection of a line segment or a straight line with a line segment.

Let a line segment be L0 = P 1P2, and another line segment or straight line be L 1 = Q 1Q2, and calculate as L0 and L 1.

The intersection of.

1. First, judge whether L0 and L 1 intersect (the method has been discussed above). If they don't intersect, there is no intersection.

Otherwise there must be an intersection between L0 and L 1. We regard L0 and L 1 as straight lines.

2. If P 1 and P2 have the same abscissa, that is, L0 is parallel to the Y axis.

A) if L 1 is also parallel to the y axis,

1. If the ordinate of P 1 is the same as that of Q 1, it means that L0 and L 1*** lines, and if L 1 is a straight line, they have.

Infinite intersection, if L 1 is a line segment, they can be found by the algorithm of "calculating the intersection of two * * * line segments".

The intersection of (this method has been discussed above);

Two. Otherwise, L0 and L 1 are parallel, and they have no intersection;

B) if L 1 is not parallel to the y axis, the abscissa of the intersection point is P 1, and it can be calculated by substituting it into the linear equation of L 1.

Calculate that ordinate of the intersection point;

3. If the abscissas of P 1 and P2 are different, but the abscissas of Q 1 and Q2 are the same, that is, L 1 is parallel to the Y axis, then the intersection point is horizontal.

The abscissa with the coordinate of Q 1 can be substituted into the linear equation of L0 to calculate the ordinate of the intersection;

4. If P 1 and P2 have the same ordinate, that is, L0 is parallel to the X axis.

A) if L 1 is also parallel to the x axis,

1. If the abscissa of P 1 is the same as that of Q 1, it means L0 and L 1 * *, and if l1is a straight line, it means.

There are infinite intersections. If L 1 is a line segment, it can be found by the algorithm of "calculating the intersection of two * * * line segments".

Their intersection (this method was discussed in the last article);

Two. Otherwise, L0 and L 1 are parallel, and they have no intersection;

B) If L 1 is not parallel to the X axis, the ordinate of the intersection point is the ordinate of P 1, and it can be calculated by substituting it into the linear equation of L 1.

Calculate that abscissa of the intersection point;

5. If the vertical coordinates of P 1 and P2 are different, but the vertical coordinates of Q 1 and Q2 are the same, that is, L 1 is parallel to the X axis, then the vertical coordinates of the intersection point.

Is the ordinate of Q 1, and the abscissa of the intersection point can be calculated by substituting it into the linear equation of L0;

6. The remaining situation is that the slopes of L 1 and L0 both exist and are not zero.

A) calculating the slope K0 of L0 and the slope k1of L 1;

B) if K 1 = K2.

A, if Q 1 on L0, that if L 1 is a straight line, L0 and L 1 * * * lines have infinite intersections, if l1.

If it is a line segment, you can use the algorithm of "calculating the intersection of two * * * line segments" to find their intersection (this method is used in

As described above);

Two. If Q 1 is not on L0, then L0 and L 1 are parallel, and they do not intersect.

C) The intersection point can be solved by simultaneous equations of two straight lines.

Note: this algorithm is not complicated, but it should be discussed clearly in different situations, especially when there are two line segments.

Need to be considered separately, so the algorithm for finding two * * * line segments will be written separately in the last article. In addition, from the beginning,

Firstly, the vector cross product is used to judge whether the line segment intersects with the line segment (or straight line). If the result is intersection, then the line segment is behind.

This surface can treat all line segments as straight lines.

23. Find the intersection of line segment or straight line with polyline, rectangle and polygon.

Find the intersection points with each side respectively.

24. Find the intersection of a line segment or a straight line and a circle.

Let the center of the circle be O, the radius of the center be R, and the two points on the straight line (or line segment) L be P 1, P2.

1. If L is a line segment and both P 1 and P2 are contained in the circle O, there is no intersection; Otherwise, continue to the next step.

2. if l is parallel to the y axis,

A) calculate the distance dis from the center of the circle to l

B) if dis > R, then l and circle do not intersect;

C) Using Pythagorean theorem, the coordinates of two intersections can be obtained, as shown in Figure 6(a); But pay attention to the phase of l and circle.

Tangent condition

3. If L is parallel to the X axis, it is similar to the case that L is parallel to the Y axis;

4. If L is neither parallel to the X-axis nor parallel to the Y-axis, the slope k of L can be found, and then the point inclination equation of L can be listed.

, and the circle equation can immediately solve the two intersections of l and circle;

5. If l is a line segment, it is necessary to judge whether the intersection points found in 2, 3 and 4 belong to the range of the line segment.