2
$\begingroup$

I'm reading the book Computational Geometry in C by O'Rourke. One of the problems ask the following

Diagonals$\rightarrow$triangulation. Given a list of diagonals of a polygon forming a triangulation, with each diagonal specified by a counterclockwise indices of the endpoints, design an algorithm to build the triangulation dual tree.

While I have a vague idea of how to solve the given problem, it isn't clear to me what exactly diagonal specified by a counterclockwise indices of the endpoints mean as this seems important in the algorithm design.

O'Rourke's own sample input (below) specified a list of coordinates which isn't obvious to me how they are a list of diagonals.

0   0
10  7
12  3
20  8
13  17
10  12
12  14
14  9
8   10
6   14
10  15
7   18
0   16
1   13
3   15
5   8
-2  9
5   5

I would be grateful if someone could give a hint on either what the counterclockwise indices of the endpoints mean, or how the list of points above translates to a list of diagonals. Thank you.

$\endgroup$
1
  • $\begingroup$ This list is called "Table 1.1. Vertex coordinates for the polygon shown in Figure 1.27". There are no diagonals in this list, however you can find all the diagonals in this Figure 1.27 (if you want to experiment with them). It looks like the counterclockwise indexing is about indices of the polygon vertices, but not about its diagonals. $\endgroup$
    – HEKTO
    Feb 20, 2022 at 0:23

1 Answer 1

1
$\begingroup$

I can only guess, but here is my guess. Indices means that if there are $n$ points, you assign each point a different number from $1,2,\dots,n$. Counterclockwise means that you imagine walking around the perimeter in counterclockwise direction, sequentially numbering the points you visit 1, 2, 3, ..., respectively. This assigns an index to each point. "diagonal specified by a counterclockwise indices of the endpoints" means that the way a diagonal represented is by identifying its two endpoints; each endpoint is identified by the index assigned above.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.