Skip to main content
deleted 3 characters in body
Source Link
HEKTO
  • 3.1k
  • 16
  • 19

The paper of Preparata and Hong says:

We let $l_A$ and $r_A$ be two points of A such that $x_2(l_A) = \min_i {x_2(a_i)}$ and $x_2(r_A) = \max_i{x_2(a_i)}$; similarly $l_B$ and $r_B$ are defined in B.

and:

Without loss of generality, we shall also assume that $r_A = a_1$ and $r_B = b_1$.

So, in this notation, vertices in your two polygons will be numbered differently:

$$A=((1.2,1),(0.2,0.2),(0.3,1.3))$$ $$B=((3,2),(2,2),(2,3))$$

In simple words, the algorithm starts from rightmost vertices on both polygons and continues clockwise potentially until leftmost vertices - so, only the lower sidesides of both polygons will be involved. Tangential vertices $(0.2,0.2)$ and $(3,2)$ will be found.

This paper has been published long time ago, and since then this algorithm has been clarified and simplified. The newest version of it starts from the rightmost vertex on the left polygon and the leftmost vertex on the right polygon, and continues clockwise for the left polygon and counterclockwise for the right polygon (to find lower tangential line). Also they usually check a vertex location relative to a line using the dot product instead of calculating and comparing slopes - because the tangential vertex has to have both its neighbors on the same side of the tangential line. For more information, pictures and code - please see this monograph, Section 3.8.

The paper of Preparata and Hong says:

We let $l_A$ and $r_A$ be two points of A such that $x_2(l_A) = \min_i {x_2(a_i)}$ and $x_2(r_A) = \max_i{x_2(a_i)}$; similarly $l_B$ and $r_B$ are defined in B.

and:

Without loss of generality, we shall also assume that $r_A = a_1$ and $r_B = b_1$.

So, in this notation, vertices in your two polygons will be numbered differently:

$$A=((1.2,1),(0.2,0.2),(0.3,1.3))$$ $$B=((3,2),(2,2),(2,3))$$

In simple words, the algorithm starts from rightmost vertices on both polygons and continues clockwise potentially until leftmost vertices - so, only the lower side of both polygons will be involved. Tangential vertices $(0.2,0.2)$ and $(3,2)$ will be found.

This paper has been published long time ago, and since then this algorithm has been clarified and simplified. The newest version of it starts from the rightmost vertex on the left polygon and the leftmost vertex on the right polygon, and continues clockwise for the left polygon and counterclockwise for the right polygon (to find lower tangential line). Also they usually check a vertex location relative to a line using the dot product instead of calculating and comparing slopes - because the tangential vertex has to have both its neighbors on the same side of the tangential line. For more information, pictures and code - please see this monograph, Section 3.8.

The paper of Preparata and Hong says:

We let $l_A$ and $r_A$ be two points of A such that $x_2(l_A) = \min_i {x_2(a_i)}$ and $x_2(r_A) = \max_i{x_2(a_i)}$; similarly $l_B$ and $r_B$ are defined in B.

and:

Without loss of generality, we shall also assume that $r_A = a_1$ and $r_B = b_1$.

So, in this notation, vertices in your two polygons will be numbered differently:

$$A=((1.2,1),(0.2,0.2),(0.3,1.3))$$ $$B=((3,2),(2,2),(2,3))$$

In simple words, the algorithm starts from rightmost vertices on both polygons and continues clockwise potentially until leftmost vertices - so, only lower sides of both polygons will be involved. Tangential vertices $(0.2,0.2)$ and $(3,2)$ will be found.

This paper has been published long time ago, and since then this algorithm has been clarified and simplified. The newest version of it starts from the rightmost vertex on the left polygon and the leftmost vertex on the right polygon, and continues clockwise for the left polygon and counterclockwise for the right polygon (to find lower tangential line). Also they usually check a vertex location relative to a line using the dot product instead of calculating and comparing slopes - because the tangential vertex has to have both its neighbors on the same side of the tangential line. For more information, pictures and code - please see this monograph, Section 3.8.

Source Link
HEKTO
  • 3.1k
  • 16
  • 19

The paper of Preparata and Hong says:

We let $l_A$ and $r_A$ be two points of A such that $x_2(l_A) = \min_i {x_2(a_i)}$ and $x_2(r_A) = \max_i{x_2(a_i)}$; similarly $l_B$ and $r_B$ are defined in B.

and:

Without loss of generality, we shall also assume that $r_A = a_1$ and $r_B = b_1$.

So, in this notation, vertices in your two polygons will be numbered differently:

$$A=((1.2,1),(0.2,0.2),(0.3,1.3))$$ $$B=((3,2),(2,2),(2,3))$$

In simple words, the algorithm starts from rightmost vertices on both polygons and continues clockwise potentially until leftmost vertices - so, only the lower side of both polygons will be involved. Tangential vertices $(0.2,0.2)$ and $(3,2)$ will be found.

This paper has been published long time ago, and since then this algorithm has been clarified and simplified. The newest version of it starts from the rightmost vertex on the left polygon and the leftmost vertex on the right polygon, and continues clockwise for the left polygon and counterclockwise for the right polygon (to find lower tangential line). Also they usually check a vertex location relative to a line using the dot product instead of calculating and comparing slopes - because the tangential vertex has to have both its neighbors on the same side of the tangential line. For more information, pictures and code - please see this monograph, Section 3.8.