C++ UE4 将凹多边形拆分为多个凸多边

admin

1. /*从多边形的有序的点数组获取顶点和三角面数据信息（凹凸多边形）
2.         参数1： 顶点数组
3.         参数2： 是否是逆时针
4.         */
5. TArray<TArray<FVector>> GetPolygonDataFromOrderVertexs(TArray<FVector> 采用points, bool 采用antiClockwise)
6. {
7.         int t采用pointsNum = 采用points.Num();
8.         if (t采用pointsNum > 3)
9.         {
10.                 TArray<TArray<FVector>> polygonDividedArr = DividePolygonIfConcave(采用points, 采用antiClockwise);  //递归
11.                 if (polygonDividedArr.Num() > 0)
12.                 {
13.                         UE采用LOG(LogTemp, Warning, TEXT("多边形分割成了%d  个多边形"), polygonDividedArr.Num());
14.                 }
15.                 return polygonDividedArr;
16.         }
17.         else
18.                 UE采用LOG(LogTemp, Error, TEXT("多边形分割失败"));
19.         return TArray<TArray<FVector>>();
20. }
22. //分割
23. /*检查多边形是否是凹多边形，如果是就切割
24.         参数1：点集
25.         参数2：需要返回的被切割多边形1
26.         参数2：需要返回的被切割多边形2
27.         */
28. TArray<TArray<FVector>> DividePolygonIfConcave(TArray<FVector> 采用points, bool 采用antiClockwise)
29. {
30.         TArray<TArray<FVector>> polygonDividedArr;
32.         int t采用pointsNum = 采用points.Num();
33.         if (采用points.Num() < 3)
34.         {
35.                 return polygonDividedArr;
36.         }
37.         else if (t采用pointsNum == 3)
38.         {
39.                 polygonDividedArr.Add(采用points);
40.                 return polygonDividedArr;
41.         }
42.         else if (t采用pointsNum > 3)
43.         {
44.                 TArray<FVector> 采用dividePolygonA;
45.                 TArray<FVector> 采用dividePolygonB;
46.                 float t采用hei = 采用points[0].Z;
47.                 SetPointsZvalueBySpecify(采用points, 0);
49.                 FVector t采用p1;
50.                 FVector t采用p2;
51.                 TArray<FVector> t采用dirs = GetVectorArrByPointsArr(采用points);
53.                 bool t采用divideResult = false;
54.                 int t采用indexNew = 0;
55.                 for (int i = 0; i < t采用dirs.Num(); i++)
56.                 {
57.                         t采用p1 = t采用dirs[i];
58.                         if (i == t采用dirs.Num() - 1)
59.                         {
60.                                 t采用p2 = t采用dirs[0];
61.                                 t采用indexNew = 0;
62.                         }
63.                         else
64.                         {
65.                                 t采用p2 = t采用dirs[i + 1];
66.                                 t采用indexNew = i + 1;
67.                         }
69.                         float t采用rotateDir = FVector::CrossProduct(t采用p1, t采用p2).Z;
71.                         //检查出是凹多边形
72.                         if (t采用rotateDir < -0.01f && 采用antiClockwise == true || t采用rotateDir > 0.01f && 采用antiClockwise == false)
73.                         {
74.                                 //UE采用LOG(LogTemp, Warning, TEXT("t采用rotateDir:   %f"), t采用rotateDir);
75.                                 UE采用LOG(LogTemp, Warning, TEXT("是凹多边形~~~~~~~~~~~"));
76.                                 //求分割点
78.                                 t采用divideResult = GetRayIntersectionOfVecInVecArr(t采用dirs, 采用points, i, i, t采用pointsNum - 1, 采用dividePolygonA, 采用dividePolygonB);
79.                                 if (t采用divideResult == false)
80.                                 {
81.                                         t采用divideResult = GetRayIntersectionOfVecInVecArr(t采用dirs, 采用points, i, 0, i - 1, 采用dividePolygonA, 采用dividePolygonB);
82.                                 }
83.                                 if (t采用divideResult == false)
84.                                 {
85.                                         UE采用LOG(LogTemp, Error, TEXT("线段%d  没有得到分割点"), i);
86.                                 }
87.                                 break;
88.                         }
89.                 }
91.                 if (t采用divideResult == false)
92.                 {
93.                         SetPointsZvalueBySpecify(采用points, t采用hei);
94.                         polygonDividedArr.Add(采用points);
95.                 }
96.                 else
97.                 {
98.                         if (采用dividePolygonA.Num() > 2)
99.                         {
100.                                 SetPointsZvalueBySpecify(采用dividePolygonA, t采用hei);
101.                                 DividePolygonIfConcave(采用dividePolygonA, 采用antiClockwise);
102.                         }
103.                         if (采用dividePolygonB.Num() > 2)
104.                         {
105.                                 SetPointsZvalueBySpecify(采用dividePolygonB, t采用hei);
106.                                 DividePolygonIfConcave(采用dividePolygonB, 采用antiClockwise);
107.                         }
108.                 }
109.         }
111.         return polygonDividedArr;
112. }
114. /*给定点数组的Z值统一化
115.         */
116. bool SetPointsZvalueBySpecify(TArray<FVector>& 采用points, float 采用zValue)
117. {
118.         if (采用points.Num() > 0)
119.         {
120.                 for (int i = 0; i < 采用points.Num(); i++)
121.                 {
122.                         采用points[i].Z = 采用zValue;
123.                 }
124.                 return true;
125.         }
127.         return false;
128. }
130. /*根据点数组获取向量数组
131.         */
132. TArray<FVector> GetVectorArrByPointsArr(const TArray<FVector> 采用points)
133. {
134.         TArray<FVector> t采用res;
135.         int t采用pointsNum = 采用points.Num();
136.         if (t采用pointsNum > 1)
137.         {
138.                 FVector t采用p1;
139.                 FVector t采用p2;
140.                 for (int i = 0; i < 采用points.Num(); i++)
141.                 {
142.                         t采用p1 = 采用points[i];
143.                         if (i == t采用pointsNum - 1)
144.                         {
145.                                 t采用p2 = 采用points[0];
146.                         }
147.                         else
148.                         {
149.                                 t采用p2 = 采用points[i + 1];
150.                         }
152.                         t采用res.Add(t采用p2 - t采用p1);
153.                 }
154.         }
156.         return t采用res;
157. }
159. bool IsRectCross(const FVector& p1, const FVector& p2, const FVector& q1, const FVector& q2)
160. {
161.         bool ret = FMath::Min(p1.X, p2.X) <= FMath::Max(q1.X, q2.X) &&
162.                 FMath::Min(q1.X, q2.X) <= FMath::Max(p1.X, p2.X) &&
163.                 FMath::Min(p1.Y, p2.Y) <= FMath::Max(q1.Y, q2.Y) &&
164.                 FMath::Min(q1.Y, q2.Y) <= FMath::Max(p1.Y, p2.Y);
165.         return ret;
166. }
169. //跨立判断
170. bool IsLineSegmentCross(const FVector& P1, const FVector& P2, const FVector& Q1, const FVector& Q2)
171. {
172.         if (
173.                 ((Q1.X - P1.X) * (Q1.Y - Q2.Y) - (Q1.Y - P1.Y) * (Q1.X - Q2.X)) * ((Q1.X - P2.X) * (Q1.Y - Q2.Y) - (Q1.Y - P2.Y) * (Q1.X - Q2.X)) < 0 ||
174.                 ((P1.X - Q1.X) * (P1.Y - P2.Y) - (P1.Y - Q1.Y) * (P1.X - P2.X)) * ((P1.X - Q2.X) * (P1.Y - P2.Y) - (P1.Y - Q2.Y) * (P1.X - P2.X)) < 0
175.                 )
176.                 return true;
177.         else
178.                 return false;
179. }
182. /**
183. 求线段P1P2与Q1Q2的交点。
184. 先进行快速排斥实验和跨立实验确定有交点再进行计算。
185. 交点（X,Y）使用引用返回。
186. 没有验证过
187. **/
188. int CheckTwoLineIntersectionResult(const FVector& p1, const FVector& p2, const FVector& q1, const FVector& q2, FVector& t采用intersectionFVector)
189. {
190.         if (IsRectCross(p1, p2, q1, q2))
191.         {
192.                 if (IsLineSegmentCross(p1, p2, q1, q2))
193.                 {
194.                         //求交点
195.                         float tmpLeft, tmpRight;
196.                         tmpLeft = (q2.X - q1.X) * (p1.Y - p2.Y) - (p2.X - p1.X) * (q1.Y - q2.Y);
197.                         tmpRight = (p1.Y - q1.Y) * (p2.X - p1.X) * (q2.X - q1.X) + q1.X * (q2.Y - q1.Y) * (p2.X - p1.X) - p1.X * (p2.Y - p1.Y) * (q2.X - q1.X);
199.                         float X = ((float)tmpRight / (float)tmpLeft);
201.                         tmpLeft = (p1.X - p2.X) * (q2.Y - q1.Y) - (p2.Y - p1.Y) * (q1.X - q2.X);
202.                         tmpRight = p2.Y * (p1.X - p2.X) * (q2.Y - q1.Y) + (q2.X - p2.X) * (q2.Y - q1.Y) * (p1.Y - p2.Y) - q2.Y * (q1.X - q2.X) * (p2.Y - p1.Y);
203.                         float Y = ((float)tmpRight / (float)tmpLeft);
205.                         t采用intersectionFVector = FVector(X, Y, p1.Z);
206.                         return true;
207.                 }
208.         }
209.         return false;
210. }
212. //       
213. TArray<FVector> GetPointsByIndexRange(const TArray<FVector> 采用points, int startIndex, int endIndex)
214. {
215.         TArray<FVector> pts;
216.         int idx = startIndex;
217.         while ( idx <= endIndex && idx < 采用points.Num() )
218.         {
219.                 pts.Add(采用points[idx]);
220.                 idx++;
222.                 if (idx >= 采用points.Num())
223.                         idx = 0;
224.         }
225.         return pts;
226. }
228. /*从向量数组中获取一个向量在这个数组中的延长线与其他向量的交点
229.         注意：顺序必须先从这个向量的下标开始，不能是0;交点不包括向量端点
230.         参数1：方向向量数组
231.         参数2：对应的点数组（长度需保持一致）
232.         参数3：这个向量的下标
233.         参数4，5：开始和结束下标
234.         参数6，7: 根据交点被切分的两组点数组
235.         返回值：true 为成功,反之无
236.         */
237. bool GetRayIntersectionOfVecInVecArr(const TArray<FVector> 采用dirs, const TArray<FVector> 采用points, const int 采用vecIndex, const int 采用beginIndex, const int 采用endIndex,
238.         TArray<FVector>& 采用dividePolygonA, TArray<FVector>& 采用dividePolygonB)
239. {
240.         int t采用dirsNum = 采用dirs.Num();
241.         int t采用pointsNum = 采用points.Num();
243.         if (t采用dirsNum > 3 && t采用pointsNum > 3)
244.         {
245.                 if (t采用dirsNum == t采用pointsNum)
246.                 {
247.                         if (采用beginIndex >= 0 && 采用beginIndex < t采用dirsNum)
248.                         {
249.                                 if (采用endIndex >= 0 && 采用endIndex < t采用dirsNum)
250.                                 {
251.                                         int t采用indexNew = 采用vecIndex == (t采用dirsNum - 1) ? 0 : 采用vecIndex + 1;
252.                                         FVector t采用beginA = 采用points[采用vecIndex];
253.                                         FVector t采用endA = t采用beginA + 采用dirs[采用vecIndex];
254.                                         FVector t采用intersectionPoint;
256.                                         for (int j = 采用beginIndex; j <= 采用endIndex; j++)
257.                                         {
258.                                                 if (j != 采用vecIndex && j != t采用indexNew)
259.                                                 {
260.                                                         FVector t采用beginB = 采用points[j];
261.                                                         if (CheckTwoLineIntersectionResult(t采用beginA, t采用endA, t采用beginB, t采用beginB + 采用dirs[j], t采用intersectionPoint) == 2)
262.                                                         {
263.                                                                 //给分割的多边形点组加点
264.                                                                 采用dividePolygonA = GetPointsByIndexRange(采用points, t采用indexNew, j);
265.                                                                 采用dividePolygonA.Add(t采用intersectionPoint);
266.                                                                 UE采用LOG(LogTemp, Warning, TEXT("采用dividePolygonA向量数组个数： %d"), 采用dividePolygonA.Num());
268.                                                                 采用dividePolygonB = GetPointsByIndexRange(采用points, j, t采用indexNew);
269.                                                                 if (采用dividePolygonB.Num() > 0)
270.                                                                 {
271.                                                                         采用dividePolygonB[0] = t采用intersectionPoint;
272.                                                                 }
273.                                                                 UE采用LOG(LogTemp, Warning, TEXT("采用dividePolygonB向量数组个数： %d"), 采用dividePolygonB.Num());
274.                                                                 return true;
275.                                                         }
276.                                                 }
277.                                         }
278.                                 }
279.                         }
280.                 }
281.         }
283.         return false;
284. }

复制代码