|
1 /* |
|
2 * Copyright (c) 2006 Nokia Corporation and/or its subsidiary(-ies). |
|
3 * All rights reserved. |
|
4 * This component and the accompanying materials are made available |
|
5 * under the terms of the License "Eclipse Public License v1.0" |
|
6 * which accompanies this distribution, and is available |
|
7 * at the URL "http://www.eclipse.org/legal/epl-v10.html". |
|
8 * |
|
9 * Initial Contributors: |
|
10 * Nokia Corporation - initial contribution. |
|
11 * |
|
12 * Contributors: |
|
13 * |
|
14 * Description: |
|
15 * |
|
16 */ |
|
17 |
|
18 |
|
19 #include "config.h" |
|
20 #include "Path.h" |
|
21 #include "PathSymbian.h" |
|
22 |
|
23 using namespace WebCore; |
|
24 |
|
25 /* |
|
26 The following code is based on an algorithm presented in "Algorithms" by Robert Sedgewick, |
|
27 Addison-Wesley, 1988, 2nd ed. ISBN 0201066734 |
|
28 */ |
|
29 |
|
30 bool pointInPolygon(WTF::Vector<FloatPoint>& rgpts, const FloatPoint& ptTest); |
|
31 |
|
32 bool pointInPolyRect(WTF::Vector<FloatPoint>& rgpts, const FloatPoint& ptTest, FloatRect *prbound) ; |
|
33 |
|
34 bool intersects(const FloatPoint& p1, const FloatPoint& p2, const FloatPoint& p3, const FloatPoint& p4) ; |
|
35 |
|
36 int CCW(const FloatPoint& p0, const FloatPoint& p1, const FloatPoint& p2) ; |
|
37 |
|
38 bool pointInPolygon(WTF::Vector<FloatPoint>& rgpts, const FloatPoint& ptTest) |
|
39 { |
|
40 int wnumpts = rgpts.size(); |
|
41 if (!wnumpts) |
|
42 return false; |
|
43 FloatRect r; |
|
44 int i ; |
|
45 FloatPoint pt1, pt2 ; |
|
46 int wnumintsct = 0 ; |
|
47 |
|
48 if (!pointInPolyRect(rgpts,ptTest,&r)) return false; |
|
49 |
|
50 pt1 = ptTest ; |
|
51 pt2 = FloatPoint(r.right() + 50, ptTest.y()) ; |
|
52 |
|
53 // Now go through each of the lines in the polygon and see if it |
|
54 // intersects |
|
55 for (i = 0 ; i < wnumpts-1 ; i++) { |
|
56 if (intersects(pt1, pt2, rgpts[i], rgpts[i+1])) |
|
57 wnumintsct++ ; |
|
58 } |
|
59 |
|
60 // And the last line |
|
61 if (intersects(pt1, pt2, rgpts[wnumpts-1], rgpts[0])) |
|
62 wnumintsct++ ; |
|
63 |
|
64 return (wnumintsct&1) ; |
|
65 } |
|
66 |
|
67 |
|
68 bool pointInPolyRect(WTF::Vector<FloatPoint>& rgpts, const FloatPoint& ptTest, FloatRect *res) |
|
69 { |
|
70 int wnumpts = rgpts.size(); |
|
71 if (!wnumpts) |
|
72 return false; |
|
73 |
|
74 FloatRect r ; |
|
75 int xmin, xmax, ymin, ymax ; |
|
76 FloatPoint *ppt ; |
|
77 int i ; |
|
78 |
|
79 xmin = ymin = INT_MAX ; |
|
80 xmax = ymax = -INT_MAX ; |
|
81 |
|
82 for (i=0; i < wnumpts ; i++) { |
|
83 ppt = &rgpts[i]; |
|
84 if (ppt->x() < xmin) |
|
85 xmin = ppt->x() ; |
|
86 if (ppt->x() > xmax) |
|
87 xmax = ppt->x() ; |
|
88 if (ppt->y() < ymin) |
|
89 ymin = ppt->y() ; |
|
90 if (ppt->y() > ymax) |
|
91 ymax = ppt->y() ; |
|
92 } |
|
93 r = FloatRect(xmin, ymin, xmax-xmin, ymax-ymin); |
|
94 |
|
95 if (res) |
|
96 *res = r; |
|
97 |
|
98 return r.contains(ptTest.x(),ptTest.y()); |
|
99 } |
|
100 |
|
101 bool intersects(const FloatPoint& p1, const FloatPoint& p2, const FloatPoint& p3, const FloatPoint& p4) |
|
102 { |
|
103 return ((( CCW(p1, p2, p3) * CCW(p1, p2, p4)) <= 0) |
|
104 && (( CCW(p3, p4, p1) * CCW(p3, p4, p2) <= 0) )) ; |
|
105 } |
|
106 |
|
107 |
|
108 int CCW(const FloatPoint& p0, const FloatPoint& p1, const FloatPoint& p2) |
|
109 |
|
110 { |
|
111 int dx1, dx2 ; |
|
112 int dy1, dy2 ; |
|
113 |
|
114 dx1 = p1.x() - p0.x() ; dx2 = p2.x() - p0.x() ; |
|
115 dy1 = p1.y() - p0.y() ; dy2 = p2.y() - p0.y() ; |
|
116 |
|
117 /* This is basically a slope comparison: we don't do divisions because |
|
118 * of divide by zero possibilities with pure horizontal and pure |
|
119 * vertical lines. |
|
120 */ |
|
121 return ((dx1 * dy2 > dy1 * dx2) ? 1 : -1) ; |
|
122 } |
|
123 |
|
124 |
|
125 // FIXME: PlatformPath only supports Rectangle, Ellipse and Polygon right now |
|
126 |
|
127 PlatformPath::~PlatformPath() |
|
128 { |
|
129 } |
|
130 |
|
131 void PlatformPath::addRect( const FloatRect& rect ) |
|
132 { |
|
133 m_type = Rectangle; |
|
134 m_boundingRect = rect; |
|
135 } |
|
136 |
|
137 bool PlatformPath::contains( const FloatPoint& point, WindRule rule ) |
|
138 { |
|
139 if( m_type == Rectangle ) |
|
140 return m_boundingRect.contains( point ); |
|
141 else if( m_type == Polygon ) |
|
142 return pointInPolygon( m_points, point ); |
|
143 else if( m_type == Ellipse ) { |
|
144 /** |
|
145 in order for point(x,y) to stay in the ellipse, |
|
146 it has to fulfill the ellipse equation: |
|
147 sqr(dx)/sqr(a) + sqr(dy)/sqr(b) <= 1 |
|
148 where 'a' is half the long axis of the ellipse, and 'b' is half the short axis |
|
149 x = a * cos(t) and y = b * sin(t) |
|
150 (see "http://www.3dsoftware.com/Math/PlaneCurves/EllipseAlgebra" for details) |
|
151 **/ |
|
152 const FloatRect& r = m_boundingRect; |
|
153 int r2x = (r.width() * r.width()) / 4; // sqr(a) |
|
154 int r2y = (r.height() * r.height()) / 4; // sqr(b) |
|
155 |
|
156 if (!r2x || !r2y) /*avoid division by zero*/ |
|
157 return false; |
|
158 |
|
159 int cx = (r.x() + r.width()/2); // center of ellipse, x |
|
160 int cy = (r.y() + r.height()/2); // center of ellipse, y |
|
161 int dx = point.x() - cx; // dx |
|
162 int dy = point.y() - cy; // dy |
|
163 return (dx*dx*r2y + dy*dy*r2x <= r2x*r2y); |
|
164 } |
|
165 else |
|
166 return false; |
|
167 } |
|
168 |
|
169 void PlatformPath::addLineTo( const FloatPoint& point ) |
|
170 { |
|
171 if( m_type == Unknown ) |
|
172 m_type = Polygon; |
|
173 |
|
174 m_points.append( point ); |
|
175 } |
|
176 |
|
177 void PlatformPath::addEllipse( const FloatRect& rect ) |
|
178 { |
|
179 m_type = Ellipse; |
|
180 m_boundingRect = rect; |
|
181 } |
|
182 |
|
183 void PlatformPath::closeSubPath() |
|
184 { |
|
185 // since the above intersection algorithm takes an extra step to test |
|
186 // last line segment in this polygon, we don't need to close the polygon here. |
|
187 } |
|
188 |
|
189 void PlatformPath::translate( const FloatSize& sz ) |
|
190 { |
|
191 float deltaX = sz.width(); |
|
192 float deltaY = sz.height(); |
|
193 |
|
194 if (m_type == Polygon) { |
|
195 for (int i = 0 ; i < m_points.size() ; i++) { |
|
196 m_points[i] = FloatPoint(m_points[i].x()+deltaX, m_points[i].y()+deltaY); |
|
197 } |
|
198 } else { |
|
199 m_boundingRect.setX(m_boundingRect.x()+deltaX); |
|
200 m_boundingRect.setY(m_boundingRect.y()+deltaY); |
|
201 } |
|
202 } |
|
203 |
|
204 // WebCore::Path member functions |
|
205 |
|
206 Path::Path() |
|
207 { |
|
208 m_path = new PlatformPath(); |
|
209 } |
|
210 |
|
211 Path::~Path() |
|
212 { |
|
213 delete m_path; |
|
214 } |
|
215 |
|
216 Path::Path(const Path& p) |
|
217 { |
|
218 m_path = new PlatformPath(); |
|
219 // deep copy |
|
220 *m_path = *(p.m_path); |
|
221 } |
|
222 |
|
223 Path& Path::operator=(const Path& other) |
|
224 { |
|
225 if( !m_path ) |
|
226 m_path = new PlatformPath(); |
|
227 // deep copy |
|
228 *m_path = *(other.m_path); |
|
229 |
|
230 return *this; |
|
231 } |
|
232 |
|
233 bool Path::contains(const FloatPoint& point, WindRule rule) const |
|
234 { |
|
235 return m_path->contains( point, rule ); |
|
236 } |
|
237 |
|
238 void Path::addRect(const FloatRect& rect) |
|
239 { |
|
240 m_path->addRect( rect ); |
|
241 } |
|
242 |
|
243 FloatRect Path::boundingRect() const |
|
244 { |
|
245 return m_path->m_boundingRect; |
|
246 } |
|
247 |
|
248 void Path::translate(const FloatSize& sz) |
|
249 { |
|
250 m_path->translate( sz ); |
|
251 } |
|
252 |
|
253 void Path::addEllipse(const FloatRect& rect ) |
|
254 { |
|
255 m_path->addEllipse( rect ); |
|
256 } |
|
257 |
|
258 void Path::addLineTo(const FloatPoint& point) |
|
259 { |
|
260 m_path->addLineTo( point ); |
|
261 } |
|
262 |
|
263 void Path::closeSubpath() |
|
264 { |
|
265 m_path->closeSubPath(); |
|
266 } |
|
267 |
|
268 void Path::clear() |
|
269 { |
|
270 m_path->m_type = PlatformPath::Unknown; |
|
271 m_path->m_points.clear(); |
|
272 m_path->m_boundingRect = FloatRect(); |
|
273 } |
|
274 |
|
275 // END OF FILE |