Menghitung C(n,4) Titik Potong Segmen dalam Lingkaran dengan TikZ

Artikel ini membahas analisis geometri kombinatorik mengenai titik potong tali busur dalam lingkaran dan cara mengimplementasikan algoritmanya menggunakan paket TikZ di LaTeX.

Pendahuluan

Dalam geometri kombinatorik, terdapat sebuah teorem yang sangat menarik mengenai hubungan antara titik pada kurva cembung dan garis tali busur yang menghubungkannya.

Jika kita memilih $n$ buah titik pada keliling lingkaran (atau kurva tertutup cembung mana pun) dan menghubungkan setiap pasang titik dengan garis lurus, kita akan membentuk sebuah graf lengkap $K_n$. Pertanyaannya: Berapa banyak titik potong yang terbentuk di dalam lingkaran dari segmen-segmen garis tersebut?

Secara matematis, jawabannya adalah tepat $\binom{n}{4} = C(n,4)$ titik potong (dengan asumsi tidak ada tiga garis yang berpotongan di satu titik yang sama).

Artikel ini mengulas kode LaTeX TikZ karya Hugues Vermeiren yang menggunakan algoritma pembentukan kombinasi 4 elemen untuk secara otomatis mendeteksi dan menggambar seluruh titik potong tersebut.

Prinsip Matematika: Mengapa $C(n,4)$?

Untuk memahami mengapa jumlah titik potongnya adalah $C(n,4)$, perhatikan logika berikut:

1. Setiap empat titik terpisah ($A, B, C, D$) pada keliling lingkaran membentuk sebuah segi empat cembung.
2. Segi empat cembung tersebut memiliki dua diagonal, yaitu segmen $AC$ dan segmen $BD$.
3. Dua diagonal ini pasti saling berpotongan di satu titik di bagian dalam lingkaran.
4. Sebaliknya, setiap satu titik potong di dalam lingkaran selalu dihasilkan secara unik oleh persilangan dua diagonal dari tepat satu kelompok 4 titik.

Oleh karena itu, jumlah titik potong di dalam lingkaran sama dengan banyaknya cara memilih 4 titik dari total $n$ titik yang ada, yang dirumuskan sebagai:

Sebagai contoh, jika terdapat $n = 8$ titik pada lingkaran, maka akan terbentuk:

Kode Sumber LaTeX

Berikut adalah kode lengkap karya Hugues Vermeiren untuk menggambar graf lengkap $K_8$ dan menandai ke-70 titik potongnya secara otomatis:

% C(n,4) points of intersection
% Author: Hugues Vermeiren
\documentclass{article}
\usepackage{tikz}
\usepackage[active,tightpage]{preview}
\setlength\PreviewBorder{5pt}%
\usepackage{ifthen}
\usepackage{amsmath}
\usetikzlibrary{arrows,calc,intersections}

\begin{document}
\def\r{4}
\def\n{8}
\def\myangles{{25,50,85,125,160,220,250,280,340}} % Vektor posisi sudut titik

% Variabel dan counter untuk menghasilkan kombinasi 4-elemen
\newcounter{np}
\pgfmathsetcounter{np}{\n+1}
\newcounter{na}
\newcounter{nb}
\newcounter{nc}
\newcounter{ia}
\pgfmathsetcounter{na}{\n-1}
\pgfmathsetcounter{nb}{\n-2}
\pgfmathsetcounter{nc}{\n-3}

\newcounter{q}
\setcounter{q}{0} % flag berhenti
\newcounter{e}
\setcounter{e}{0} % penghitung kombinasi / titik potong
\newcounter{a}
\setcounter{a}{0}
\newcounter{b}
\setcounter{b}{1}
\newcounter{c}
\setcounter{c}{2}
\newcounter{d}
\setcounter{d}{2}

\begin{preview}
Consider $n$ randomly placed points on a circle.
\begin{enumerate}
  \item The complete graph on the $n$ points has $\begin{pmatrix}n\\2\end{pmatrix}$ edges.
  \item Each pair of edges yields an intersection point and there are (at most) $\begin{pmatrix}n\\4\end{pmatrix}$ such points.
\end{enumerate}

\begin{center}
\begin{tikzpicture}
% 1. Menggambar Graf Lengkap K_n
\fill[fill=blue!10!green!10!,draw=blue,dotted,thick] (0,0) circle (\r);
\pgfmathparse{\n-1}
\let\nn\pgfmathresult

\foreach \i in {0,...,\nn}{
  \pgfmathparse{\i+1}
  \let\ii\pgfmathresult
  \pgfmathparse{\myangles[\i]}
  \let\t\pgfmathresult
  \foreach \j in {\ii,...,\n} {
    \pgfmathparse{\myangles[\j]}
    \let\u\pgfmathresult
    \draw[blue,very thick] ({\r*cos(\t)},{\r*sin(\t)})--({\r*cos(\u)},{\r*sin(\u)});
  }
}

% 2. Menggambar Titik Simpul (Nodes) pada Lingkaran
\foreach \i in {0,...,\n}{
  \pgfmathparse{\myangles[\i]}
  \let\t\pgfmathresult
  \pgfmathsetcounter{ia}{\i+1}
  \fill[draw=blue,fill=blue!20!,thick] ({\r*cos(\t)},{\r*sin(\t)}) circle (2.5mm) node{$\mathbf{\theia}$};
}

