Javascript-форум (https://javascript.ru/forum/)
-   Общие вопросы Javascript (https://javascript.ru/forum/misc/)
-   -   Построение правильного многоугольника без тригонометрических функций (https://javascript.ru/forum/misc/83490-postroenie-pravilnogo-mnogougolnika-bez-trigonometricheskikh-funkcijj.html)

Teamur 23.12.2021 12:29

Построение правильного многоугольника без тригонометрических функций
 
См. функцию poly :
<!DOCTYPE html>
<canvas id=c width=600 height=600 style='outline:1px solid'></canvas>
<script>
'use strict';
const cx=c.getContext('2d'), {PI,sin,cos,round}=Math,
pi2=PI*2,
ra=PI/180, // 1 радиан
ra90=90*ra,
 
line=(x1,y1,x2,y2)=>(cx.beginPath(),cx.moveTo(x1,y1),cx.lineTo(x2,y2),cx.stroke(),line),
cross=(x,y,d=20)=>(line(x-(d/=2),y,x+d,y)(x,y-d,x,y+d),cross),
circle=(x,y,d=20)=>(cx.beginPath(),cx.arc(x,y,d/2,0,pi2),cx.stroke(),circle),
 
poly=(x,y,d=20,n=4,a=-ra90)=>{ // a - первая вершина будет сверху холста
  if(n>2){ d/=2;
    cx.beginPath();
    for(let b=pi2/n++; n--; cx.lineTo( x+d*cos(a+=b), y+d*sin(a) ));
    cx.stroke()
  }
};
 
poly(300,300,400,8); // 400 - диаметр описанной окружности, 8 - количество вершин
 
cross(300,300); // центр правильного многоугольника
 
cx.strokeStyle='red'; // первая вершина
circle(300,100);
 
cx.strokeStyle='blue';
circle(300,300,400);
 
</script>

Возможно ли избавиться от sin и cos при построении многоугольника, если знать диаметр описанной окружности, количество вершин многоугольника?

Может здесь поможет векторная алгебра, всякие скалярные и векторные произведения.
Или как-то найти соотношение длины дуги описанной коружности к хорде, которая будет стороной многоугольника.
Получить равнобедренный треугольник и зная хорду и 2 стороны, равные диаметру, найти координаты вершин.
В общем я запутался, есть чувство, что можно обойтись без тригонометрии, хотя бы в цикле.

Одной из причин, которая сподвигла задать вопрос, был просмотр мною видео об истории числа ПИ, которые нашли разбиением окружности на сегменты. И чем больше сегментов, тем точнее ПИ.
И спрашивается можно ли вообще без него обойтись при построении правильного многоугольника и почему я должен разбивать окружность на 360 частей, если надо например только на 8, или скажем на 1000.
И вообще, возможно было бы удобно, представить длину окружности за единицу (нормализовать) и иметь дело с соотношениями сторон, координатами.

Также мне очень понравились статьи с хабра про векторную алгебру:
Избегаем тригонометрии :
https://habr.com/ru/post/462539/
Когда не нужна тригонометрия :
https://habr.com/ru/post/105882/

Надеюсь получится улучшить функцию poly и сделать её настолько быстрой, насколько возможно,
ведь так здорово когда всё работает быстро и без извращений )))

Alexandroppolus 23.12.2021 13:14

Цитата:

Сообщение от Teamur
Надеюсь получится улучшить функцию poly и сделать её настолько быстрой, насколько возможно

там самая медленная часть - рисование.
а эти твои синусы вычисляются очень быстро.

Alexandroppolus 23.12.2021 13:35

Можно попробовать поэкспериментировать с трансформацией
https://developer.mozilla.org/ru/doc...tions#rotating
по идее, если вращать вокруг центра фигуры, то можно будет рисовать одну и ту же хорду. Хотя не факт, что это позволит ускориться.

MallSerg 23.12.2021 14:27

