Remains of trenches used by infantry during World War 1 play an important role in understanding and reconstructing the happenings during one of the darkest eras of human history. They allow us to look at and simulate the course of war in Europe. With developments of Lidar systems and progress in the areas of mapping and topology, we can now observe the terrain previously hidden from our view. In our thesis we present an algorithm for automatic detection of trenches on non-uniform terrain. The proposed algorithm uses principles of computer vision and applies them to the height map of the terrain, made from point cloud created by Lidar, to detect and mark trench-like structures. Results show that our approach outperforms a related method, while leaving enough room for possible upgrades and future work.