Google Test Framework and Visual Studio 2010

Here is a few issues people get when they start using Google Test Framework with Visual Studio:

1. When an empty project is created with the default configuration in Visual Studio and you link it with gtest.lib, you get a lot of link errors like the following:

1>msvcprtd.lib(MSVCP100D.dll) : error LNK2005: “public: virtual __thiscall std::basic_iostream<char,struct std::char_traits<char> >::~basic_iostream<char,struct std::char_traits<char> >(void)” (??1?$basic_iostream@DU?$char_traits@D@std@@@std@@UAE@XZ) already defined in gtest.lib(gtest-all.obj)
1>msvcprtd.lib(MSVCP100D.dll) : error LNK2005: “public: virtual __thiscall std::basic_ios<char,struct std::char_traits<char> >::~basic_ios<char,struct std::char_traits<char> >(void)” (??1?$basic_ios@DU?$char_traits@D@std@@@std@@UAE@XZ) already defined in gtest.lib(gtest-all.obj)
1>msvcprtd.lib(MSVCP100D.dll) : error LNK2005: “public: __thiscall std::basic_iostream<char,struct std::char_traits<char> >::basic_iostream<char,struct std::char_traits<char> >(class std::basic_streambuf<char,struct std::char_traits<char> > *)” (??0?$basic_iostream@DU?$char_traits@D@std@@@std@@QAE@PAV?$basic_streambuf@DU?$char_traits@D@std@@@1@@Z) already defined in gtest.lib(gtest-all.obj)

This happens because the default compiler switch of gtest is /MTd and your empty project has /MDd. You need to make them consistent. One option is to change your test project and the tested project to /MTd.

2. You get the following errors when you mix your Release with gtest Debug and vice verse:

gtest.lib(gtest-all.obj) : error LNK2038: mismatch detected for ‘_ITERATOR_DEBUG_LEVEL’: value ‘0’ doesn’t match value ‘2’ in convex_hull_tests.obj
2>LIBCMT.lib(invarg.obj) : error LNK2005: __initp_misc_invarg already defined in LIBCMTD.lib(invarg.obj)
2>LIBCMT.lib(invarg.obj) : error LNK2005: __call_reportfault already defined in LIBCMTD.lib(invarg.obj)
2>LIBCMT.lib(invarg.obj) : error LNK2005: __set_invalid_parameter_handler already defined in LIBCMTD.lib(invarg.obj)
2>LIBCMT.lib(invarg.obj) : error LNK2005: __get_invalid_parameter_handler already defined in LIBCMTD.lib(invarg.obj)
2>LIBCMT.lib(invarg.obj) : error LNK2005: __invoke_watson already defined in LIBCMTD.lib(invarg.obj)

Convex Hull

I read about the problem of finding Convex Hull in Algorithm Design Manual and knew that the complexity should be N for points sorted by one coordinate. Before reading about existing solutions I determined to find my own. “Invent the wheel” in other words. I spent hours thinking about a solution. In the end I found one:

I have a collection containing convex hull points. It is an stl::list. It’s empty at the beginning. I loop through points sorted by x. So I move from left to right of the picture. At the end of processing each point I maintain the algorithm invariant in which the list contains the convex hull of the points processed so far.  If you imagine this visually, it’s like putting a deflated balloon on an object from left to right.

When I process a point, I calculate if it’s on the top edge of the hull and then I do the same for the bottom edge. I also loop through the points that are already in my existing convex hull collection to see if they are not on the edge yet given the current processed point. If it’s not I remove it from the hull collection.

An important part of the algorithm is the function ConvexHull::compare_vectors. It takes three points and calculates if the point in the middle is on the edge of the convex hull. It represents the three points p1, p2 and p3 as two vectors p1 – p2 and p2 – p3. Then it prolongs p1 – p2 vector until it intersects with x = p3.x line. If y of the intersection point is higher than p3.y, the point is on the top edge of the convex hull (picture 1).

Picture 1

The algorithm is in a console application that takes an image file (Picture 2), draws the convex hull and saves it to another image file (Picture 3). It supports multiple image file formats thanks to the stbi_image library.

Picture 2

 

After experimenting with my rasterizing algorithm I used Anti-Grain Geometry by Maxim Shemanarev. See the result on Picture 4.

 

 

Picture 3

Picture 4

You can find the sources on GitHub: https://github.com/evpo/ConvexHull

Binaries for windows are also available:

http://sourceforge.net/projects/convexhull/files/ (100% CLEAN award granted by Softpedia)

Download the zip file and run the cmd file to see it in action.