<iframe 
    src="https://jsxgraph.uni-bayreuth.de/share/iframe/poisson-disk-sampling-with-many-points" 
    style="border: 1px solid black; overflow: hidden; width: 550px; aspect-ratio: 55 / 65;" 
    name="JSXGraph example: Poisson disk sampling with many points" 
    allowfullscreen
></iframe>

<div id="board-0-wrapper" class="jxgbox-wrapper " style="width: 100%; ">
   <div id="board-0" class="jxgbox" style="aspect-ratio: 1 / 1; width: 100%;" data-ar="1 / 1"></div>
</div>

<script type = "text/javascript"> 
    /*
    This example is licensed under a 
    Creative Commons Attribution ShareAlike 4.0 International License.
    https://creativecommons.org/licenses/by-sa/4.0/
    
    Please note you have to mention 
    The Center of Mobile Learning with Digital Technology
    in the credits.
    */
    
    const BOARDID = 'board-0';

    // ----------------------------------------------------------
    // Start external file
    //
    // Poisson disk sampling.
    // Pure JavaScript, no JSXGraph, yet.
    //
    /**
     * Poisson Disk Sampling (Bridson Algorithm)
     * Generates points with a minimum distance between each other.
     *
     * @param {number} width - area width
     * @param {number} height - area height
     * @param {number} radius - Minimum distance between points
     * @returns {Array<{x: number, y: number}>} Array of sampled points
     */
    var poissonDiskSampling = function (width, height, radius) {
      const k = 30; // max attempts per point before rejection
      const cellSize = radius / Math.sqrt(2);
      const cols = Math.ceil(width / cellSize);
      const rows = Math.ceil(height / cellSize);
    
      // Grid to track occupied cells (flat array for performance)
      const grid = new Int32Array(cols * rows).fill(-1);
    
      // Helper: map (x, y) to grid cell index
      function cellIndex(x, y) {
        const col = Math.floor(x / cellSize);
        const row = Math.floor(y / cellSize);
        if (col < 0 || col >= cols || row < 0 || row >= rows) return -1;
        return row * cols + col;
      }
    
      // Result points
      const points = [];
    
      // Active list (indices into `points`)
      const active = [];
    
      // Seed the first point
      points.push({ x: Math.random() * width, y: Math.random() * height });
      active.push(0);
      grid[cellIndex(points[0].x, points[0].y)] = 0;
    
      while (active.length > 0) {
        // Pick a random active point
        const idx = Math.floor(Math.random() * active.length);
        const point = points[active[idx]];
    
        // Try k random points in the annulus around it
        let found = false;
        for (let attempt = 0; attempt < k; attempt++) {
          // Random angle + random radius in [radius, 2*radius]
          const angle = Math.random() * 2 * Math.PI;
          const r = radius * (1 + Math.random()); // uniform in annulus
          const x = point.x + r * Math.cos(angle);
          const y = point.y + r * Math.sin(angle);
    
          // Check bounds
          if (x < 0 || x >= width || y < 0 || y >= height) continue;
    
          // Check nearby cells in the grid
          const col = Math.floor(x / cellSize);
          const row = Math.floor(y / cellSize);
    
          let tooClose = false;
          // Search the 5x5 neighborhood of cells
          for (let dr = -2; dr <= 2; dr++) {
            for (let dc = -2; dc <= 2; dc++) {
              const nc = col + dc;
              const nr = row + dr;
              if (nc < 0 || nc >= cols || nr < 0 || nr >= rows) continue;
              const neighborIdx = grid[nr * cols + nc];
              if (neighborIdx === -1) continue;
    
              const dx = points[neighborIdx].x - x;
              const dy = points[neighborIdx].y - y;
              if (dx * dx + dy * dy < radius * radius) {
                tooClose = true;
                break;
              }
            }
            if (tooClose) break;
          }
    
          if (tooClose) continue;
    
          // Valid point found
          const newIdx = points.length;
          points.push({ x, y });
          active.push(newIdx);
          grid[cellIndex(x, y)] = newIdx;
          found = true;
          break;
        }
    
        // If no valid point found after k attempts, remove from active
        if (!found) {
          active[idx] = active[active.length - 1];
          active.pop();
        }
      }
    
      return points;
    };
    
    // Add new defaults and new attributes
    JXG.extend(JXG.Options, {
      poissonsample: {         // Lower case
        name: '',
        highlight: false,
        size: 1,
        strokeWidth: 0,
        color: JXG.palette.blue,
        withLabel: false,
        withCircle: false,
        circle: {
          strokeWidth: 0.5,
          strokeColor: 'red',
          strokeOpacity: 0.5,
          highlight: false
        }
      }
    });
    
    // Create constructor and register element
    // Create new JSXGraph composition element poissonsample
    // Add two methods: sample() and resample()
    JXG.createPoissonSample = function (board, parents, attributes) {
      var box = parents[0],
        r = parents[1],
        el;
    
      if (!JXG.isArray(box) || box.length != 4 || !JXG.isNumber(r)) {
        throw new Error("JSXGraph: Can't create Poisson sample with these parameters. Supply bounding box array and number radius.");
      }
    
      el = new JXG.Composition();
    
      el.box = box;
      el.radius = r;
      el.poissonDiskSampling = poissonDiskSampling;
      el.poissonpoints = null;
    
      el.sample = function () {
        var w = this.box[2] - this.box[0],
          h = this.box[1] - this.box[3],
          w2 = w / 2,
          h2 = h / 2,
          withCircle,
          attr, points;
    
        attr = JXG.copyAttributes(attributes, board.options, 'poissonsample');
        this.poissonpoints = this.poissonDiskSampling(w, h, JXG.evaluate(this.radius));
        // console.log(this.points.length)
        withCircle = attr.withcircle;
    
        // console.time('sample');
        let pp = this.poissonpoints;
        for (let i = 0; i < pp.length; i++) {
          let p = board.create('point', [pp[i].x - w2, pp[i].y - h2], attr);
          el.add(i, p);
          if (withCircle) {
            el.add( i + '_c', board.create('circle', [p, this.radius], attr.circle) );
          }
        }
        // console.timeEnd('sample');
      };
    
      el.resample = function () {
        var le = this.poissonpoints.length, i;
    
        // Remove all points
        board.removeObject(this.objectsList, false);
        for (i = 0; i < le; i++) {
          this.remove(i);
          this.remove(i + '_c');
        }
    
        // Sample again
        this.sample();
      };
    
      el.sample();
    
      return el;
    };
    JXG.registerElement('poissonsample', JXG.createPoissonSample);
    // End external file
    // ----------------------------------------------------------
    
    // Use the new element 
    const board = JXG.JSXGraph.initBoard(BOARDID, {
      boundingbox: [-5, 5, 5, -5],
      axis: true,
      pan: { enabled: true },      // Disable pan for 3D view
      zoom: { enabled: true }      // Disable zoom for 3D view
    });
    
    var points = board.create('poissonsample', [[-4, 4, 4, -4], 1], {
        size: 3,
        withCircle: true,
        circle: {
            dash: 1
        }
    });
    // points[10].setAttribute({color: 'red', size: 10});
    //setInterval(() => { points.resample(); }, 1000);
    
 </script> 

