1 //:
2 // \file
3 // \brief  Polygon scan iterator tests.
4 // \author Amitha Perera
5 // \date   Apr 2002
6 //
7 // \verbatim
8 //  Modifications
9 //   25-SEP-2003 Michal Sofka - Adding test case for iterating polygon including its boundary.
10 //                              Iteration has been fixed, so conditions were corrected to test
11 //                              the exact number points inside the polygon (not just range).
12 //   30-APR-2004 Peter Vanroose - Test case added for which the iterator fails
13 //                                (it produced a very large value for xend()),
14 //                                as signalled by Kenneth Fritzsche and Gehua Yang.
15 // \endverbatim
16 
17 #include <iostream>
18 #include "testlib/testlib_test.h"
19 #include "vgl/vgl_polygon.h"
20 #include "vgl/vgl_polygon_scan_iterator.h"
21 #ifdef _MSC_VER
22 #  include "vcl_msvc_warnings.h"
23 #endif
24 
25 using Point_type = vgl_polygon<float>::point_t;
26 using Polygon_type = vgl_polygon<float>;
27 using Polygon_scan = vgl_polygon_scan_iterator<float>;
28 
29 static void
test_without_boundary()30 test_without_boundary()
31 {
32   Polygon_type poly;
33   poly.new_sheet();
34   // This is a triangle with 2 sides of length 3 parallel to the axes,
35   // at X=2.3 and Y=-0.4 resp.
36   poly.push_back(Point_type(-0.7f, -0.4f));
37   poly.push_back(Point_type(2.3f, 2.6f));
38   poly.push_back(Point_type(2.3f, -0.4f));
39 
40   // There will be scan lines at y=0, 1 and 2.
41   // Since boundary pixels (with their center outside of the triangle) are not
42   // to be included, the 6 pixels are (0,0) (1,0) (2,0) (1,1) (2,1) (2,2).
43   unsigned int count = 0;
44   Polygon_scan it(poly, false);
45   int y = 0;
46   for (it.reset(); it.next(); ++y)
47   {
48     std::cout << "Scan line at y=" << it.fscany() << " (" << it.scany() << ") goes from " << it.fstartx() << " ("
49               << it.startx() << ") to " << it.fendx() << " (" << it.endx() << ")\n";
50     TEST("iteration without boundary: y value", it.scany(), y);
51     TEST("iteration without boundary: first x value", it.startx(), y);
52     TEST("iteration without boundary: last x value", it.endx(), 2);
53     count += it.endx() - it.startx() + 1;
54   }
55   TEST("iteration without boundary: count", count, 6);
56 }
57 
58 static void
test_with_boundary()59 test_with_boundary()
60 {
61   Polygon_type poly;
62   poly.new_sheet();
63   // This is a 2x2 square with corner points at non-integer coordinates.
64   poly.push_back(Point_type(10.5f, 20.5f));
65   poly.push_back(Point_type(12.5f, 20.5f));
66   poly.push_back(Point_type(12.5f, 22.5f));
67   poly.push_back(Point_type(10.5f, 22.5f));
68 
69   // The "boundary" pixels (which only partially overlap the square) should be
70   // included, hence there are 3x4=12 pixels "inside" of this square:
71   unsigned int count = 0;
72   Polygon_scan it(poly);
73   int y = 21;
74   for (it.reset(); it.next(); ++y)
75   {
76     std::cout << "Scan line at y=" << it.fscany() << " (" << it.scany() << ") goes from " << it.fstartx() << " ("
77               << it.startx() << ") to " << it.fendx() << " (" << it.endx() << ")\n";
78     TEST("iteration with boundary: y value", it.scany(), y);
79     TEST("iteration with boundary: first x value", it.startx(), 10);
80     TEST("iteration with boundary: last x value", it.endx(), 13);
81     count += it.endx() - it.startx() + 1;
82   }
83   // There are points within the polygon. This includes points with
84   // integer valued coordinates and the ones at the boundary
85   // (each scan line begins at the boundary of the polygon).
86   TEST("iteration with boundary: count", count, 12);
87 }
88 
89 static void
test_degenerate_polygon()90 test_degenerate_polygon()
91 {
92   Polygon_type poly;
93   poly.new_sheet();
94   // This is a triangle with 2 sides of length 29 parallel to the axes,
95   // at X=39 and Y=10 resp., and with one duplicate corner point.
96   poly.push_back(Point_type(10, 10));
97   poly.push_back(Point_type(39, 10));
98   poly.push_back(Point_type(39, 39));
99   poly.push_back(Point_type(10, 10));
100 
101   // There will be scan lines at y=10 to 39, with x values going from y to 39.
102   // Hence the number of integer-valued points is 30+29+...+2+1=30*31/2=465.
103   Polygon_scan it(poly);
104   unsigned int count = 0;
105   int y = 10;
106   for (it.reset(); it.next(); ++y)
107   {
108     std::cout << "Scan line at y=" << it.fscany() << " (" << it.scany() << ") goes from " << it.fstartx() << " ("
109               << it.startx() << ") to " << it.fendx() << " (" << it.endx() << ")\n";
110     TEST("zero-length edges: y value", it.scany(), y);
111     TEST("zero-length edges: first x value", it.startx(), y);
112     TEST("zero-length edges: last x value", it.endx(), 39);
113     count += it.endx() - it.startx() + 1;
114   }
115   TEST("zero-length edges", count, 465);
116 }
117 
118 static void
test_empty_polygon()119 test_empty_polygon()
120 {
121   // This is an empty polygon.
122   Polygon_type poly;
123 
124   Polygon_scan it(poly);
125   unsigned int count = 0;
126   for (it.reset(); it.next();)
127   {
128     std::cout << "Scan line at y=" << it.fscany() << " (" << it.scany() << ") goes from " << it.fstartx() << " ("
129               << it.startx() << ") to " << it.fendx() << " (" << it.endx() << ")\n";
130     count += it.endx() - it.startx() + 1;
131   }
132   TEST("empty polygon", count, 0);
133 }
134 
135 static void
test_almost_horizontal()136 test_almost_horizontal()
137 {
138   Polygon_type poly;
139   poly.new_sheet();
140   poly.push_back(Point_type(424.f, 785.99975f));
141   poly.push_back(Point_type(426.f, 786.00012f));
142   poly.push_back(Point_type(426.f, 789.91188f));
143   poly.push_back(Point_type(424.f, 790.06225f));
144 
145   // There should be scan lines at y=786,787,788,789 and 790.
146   // The 3 middle ones are exactly of length 2, containing 3 integer points.
147   // The one at y=786 goes from x=424 to x=,
148   // while the one at y=490 goes from x=424 to x=.
149   Polygon_scan it(poly, false);
150   int y = 786;
151   for (it.reset(); it.next(); ++y)
152   {
153     std::cout << "Scan line at y=" << it.fscany() << " (" << it.scany() << ") goes from " << it.fstartx() << " ("
154               << it.startx() << ") to " << it.fendx() << " (" << it.endx() << ")\n";
155     TEST("almost horizontal sides: y value", it.scany(), y);
156     TEST("almost horizontal sides: first x value", it.startx(), 424);
157     int x = 426;
158     if (y == 790)
159       x -= 2;
160     if (y == 786)
161       --x;
162     TEST("almost horizontal sides: last x value", it.endx(), x);
163   }
164 }
165 
166 
167 static void
test_polygon_scan_iterator()168 test_polygon_scan_iterator()
169 {
170   test_without_boundary();
171   test_with_boundary();
172   test_degenerate_polygon();
173   test_empty_polygon();
174   test_almost_horizontal();
175 }
176 
177 TESTMAIN(test_polygon_scan_iterator);
178