Пи - это иррациональное число. Иррациональные числа невозможно соизмерять с единицей (рациональными числами) это и есть их основное свойство.
Очень странным выглядит попытка вычисления углов с попыткой игнорирования науки о вычислении углов. Для меня все это выглядит как изобретение велосипеда. т.е. переизобретение тригонометрии.
В общем даже древние греки знали что
Пифагоровы штаны во все стороны ровны.
теорема Пифагора поможет тебе с помощью умножения и деления описать тригонометрические функции но библиотечные реализации sin cos работают быстрее и оптимальнее.

Teamur 23.12.2021 14:51

Цитата:

Сообщение от Alexandroppolus
Можно попробовать поэкспериментировать с трансформацией

Я планирую переписать код для использования в WebGPU ( WGSL ) API.
Разработка CAD-приложения. В API нет функций setTransform, rotate, translate, там вообще ничего нет, кроме рисования прямых линий и треугольников - соответственно окружность будет правильным многоугольником, хоть треугольником ))
И чтобы облегчить разработку, я использую обычный Canvas API, отрабатываю алгоритмы и уже потом имея логику, постараюсь засунуть в WebGPU.
Просто бросается в глаза простота процесса отрисовки - использовать одинаковое угловое приращение и прям так вылезает на поверхность вопрос - зачем высчитывать синусы и косинусы если угол приращения одинаковый, всё равномерно ))

Цитата:

Сообщение от MallSerg
библиотечные реализации sin cos работают быстрее и оптимальнее

Это хорошо, но мне важно знать - принципиально это как-то возможно, обойтись без тригонометрии, чисто координатами, длинами сторон, диаметрами, теорией по треугольникам?

MallSerg 23.12.2021 17:01

Мне непонятна твоя логика и на мой скромный взгляд в ней куча элементарных ошибок и заблуждений.


Ну может пригодится простейший пример рисование правильного многоугольника шейдерной программкой (кнопочка SHOW CODE ну и раскомменчивать построчно).
со смещением и вращением глобальных координат матрицей трансформации.
https://glslsandbox.com/e#78075.1

Teamur 23.12.2021 21:58

Цитата:

Сообщение от MallSerg
Мне непонятна твоя логика и на мой скромный взгляд в ней куча элементарных ошибок и заблуждений

Потому что, я был уверен, что можно как-то исхитриться и задействовать Пифагора, а синусы и косинусы представить в виде отношений катетов к гипотенузе, которая была бы радиусом от центра окружности до вершины многоугольника.
А затем, надеясь на векторную алгебру, которую что-то не могу осилить )), а также помощь форума, решить задачу.
Я ещё поколдую )) Хотя другая часть меня говорит: Ты занимаешься фигнёй ))

voraa 23.12.2021 23:29

Вложений: 1
Ну если не совсем произвольный многоугольник, а последовательно переходить удваивая количество вершин. Например, от квадрата перейти к правильному восьмиугольнику, потом к правильному 16-ти угольнику, то можно строить эти вершины без синусов и косинусов. Правда квадратный корень извлекать придется
Надо находить точку на окружности между двумя вершинами треугольника
Вроде так можно
(см рисунок)
Есть Треугольник O(Xo,Yo), A(Xa,Ya) B(Xb, Yb), O - центр окружности радиуса R
Найти точку C(Xc,Yc), чтобы OC "делила треугольник на равные части"

Найдем P(Xp, Yp)
Xp = (Xa+Xb)/2; Yp = (Ya+Yb)/2;
Длина OP d = Sqrt((Xp-Xo)^2 + (Yp-Yo)^2)
Отсюда Xc = Xo + (Xp-Xo)*R/d; Yc = Yo + (Yp-Yo)*R/d

voraa 24.12.2021 00:28

Небольшой тест на svg
<body>
<button id="p2">Удвоить</button>
<br>
<svg width="410" height="410" version="1.1" xmlns="http://www.w3.org/2000/svg">
<circle cx="205" cy="205" r="200" stroke="black" fill="transparent" stroke-width="1"/>
<polygon id="mnog" stroke="red" fill="transparent" stroke-width="1"/>
</svg>
<script>
const O =[205,205];
const R = 200;
let mnog = [[205, 5], [405, 205], [205, 405], [5, 205]];

