[Insight-users] Bresenham Line Iterator

[Miller, James V (Research)]

Benjamin, 

This is sounding good.

The IsAtEnd() is the best name we found to describe what an ITK iterator 
is doing.  We liked the STL convention that container.end() returned an iterator
one past the end of the container.  As you have seen, ITK can provide a much
richer set of iterators than an STL container, so we couldn't incorporate all
the iterators into the ITK containers.  Furthermore, the ITK iterators are
fairly heavyweight, so we wouldn't want to create them frequently, like in an
STL loop below (in the it != vec.end() clause)

	for (std::vector<int>:iterator it = vec.begin(); it != vec.end(); ++it)
	   {}

I would change the IsAtLastElement() to just IsAtLast(). STL also has a notion
of front() and back() that could be used.  I always forget the name of the back()
method in STL and end up trying to call last().  I may have polluted some of the
ITK iterators with the notion of "last" when it probably should be "back".  In 
my defense, "back" doesn't sound quite right to me in the context of ND iterators.
(I also wonder if the early versions of STL, circa 1992, called back() last()).

Your LineInterpolator2D might be called an Linear2DIndexInterpolator. I'd want
to keep the name sufficiently different for the ImageFunction Interpolators we have.

Your function object CurrentXSmallerCurrentYSmaller could be called 
Linear2DIndexComparator

Does your scan converter only work on the XY plane?  Or could I scan convert
a polygon on the YZ plane?

Jim


-----Original Message-----
From: Benjamin King [mailto:king.benjamin at mh-hannover.de]
Sent: Tuesday, June 07, 2005 4:43 AM
To: Miller, James V (Research); ITK
Subject: Re: [Insight-users] Bresenham Line Iterator


Hi Jim,

> FYI, I checked in a few changes to the LineIterator this morning.
I just took a look at them and I think you found a nice way to check for "one 
past the end" condition.

> IsAtEnd() is supposed to report true if the 
> iterator is one pixel past the end of the section it is iterating.  
Oh dear, I think I got this wrong. Matches the STL way, though. I probably was 
confused by the method's name.

I changed the polygon scan conversion code in this regard and removed some 
documentation debris from an earlier version. 

Summary:

Two (+0.5) new classes interact (with some STL-code):


1) LineInterpolator2D

A class similar but not equal to itk::LineIterator. The constructor takes two 
coordinates, x1, y1 and x2, y2. Let n := x2 - x1.

After initialization or a call to GoToBegin(), GetX()/GetY() return x1/y1.

After i calls of operator++ (0 <= i <= n), 
	GetX() returns x1+i/n(x2-x1) = x1+i and
	GetY() returns floor(y1+i/n(y2-y1))

With a call to IsYExact() the user of the class can test if rounding was 
necessary.

I just changed IsAtEnd() to return true after *more* than n calls of 
operator++ to match ITK convention.

IsAtLastElement() returns true after exactly n calls of operator++. This is a 
non-standard iterator feature, but I really need that functionality in the 
PolygonScanConverter class. Could be moved to the private section if 
PolygonScanConverter is made a friend class of LineInterpolator2D.


1.5) CurrentXSmallerCurrentYSmaller

That's a function class that sorts LineInterpolator2D's first by current x, 
then by current y, then by error offset.


2) PolygonScanConverter

The constructor takes a list of 2D coordinates that are the vertices of a 
closed 2D polygon in cyclic order. The polygon may be self-intersecting.
It can be used to iterate over all pixels inside the polygon.
A pixel is inside, iff there is a line from this pixel to infinity that 
intersects an odd number of polygon edges.
Please note that the set of inside pixels may be not connected even for simple 
polygons like this triangle: (0,0) (0,1) (3,2).

During iteration with operator++, scan rows are traversed from small x to 
large x and within a scan row from small y to large y.

GetX()/GetY() return the current iterator position

IsAtEnd() now matches the ITK convention and returns true iff the iterator 
travelled past the end.


Both classes still lack the ability to take an itk::Image and the 
corresponding Get()/Set(), GetIndex()/SetIndex() methods, but that is easily 
added.

I also provided a test program for PolygonScanConverter that can also measure 
iteration performance. For random polygons with n vertices, the run time is 
more than O(n), because there is some sorting necessary, <handwaiving>but 
that's not too bad in practice</handwaiving>.


Okay, please ignore the code I sent before and take the one in the attachment 
instead.


Cheers,
	Benjamin

-- 
Benjamin King
Experimentelle Radiologie
Medizinische Hochschule Hannover
Tel.: +49  511  532-2663