{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "9e84b97a",
   "metadata": {},
   "source": [
    "# kdTreeBinning\n",
    "Example binning the data in cells of equal content using a kd-tree.\n",
    "\n",
    "Using TKDTree wrapper class as a data binning structure\n",
    "Plot the 2D data using the TH2Poly class\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "**Author:** Bartolomeu Rabacal  \n",
    "<i><small>This notebook tutorial was automatically generated with <a href= \"https://github.com/root-project/root/blob/master/documentation/doxygen/converttonotebook.py\">ROOTBOOK-izer</a> from the macro found in the ROOT repository  on Tuesday, May 19, 2026 at 08:25 PM.</small></i>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9f7fdecf",
   "metadata": {},
   "source": [
    "-----------------------------------------------------------------------------------------------\n",
    "Create random sample with regular binning plotting"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a42d67de",
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    " const UInt_t DATASZ = 10000;\n",
    " const UInt_t DATADIM = 2;\n",
    " const UInt_t NBINS = 50;\n",
    "\n",
    " Double_t smp[DATASZ * DATADIM];\n",
    "\n",
    " double mu[2] = {0,2};\n",
    " double sig[2] = {2,3};\n",
    " TRandom3 r;\n",
    " r.SetSeed(1);\n",
    " for (UInt_t i = 0; i < DATADIM; ++i)\n",
    "    for (UInt_t j = 0; j < DATASZ; ++j)\n",
    "       smp[DATASZ * i + j] = r.Gaus(mu[i], sig[i]);\n",
    "\n",
    " UInt_t h1bins = (UInt_t) sqrt(NBINS);\n",
    "\n",
    " TH2D* h1 = new TH2D(\"h1BinTest\", \"Regular binning\", h1bins, -5., 5., h1bins, -5., 5.);\n",
    " for (UInt_t j = 0; j < DATASZ; ++j)\n",
    "    h1->Fill(smp[j], smp[DATASZ + j]);"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d3ed0711",
   "metadata": {},
   "source": [
    "---------------------------------------------------------------------------------------------\n",
    "Create KDTreeBinning object with TH2Poly plotting"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4dff6f59",
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    " TKDTreeBinning* kdBins = new TKDTreeBinning(DATASZ, DATADIM, smp, NBINS);\n",
    "\n",
    " UInt_t nbins = kdBins->GetNBins();\n",
    " UInt_t dim   = kdBins->GetDim();\n",
    "\n",
    " const Double_t* binsMinEdges = kdBins->GetBinsMinEdges();\n",
    " const Double_t* binsMaxEdges = kdBins->GetBinsMaxEdges();\n",
    "\n",
    " TH2Poly* h2pol = new TH2Poly(\"h2PolyBinTest\", \"KDTree binning\", kdBins->GetDataMin(0), kdBins->GetDataMax(0), kdBins->GetDataMin(1), kdBins->GetDataMax(1));\n",
    "\n",
    " for (UInt_t i = 0; i < nbins; ++i) {\n",
    "    UInt_t edgeDim = i * dim;\n",
    "    h2pol->AddBin(binsMinEdges[edgeDim], binsMinEdges[edgeDim + 1], binsMaxEdges[edgeDim], binsMaxEdges[edgeDim + 1]);\n",
    " }\n",
    "\n",
    " for (UInt_t i = 1; i <= kdBins->GetNBins(); ++i)\n",
    "    h2pol->SetBinContent(i, kdBins->GetBinDensity(i - 1));\n",
    "\n",
    " std::cout << \"Bin with minimum density: \" << kdBins->GetBinMinDensity() << std::endl;\n",
    " std::cout << \"Bin with maximum density: \" << kdBins->GetBinMaxDensity() << std::endl;\n",
    "\n",
    " TCanvas* c1 = new TCanvas(\"glc1\", \"TH2Poly from a kdTree\",0,0,600,800);\n",
    " c1->Divide(1,3);\n",
    " c1->cd(1);\n",
    " h1->Draw(\"lego\");\n",
    "\n",
    " c1->cd(2);\n",
    " h2pol->Draw(\"COLZ L\");\n",
    " c1->Update();"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "df474ac8",
   "metadata": {},
   "source": [
    "-------------------------------------------------\n",
    "Draw an equivalent plot showing the data points"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "28f82e63",
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    " std::vector<Double_t> z = std::vector<Double_t>(DATASZ, 0.);\n",
    " for (UInt_t i = 0; i < DATASZ; ++i)\n",
    "    z[i] = (Double_t) h2pol->GetBinContent(h2pol->FindBin(smp[i], smp[DATASZ + i]));\n",
    "\n",
    " TGraph2D *g = new TGraph2D(DATASZ, smp, &smp[DATASZ], &z[0]);\n",
    " g->SetMarkerStyle(20);\n",
    "\n",
    " c1->cd(3);\n",
    " g->Draw(\"pcol\");\n",
    " c1->Update();"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "145ef6fa",
   "metadata": {},
   "source": [
    "---------------------------------------------------------\n",
    "make a new TH2Poly where bins are ordered by the density"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d6bbcce5",
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    " TH2Poly* h2polrebin = new TH2Poly(\"h2PolyBinTest\", \"KDTree binning\", kdBins->GetDataMin(0), kdBins->GetDataMax(0), kdBins->GetDataMin(1), kdBins->GetDataMax(1));\n",
    " h2polrebin->SetFloat();"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "87850904",
   "metadata": {},
   "source": [
    "---------------------------------\n",
    "Sort the bins by their density"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8dfebecf",
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    " kdBins->SortBinsByDensity();\n",
    "\n",
    " for (UInt_t i = 0; i < kdBins->GetNBins(); ++i) {\n",
    "    const Double_t* binMinEdges = kdBins->GetBinMinEdges(i);\n",
    "    const Double_t* binMaxEdges = kdBins->GetBinMaxEdges(i);\n",
    "    h2polrebin->AddBin(binMinEdges[0], binMinEdges[1], binMaxEdges[0], binMaxEdges[1]);\n",
    " }\n",
    "\n",
    " for (UInt_t i = 1; i <= kdBins->GetNBins(); ++i){\n",
    "    h2polrebin->SetBinContent(i, kdBins->GetBinDensity(i - 1));}\n",
    "\n",
    " std::cout << \"Bin with minimum density: \" << kdBins->GetBinMinDensity() << std::endl;\n",
    " std::cout << \"Bin with maximum density: \" << kdBins->GetBinMaxDensity() << std::endl;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4b1824f9",
   "metadata": {},
   "source": [
    "now make a vector with bin number vs position"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8fce196b",
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    " for (UInt_t i = 0; i < DATASZ; ++i)\n",
    "   z[i] = (Double_t) h2polrebin->FindBin(smp[i], smp[DATASZ + i]);\n",
    "\n",
    " TGraph2D *g2 = new TGraph2D(DATASZ, smp, &smp[DATASZ], &z[0]);\n",
    " g2->SetMarkerStyle(20);"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4a0b6238",
   "metadata": {},
   "source": [
    "plot new TH2Poly (ordered one) and TGraph2D\n",
    "The new TH2Poly has to be same as old one and the TGraph2D should be similar to\n",
    "the previous one. It is now made using as z value the bin number"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b58e1e69",
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    " TCanvas* c4 = new TCanvas(\"glc4\", \"TH2Poly from a kdTree (Ordered)\",50,50,800,800);\n",
    "\n",
    " c4->Divide(2,2);\n",
    " c4->cd(1);\n",
    " h2polrebin->Draw(\"COLZ L\");  // draw as scatter plot\n",
    "\n",
    " c4->cd(2);\n",
    " g2->Draw(\"pcol\");\n",
    "\n",
    " c4->Update();"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "484210d4",
   "metadata": {},
   "source": [
    "make also the 1D binned histograms"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "baae3080",
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    " TKDTreeBinning* kdX = new TKDTreeBinning(DATASZ, 1, &smp[0], 20);\n",
    " TKDTreeBinning* kdY = new TKDTreeBinning(DATASZ, 1, &smp[DATASZ], 40);\n",
    "\n",
    "\n",
    "kdX->SortOneDimBinEdges();\n",
    "kdY->SortOneDimBinEdges();\n",
    "\n",
    "TH1* hX=new TH1F(\"hX\", \"X projection\", kdX->GetNBins(), kdX->GetOneDimBinEdges());\n",
    "for(int i=0; i<kdX->GetNBins(); ++i){\n",
    "  hX->SetBinContent(i+1, kdX->GetBinDensity(i));\n",
    "}\n",
    "\n",
    "TH1* hY=new TH1F(\"hY\", \"Y Projection\", kdY->GetNBins(), kdY->GetOneDimBinEdges());\n",
    "for(int i=0; i<kdY->GetNBins(); ++i){\n",
    "  hY->SetBinContent(i+1, kdY->GetBinDensity(i));\n",
    "}\n",
    "\n",
    "c4->cd(3);\n",
    "hX->Draw();\n",
    "c4->cd(4);\n",
    "hY->Draw();"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "21fcbaec",
   "metadata": {},
   "source": [
    "Draw all canvases "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a6f4f015",
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "gROOT->GetListOfCanvases()->Draw()"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "ROOT C++",
   "language": "c++",
   "name": "root"
  },
  "language_info": {
   "codemirror_mode": "text/x-c++src",
   "file_extension": ".C",
   "mimetype": " text/x-c++src",
   "name": "c++"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}