Convex Hull

23/09/2022 /

Original link: https://yousazoe.top/archives/84b74385.html

introduction

In this section we will explore the central problem of computational geometry: the convex hull problem.

Convexity

Why Convex Hull

The first stop of our computational geometry is the convex hull problem, which is at the core of computational geometry, and this core is reflected in the fact that almost all problems can theoretically be reduced to convex hull problems.

Nails In The Table

Next, we will understand what the convex hull is through a specific hands-on experiment.

To do this you need to find a table or screen, put a series of pegs on the table, and then use a rubber band to hold it big enough to cover all the pegs on the table top.

The next thing is very easy, you just let go. Then with a snap, you’ll see this picture:

The rubber band just now will become such a segment of blue line segments, which are connected end to end to form a tight encirclement. The blue rubber band in the current state of the picture is what we call the convex hull. We can see that the so-called convex hull is determined by several nails on it, although some of them do not play a role. , which we can roughly feel because they stay inside.

So, what is the mystery between this?

Paint Blending

To better understand what a convex hull is, let’s look at another example of an application.

The artist often has to mix to get a paint that he wants but is not directly from the factory. We know that in general, each pigment can be divided into three numerical indicators of red, green and blue, and each combination corresponds to roughly one pigment.

We might as well consider only the two components of red and green for the sake of simplicity, so in this case, each pigment, that is, its corresponding color, can use two numbers such as red and green, or their overall composition. corresponding to the percentage of .

 C = (R, G)

For example, for a certain pigment X, its corresponding red component may be 10%, and the green component is 35%; for another pigment, such as Y, then its corresponding two components are 16% and 20%. %. Now the question is, can some of the pigments we hope be converted with these two pigments?

 X = (10%, 35%) Y = (16%, 20%)

Let’s take a look. When the pigments are mixed together, they change in many ways. There are many, many combinations. The colors obtained by blending each type of pigment according to different weights and proportions will actually be different. Of course, the artist has his blending methods, including his inspiration, so if we consider it from a mathematical point of view and an algorithmic point of view, what kind of guiding method should be used in this?

So from a mathematical point of view, we can generally think that there is a target color, such as U here. For this color, for example, he hopes that the proportion of red is 12%, and the proportion of green is 30%. %.

 U = (12%, 30%)

For such a target pigment, we should use the X and Y just now. What ratio should be used to mix and blend these two original pigments from the factory?

Well, I think you already know the answer. That’s right, we should mix two copies of X and one copy of Y to get U.

You might as well do a simple check, 10% of the two copies plus 16% of the one copy are combined and divided by 3, which is exactly 12%; and 35% of the two copies, plus 20 of the one copy Dividing % by 3 also happens to be 30%, so using a ratio of 2 to 1 is a solution to this problem.

Well, if it’s worth the time we spend on this, we’d still like to get a way, otherwise we’re going to be confused because if you don’t have a unified way behind this, then if you change the color next time For example, the V here requires 13% and 22%, then you may have to spend some time.

 V = (13%, 22%)

So the first question is whether this pigment can be blended out. It’s not like we said here, every two colors are given and you can mix all the colors. In fact, we may need a third color at this time. For example, here we may get the third color Z from the factory, and its corresponding proportion is 7% and 15%.

 Z = (07%, 15%)

Well, can I blend it with these three colors at this time?

OK, now I’ll reveal the answer. The correct ratio should be one part X, three parts Y plus the third color Z we just added, 1:3:1. You can calculate it according to the same method as just now, and I think the answer should be it.

So all the things discussed here are actually colors, or to be more precise, the blending of pigments. What does this have to do with computational geometry we’re talking about here? In fact, there is a very deep connection between them.

Color Space

Since we talk about geometry, we must talk about its most basic concept called space, Euclidean space.