const draw = (mnog) =>{
	const pol = mnog.flat()
	document.getElementById('mnog').setAttribute('points', pol)
}

const sredn = ([xo, yo], [xa, ya], [xb, yb], R) => {
	const xp = (xa+xb)/2;
	const yp= (ya+yb)/2
	const d = Math.sqrt((xp-xo)**2 + (yp-yo)**2)
	return [xo+(xp-xo)*R/d, yo+(yp-yo)*R/d]
}

const doublm = (mnog) => {
	const sred = []
	for (let i=0; i<mnog.length; i++)
		sred.push(sredn(O, mnog[i], mnog[i === mnog.length-1? 0: i+1], R))
	const res = []
		for (let i=0; i<mnog.length; i++)
			res.push(mnog[i], sred[i])
	return res	
}

document.getElementById('p2').addEventListener('click', () => {
	mnog = doublm(mnog)
	draw(mnog)
})

draw(mnog);
</script>
</body>

Teamur 24.12.2021 15:31

voraa,
хитро ))
Тогда можно в принципе, на входе функции проверить чётность количества переданных вершин и в зависимости от чётности выполнять блок построения квдаратов, восьмиугольников, ... А если нечётно, то блок отрисовки треугольников, пятиугольников.
Хотя если взять шестиугольник, то можно ли будет построить его по вашему алгоритму?

voraa 24.12.2021 15:43

Этот алгоритм удваивает количество вершин.
Если есть произвольный N угольник вписанный в окружность, то он строит 2*N угольник.
Если начать с треугольника, то получится 6-угольник на следующем шаге.

Teamur 24.12.2021 15:55

voraa,
тогда для 5, 7, 9, 11 угольников и тд надо будет извращаться ))

voraa 24.12.2021 16:03

А цель - строить произвольный многоугольник вписанный в окружность?
Ну да. Не любой можно построить без тригонометрии
Собственно только с треугольника и квадрата можно начинать. Так как там фигурируют углы в 30, 60, 45, синусы и косинусы которых можно вычислить квадратными корнями и дробями.

С другой стороны, если в этом большая необходимость, но вы подозреваете, что из-за вычисления синусов и косинусов будут какие то тормоза, то там не так много и вычислять. Например, для пятиугольника могут быть нужны син и кос углов типа 36, 72, 18. Ну вычислить их один раз, записать в переменные, и потом работать с ними.

Rise 24.12.2021 17:00

Teamur,
А зачем вы в цикле их (косинусы и синусы) считаете они же не меняются или нет?

Teamur 24.12.2021 17:17

Цитата:

Сообщение от voraa
А цель - строить произвольный многоугольник вписанный в окружность?

Да
Цитата:

Сообщение от Rise
А зачем вы в цикле их (косинусы и синусы) считаете они же не меняются или нет?

Там радианы меняются, а надо как-то получать координаты вершин

Rise 24.12.2021 18:17

Teamur,
Матрицы трансформации надо:
<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Matrix</title>
</head>
<body>
    
<canvas id="canvas" width=600 height=300 style="outline:1px solid"></canvas>

<script>
class Path extends Path2D {
    constructor(radius, vertices) {
        super();
        for (let A = 2 * Math.PI / vertices, a, i = 0; i < vertices; i++) {
            a = i * A;
            this.lineTo(radius * Math.cos(a), radius * Math.sin(a));
        }
        this.closePath();
    }
}
class Polygon {
    constructor(x, y, path) {
        this.path = path;
        this.matrix = new DOMMatrix();
        this.translate(x, y);
        this.rotate(0);
        this.scale(1);
    }
    translate(x, y) {
        this.matrix.translateSelf(x, y);
    }
    rotate(angle) {
        this.matrix.rotateSelf(angle);
    }
    scale(factor) {
        this.matrix.scaleSelf(factor);
    }
    render(ctx, color) {
        ctx.save();
        ctx.setTransform(this.matrix);
        ctx.strokeStyle = color;
        ctx.stroke(this.path);
        ctx.restore();
    }
}

