1 /*
2 * Copyright (c) 2020-2022 Huawei Device Co., Ltd.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15
16 #include "gfx_utils/geometry2d.h"
17 #include "securec.h"
18
19 namespace OHOS {
20 /* return point of intersection of two lines when it is sure a and b is intersected */
Intersect(const Line & a,const Line & b,Vector2<int16_t> & out)21 bool Intersect(const Line& a, const Line& b, Vector2<int16_t>& out)
22 {
23 Vector2<int16_t> aA = a[0];
24 Vector2<int16_t> aB = a[1];
25 Vector2<int16_t> bA = b[0];
26 Vector2<int16_t> bB = b[1];
27 int32_t den = static_cast<int32_t>(aA.x_ - aB.x_) * (bA.y_ - bB.y_) -
28 static_cast<int32_t>(aA.y_ - aB.y_) * (bA.x_ - bB.x_);
29 if (den == 0) {
30 return false;
31 }
32 int32_t xNum = (static_cast<int32_t>(aA.x_) * aB.y_ - static_cast<int32_t>(aA.y_) * aB.x_) * (bA.x_ - bB.x_) -
33 (aA.x_ - aB.x_) * (static_cast<int32_t>(bA.x_) * bB.y_ - static_cast<int32_t>(bA.y_) * bB.x_);
34 int32_t yNum = (static_cast<int32_t>(aA.x_) * aB.y_ - static_cast<int32_t>(aA.y_) * aB.x_) * (bA.y_ - bB.y_) -
35 (aA.y_ - aB.y_) * (static_cast<int32_t>(bA.x_) * bB.y_ - static_cast<int32_t>(bA.y_) * bB.x_);
36 out.x_ = xNum / den;
37 out.y_ = yNum / den;
38 return true;
39 }
40
41 /* check two line intersect if intersect return true, else false */
IsIntersect(const Line & a,const Line & b)42 bool IsIntersect(const Line& a, const Line& b)
43 {
44 Vector2<int16_t> aA = a[0];
45 Vector2<int16_t> aB = a[1];
46 Vector2<int16_t> bA = b[0];
47 Vector2<int16_t> bB = b[1];
48
49 int32_t iPos = static_cast<int32_t>(aB.x_ - aA.x_) * (bA.y_ - aA.y_) -
50 static_cast<int32_t>(aB.y_ - aA.y_) * (bA.x_ - aA.x_);
51 int32_t kPos = static_cast<int32_t>(aB.x_ - aA.x_) * (bB.y_ - aA.y_) -
52 static_cast<int32_t>(aB.y_ - aA.y_) * (bB.x_ - aA.x_);
53
54 if (static_cast<int64_t>(iPos) * kPos <= 0) {
55 return true;
56 }
57 return false;
58 }
59
60 /* This functions clips all the edges w.r.t one clip edge of clipping area */
Clip(Polygon & poly,const Line & line)61 void Clip(Polygon& poly, const Line& line)
62 {
63 uint8_t vertexNum = poly.GetVertexNum();
64 Polygon newPoly;
65
66 /* (iX, iY), (kX, kY) are the co-ordinate values of the points */
67 for (int8_t i = 0; i < vertexNum; i++) {
68 /* i and k form a line in polygon */
69 int8_t k = (i + 1) % vertexNum;
70 int16_t iX = poly[i].x_;
71 int16_t iY = poly[i].y_;
72 int16_t kX = poly[k].x_;
73 int16_t kY = poly[k].y_;
74
75 int16_t x1 = line[0].x_;
76 int16_t y1 = line[0].y_;
77 int16_t x2 = line[1].x_;
78 int16_t y2 = line[1].y_;
79
80 /* Calculating position of first point w.r.t. clipper line */
81 int32_t iPos = static_cast<int32_t>(x2 - x1) * (iY - y1) - static_cast<int32_t>(y2 - y1) * (iX - x1);
82
83 /* Calculating position of second point w.r.t. clipper line */
84 int32_t kPos = static_cast<int32_t>(x2 - x1) * (kY - y1) - static_cast<int32_t>(y2 - y1) * (kX - x1);
85
86 uint8_t newVertexNum = newPoly.GetVertexNum();
87
88 if (iPos < 0 && kPos < 0) {
89 /* Case 1 : When both points are inside */
90 newPoly[newVertexNum].x_ = kX;
91 newPoly[newVertexNum].y_ = kY;
92
93 newVertexNum++;
94 } else if (iPos >= 0 && kPos < 0) {
95 /* Case 2: When only first point is outside */
96 Vector2<int16_t> intersectPoint;
97 bool intersect = Intersect(Line(x1, y1, x2, y2), Line(iX, iY, kX, kY), intersectPoint);
98 if (!intersect) {
99 continue;
100 }
101
102 newPoly[newVertexNum].x_ = intersectPoint.x_;
103 newPoly[newVertexNum].y_ = intersectPoint.y_;
104 newVertexNum++;
105
106 newPoly[newVertexNum].x_ = kX;
107 newPoly[newVertexNum].y_ = kY;
108 newVertexNum++;
109 } else if (iPos < 0 && kPos >= 0) {
110 /* Case 3: When only second point is outside Only point of intersection with edge is added */
111 Vector2<int16_t> intersectPoint;
112 bool intersect = Intersect(Line(x1, y1, x2, y2), Line(iX, iY, kX, kY), intersectPoint);
113 if (!intersect) {
114 continue;
115 }
116
117 newPoly[newVertexNum].x_ = intersectPoint.x_;
118 newPoly[newVertexNum].y_ = intersectPoint.y_;
119 newVertexNum++;
120 }
121 newPoly.SetVertexNum(newVertexNum);
122 }
123
124 /* Copying new points into original array and changing the no. of vertices */
125 poly = newPoly;
126 }
127
128 /* Implements Sutherland–Hodgman algorithm for polygon clipping */
SuthHodgClip(const Rect & clipRect,const Polygon & polygon)129 Polygon SuthHodgClip(const Rect& clipRect, const Polygon& polygon)
130 {
131 Polygon newPolygon(polygon);
132
133 Clip(newPolygon, Line(clipRect.GetLeft(), clipRect.GetTop(), clipRect.GetRight(), clipRect.GetTop()));
134 Clip(newPolygon, Line(clipRect.GetRight(), clipRect.GetTop(), clipRect.GetRight(), clipRect.GetBottom()));
135 Clip(newPolygon, Line(clipRect.GetRight(), clipRect.GetBottom(), clipRect.GetLeft(), clipRect.GetBottom()));
136 Clip(newPolygon, Line(clipRect.GetLeft(), clipRect.GetBottom(), clipRect.GetLeft(), clipRect.GetTop()));
137 return newPolygon;
138 }
139
140 /* the max cross point is two when a line cross a convex polygon */
Clip(const Line & line,const Polygon & poly,Vector2<int16_t> * pOut,uint8_t * pNum)141 void Clip(const Line& line, const Polygon& poly, Vector2<int16_t>* pOut, uint8_t *pNum)
142 {
143 if (pOut == nullptr || pNum == nullptr) {
144 return;
145 }
146 uint8_t vertexNum = poly.GetVertexNum();
147
148 /* (iX, iY), (kX, kY) are the co-ordinate values of the points */
149 for (int8_t i = 0; i < vertexNum; i++) {
150 /* i and k form a line in polygon */
151 int8_t k = (i + 1) % vertexNum;
152 int16_t iX = poly[i].x_;
153 int16_t iY = poly[i].y_;
154 int16_t kX = poly[k].x_;
155 int16_t kY = poly[k].y_;
156
157 int16_t x1 = line[0].x_;
158 int16_t y1 = line[0].y_;
159 int16_t x2 = line[1].x_;
160 int16_t y2 = line[1].y_;
161
162 /* Calculating position of first point w.r.t. clipper line */
163 int32_t iPos = static_cast<int32_t>(x2 - x1) * (iY - y1) - static_cast<int32_t>(y2 - y1) * (iX - x1);
164
165 /* Calculating position of second point w.r.t. clipper line */
166 int32_t kPos = static_cast<int32_t>(x2 - x1) * (kY - y1) - static_cast<int32_t>(y2 - y1) * (kX - x1);
167
168 if ((iPos >= 0 && kPos < 0) || (iPos < 0 && kPos >= 0)) {
169 Vector2<int16_t> intersectPoint;
170 Intersect(Line(x1, y1, x2, y2), Line(iX, iY, kX, kY), intersectPoint);
171 (*pOut) = intersectPoint;
172 (*pNum)++;
173 }
174 }
175 }
176
Polygon(const Vector2<int16_t> * vertexes,const uint8_t vertexNum)177 Polygon::Polygon(const Vector2<int16_t>* vertexes, const uint8_t vertexNum)
178 {
179 ASSERT(vertexNum <= MAX_VERTEX_NUM);
180 if (memcpy_s(vertexes_, MAX_VERTEX_NUM * sizeof(Vector2<int16_t>),
181 vertexes, vertexNum * sizeof(Vector2<int16_t>)) != EOK) {
182 ASSERT(0);
183 }
184 vertexNum_ = vertexNum;
185 }
186
MakeAABB() const187 Rect Polygon::MakeAABB() const
188 {
189 int16_t minX = vertexes_[0].x_;
190 int16_t maxX = vertexes_[0].x_;
191 int16_t minY = vertexes_[0].y_;
192 int16_t maxY = vertexes_[0].y_;
193 for (uint8_t i = 1; i < vertexNum_; i++) {
194 if (minX > vertexes_[i].x_) {
195 minX = vertexes_[i].x_;
196 }
197 if (maxX < vertexes_[i].x_) {
198 maxX = vertexes_[i].x_;
199 }
200 if (minY > vertexes_[i].y_) {
201 minY = vertexes_[i].y_;
202 }
203 if (maxY < vertexes_[i].y_) {
204 maxY = vertexes_[i].y_;
205 }
206 }
207 return Rect(minX, minY, maxX, maxY);
208 }
209 } // namespace OHOS
210