Here we correspond the Euclidean space to the color, which we call the color space. Specifically, we want to correspond each color to a point in this space. Whether this color or pigment comes from the basic pigment directly supplied by the manufacturer, or a new color that the artist must re-blend for his creative needs. All in all, each color corresponds to a point in this space.

Of course, because we are talking about positive numbers here, it can be considered that it is basically limited to the first quadrant, which is not the main problem. So the problem now is that we can use this method to divide our three pigments, namely X, Y, and Z, according to the horizontal axis, that is, the value of the red component and the vertical axis, that is, the green component. The value of , draws one point one by one correspondingly, and three kinds of paint, which are three kinds of points respectively.

We just saw that if we were to blend U when we only had X and Y pigments, the ratio would be 2 to 1. In fact, this thing is reversed. After we give fixed X and Y, I can also draw the U of our target on this screen. If you draw it, you will find that it is actually very coincidental, we can Verify that the three of them are so-called collinear.

If this is the case, then we believe that U must be able to be blended, and its blending ratio can be explained geometrically at a glance.

You can do the calculation again, and I will tell you that the distance from U to X is relatively short, and the distance from U to Y is relatively long, and the ratio of the distances between the two is actually 1 to 2, and the ratio we just blended was 2 to 1 in reverse.

In fact, this is a rule, that is to say, if the color I want to blend happens to be on the connecting line segment between these two vertices, and there is a ratio between their distances, then this color must be able to be blended. come out. And the method of blending is contained in the ratio just now, as long as the distance ratio just now is reversed from 1 to 2 and becomes 2 to 1, it will definitely get this color.

You can think about it as an extreme example, the whole thing is that if you want to blend Y and blend X itself, the other component is 0 is the same reason.

Well, then we can also explain why the color V must be blended with the help of a third color. Because you can roughly see that because V is not located on the line segment determined by X and Y, and in this case we say that we must use Z, and the reason why we need to use Z or exactly according to our Just now that the ratio must be 1 to 3 to 1 is also implied in this diagram, the principle is the same.

In this case, what we need to do is to first confirm whether the point corresponding to the pigment V falls inside the triangle defined by X, Y, and Z. If it is, it must be blended; if No, at least it can’t be blended out.

Well, if it can be blended, what is the specific blending ratio? It is also given in this figure, so we only need to measure the distance from V to these three points, and then find their ratio. We will find that their ratio here is exactly 3 to 3 to 1, so the ratio of our blending here is naturally the color corresponding to the shortest and nearest point, and the opposite is true. In other words, it takes three parts; and the proportion of the color corresponding to the two points farther away is less, which can be used to measure

Of course, you still need to do careful derivation and rigorous verification of the above conclusions after class. Here you may wish to write down this conclusion: that is to say, if there is a pigment that can be blended by two known pigments, it will must lie on the connecting line between the two; if it is the case for three pigments, then the color of a certain target can be blended out if and only if it is located in the color space corresponding to the three points inside the triangle, and the ratio of blending is inversely proportional to their distance.

Convex Hull

Although we do not like mathematics very much, we have to use some simple mathematics to strictly express the conclusion we have just seen.

That is to say, if we are given a series of points in a plane two-dimensional space, what new pigments can be constructed from the pigments corresponding to these points? We will find that each new pigment corresponds geometrically to a certain harmonic scheme of the original pigments.

Then there are some blending schemes specifically called convex blending schemes, or Convex Combination. Specifically, if it is a convex combination, what conditions are required?

We say that there are roughly two main conditions:

  1. The sum of all components must be 100%
  2. All components must be non-negative

Extreme Points

Extremity

Among the points we gave at the beginning, which ones are stretched by the rubber bands that ultimately contribute to the convex hull, and which ones have no substantial effect, this property can be summed up in the so-called polarity.

Following the idea just now, our observation conclusion can be expressed as such a picture. Among all the nails just now, we see that everything is stretched by the final rubber band. For the time being, these nails that have no substantial effect are represented by cyan. What is the essential difference?

 if there exists a line L through p
 such that
 all points of S lie on the same side of L