const ctx = canvas.getContext('2d');

let path1 = new Path(50, 5);
let path2 = new Path(100, 10);

let polygon1 = new Polygon(150, 100, path1);
    polygon1.rotate(-90);
    polygon1.render(ctx, 'green');

let polygon2 = new Polygon(450, 100, path1);
    polygon2.render(ctx, 'blue');

let polygon3 = new Polygon(300, 150, path2);
    polygon3.render(ctx, 'red');

setTimeout(() => {
    polygon3.translate(0, -50);
    polygon3.scale(0.5);
    polygon3.render(ctx, 'gray');
}, 3000);
</script>

</body>
</html>

voraa 24.12.2021 20:34

Цитата:

Сообщение от Teamur
Там радианы меняются, а надо как-то получать координаты вершин

Так они не произвольно меняются, а все время на один и тот же угол.
Синусы косинусы достаточно один раз вычислить

<body>
<label>Количество вершин: <input id="nu" type="number" min="3" value=3></label>
<button id="p2">Построить</button>
<br>
<svg width="410" height="410" version="1.1" xmlns="http://www.w3.org/2000/svg">
<circle cx="205" cy="205" r="200" stroke="black" fill="transparent" stroke-width="1"/>
<polygon id="mnog" stroke="red" fill="transparent" stroke-width="1"/>
</svg>
<script>
const cx = 205
const cy = 205
const R = 200;

const draw = (mnog) =>	document.getElementById('mnog').setAttribute('points', mnog.flat())


const mnogoug = (n) => {
	const a = Math.PI*2/n;
	const sa = Math.sin(a)
	const ca = Math.cos(a)
	let sc = 0.;
	let cc = 1.;
	const mnog = []
	for (let i=0; i< n; i++) {
		mnog.push([R*cc+cx, R*sc+cy])
		let tsc = sc;
		sc = sc*ca+cc*sa;
		cc = cc*ca-tsc*sa;
	}
	return mnog
}

document.getElementById('p2').addEventListener('click', () => {
	const n = document.getElementById('nu').valueAsNumber;
	mnog = mnogoug(n)
	draw(mnog)
})
</script>
</body>

Teamur 24.12.2021 20:41

Цитата:

Сообщение от Rise
Матрицы трансформации надо

матрицы - это, конечно, здорово, но в цикле конструктора Path синус и косинус.
Вообще если смотреть на круг как на правильный многоугольник, количество вершин которого стремиться к бесконечности, то многоугольники с небольшим числом вершин, по сути, подчиняются тем же законам построения что и круг.
Отличие лишь в том что в качестве основы тригонометрии взяли многоугольник, состоящий из 360 граней и назвали одну грань градусом.
Я же хочу понять эти закономерности и вывести, если смогу, формулу, позволяющую мне самому задавать разбивку круга = градусную меру,
а число ПИ - это предельный случай.
Длина окружности = периметр правильного многоугольника с бесконечным числом вершин.
В общем, есть чувство, что можно что-то вывести. Пока мне интересно, я буду пробовать, а если не смогу, то вернусь к косинусам или, действительно, предварительно вычислю их, и нап сформирую массив, в котором начиная с индекса 3 будут вычисленные значения
SINCOS[ , , ,[sin,cos],[sin,cos],... ].

Ну и в цикле по индексу что-то вроде

let[sin,cos]=SINCOS[n++]; cx.lineTo(x+d*sin,y+d*cos);

voraa 24.12.2021 20:45

Углы все одинаковые. От 0 до 360 с шагом 360/n
Школу вспомни.
синусы/косинусы суммы углов
Зная син/кос текущего угла, на получение син/кос следующего надо 4 умножения и 2 сложения.

Teamur 24.12.2021 21:22

Цитата:

Сообщение от voraa
Школу вспомни

синусы, косинусы, медианы, высоты, хорды, ... начинаю вспоминать ))
Цитата:

Сообщение от voraa
4 умножения и 2 сложения

вот она простота !


Часовой пояс GMT +3, время: 01:00.