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

Вход на сайт

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

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

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

Выдаёт ошибку glut32.dll не найден! При том, что он лежит в System32! Всё решил) Нужно отправить не в System32, а в System.
Спасибо за статью. Я не Ваш студент. Но мне она помогла написать функцию для Канторова множества на Python для черепашки: import turtle def kanter(x, y, d):     if d > 1:         turtle...
Как реализовать в данном примере границы расчёта?

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

Рейтинг@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 кб