Mathematical observations tell us that the so-called useful points all have one characteristic in common: through them we can always find a line such that all the points fall on the same side of the line.

Strategy

There is a very interesting algorithm in the sorting algorithm: Bubblesort. Our algorithm design here is very similar to it:

How to distinguish between poles and non-poles?

We need to recall the example of paint blending, where a paint can be blended with several other paints if and only if it falls inside a triangle. Conversely, a color like a pole that cannot be blended by other pigments cannot be included in any triangle. In this case, we have taken a step forward and transformed our screening task into whether a certain point will be included in the The interior of the triangle defined by the other three points.

In-Triangle Test

According to the analysis just now, the so-called convex hull problem can be reduced to a series of judgments: whether any point will fall inside the triangle corresponding to the other three points and be surrounded by them, we call this the In-Triangle Test.

Based on the In-Triangle Test, we can find out the non-poles one by one and exclude them from our field of vision.

First do the initialization, to set all points as poles like innocence inference. Then enumerate all possible triangles, and for each triangle we have to examine every point s except them; once we find that s does fall inside the current triangle, we can immediately conclude that it is not a pole , thereby excluding it.

 Make all points of S as EXTREME
 For each triangle Δ(p, ​​q, r)
 For each s in S\{p, q, r}
 If s in Δ(p, ​​q, r)
 marks as NON_EXTREME
 
 void extremePoint (Point S[], int n) {
 for ( int s = 0 ; s < n; s++)
 S[s].extreme = TRUE;

 // For each triangle
 for ( int p = 0 ; p < n; p++) {
 for ( int q = p + 1 ; q < n; q++) {
 for ( int r = q + 1 ; r < n; r++) {
 // For each point
 for ( int s = 0 ; s < n; s++) {
 if (s == p || s == q || s == r || !S[s].extreme)
 continue ;
                        
if ( InTriangle (S[p], S[q], S[r], S[s]))
 S[s].extreme = FALSE;
 }
 }
 }
 }

 }

To-Left Test

The first pole-based convex hull algorithm we gave is inefficient, but its significance is still very important, it will lead to the To-Left Test, the latter test is almost throughout our computational geometry course.

Whenever we give a point and a triangle, how to determine whether the point falls inside the triangle?

It is still a matter of trivial matters. We transformed the In-Triangle Test into three To-Left Tests. That is to say, if a point does fall inside a triangle, the To-Left Test performed relative to the three sides of the triangle will uniformly return true.

The so-called To-Left Test means that the point is on the left or right relative to the directed line segment. The keen observation here boils down to the fact that if a point falls inside the triangle, its necessary and sufficient conditions are true if and only if its To-Left Test is true with respect to these three lines, and it is on the left side of these three lines at the same time.

So now the question turns to how to judge a point to the left/right of a line segment?

Determinant

 bool ToLeft (Point p, Point q, Point s)
 return Area (p, q, s) > 0 ;

 int Area2 (Point p, Point q, Point s)
 return px * qy - py * qx
 + qx * ​​sy - qy * sx
 + sx * py - sy * px ;

Extreme Edges

Definition

The idea of ​​continuation of poles is extended to edges, and so-called pole edges are introduced.

The candidates for polar edges are actually the edges from any two adjacent poles. Those edges that contribute to the final convex hull are called polar edges; those that do not contribute to the convex hull are not polar edges. Or called non-polar edge, non-extreme Edge.

Just as we define a pole, if there is such a connecting edge that is indeed a pole edge, then all the points will fall on the same side of it at the same time, and the corresponding other side must be empty. More specifically, each edge of the convex hull boundary in counterclockwise order has the property that all points fall exactly to its left, and their right is empty.

In this way, the substantive problem in our algorithm is naturally transformed and embodied into the problem of how to identify whether the connecting edge between any two points is a polar edge.

