How to decompose a polygon into a tree of vertices?

Question

Algorithms

Was looking for algorithms to determine if a point is inside a polygon. I found an interesting article on Habré: "Methods for determining whether a point belongs to a polygon .... It discusses three methods, two of which have complexity O(log n) .

I did not understand how you can split a closed ring of vertices into a tree. Googled, and I found that trees are made for 3D models, but there it is justified by the triangulation of polygons and the subsequent dynamic change in the level of detail.I

don’t understand how this applies here.Is this the author’s mistake or is it really possible?

Answer 1

It looks like the author messed up. I heard somewhere about the logarithmic algorithm, I know what kind of logarithm balanced binary trees usually work with, so I tied it together.
In the case of ray tracing, there is no implementation for the logarithm at all - because a non-convex polygon can have O(n) intersections with a ray (think of a saw).
In the case of the closest point - if there is a structure, then this is something like a trapezoidal map - this is such a mind-blowing thing that I don’t advise you to even think about it. You need to break the space into areas closest to each side.
For the logarithm there is a solution through binary search.
Break the space into vertical columns with all the x coordinates of all the vertices of the polygon. Inside each of them there will be an even number of sides. Write an equation for each side and sort them by height.
When prompted, first use a binsearch to find in which column the point lies. Then, using one more binsearch, find between which of the two lines the point lies. Here comparisons will no longer be easy numbers, but it will be necessary to substitute a point in the equations of lines and see if the point lies above or below. If a point lies in such a way that an odd number of lines are above (and below) it, then the point is inside.
The problem with this method is that it requires O(n^2) memory in the worst case and the same preprocessing.
But, for convex polygons, there will be only two straight lines in each column. Herea description of the method with an implementation for this simplified case.