trszdev/prekol.html

## prekol.html
<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <meta http-equiv="X-UA-Compatible" content="ie=edge">
  <title>kgg</title>
  <style>
    body {
      display: flex;
      flex-flow: column;
      align-items: center;
      justify-content: center;
    }

    #canvas {
      display: block;
      margin-bottom: 10px;
      background: #eee;
    }
  </style>
</head>
<body>
  <canvas id=canvas width=512 height=512></canvas>
  <div>
    <button onclick="generate(3)">generate [N=3]</button>
    <button onclick="generate(4)">generate [N=4]</button>
    <button onclick="generate(5)">generate [N=5]</button>
    <button onclick="generate(6)">generate [N=6]</button>
    <button onclick="generate(7)">generate [N=7]</button>
    <button onclick="generate(8)">generate [N=8]</button>
    <button onclick="solveShuffle()">solve</button>
  </div>
  <script>
    var canvas = document.getElementById('canvas')
    var ctx = canvas.getContext('2d')
    var currentPoints = []
    var currentN = 0
    var solved = false
    var solving = false
    var deltaRedraw = 60
    var maxRandomSolve = 3000
    var maxRandomSolveMult = 250

    function randInt(min, max) {
      return Math.round(Math.random() * (max - min)) + min
    }

    function generate(n) {
      if (solving) return
      var newPoints = []
      for (var i = 0; i < 3 * n; i++) {
        newPoints.push(randomPoint())
      }
      solved = false
      currentPoints = newPoints
      currentN = n
      maxRandomSolve = maxRandomSolveMult * n
      drawPoints(newPoints, n, false)
    }

    function shuffle(a) {
      var j, x, i;
      for (i = a.length - 1; i > 0; i--) {
          j = Math.floor(Math.random() * (i + 1))
          x = a[i]
          a[i] = a[j]
          a[j] = x
      }
      return a
    }

    function checkSolved(points, n) {
      var outsides = 0
      var insides = 0
      for (var point = n; point < points.length; point++) {
        var px = points[point][0]
        var py = points[point][1]
        var inside = false

        for (var i = 0, j = n - 1; i < n; j = i++) {
          var ix = points[i][0]
          var iy = points[i][1]
          var jx = points[j][0]
          var jy = points[j][1]
          if ((iy > py) != (jy > py) && px < (jx - ix) * (py - iy) / (jy - iy) + ix) {
            inside = !inside
          }
        }

        if (inside) insides++
        else outsides++
        if (outsides > n || insides > n) return false
      }
      return true
    }

    async function solveShuffle() {
      if (solved || solving) return
      solving = true
      var firstTime = Date.now()
      try {
        var lastTime = Date.now()
        for (var i = 1; !solved; i++) {
          if (Date.now() - firstTime > maxRandomSolve) {
            alert('No solution')
            drawPoints(currentPoints, currentN, false)
            break
          }
          solved = checkSolved(currentPoints, currentN)
          var needRedraw = solved || (Date.now() - lastTime) > deltaRedraw
          if (needRedraw) {
            await new Promise(res => requestAnimationFrame(res))
            drawPoints(currentPoints, currentN, true)
            lastTime = Date.now()
          }
          if (!solved) shuffle(currentPoints)
        }
      } finally {
        solving = false
      }
    }

    function randomPoint() {
      return [randInt(0, canvas.width), randInt(0, canvas.height)]
    }

    function drawPoints(points, n, shouldDrawEdges) {
      ctx.clearRect(0, 0, canvas.width, canvas.height)
      ctx.fillStyle = 'blue'
      if (shouldDrawEdges) {
        ctx.beginPath()
        ctx.moveTo(points[0][0], points[0][1])
        for (var i = 1; i < n; i++) {
          ctx.lineTo(points[i][0], points[i][1])
        }
        ctx.closePath()
        ctx.fillStyle = 'gray'
        ctx.fill()
        ctx.fillStyle = 'red'
      }
      for (var i = 0; i < n; i++) {
        ctx.beginPath()
        ctx.arc(points[i][0], points[i][1], 2, 0, 2 * Math.PI, false)
        ctx.fill()
      }
      ctx.fillStyle = 'blue'
      for (var i = n; i < points.length; i++) {
        ctx.beginPath()
        ctx.arc(points[i][0], points[i][1], 2, 0, 2 * Math.PI, false)
        ctx.fill()
      }
    }
  </script>