Algorithm

 Let EE = null
 For each directed segment pq
 If points in S\{p, q} lie to the same side of pq
 Let {pq} = EE

According to the idea of ​​extreme edge, we can refine the pseudo code into such a real code:

 void markEE (Point S[], int n) {
 for ( int k = 0 ; k < n; k++)
 S[k].extreme = FALSE;

 for ( int p = 0 ; p < n; p++)
 for ( int q = p + 1 ; q < n; q++)
 checkEdge (S, n, p, q);
 }

 void checkEdge () {
 bool LEmpty = TRUE, REmpty = TRUE;
 for ( int k = 0 ; k < n && (LEmpty || REmpty); k++) {
 if (k != p && k != q) {
 ToLeft (S[p], S[q], S[k])? LEmpty = FALSE: REmpty = FALSE;
 }
 }

 if (LEmpty || REmpty)
 S[p].extreme = S[q].extreme = TRUE;
 }

Incremental Construction

Decrease and Conquer

Next, we will further improve from a typical algorithm idea of ​​Decrease and Conquer.

A classic algorithm that should be recalled is Insertionsort. The whole idea of ​​insertion sorting can be summarized as storing the entire sequence to be sorted into a linear structure, and then dividing it into sorted and unsorted parts at any time, and randomly find one in the unsorted part (usually the one that demarcates the two) element) to find the appropriate insertion position for this element in the sorted subsequence with a single lookup.

Similarly, we can also apply to polar edge algorithms.

In-Convex-Polygon Test

The progressive core technology is the In-Convex-Polygon Test, which is the problem of judging the interior or exterior of a polygon.

We need to judge whether a newly introduced point is the current pole. In fact, it is essentially to judge whether the current point is outside or inside the previous convex hull.

To convert the intuition just now into a mathematical judgment: every time we incrementally introduce this new point if it is the current extreme point, then the necessary and sufficient condition is actually to see whether it falls outside the current convex hull: if If it falls outside then it is the next extreme point; otherwise it is not.

If the convex polygon is indeed given, and you are going to do this kind of query multiple times after that, you can do a preprocessing (essentially sorting) on ​​the polygon.

We can roughly use one point as the base, and find a centered connection among the remaining n – 1 points to define a directed line segment. Next is our usual To-Left Test. After such a constant cost operation, we can indeed determine whether the unknown point falls on the left or the right, no matter which side we are searching for. The range is effectively halved.

In this way, every time we pass the cost of constant time, the scope of this problem can be effectively degraded to half of the previous one, and so on, we will eventually reach the trivial case – trivial case: In-Triangle Test.

But this algorithm is not feasible, the most important thing is that the convex hull is not static, in this case our preprocessing is ineffective.

Why Not Binary Search

Similar to insertion sort, the sorted part itself is dynamic, and even if binary search could be used, the insertion cost of linear storage would in the worst case invalidate this optimization.

Going back to the convex hull, the naive approach is best for this case. We can do the habitual CCW counterclockwise traversal along the given convex polygon boundary, and we can find that the interior points must be on the left-hand side; otherwise, if we find a point on the right side in any segment, then we can immediately Decide that it doesn’t fall inside.

Support-Lines

In fact, we still have a task to complete, to solve how to attach or add the newly introduced point to the original convex hull to make it a complete structure that can continue to be used.

The convex hull tangent is also known as the Support Line.

Pattern Of Turns

It only takes two To-Left Tests to unambiguously determine whether a vertex is from ts(L + R) or st(R + L).

Exterior/Interior

Jarvis March

Lower Bound

Graham Scan: Algorithm

Graham Scan: Example

Graham Scan: Correctness

Graham Scan: Analysis

Divide-And-Conquer (1)

Divide-And-Conquer (2)

Wrap-Up

This article is reprinted from: https://yousazoe.top/archives/84b74385.html
This site is for inclusion only, and the copyright belongs to the original author.