Mercurial > hg > orthanc

comparison OrthancFramework/Sources/Images/ImageProcessing.cpp @ 4875:5dae41084ab7

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
fix filling polygons
author Sebastien Jodogne <s.jodogne@gmail.com>
date Tue, 18 Jan 2022 15:04:04 +0100
parents bee6da5155dc
children d8c8274d4e41
comparison
equal deleted inserted replaced
4874:bee6da5155dc 4875:5dae41084ab7
1981 }; 1981 };
1982 } 1982 }
1983 1983
1984 1984
1985 // For an index, return y-coordinate of next nonhorizontal line 1985 // For an index, return y-coordinate of next nonhorizontal line
1986 static size_t GetPolygonNextY(const std::vector<ImageProcessing::ImagePoint>& points, 1986 static int GetPolygonNextY(const std::vector<ImageProcessing::ImagePoint>& points,
1987 size_t k) 1987 size_t k)
1988 { 1988 {
1989 // cf. "yNext()" in textbook 1989 // cf. "yNext()" in textbook
1990 size_t j = k; 1990 size_t j = k;
1991 1991
1992 for (;;) 1992 for (;;)
2003 } 2003 }
2004 } 2004 }
2005 } 2005 }
2006 2006
2007 2007
2008 static size_t GetPolygonPreviousY(const std::vector<ImageProcessing::ImagePoint>& points, 2008 static int GetPolygonPreviousY(const std::vector<ImageProcessing::ImagePoint>& points,
2009 size_t k) 2009 size_t k)
2010 { 2010 {
2011 size_t j = k; 2011 size_t j = k;
2012 2012
2013 for (;;) 2013 for (;;)
2014 { 2014 {
2044 if (points.size() < 2) 2044 if (points.size() < 2)
2045 { 2045 {
2046 return; 2046 return;
2047 } 2047 }
2048 2048
2049 bool onlyHorizontalSegments = true;
2050 for (size_t i = 1; i < points.size(); i++)
2051 {
2052 if (points[0].GetY() != points[i].GetY())
2053 {
2054 onlyHorizontalSegments = false;
2055 break;
2056 }
2057 }
2058
2059 if (onlyHorizontalSegments)
2060 {
2061 // Degenerate case: There are only horizontal lines. If this is
2062 // the case, "GetPolygonPreviousY()" will be an infinite loop
2063 int x1 = points[0].GetX();
2064 int x2 = points[0].GetX();
2065 for (size_t i = 1; i < points.size(); i++)
2066 {
2067 assert(points[i].GetY() == points[0].GetY());
2068 x1 = std::min(x1, points[i].GetX());
2069 x2 = std::max(x2, points[i].GetX());
2070 }
2071 filler.Fill(points[0].GetY(), x1, x2);
2072 return;
2073 }
2074
2049 EdgeTable globalEdgeTable; 2075 EdgeTable globalEdgeTable;
2050 2076
2051 // cf. "buildEdgeList()" in textbook 2077 // cf. "buildEdgeList()" in textbook
2052 2078
2053 // Error in the textbook: we use "GetPolygonPreviousY()" instead of "points.size() - 2" 2079 // Error in the textbook: we use "GetPolygonPreviousY()" instead of "points.size() - 2"
2079 } 2105 }
2080 2106
2081 v1 = v2; 2107 v1 = v2;
2082 } 2108 }
2083 2109
2084 if (globalEdgeTable.empty()) 2110 assert(!globalEdgeTable.empty());
2085 {
2086 // Degenerate case: There were only horizontal lines
2087 int x1 = points[0].GetX();
2088 int x2 = points[0].GetX();
2089 for (size_t i = 1; i < points.size(); i++)
2090 {
2091 assert(points[i].GetY() == points[0].GetY());
2092 x1 = std::min(x1, points[i].GetX());
2093 x2 = std::max(x2, points[i].GetX());
2094 }
2095 filler.Fill(points[0].GetY(), x1, x2);
2096 return;
2097 }
2098 2111
2099 std::vector<PolygonEdge> activeEdges; 2112 std::vector<PolygonEdge> activeEdges;
2100 2113
2101 for (EdgeTable::const_iterator it = globalEdgeTable.begin(); it != globalEdgeTable.end(); ++it) 2114 for (EdgeTable::const_iterator it = globalEdgeTable.begin(); it != globalEdgeTable.end(); ++it)
2102 { 2115 {
2145 2158
2146 assert(activeEdges.size() % 2 == 0); 2159 assert(activeEdges.size() % 2 == 0);
2147 std::sort(activeEdges.begin(), activeEdges.end()); 2160 std::sort(activeEdges.begin(), activeEdges.end());
2148 2161
2149 // cf. "fillScan()" in textbook 2162 // cf. "fillScan()" in textbook
2150 for (size_t k = 0; k + 1 < activeEdges.size(); k += 2) 2163 for (size_t k = 0; k + 1 < activeEdges.size(); )
2151 { 2164 {
2152 int a = activeEdges[k].GetExitX(); 2165 int a = activeEdges[k].GetExitX();
2153 int b = activeEdges[k + 1].GetEnterX(); 2166 int b = activeEdges[k + 1].GetEnterX();
2154 filler.Fill(y, std::min(a, b), std::max(a, b)); 2167
2168 // Fix wrt. the textbook: merge overlapping segments
2169 k += 2;
2170 while (k + 1 < activeEdges.size() &&
2171 activeEdges[k].GetExitX() == b)
2172 {
2173 assert(a <= b);
2174 b = activeEdges[k + 1].GetEnterX();
2175 k += 2;
2176 }
2177
2178 assert(a <= b);
2179 filler.Fill(y, a, b);
2155 } 2180 }
2156 2181
2157 // cf. "updateActiveList()" in textbook 2182 // cf. "updateActiveList()" in textbook
2158 for (size_t k = 0; k < activeEdges.size(); k++) 2183 for (size_t k = 0; k < activeEdges.size(); k++)
2159 { 2184 {