Clipping Lines to a Rectangle using the Cohen-Sutherland Algorithm
Line Clipping C# Cohen-Sutherland
As I mentioned, most of the implementations I’ve studied are either incomplete or broken. Particularly, I haven’t found an example yet that correctly clips the edges of the generated Voronoi polygons to a rectangular area. So long as all you care about is rendering the graph to the screen, this isn’t a big problem, since most 2D graphics libraries will happily draw lines that extend beyond the drawable area of the screen. However, if you’re trying to subdivide a rectangular region into Voronoi polygons, its kind of nice to have your edges actually clipped to that region. What I’m envisioning doing with this code eventually is using it to render 3D maps, subdivided into territories, but with an overlaid rectangular grid for moving units – think of the strategic map in Total War games or Lords of the Realm.
After I got frustrated with trying to make the broken clipping code I was working from perform correctly, I trolled Google and came across theCohen-Sutherland line-clipping algorithm. This looked to be exactly what I needed, and wonder of wonders, the Wikipedia page actually featured a readable, reasonable example, rather than the obtuse academic pseudo-code you usually find there (see the Fortune’s Algorithm article…). The only thing I would caution you about with the Wikipedia example is that it uses a coordinate system where the origin is the lower-left bounds of a rectangle as usually encountered in mathematics, rather than the upper-left origin we commonly use in computer graphics, so some tweaking is necessary.
The code for this example can be downloaded from my github repository, at https://github.com/ericrrichards/dx11.git. The algorithm is included in the Algorithms project, while the example code is in the CohenSutherlandExample project. The example code is a quick-and-dirty mess of GDI drawing code, so I’m going to focus on the algorithm code.
Read more »