</body>
</html>
	<!DOCTYPE html>
	<html lang="en">
	<head>
	<meta charset="UTF-8">
	<meta name="viewport" content="width=device-width, initial-scale=1.0">
	<meta http-equiv="X-UA-Compatible" content="ie=edge">
	<title>kgg</title>
	<style>
	body {
	display: flex;
	flex-flow: column;
	align-items: center;
	justify-content: center;
	}

	#canvas {
	display: block;
	margin-bottom: 10px;
	background: #eee;
	}
	</style>
	</head>
	<body>
	<canvas id=canvas width=512 height=512></canvas>
	<div>
	<button onclick="generate(3)">generate [N=3]</button>
	<button onclick="generate(4)">generate [N=4]</button>
	<button onclick="generate(5)">generate [N=5]</button>
	<button onclick="generate(6)">generate [N=6]</button>
	<button onclick="generate(7)">generate [N=7]</button>
	<button onclick="generate(8)">generate [N=8]</button>
	<button onclick="solveShuffle()">solve</button>
	</div>
	<script>
	var canvas = document.getElementById('canvas')
	var ctx = canvas.getContext('2d')
	var currentPoints = []
	var currentN = 0
	var solved = false
	var solving = false
	var deltaRedraw = 60
	var maxRandomSolve = 3000
	var maxRandomSolveMult = 250

	function randInt(min, max) {
	return Math.round(Math.random() * (max - min)) + min
	}

	function generate(n) {
	if (solving) return
	var newPoints = []
	for (var i = 0; i < 3 * n; i++) {
	newPoints.push(randomPoint())
	}
	solved = false
	currentPoints = newPoints
	currentN = n
	maxRandomSolve = maxRandomSolveMult * n
	drawPoints(newPoints, n, false)
	}

	function shuffle(a) {
	var j, x, i;
	for (i = a.length - 1; i > 0; i--) {
	j = Math.floor(Math.random() * (i + 1))
	x = a[i]
	a[i] = a[j]
	a[j] = x
	}
	return a
	}

	function checkSolved(points, n) {
	var outsides = 0
	var insides = 0
	for (var point = n; point < points.length; point++) {
	var px = points[point][0]
	var py = points[point][1]
	var inside = false

	for (var i = 0, j = n - 1; i < n; j = i++) {
	var ix = points[i][0]
	var iy = points[i][1]
	var jx = points[j][0]
	var jy = points[j][1]
	if ((iy > py) != (jy > py) && px < (jx - ix) * (py - iy) / (jy - iy) + ix) {
	inside = !inside
	}
	}

	if (inside) insides++
	else outsides++
	if (outsides > n \|\| insides > n) return false
	}
	return true
	}

	async function solveShuffle() {
	if (solved \|\| solving) return
	solving = true
	var firstTime = Date.now()
	try {
	var lastTime = Date.now()
	for (var i = 1; !solved; i++) {
	if (Date.now() - firstTime > maxRandomSolve) {
	alert('No solution')
	drawPoints(currentPoints, currentN, false)
	break
	}
	solved = checkSolved(currentPoints, currentN)
	var needRedraw = solved \|\| (Date.now() - lastTime) > deltaRedraw
	if (needRedraw) {
	await new Promise(res => requestAnimationFrame(res))
	drawPoints(currentPoints, currentN, true)
	lastTime = Date.now()
	}
	if (!solved) shuffle(currentPoints)
	}
	} finally {
	solving = false
	}
	}

	function randomPoint() {
	return [randInt(0, canvas.width), randInt(0, canvas.height)]
	}

	function drawPoints(points, n, shouldDrawEdges) {
	ctx.clearRect(0, 0, canvas.width, canvas.height)
	ctx.fillStyle = 'blue'
	if (shouldDrawEdges) {
	ctx.beginPath()
	ctx.moveTo(points[0][0], points[0][1])
	for (var i = 1; i < n; i++) {
	ctx.lineTo(points[i][0], points[i][1])
	}
	ctx.closePath()
	ctx.fillStyle = 'gray'
	ctx.fill()
	ctx.fillStyle = 'red'
	}
	for (var i = 0; i < n; i++) {
	ctx.beginPath()
	ctx.arc(points[i][0], points[i][1], 2, 0, 2 * Math.PI, false)
	ctx.fill()
	}
	ctx.fillStyle = 'blue'
	for (var i = n; i < points.length; i++) {
	ctx.beginPath()
	ctx.arc(points[i][0], points[i][1], 2, 0, 2 * Math.PI, false)
	ctx.fill()
	}
	}
	</script>
	</body>
	</html>