// Forked from "Ripples 004" by rupertxrussell
// https://turtletoy.net/turtle/5e4b7e6483

// Forked from "Fork: Ripples 002" by Jurgen
// https://turtletoy.net/turtle/9a9e87ac98

// Not my code, just wanted to remove unused methods and expand the Polygon function
// to be able to learn how the clipping works.

// You can find the Turtle API reference here: https://turtletoy.net/syntax

/**
 * Cleaned Ripple Scene
 * Uses Hidden Line Removal via the Polygons utility.
 */

Canvas.setpenopacity(1);

// --- Parameters ---
const Xspread = 75;
const Yspread = 30;
const frequency = 0.5;
const rippleCount = 8;
const numberOfRaindrops = 256;

// --- Initialization ---
const turtle = new Turtle();
const polygons = new Polygons();

// --- Main Loop ---
for (let i = 0; i < numberOfRaindrops; i++) {
    const position = [
        getRndInteger(-Xspread, Xspread), 
        getRndInteger(-Yspread, Yspread)
    ];
    const count = getRndInteger(3, rippleCount);
    const growth = getRndInteger(3, frequency);
    
    drawRipples(position, count, growth);
}

// --- Core Functions ---

function drawRipples(position, count, radiusIncrease) {
    for (let i = 1; i <= count; i++) {
        const radius = i * radiusIncrease;
        const p = polygons.create();
        
        // Generate points for the circle and offset them to the ripple position
        const points = circlePoints(radius).map(pt => [
            pt[0] + position[0], 
            pt[1] + position[1]
        ]);
        
        p.addPoints(...points);
        p.addOutline();
        
        // This handles the clipping against previously drawn shapes
        polygons.draw(turtle, p);
    }
}

function getRndInteger(min, max) {
    return Math.floor(Math.random() * (max - min + 1)) + min;
}

function circlePoints(radius) {
    const steps = Math.floor(radius * (2 * Math.PI) + 1);
    const pts = [];
    for (let i = 0; i < steps; i++) {
        const theta = (i / steps) * (2 * Math.PI);
        pts.push([
            radius * Math.cos(theta),
            radius * Math.sin(theta)
        ]);
    }
    return pts;
}

/**
 * Polygon Clipping Utility
 * Created by Reinder Nijhoff & Lionel Lemarie
 */