<jsxgraph width="100%" aspect-ratio="1 / 1" title="Poisson disk sampling with many points" description="This construction was copied from JSXGraph examples database: BTW HERE SHOULD BE A GENERATED LINKuseGlobalJS="false">
   /*
   This example is licensed under a 
   Creative Commons Attribution ShareAlike 4.0 International License.
   https://creativecommons.org/licenses/by-sa/4.0/
   
   Please note you have to mention 
   The Center of Mobile Learning with Digital Technology
   in the credits.
   */
   
   // ----------------------------------------------------------
   // Start external file
   //
   // Poisson disk sampling.
   // Pure JavaScript, no JSXGraph, yet.
   //
   /**
    * Poisson Disk Sampling (Bridson Algorithm)
    * Generates points with a minimum distance between each other.
    *
    * @param {number} width - area width
    * @param {number} height - area height
    * @param {number} radius - Minimum distance between points
    * @returns {Array<{x: number, y: number}>} Array of sampled points
    */
   var poissonDiskSampling = function (width, height, radius) {
     const k = 30; // max attempts per point before rejection
     const cellSize = radius / Math.sqrt(2);
     const cols = Math.ceil(width / cellSize);
     const rows = Math.ceil(height / cellSize);
   
     // Grid to track occupied cells (flat array for performance)
     const grid = new Int32Array(cols * rows).fill(-1);
   
     // Helper: map (x, y) to grid cell index
     function cellIndex(x, y) {
       const col = Math.floor(x / cellSize);
       const row = Math.floor(y / cellSize);
       if (col < 0 || col >= cols || row < 0 || row >= rows) return -1;
       return row * cols + col;
     }
   
     // Result points
     const points = [];
   
     // Active list (indices into `points`)
     const active = [];
   
     // Seed the first point
     points.push({ x: Math.random() * width, y: Math.random() * height });
     active.push(0);
     grid[cellIndex(points[0].x, points[0].y)] = 0;
   
     while (active.length > 0) {
       // Pick a random active point
       const idx = Math.floor(Math.random() * active.length);
       const point = points[active[idx]];
   
       // Try k random points in the annulus around it
       let found = false;
       for (let attempt = 0; attempt < k; attempt++) {
         // Random angle + random radius in [radius, 2*radius]
         const angle = Math.random() * 2 * Math.PI;
         const r = radius * (1 + Math.random()); // uniform in annulus
         const x = point.x + r * Math.cos(angle);
         const y = point.y + r * Math.sin(angle);
   
         // Check bounds
         if (x < 0 || x >= width || y < 0 || y >= height) continue;
   
         // Check nearby cells in the grid
         const col = Math.floor(x / cellSize);
         const row = Math.floor(y / cellSize);
   
         let tooClose = false;
         // Search the 5x5 neighborhood of cells
         for (let dr = -2; dr <= 2; dr++) {
           for (let dc = -2; dc <= 2; dc++) {
             const nc = col + dc;
             const nr = row + dr;
             if (nc < 0 || nc >= cols || nr < 0 || nr >= rows) continue;
             const neighborIdx = grid[nr * cols + nc];
             if (neighborIdx === -1) continue;
   
             const dx = points[neighborIdx].x - x;
             const dy = points[neighborIdx].y - y;
             if (dx * dx + dy * dy < radius * radius) {
               tooClose = true;
               break;
             }
           }
           if (tooClose) break;
         }
   
         if (tooClose) continue;
   
         // Valid point found
         const newIdx = points.length;
         points.push({ x, y });
         active.push(newIdx);
         grid[cellIndex(x, y)] = newIdx;
         found = true;
         break;
       }
   
       // If no valid point found after k attempts, remove from active
       if (!found) {
         active[idx] = active[active.length - 1];
         active.pop();
       }
     }
   
     return points;
   };
   
   // Add new defaults and new attributes
   JXG.extend(JXG.Options, {
     poissonsample: {         // Lower case
       name: '',
       highlight: false,
       size: 1,
       strokeWidth: 0,
       color: JXG.palette.blue,
       withLabel: false,
       withCircle: false,
       circle: {
         strokeWidth: 0.5,
         strokeColor: 'red',
         strokeOpacity: 0.5,
         highlight: false
       }
     }
   });
   
   // Create constructor and register element
   // Create new JSXGraph composition element poissonsample
   // Add two methods: sample() and resample()
   JXG.createPoissonSample = function (board, parents, attributes) {
     var box = parents[0],
       r = parents[1],
       el;
   
     if (!JXG.isArray(box) || box.length != 4 || !JXG.isNumber(r)) {
       throw new Error("JSXGraph: Can't create Poisson sample with these parameters. Supply bounding box array and number radius.");
     }
   
     el = new JXG.Composition();
   
     el.box = box;
     el.radius = r;
     el.poissonDiskSampling = poissonDiskSampling;
     el.poissonpoints = null;
   
     el.sample = function () {
       var w = this.box[2] - this.box[0],
         h = this.box[1] - this.box[3],
         w2 = w / 2,
         h2 = h / 2,
         withCircle,
         attr, points;
   
       attr = JXG.copyAttributes(attributes, board.options, 'poissonsample');
       this.poissonpoints = this.poissonDiskSampling(w, h, JXG.evaluate(this.radius));
       // console.log(this.points.length)
       withCircle = attr.withcircle;
   
       // console.time('sample');
       let pp = this.poissonpoints;
       for (let i = 0; i < pp.length; i++) {
         let p = board.create('point', [pp[i].x - w2, pp[i].y - h2], attr);
         el.add(i, p);
         if (withCircle) {
           el.add( i + '_c', board.create('circle', [p, this.radius], attr.circle) );
         }
       }
       // console.timeEnd('sample');
     };
   
     el.resample = function () {
       var le = this.poissonpoints.length, i;
   
       // Remove all points
       board.removeObject(this.objectsList, false);
       for (i = 0; i < le; i++) {
         this.remove(i);
         this.remove(i + '_c');
       }
   
       // Sample again
       this.sample();
     };
   
     el.sample();
   
     return el;
   };
   JXG.registerElement('poissonsample', JXG.createPoissonSample);
   // End external file
   // ----------------------------------------------------------
   
   // Use the new element 
   const board = JXG.JSXGraph.initBoard(BOARDID, {
     boundingbox: [-5, 5, 5, -5],
     axis: true,
     pan: { enabled: true },      // Disable pan for 3D view
     zoom: { enabled: true }      // Disable zoom for 3D view
   });
   
   var points = board.create('poissonsample', [[-4, 4, 4, -4], 1], {
       size: 3,
       withCircle: true,
       circle: {
           dash: 1
       }
   });
   // points[10].setAttribute({color: 'red', size: 10});
   //setInterval(() => { points.resample(); }, 1000);
   
</jsxgraph>