1 //========================================================================
3 // SplashXPathScanner.cc
5 //========================================================================
10 #pragma implementation
15 #include "SplashMath.h"
16 #include "SplashXPath.h"
17 #include "SplashXPathScanner.h"
19 //------------------------------------------------------------------------
21 struct SplashIntersect {
22 int x0, x1; // intersection of segment with [y, y+1)
23 int count; // EO/NZWN counter increment
26 static int cmpIntersect(const void *p0, const void *p1) {
27 return ((SplashIntersect *)p0)->x0 - ((SplashIntersect *)p1)->x0;
30 //------------------------------------------------------------------------
32 //------------------------------------------------------------------------
34 SplashXPathScanner::SplashXPathScanner(SplashXPath *xPathA, GBool eoA) {
36 SplashCoord xMinFP, yMinFP, xMaxFP, yMaxFP;
43 seg = &xPath->segs[0];
44 if (seg->x0 <= seg->x1) {
51 if (seg->flags & splashXPathFlip) {
58 for (i = 1; i < xPath->length; ++i) {
59 seg = &xPath->segs[i];
60 if (seg->x0 < xMinFP) {
62 } else if (seg->x0 > xMaxFP) {
65 if (seg->x1 < xMinFP) {
67 } else if (seg->x1 > xMaxFP) {
70 if (seg->flags & splashXPathFlip) {
71 if (seg->y0 > yMaxFP) {
75 if (seg->y1 > yMaxFP) {
80 xMin = splashFloor(xMinFP);
81 xMax = splashFloor(xMaxFP);
82 yMin = splashFloor(yMinFP);
83 yMax = splashFloor(yMaxFP);
88 interLen = interSize = 0;
89 computeIntersections(yMin);
92 SplashXPathScanner::~SplashXPathScanner() {
96 void SplashXPathScanner::getSpanBounds(int y, int *spanXMin, int *spanXMax) {
98 computeIntersections(y);
101 *spanXMin = inter[0].x0;
102 *spanXMax = inter[interLen - 1].x1;
104 *spanXMin = xMax + 1;
109 GBool SplashXPathScanner::test(int x, int y) {
113 computeIntersections(y);
116 for (i = 0; i < interLen && inter[i].x0 <= x; ++i) {
117 if (x <= inter[i].x1) {
120 count += inter[i].count;
122 return eo ? (count & 1) : (count != 0);
125 GBool SplashXPathScanner::testSpan(int x0, int x1, int y) {
129 computeIntersections(y);
133 for (i = 0; i < interLen && inter[i].x1 < x0; ++i) {
134 count += inter[i].count;
137 // invariant: the subspan [x0,xx1] is inside the path
143 if (inter[i].x0 > xx1 + 1 &&
144 !(eo ? (count & 1) : (count != 0))) {
147 if (inter[i].x1 > xx1) {
150 count += inter[i].count;
157 GBool SplashXPathScanner::getNextSpan(int y, int *x0, int *x1) {
161 computeIntersections(y);
163 if (interIdx >= interLen) {
166 xx0 = inter[interIdx].x0;
167 xx1 = inter[interIdx].x1;
168 interCount += inter[interIdx].count;
170 while (interIdx < interLen &&
171 (inter[interIdx].x0 <= xx1 ||
172 (eo ? (interCount & 1) : (interCount != 0)))) {
173 if (inter[interIdx].x1 > xx1) {
174 xx1 = inter[interIdx].x1;
176 interCount += inter[interIdx].count;
184 void SplashXPathScanner::computeIntersections(int y) {
185 SplashCoord ySegMin, ySegMax, xx0, xx1;
189 // find the first segment that intersects [y, y+1)
190 i = (y >= interY) ? xPathIdx : 0;
191 while (i < xPath->length &&
192 xPath->segs[i].y0 < y && xPath->segs[i].y1 < y) {
197 // find all of the segments that intersect [y, y+1) and create an
198 // Intersect element for each one
200 for (j = i; j < xPath->length; ++j) {
201 seg = &xPath->segs[j];
202 if (seg->flags & splashXPathFlip) {
210 // ensure that: ySegMin < y+1
212 if (ySegMin >= y + 1) {
219 if (interLen == interSize) {
220 if (interSize == 0) {
225 inter = (SplashIntersect *)grealloc(inter,
226 interSize * sizeof(SplashIntersect));
229 if (seg->flags & splashXPathHoriz) {
232 } else if (seg->flags & splashXPathVert) {
236 // intersection with top edge
237 xx0 = seg->x0 + (y - seg->y0) * seg->dxdy;
239 // x coord of segment endpoint with min y coord
240 xx0 = (seg->flags & splashXPathFlip) ? seg->x1 : seg->x0;
242 if (ySegMax >= y + 1) {
243 // intersection with bottom edge
244 xx1 = seg->x0 + (y + 1 - seg->y0) * seg->dxdy;
246 // x coord of segment endpoint with max y coord
247 xx1 = (seg->flags & splashXPathFlip) ? seg->x0 : seg->x1;
251 inter[interLen].x0 = splashFloor(xx0);
252 inter[interLen].x1 = splashFloor(xx1);
254 inter[interLen].x0 = splashFloor(xx1);
255 inter[interLen].x1 = splashFloor(xx0);
257 if (ySegMin <= y && y < ySegMax && !(seg->flags & splashXPathHoriz)) {
258 inter[interLen].count = eo ? 1
259 : (seg->flags & splashXPathFlip) ? 1 : -1;
261 inter[interLen].count = 0;
266 qsort(inter, interLen, sizeof(SplashIntersect), &cmpIntersect);