Уроки, алгоритмы, программы, примеры

Вход на сайт

Материалы по разделам

Построения
на плоскости (2D)
Графика
в пространстве (3D)
Вычислительная
геометрия
Физическое
моделирование
Фрактальная
графика

Новые комментарии

Большое спасибо. Единственный код который прошел без каких либо ошибок. Ура!!!
Скажите пожалуйста, подскажите алгоритм по которому по заданным точкам можно определить тип многогранника, скажем это куб или прямоугольный параллелепипед. Нашел теорию по этим фигурам: https://www.mat... https://www.mat... Акцентировать внимание...
Всем у кого не работает. файл wizard.script Ещё одно упоминание Glut32 в строке "if (!VerifyLibFile(dir_nomacro_lib, _T("glut32"), _T("GLUT's"))) return false;" меняем на "if (!VerifyLibFile(dir_nomacro_lib, _T("freeglut"), _T("GLUT's"))) return...
Не получается, емаё
огромное спасибо за подробное объяснение про 3д графику на питоне, в интернете очень мало подобной информации

Счетчики и рейтинг

Рейтинг@Mail.ru Яндекс.Метрика
Скриншот к примеру
Среда программирования: 
Notepad++

Задача: для заданных n точек на плоскости найти пару точек, расположенных ближе друг к другу с помощью алгоритма "Разделяй и властвуй".

Код программы: 

function closRecurse(coordMas) { //рекурсивная функция для нахождения ближайщей пары точек
  var len = coordMas.length;
 
  if (len <= 3) { //Если есть 2 или 3 точки, то использует функцию brute
    return brute(coordMas);
  }
 
  var middle = Math.floor(len / 2), //Находим среднюю точку и выделяем 2 подмассива
      leftClosPair = closRecurse(coordMas.slice(0,middle)), //Рекурсивно находим наименьшее расстояние в первом подмассиве
      rightClosPair = closRecurse(coordMas.slice(middle)), //Рекурсивно находим наименьшее расстояние во втором подмассиве
      minDista = minPair(leftClosPair, rightClosPair), //Находим минимум
      DividePairs = coordMas.filter(function(coord) {
        return coord[0] - coordMas[middle][0] < minDista[1] //Построит массив, который содержит точки ближе, чем minDista к линии, проходящей через среднюю точку
      }),
      closDividePair = [Infinity, Infinity], 
      bestPair;
 
  if (DividePairs.length > 1) { //Если точек больше чем 1, то использует функцию brute
    closDividePair = brute(DividePairs);
  }
  bestPair = minPair(minDista,closDividePair); //Находим самое короткое расстояние сравнивая minDista и closDividePair
  return bestPair;
}
 
 //brute вернет наименьшее расстояние между 2 точками в массиве  
function brute(coordMas) {
  var mDist,
      len = coordMas.length,
      closPair,
      currDist;
 
  for (var i = 0; i < len - 1; i++) {  //перебор для поиска наименьшего расстояния
    for (var j = i+1; j < len; j++) {
      currDist = dist(coordMas[i], coordMas[j]);
      if (currDist < mDist || !mDist) {
        mDist = currDist;
        closPair = [coordMas[i], coordMas[j]];
      }
    }
  }
  return [closPair, mDist];
}
 
function dist(point1, point2) { //Функция полезности для поиска расстояние между двумя точками 
  var x1 = point1[0] || point1.x,
      x2 = point2[0] || point2.x,
      y1 = point1[1] || point1.y,
      y2 = point2[1] || point2.y;
  return Math.pow(x2 - x1, 2) + Math.pow(y2 - y1, 2);
}
 
function minPair(pair1, pair2) { // Функция  для поиска минимум из двух значений с плавающей запятой
  return pair1[1] < pair2[1] ? pair1 : pair2;
}
 
function parseInput(rawInput) {
  var coordMas = rawInput.split("\n").map(row => { //считывает всю строку пользовательского ввода
    return row.replace(/[^\w.,]/g, "").split(",") //убирает в строках все неподходящие символы
  })
  coordMas.sort(function(a, b) {
    return a[0] - b[0];
  });
 
  return coordMas;
}
 
function circle(coordMas,result) //функция для отрисовки точек
{
var canvas = document.getElementById('paint');
var ctx = canvas.getContext('2d');
    ctx.beginPath();//граница
    ctx.moveTo(0,0);
    ctx.lineTo(0,500);
    ctx.lineTo(500,500);
    ctx.lineTo(500,0);
    ctx.lineTo(0,0);
	ctx.strokeStyle = 'grey';
    ctx.stroke();
 
    ctx.beginPath(); //расстояние
    ctx.moveTo(result[0][0][0],result[0][0][1]);
    ctx.lineTo(result[0][1][0],result[0][1][1]);
    ctx.strokeStyle = 'red';
	ctx.stroke();
	ctx.beginPath();
	ctx.arc(result[0][0][0],result[0][0][1], 5, 0, 2*Math.PI, false);
	ctx.arc(result[0][1][0],result[0][1][1], 5, 0, 2*Math.PI, false);
	ctx.fillStyle='red';
	ctx.fill(); 
 
	for (var j = 1; j <= coordMas.length; j++) { //отрисовка всех точек
	ctx.beginPath();
	ctx.arc(coordMas[j][0], coordMas[j][1], 3, 0, 2*Math.PI, false);
	ctx.fillStyle='black';
	ctx.fill(); 
	}
 
return 0;
}
 
function closest() {
 
  var coordMas = parseInput(document.getElementById("input").value),  //функция для считывания информации из html
      outputEl = document.getElementById("output"),
      result = brute(coordMas);
 
      //result = closRecurse(coordMas);
      //Этот рекурсивный код работает медленнее, чем brute 
    console.log(result);
	// выводим ближайшую пару точек и расстояние между ними
  outputEl.innerHTML = `(${result[0][0][0]}, ${result[0][0][1]}), (${result[0][1][0]}, ${result[0][1][1]}), distance: ${Math.sqrt(result[1])}`;
  circle(coordMas,result);
}
 
window.onload = function() {
  document.getElementById("submit").onclick = closest;
};

Прикрепленный файлРазмер
Closest pair of points.zip2.47 кб