On Mon, 2004-10-25 at 23:19, Eric Jonas wrote:
I started writing my nice little implementation of Graham Scan, but then realized I was creating lots of little helper functions and whatnot, cluttering up the namespace. Before I get too far into this:
- Would it be appropriate to create a real Convex Hull class in NR (or
modify the existing one) such that you could call either: ConvexHull c(stl-container-of-points) or just do: ConvexHull c; c.add(p1) ... (where the points are NR points)?
That'd be nice to have; if you'd like to have a go at it, it'd be much appreciated. ConvexHull isn't apparently being used for its original purpose now, so you are free to do what you like with it.
Hmm, one thing ... having a constructor that takes a reference to an STL container isn't really in the spirit of the STL; it's probably better to have one that takes a start and end iterator. That's particularly helpful since some STL iterators do not have associated containers.
The only other thing to keep in mind is our definition of "insideness" for libnr: all points on the perimiter of a figure are considered to be inside the figure.
Hence, given a rectangle with opposite corners at (0,0) and (5,5), the points (2,3) and (3,5) are both considered to be "inside" the rectangle.
This also holds true for degenerate figures; for example, a rectangle with "opposite" corners at (0,0) and (0,5) still contains all points on the line from (0,0) to (0,5), inclusive, despite having no width and hence zero area. Similarly, a rectangle with corners (0,0) and (0,0) is considered to contain exactly one point.
[ If the above definition seems counterintuitive to anyone reading and thinking of bitmapped displays, please remember that pixels are a unit of area, not of length, so your expectations about the "insideness" of pixels still hold. A zero-area figure will contain no pixels. ]
I mention this since in the past we had difficulties with different definitions being applied in different parts of the code, resulting in happy fencepost errors; after long discussion we settled on this definition as the least mathematically troublesome.
-mental