function Polygons() {
    const polygonList = [];
    const gridResolution = 25;
    const spatialGrid = Array.from({ length: gridResolution ** 2 }, () => []);

    class Polygon {
        constructor() {
            this.cp = []; // Control Points (the boundary)
            this.dp = []; // Drawing Points (the actual lines to be drawn)
            this.aabb = []; // Axis-Aligned Bounding Box [minX, minY, maxX, maxY]
        }

        /**
         * Defines the shape's area for clipping purposes.
         */
        addPoints(...points) {
            let minX = 1e5, maxX = -1e5, minY = 1e5, maxY = -1e5;
            this.cp = [...this.cp, ...points];
            
            this.cp.forEach(pt => {
                minX = Math.min(minX, pt[0]);
                maxX = Math.max(maxX, pt[0]);
                minY = Math.min(minY, pt[1]);
                maxY = Math.max(maxY, pt[1]);
            });
            this.aabb = [minX, minY, maxX, maxY];
        }

        /**
         * Converts the boundary points into drawable line segments.
         */
        addOutline() {
            for (let i = 0, len = this.cp.length; i < len; i++) {
                this.dp.push(this.cp[i], this.cp[(i + 1) % len]);
            }
        }

        /**
         * Instructs the Turtle to draw the segments that survived clipping.
         */
        render(turtle) {
            for (let i = 0, len = this.dp.length; i < len; i += 2) {
                turtle.jump(this.dp[i]);
                turtle.goto(this.dp[i + 1]);
            }
        }

        /**
         * Ray-casting algorithm to check if a point is inside this polygon.
         */
        isPointInside(point) {
            let intersections = 0;
            for (let i = 0, len = this.cp.length; i < len; i++) {
                if (this.segmentIntersect(point, [0.1, -1000], this.cp[i], this.cp[(i + 1) % len])) {
                    intersections++;
                }
            }
            return (intersections % 2) === 1;
        }

        /**
         * The Clipping Engine: 
         * Compares this polygon's lines against another polygon (target).
         */
        boolean(target) {
            const newDrawingPoints = [];
            
            for (let i = 0, len = this.dp.length; i < len; i += 2) {
                const start = this.dp[i];
                const end = this.dp[i + 1];
                const intersections = [];

                // Find all points where our line crosses the target's boundary
                for (let j = 0; j < target.cp.length; j++) {
                    const intersect = this.segmentIntersect(start, end, target.cp[j], target.cp[(j + 1) % target.cp.length]);
                    if (intersect !== false) intersections.push(intersect);
                }

                if (intersections.length === 0) {
                    // If no intersections, keep the line only if it's outside the target
                    if (!target.isPointInside(start)) {
                        newDrawingPoints.push(start, end);
                    }
                } else {
                    // Split the line into segments at intersection points
                    intersections.push(start, end);
                    const dx = end[0] - start[0];
                    const dy = end[1] - start[1];
                    
                    // Sort points along the line
                    intersections.sort((a, b) => (a[0] - start[0]) * dx + (a[1] - start[1]) * dy - ((b[0] - start[0]) * dx + (b[1] - start[1]) * dy));

                    for (let k = 0; k < intersections.length - 1; k++) {
                        const p1 = intersections[k];
                        const p2 = intersections[k + 1];
                        const mid = [(p1[0] + p2[0]) / 2, (p1[1] + p2[1]) / 2];
                        
                        // Only keep segments whose midpoint is outside the target
                        if (!target.isPointInside(mid)) {
                            newDrawingPoints.push(p1, p2);
                        }
                    }
                }
            }
            this.dp = newDrawingPoints;
            return this.dp.length > 0;
        }

        /**
         * Standard Line-Segment Intersection math.
         */
        segmentIntersect(p1, p2, p3, p4) {
            const denominator = (p4[1] - p3[1]) * (p2[0] - p1[0]) - (p4[0] - p3[0]) * (p2[1] - p1[1]);
            if (denominator === 0) return false;
            const ua = ((p4[0] - p3[0]) * (p1[1] - p3[1]) - (p4[1] - p3[1]) * (p1[0] - p3[0])) / denominator;
            const ub = ((p2[0] - p1[0]) * (p1[1] - p3[1]) - (p2[1] - p1[1]) * (p1[0] - p3[0])) / denominator;
            if (ua >= 0 && ua <= 1 && ub >= 0 && ub <= 1) {
                return [p1[0] + ua * (p2[0] - p1[0]), p1[1] + ua * (p2[1] - p1[1])];
            }
            return false;
        }
    }

    return {
        create: () => new Polygon(),
        draw: (turtle, currentPoly, shouldStore = true) => {
            // 1. Optimization: Only check polygons nearby using the spatial grid
            const nearbyPolys = (function(aabb) {
                const foundIndices = {};
                const cellSize = 200 / gridResolution;
                for (let y = 0; y < gridResolution; y++) {
                    const yPos = y * cellSize - 100;
                    if (!(aabb[3] < yPos || aabb[1] > yPos + cellSize)) {
                        for (let x = 0; x < gridResolution; x++) {
                            const xPos = x * cellSize - 100;
                            if (!(aabb[0] > xPos + cellSize || aabb[2] < xPos)) {
                                spatialGrid[x + y * gridResolution].forEach(idx => {
                                    const other = polygonList[idx];
                                    if (!(aabb[3] < other.aabb[1] || aabb[1] > other.aabb[3] || aabb[0] > other.aabb[2] || aabb[2] < other.aabb[0])) {
                                        foundIndices[idx] = 1;
                                    }
                                });
                            }
                        }
                    }
                }
                return Object.keys(foundIndices).map(idx => polygonList[idx]);
            })(currentPoly.aabb);

            // 2. Clip the current polygon against all nearby existing ones
            for (let i = 0; i < nearbyPolys.length; i++) {
                if (!currentPoly.boolean(nearbyPolys[i])) break;
            }

            // 3. Draw the resulting lines
            currentPoly.render(turtle);

            // 4. Store the polygon in the list and spatial grid for future clipping
            if (shouldStore) {
                polygonList.push(currentPoly);
                const idx = polygonList.length - 1;
                const cellSize = 200 / gridResolution;
                spatialGrid.forEach((cell, i) => {
                    const x = (i % gridResolution) * cellSize - 100;
                    const y = Math.floor(i / gridResolution) * cellSize - 100;
                    if (!(x + cellSize < currentPoly.aabb[0] || x > currentPoly.aabb[2] || y + cellSize < currentPoly.aabb[1] || y > currentPoly.aabb[3])) {
                        cell.push(idx);
                    }
                });
            }
        }
    };
}