% 3. Pengulangan Algoritma Kombinasi C(n,4) & Pencarian Titik Potong
\whiledo{\theq=0}{
  \stepcounter{e}
  \ifthenelse{\thee=1000}{\setcounter{q}{1}}{}% pengaman loop
  \ifthenelse{\thed=\n}
    {\ifthenelse{\thec=\thena}
      {\ifthenelse{\theb=\thenb}
        {\ifthenelse{\thea=\thenc}
          {\setcounter{q}{1}}
          {
            \stepcounter{a}
            \pgfmathsetcounter{b}{\thea+1}
            \pgfmathsetcounter{c}{\thea+2}
            \pgfmathsetcounter{d}{\thea+3}
          }
        }
        {
          \stepcounter{b}
          \pgfmathsetcounter{c}{\theb+1}
          \pgfmathsetcounter{d}{\theb+2}
        }
      }
      {
        \stepcounter{c}
        \pgfmathsetcounter{d}{\thec+1}
      }
    }
    {\stepcounter{d}}
    
  \ifthenelse{\theq=0}{
    % Perhitungan Koordinat 4 Titik
    \pgfmathparse{\r*cos(\myangles[\thea])} \let\xa\pgfmathresult
    \pgfmathparse{\r*sin(\myangles[\thea])} \let\ya\pgfmathresult
    \pgfmathparse{\r*cos(\myangles[\theb])} \let\xb\pgfmathresult
    \pgfmathparse{\r*sin(\myangles[\theb])} \let\yb\pgfmathresult
    \pgfmathparse{\r*cos(\myangles[\thec])} \let\xc\pgfmathresult
    \pgfmathparse{\r*sin(\myangles[\thec])} \let\yc\pgfmathresult
    \pgfmathparse{\r*cos(\myangles[\thed])} \let\xd\pgfmathresult
    \pgfmathparse{\r*sin(\myangles[\thed])} \let\yd\pgfmathresult
    
    \coordinate (A) at (\xa,\ya);
    \coordinate (B) at (\xb,\yb);
    \coordinate (C) at (\xc,\yc);
    \coordinate (D) at (\xd,\yd);
    
    % Menentukan Lintasan Tali Busur Diagonal
    \path[name path=sega] (A) -- (C);
    \path[name path=segb] (B) -- (D);
    
    % Mencari Titik Potong dengan Pustaka Intersections TikZ
    \path [name intersections={of=sega and segb}];
    \coordinate (X) at (intersection-1);
    \fill[fill=green!50!,draw=blue] (X) circle (0.8mm);
  }{}
}
\end{tikzpicture}
\end{center}

\addtocounter{e}{-1}
Number of generated intersection points : \thee
\end{preview}
\end{document}

Hasil Kompilasi

Keluaran visual yang dihasilkan menunjukkan pola simetris yang sangat indah dari persilangan garis dan titik-titik potong hijau di dalamnya:

Analisis Struktur Kode Terperinci

1. Pustaka & Konfigurasi Utama

• intersections: Pustaka TikZ penting (\usetikzlibrary{intersections}) yang memungkinkan perhitungan titik potong antara dua path secara otomatis tanpa perlu menghitung persamaan garis secara manual.
• ifthen: Paket logika LaTeX yang menyediakan perintah percabangan \ifthenelse dan pengulangan \whiledo.

2. Pembentukan Graf Lengkap $K_n$

• Array \myangles menyimpan sudut posisi 8 titik pada lingkaran.
• Dua perulangan bertingkat \foreach \i dan \foreach \j menghubungkan setiap pasang titik $i$ dan $j$ ($0 \le i < j \le n$) dengan garis biru tebal \draw[blue,very thick]. Jumlah total garis yang digambar adalah: $\binom{8}{2} = \frac{8 \times 7}{2} = 28 \text{ garis}$

3. Generator Kombinasi 4-Elemen

• Loop \whiledo{\theq=0} mengimplementasikan algoritma leksikografis untuk menghasilkan kombinasi indeks $(a, b, c, d)$ sedemikian rupa sehingga $a < b < c < d$.
• Algoritma ini memastikan bahwa setiap subset 4 titik hanya diproses tepat satu kali.

4. Penentuan Titik Potong Interaktif

• Untuk setiap 4 titik $(A, B, C, D)$, didefinisikan dua path silang sega ($A \to C$) dan segb ($B \to D$).
• Perintah \path [name intersections={of=sega and segb}]; secara otomatis menghitung titik temu kedua garis dan menyimpannya pada koordinat (intersection-1).
• Titik potong digambar menggunakan perintah \fill[fill=green!50!,draw=blue] (X) circle (0.8mm);.

Eksperimen Variasi TikZ

Anda dapat mencoba beberapa modifikasi menarik pada kode ini:

1. Mengubah Jumlah Titik ($n$): Ubah \def\n{8} menjadi \def\n{6} untuk melihat $\binom{6}{4} = 15$ titik potong, atau \def\n{10} untuk $\binom{10}{4} = 210$ titik potong.
2. Posisi Titik Berjarak Sama (Reguler): Gantikan vektor \myangles manual dengan perhitungan posisi seragam:
   latex

   \pgfmathsetmacro{\t}{\i * 360 / \n}

3. Pewarnaan Tingkat Kedalaman: Anda dapat mewarnai titik potong berdasarkan jaraknya dari pusat lingkaran untuk efek visual yang spektakuler.

Kesimpulan

Kode TikZ ini menyatukan konsep kombinatorika matematika dan geometri komputasional secara elegan. Dengan memanfaatkan pustaka intersections pada TikZ, perhitungan posisi fisik dari puluhan titik potong dapat dilakukan secara otomatis hanya berdasarkan aturan kombinasi dasar.

Referensi

1. Hugues Vermeiren, Points of intersection, TeXample.net
2. Till Tantau, The TikZ and PGF Manual, v3.1.10, 2024.
3. Graham, R. L., Knuth, D. E., & Patashnik, O., Concrete Mathematics: A Foundation for Computer Science.

Ditulis oleh: Aan Triono
Lisensi: CC BY-SA 4.0