[Insight-users] Bresenham Line Iterator

[Benjamin King]

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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: PolygonScanConversion.tar.gz
Type: application/x-tgz
Size: 6141 bytes
Desc: not available
Url : http://public.kitware.com/pipermail/insight-users/attachments/20050607/279a916b/PolygonScanConversion.tar.bin