I implemented a triangulation of polygon in C++ in time O(n log(n))

Правка en2, от dmkz, 2023-10-20 17:11:06

Hello, codeforces!

Today, based on the article Triangulation of polygon from a book "Computational Geometry: Algorithms and applications", I implemented an algorithm of triangulation of any polygon without self intersections (non-convex polygons too) in C++.

$$$\text{ }$$$ $$$\text{ }$$$

Why it was needed for me? Probably, you know about a competition RuCode 7.0. In this year, qualification round contained next problem H: you are given an endless plane, painted in black and white stripes with height 1 and infinity width. These stripes alternate: black, white, black, white... You are given a polygon on this plane as list of $$$n\text{ }\left(3\le n \le 100000\right)$$$ 2D points with integer coordinates $$$x_i, y_i \left(-10^9 \le x_i, y_i \le 10^9\right)$$$ in some traversal order. Need to calculate a total square inside this polygon which is painted in black color.

Firstly, I solved for any triangle ($$$n=3$$$). Secondly, I thought about the triangulation of polygon and accumulating answers for each triangle.

So, the heaviest part of solution is the triangulation of polygon. I implemented this, stress-tested and fixed all of incomprehensible and dubious places of pseudo code that can be found in above book. For example, the author of this book states that vertex which has a type "merge" should be connected with another "merge" vertex, and this is used in pseudo-code, but there is an example, where it is not true. Stress-testing shows all of corner cases, which are not covered by the pseudo code.

I fixed all of mistakes which the stress-testing has found. You can just call this function:

std::vector<Triangle> triangulate(vpii points) {
    makeCounterClockwise(points);
    return triangulateFast(points);
}

The output of this function is a vector of triangles. Be careful, because I'm erasing non-meaningful vertices like if $$$P_{i-1}$$$, $$$P_{i}$$$ and $$$P_{i+1}$$$ lie on the same line than erase $$$P_i$$$.

Source code of solution for given problem

This solution works in $$$296$$$ ms in Yandex.Contest when $$$n=10^5$$$.

UPD. updated the source code by removing all unused things and commented lines

Теги rucode, geometry, computational geometry, useless algorithm

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru4 Русский dmkz 2023-10-20 17:55:32 242
en3 Английский dmkz 2023-10-20 17:43:19 9324
ru3 Русский dmkz 2023-10-20 17:36:22 9315
ru2 Русский dmkz 2023-10-20 17:14:59 23481
en2 Английский dmkz 2023-10-20 17:11:06 22576
en1 Английский dmkz 2023-10-20 01:56:27 51360 Initial revision for English translation
ru1 Русский dmkz 2023-10-20 01:19:04 51473 Первая редакция (опубликовано)