TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Zdravím vás, mám takový spíš matematicko-geometrický problém.
Potřeboval bych vytvořit metodu, která rozdělí obvod elipsy na stejné úseky a vrátí mi body XY.
Tady je hrubý náčrt:
souřadnice XY které chci vrátit jsou označeny černou barvou. Vstupem je poloměr elipsy a, b, n jako počet dělících bodů, p jako počáteční bod (obvodová vzdálenost od [a, 0].
Mým cílem je do rastru nakreslit "eliptický n-úhelník" o stranách stejné délky (nevím jestli má takovýto objekt nějaký odborný název).
Jak na to?
Možná by šlo spočítat délku té strany a pak ty body najít jako průsečíky s kružnicí, ale z toho se mi vaří hlava. A možná jen uvažuju špatným směrem.
Jestli nepotřebuješ perfektní matematické řešení, tak bych to prostě vybrutil. Vezmu minimum a maximum z vepsané a opsané kružnice a pak půlením intervalu najdu hodnotu, se kterou to vyjde na elipse. Asi by při tom mělo i jít testovat úhel "zalomení" a rychle poznat slepou uličku, tak by to nemuselo být pomalé.
#2 gna
No matematicky přesné řešení to být nemusí, stačí když to bude vizuálně OK.
Mě hned jako první řešení napadlo dělit to úhlem (to funguje dobře jen u kružnice), nedosáhne se tím konstantní délky hrany eliptického mnohoúhelníku, a to je problém.
Teď mě napadá jen vypsat všechny body rastru, kterými prochází elipsa, ty použít jako středy kroužků kterými budu zjišťovat průsečíky s elipsou. Ale přijde mi to jako neohrabané řešení.
Elipsa se pocitacove da vykreslit ruzne. Obvykle se pouziva prepocet pres sin, cos jako u kruznice. Pokud to staci priblizne, pak by stacilo spocitat pocet pixelu na obvodu a doufat, ze to bude podobne jako usecka mezi body, procentualne.
Jinak google, asi...
google = vykreslit nuhelnik do elipsy
google = nakreslit mnohouhelnik do elipsy
google = draw polygon into elipse
https://cs.wikipedia.org/wiki/Pravideln%C3%BD_mnoho%C3%BAheln%C3%ADk
Ramer–Douglas–Peucker algorithm
https://stackoverflow.com/…th-a-polygon
https://gis.stackexchange.com/…ygon-in-qgis
- tady treba pouzivaji takovy dost fake-postup, kdy vykresluji polygon na obvodu elipsy pomoci tecen v bode
https://www.geeksforgeeks.org/…-c-graphics/
Podle mne bys na to musel jit matematicky. Mozna rozdelit obvod na stejne uhly a spocitat pruseciky s elipsou. Ale, protoze u elipsy ty uhly se meni, tak bys to nemel vzdy stejne dlouhe :)
Nebo nejakym jinym zpusobem. Nenapada mne ted nic schudne, ale nejsem matematik. Mozna vyuzit pomer stran a/b, rozdil sinu kosinu pro pravidelny uhel a uhel pak nejak upravit.
Existuje forum matematika.cz
Znam jednu osobu, ktere se muzu zeptat :)
Kolegyne fyzicka mela jeste zajimavy napad. Pouzit zoom. Pouzit m-nasobek n-uhelniku a ten vepsat do o-nasobku elipsy. Tam se dostanes do stavu, ze pixelova vzdalenost bude hodne podobna primce. A muzes prave vychazet z toho obvodu.
https://tex.stackexchange.com/questions/352694/equilateral-polygon-inscribed-within-an-ellipse-in-tikz
- tady maji tez zajimave reseni
- nechce se mi to cist, ale nejspis body postupne posouvaji po obvodu elipsy a zvetsuji jejich vzajemnou vzdalenost, dokud to jde
Jakoze si vykreslis pixelove tu array do pole. Opet bych pouzil zoom, treba 100x. A pak posouvas jednotlive body po obvodu elipsy dokud netrefis zvolenou vzdalenost dvou bodu. Tak je tam nasunes vsechny a zjistis, ze ti z obvodu jeste hodnu kus zbyva. Tak vzdalenost zvetsis a body posunes.
Kdyby ta krovka byla primka, tak to vypada takto:
Věrný člen
Nahlásit jako SPAM
IP: 185.69.68.–
------------------------ rozdel na 3 stejne casti
delka primky je 24 (treba obvod elipsy)
odhadovana min delka je 24/3 = 8. ale zvolil 50%, 4
x---x---x---x----------- - nepokryl jse cely obvod, v = v + 1
x----x----x----x-------- - opet nic, znovu v = v + 1
x-----x------x------x--- - opet nic, v = v + 1
x------x-------x-------x - pokryl jsem cely obvod, zbytek je 0
A totez delas s elipsou, posunes o +1 +2, +3, dokud vzdalenost bodu A=B neodpovida nebo je vetsi nez vzdalenost, kterou sis zvolil
Obavam se, ze ve tvem reseni neustale uvazujes o kruznici.
Pokud nakreslis n-uhelnik do kruznice, pak vsechny uhly od stredu k prusecikum jsou stejne.
Pokud na obvodu udelas stejne od sebe vzdalene carku, pak opet mas stejne uhly.
Kdyz na elipsu das stejne vzdalene carky podel obvodu, tak se uhly se stredem meni :)
Kdyz na elipsu das stejne vzdalene carky pro ten polygon, tak mas zase jine uhly :)
Ale pravdu mas v tom, ze to asi jinak nez brute-force nepujde. Jak uz jsem naznacil, jen teda spis opacne, pulenim vzdalenosti misto pridavanim po jedne, by to bylo rychlejsi. Se v praci nudim, tak si s tim budu asi hrat zitra v js pres ten zoom a pole obvodu elipsy.
To balancovani neni uplne spravne, ale nechce se mi ladit. Selhava mi to pro 5, 7 a jine uhelniky, 11 a vic to zvlada v pohode.
https://mlich.zam.slu.cz/…ol-to-el.htm
Kazdopadne, spravny pocetni postup je pouzivat prunik kruznic a elipsy. Max moznou delku vis na zacatku, ta ke obvod elipsy/n. Ale muzes si to zjednodusit jako obdelnit 4.a.b nebo kruh 2.pi.a (v tomto pripade treba volit tu delsi stranu)
No, ja to resim castecne tak, ze vypocitam stranu zleva, zprava.
Muj zpusob neni dobrej jen proto, ze to nepocita presne. Takze muze nastat situace, ze posledni carka bude moc dlouha nebo moc kratka. Pak by bylo treba dorovnat ostatni body. Jenze posunutim po elipse se to muze cele dramaticky posunout :) Kdezto u te vypocetni metody dostanes ty body zhruba na spravnem miste a rozdil bude +-1 u carek, ale ta posledni na tom bude stejne.
Jako, to moje by mozna slo, kdybych nasel chybu a kdybych pouzil ten zoom, jak jsem psal. Rozdil v zoomu-plus by mohl byt minimalni. A pak to prepocitat na zoom-out, tak bych se tez trefil na +-1.
Zasadni minusko cele to moje ma v okamziku, kdyz ten uhelnik bude mit 100 stran, treba. Ten posun na konci pak muze kolisat silne kolisat, minimalne +-100, maximalne klidne +-10.000
x-------x-------x-----------
x------xXx---xxxXxxx-------
S kazdym bodem a zaokrouhlovanim na jednotky pixelu narusta nejistota polohy bodu u primky. V pripade elipsy se kvuli zakriveni ten bod muze posunout o vic nez jeden pixel, takze ten dalsi uz se muze posunout po oblouku o 5, treba.
Proste, spocitat to matematicky jako prunik kruznic s elipsou je asi nejlepsi. To mas jistotu, ze ten bod je prave tam a nejistota je +-1-2 px.
Otazkou je, k cemu to BSD potrebuje? Treba jde jen o programatorske cviceni. do hodiny IT :) Resp, nejaky program, ktery, kdyz udela, nemusi jit na zkousku :)
Ten paprskovy obrazek jsem nasel na netu a zbytek je malovani. Je videt, ze se ty usecky zkracuji, ale rozdil je vyrazny jen pri extremnejsim pomeru. A myslim, ze by to slo osidit tak, ze proste do uhlu se zapocita nejake procento vzdalenosti od pocatku. Takze, pak by vicemene to mohlo byt rovnomerne. Mel by to pokryt nejaky druh paraboly.
Připojen obrázek.
Ono, spocitat se to da. Vytvorit si nekolik 1000x vetsich elips s ruznym pomerem stran a pak pro vsechny ty druhy nechat pocitat vzdalenosti pro stejny n-uhelnik. Verim, ze metodou pokus omyl by se dalo prijit na rovnici s uspokujujicim vysledkem. Jen by nikdo nesmel dat 100x vetsi elipsu nez na jake jsem to pocital :)
Blbe je, ze, kdybys chtel pouzit tu fintu s procenty z uhlu, tak si to musis prepocitat z kruznice na elipsu :) Coz je omoc slozitejzi nez kresleni elipsy.
function computePrusecik(c, a, b, uhel) // c{x:num,y:num}
{
// y = tan(uhel) * x ... usecka z uhlu
// (x-c.x)(x-c.x)/(a*a) + (y-c.y)(y-c.y)/(b*b) = 1 ... stredova rovnice elipsy
// - z elipsy si musis vyjadrit x= nebo y=
// - dosadit x (nebo y) z rovnice usecky
// - vypocitat diskriminant, urcit y1, y2 a x1, x2
// - rozhodnout se podle uhlu, ktere vysledek pouzit
}
To se mi ted jako vubec nechce prepisovat :) Ale, ten posun by sel mozna resit pomoci kosinu uhlu.
Dalsi moznost je ten uhel upravovat primo pro rovnice elipsy. Ale, tam asi bude treba vychazet z predchoziho bodu.
// k = 0..n
// d = 2 * Math.PI / n
Math.round(c.x + a * Math.cos(d*k)),
Math.round(c.y + b * Math.sin(d*k))
Ale problem je, ze tady se ten uhel natahuje elipticky. Kdyz je elipsa na lezata, ze zacatku je maly a pak dramaticky velky. U toho procentualniho reseni je to naopak, ale nejsou ty skoky tak dramaticke.
Ja jen, jestli stale shanis nejake fake reseni a nechce se ti to pocitat postupnym natahovanim kruznice :)
Ahoj.
Tento program ve VB6 jsem vytvořil před 20 lety. Už se k němu nechci moc vracet.
Místo příkazu Pset (kreslí bod) by byl vhodnější příkaz Line (maluje linku) .
Option Explicit
Private Sub Command1_Click()
Cls
Dim sx As Integer, sy As Integer
Dim x As Integer, y As Integer
Dim r As Single
Dim a As Long, s As Integer
Dim polomer1 As Integer
Dim polomer2 As Integer
Dim i As Integer
Dim radians As Single
Dim uhel1 As Single, uhel2 As Single
sx = 200
sy = 150
polomer1 = 150 'rozmery ellipsy
polomer2 = 40
Const Pi = 3.14
Rem uhel1 = 45 ' úhel pootočení ve stupních (ve směru hod.ruč.)
uhel1 = Pi - (Val(Text1.Text) * (Pi / 180) - Pi / 2)
For s = 1 To 360
uhel1 = Pi - (s * (Pi / 180) - Pi / 2)
Cls 'vymaže kreslící plochu
For i = 1 To 360
radians = i * (Pi / 180)
x = (polomer1 * Cos(radians)) * -1
y = (polomer2 * Sin(radians)) * -1
PSet (x + sx, y + sy) 'maluje body původní elipsy
r = Sqr(x ^ 2 + y ^ 2)
If y = 0 Then
If x > 0 Then uhel2 = Pi / 2 Else uhel2 = Pi / 2 + Pi
Else
uhel2 = Atn(x / y)
End If
If y < 0 Then uhel2 = uhel2 + Pi
uhel2 = uhel1 + uhel2
x = r * Cos(uhel2)
y = r * Sin(uhel2) * -1
PSet (x + sx, y + sy) 'maluje body pootočené elipsy
Next i
For a = 1 To 5000000
Next a
DoEvents
Next s
End Sub
#27 Luboš
Zkusil jsem si tvůj kód přepsat. Výsledkem není rovnostranný n-úhelník.
Zdravím, snažím se přepsat tuto ukázku. Nevím co v kódu je deg?
struct _circle { public double x, y, r;}
struct _ellipse { public double x, y, rx, ry;}
static double Divide(double a, double b) //Překlad divide jsem doufám pochopil správně
{
return (b == 0.0) ? 0.0 : a / b;
}
private void Test2(int N)
{
const double R = 7; // satelite circles radius
const double E = 0.7; // ellipse distortion ry=rx*E
_circle[] circle = new _circle[N];
_ellipse ellipse = new _ellipse();
int i, j, k;
double l, a, da, m, dm, x, y, q, r0;//, deg = 0.2;
l = (double)N * R; // circle cener lines polygon length
ellipse.x = 0.0; // set ellipse parameters
ellipse.y = 0.0;
r0=Divide(l,Math.PI * Math.Sqrt(0.5*(1.0+(E*E))))-R;// aprox radius to match ellipse length for start
l=R+R; l*=l;
m=1.0; dm=1.0; x=0.0;
for (k=0;k<5;k++) // aproximate ellipse size to the right size
{
dm = Math.Abs(0.1 * dm); // each k-iteration layer is 10x times more accurate
if (x > l) dm = -dm;
for (; ; )
{
ellipse.rx = r0 * m;
ellipse.ry = r0 * E * m;
for (a = 0.0, i = 0; i < N; i++) // set circle parameters
{
q = (2.0 * a) - Math.Atan2(Math.Cos(a), Math.Sin(a) * E);
circle[i].x = ellipse.x + (ellipse.rx * Math.Cos(a)) + (R * Math.Cos(q));
circle[i].y = ellipse.y + (ellipse.ry * Math.Sin(a)) + (R * Math.Sin(q));
circle[i].r = R;
da = Divide(360 * deg, N);
a += da;
for (j = 0; j < 5; j++)// aproximate next position to match 2R distance from current position
{
da = Math.Abs(0.1 * da); // each j-iteration layer is 10x times more accurate
q = (2.0 * a) - Math.Atan2(Math.Cos(a), Math.Sin(a) * E);
x = ellipse.x + (ellipse.rx * Math.Cos(a)) + (R * Math.Cos(q)) - circle[i].x; x *= x;
y = ellipse.y + (ellipse.ry * Math.Sin(a)) + (R * Math.Sin(q)) - circle[i].y; y *= y; x += y;
if (x > l)
{
for (; ; ) // if too far dec angle
{
a -= da;
q = (2.0 * a) - Math.Atan2(Math.Cos(a), Math.Sin(a) * E);
x = ellipse.x + (ellipse.rx * Math.Cos(a)) + (R * Math.Cos(q)) - circle[i].x; x *= x;
y = ellipse.y + (ellipse.ry * Math.Sin(a)) + (R * Math.Sin(q)) - circle[i].y; y *= y; x += y;
if (x <= l) break;
}
}
else if (x < l)
{
for (; ; ) // if too short inc angle
{
a += da;
q = (2.0 * a) - Math.Atan2(Math.Cos(a), Math.Sin(a) * E);
x = ellipse.x + (ellipse.rx * Math.Cos(a)) + (R * Math.Cos(q)) - circle[i].x; x *= x;
y = ellipse.y + (ellipse.ry * Math.Sin(a)) + (R * Math.Sin(q)) - circle[i].y; y *= y; x += y;
if (x >= l) break;
}
}
else break;
}
}
// check if last circle is joined as it should be
x = circle[N - 1].x - circle[0].x; x *= x;
y = circle[N - 1].y - circle[0].y; y *= y; x += y;
if (dm > 0.0) { if (x >= l) break; }
else { if (x <= l) break; }
m += dm;
}
}
}Nakonec jsem vymyslel řešení, které mi nejvíc vyhovuje.
Spočívá v tom, že
using System;
using System.Collections.Generic;
using System.Drawing;
namespace Grafika
{
public struct DoublePoint
{
public double X;
public double Y;
public DoublePoint(double x, double y)
{
X = x;
Y = y;
}
}
static class Geo
{
/// Konverze zaokrouhlováním na Point
public static List<Point> ConvertToPoints(List<DoublePoint> lst)
{
if (lst == null) return null;
int cnt = lst.Count;
List<Point> points = new List<Point>(cnt);
for(int i=0; i<cnt; i++)
{
points.Add(new Point((int)Math.Round(lst[i].X), (int)Math.Round(lst[i].Y)));
//points.Add(new Point((int)lst[i].X, (int)lst[i].Y));
}
return points;
}
// Výpočet elipsy
public static List<DoublePoint> GetEllipsePoints(double rad_a, double rad_b, double res)
{
if (res == 0) throw new ArgumentException("Rozlišení nesmí být nulové!");
double a = Math.Abs(rad_a);
double b = Math.Abs(rad_b);
double resolution = Math.Abs(res);
int len = Convert.ToInt32(Math.Ceiling((2 * a) / resolution));
double b2 = b * b;
double a2 = a * a;
double x2, q, y, MI = -a;
List<DoublePoint> lst = new List<DoublePoint>(len + 2);
for (double x = a; x >= MI; x -= resolution)
{
x2 = x * x;
q = ((a2 * b2) - (x2 * b2));
y = Math.Sqrt(q / a2);
lst.Add(new DoublePoint(x, -y));
}
for (double x = -a; x <= a; x += resolution)
{
x2 = x * x;
q = ((a2 * b2) - (x2 * b2));
y = Math.Sqrt(q / a2);
lst.Add(new DoublePoint(x, y));
}
return lst;
}
// výpočet vzdálenosti mezi body
private static double GetLineLenght(DoublePoint P, DoublePoint R)
{
double x = R.X - P.X;
double y = R.Y - P.Y;
return Math.Sqrt((x * x) + (y * y));
}
// Eliptický n-úhelník bez posunu s plným zobrazením
public static List<DoublePoint> GetEllipsePolygon(double rad_a, double rad_b, double res, int N)
{
if (N < 1) return new List<DoublePoint>();
List<DoublePoint> eli = GetEllipsePoints(rad_a, rad_b, res);
if (eli.Count <= N) return eli;
int stop = eli.Count - 2;
double all = 0;
for (int i = 0; i < stop; i++)
{
all += GetLineLenght(eli[i], eli[i + 1]);
}
double segm = all / N;
double n = 0, m = segm;
int H = 0;
List<DoublePoint> pol = new List<DoublePoint>(N);
for (int i = 1; i <= stop; i++)
{
n += GetLineLenght(eli[i - 1], eli[i]);
if (n >= m)
{
H++;
pol.Add(eli[i]);
m = H * segm;
}
}
return pol;
}
// Eliptický n-úhelník s možností posunout počátečního bodu a částečným zobrazením (úsekem n-úhelníku)
public static List<DoublePoint> GetEllipsePolygon(double rad_a, double rad_b, double res, double ROT, int N, int firstN, int lastN)
{
if(ROT > 0) firstN--;
if (N < 1 || lastN < 1 || firstN > N || firstN > lastN) return new List<DoublePoint>();
if (lastN > N) lastN = N;
if (ROT < 0 || ROT >= 1) ROT = 0;
List<DoublePoint> eli = GetEllipsePoints(rad_a, rad_b, res);
if (eli.Count <= N) return eli;
int stop = eli.Count - 2;
double all = 0;
for (int i = 0; i < stop; i++)
{
all += GetLineLenght(eli[i], eli[i + 1]);
}
double segm = all / N;
double move = segm * ROT;
double n = 0, m = (move > 0) ? move :segm;
int H = 0;
List<DoublePoint> pol = new List<DoublePoint>(lastN);
for (int i = 1; i <= stop; i++)
{
n += GetLineLenght(eli[i - 1], eli[i]);
if (n >= m)
{
H++;
if (H > firstN) pol.Add(eli[i]);
m = (H * segm) + move;
if (H > lastN) break;
}
}
return pol;
}
}
}
Neuniká. Nemám slov :-)
- sečtu vzdálenosti jednotlivých bodů
Nebylo by lepsi zadat jako pocatecni hodnotu obvod elipsy? vzdalenost1 = obvod / n A od te vzdalenosti odecitat postupne 1, 2, 4, 8... dokud se s body nevejdes do elipsy?
Ale, mozna by slo pouzit i ten priklad, co meli na tom forku. Vypocitat ty body nad elipsou a pak je vlozit do rovnice primky, spojnice x,y a bodu 0,0. a kde se to protne s elipsou.
Jako, rychlejsi by bylo pocitat to na elipse rovnou, ale, kdybys byl liny, tak priblizne by to melo vyjit i s temi primkami. Nevim, co to udela v extremnich pripadech, kdy n bude prilis male na obvod.
#37 peter
- sečtu vzdálenosti jednotlivých bodů
Nebylo by lepsi zadat jako pocatecni hodnotu obvod elipsy? vzdalenost1 = obvod / n A od te vzdalenosti odecitat postupne 1, 2, 4, 8... dokud se s body nevejdes do elipsy?
Dopočítávání je jedna věc, ale jak do toho zapojit to pootočení?
(ps. pokračovat s pokusy budu až zítra)
Délka elipsy se počítá podle tzv. eliptického integrálu. Není to jednoduchá věc a neexistuje exaktní řešení. Nejjednodušší je řešit to numericky. Vypočítáš pomocí eliptického integrálu délku L křivky celé elipsy o daných parametrech a,b. Rozdělíš ji na N částí. Dále iterativně hledáš takový úhel alfa, pro který je mezi dvěma po sobě jdoucími body vzdálenost rovná 1/N celkové délky. Účelová funkce je tedy eliptický integrál mezi dvěma vždy po sobě jdoucími body vzdálenými na elipse o hledný úhel alfa. Jako optimalizátor můžeš použít třeba algoritmus PSO nebo DE nebo CMA-ES. Všechny budou fungovat dobře. I když nechápu, k čemu ti to muže bejt dobrý. Můžeš samozřejmě použít i třebas Newton-Raphson Metodu, ale PSO to spočítá jednodušeji.
Pokud by ti teda nezalezelo na presnosti (cca 5%), tak by slo pouzit vepsany kosodelnik (body -a,0, +a,0, -b,0, +b,0) a jeho obvod rozdelit n. A pak ty uhly protahnout na elipsu. Pripadne zjistit vepsany a opsany a urcit si nejaky uprostred (presnost cca 2%).
Nebo, vepsat vepsat n-uhelnik delitelny 4. To pak jsou krajni body stejne jako u kosodelniku. Cely tvar se 4x opakuje, vypocet se zjednodusi 4x. (o to ses vlastne mozna pokousel). Pac jde o useckovy utvar, opet by melo byt jednodussi delit jeho obvod. Ale nevim, zda to neni stejny problem jako puvodni zadani :)
Nicmene, slo by treba tam vepsat 10x-n uhelnik, 10x vetsi. A tim bys nahradil jakoze elipsu. A na obvodu tohoto utvaru by to bylo snadnejsi pocitat. Kazda ta strana nemusi bys stejna. Tobe jde jen o to, ziskat priblizne uhly. Pro vykresleni rohu utvaru by slo prave pouzit ty rovnice (nejsem si ted jisty, zda to je presne ten kod, naposled jsem s tim delal nejake experimenty a nevim, co z toho jeste jede)
angle_step = Math.PI * 2/n,
angle_end = Math.PI * 2,
d = 2 * Math.PI / n,
k = 0;
arr = [];
arr[k] = new classPoint(
Math.round( c.x + a * Math.cos(0) ),
Math.round( c.y - b * Math.sin(0) )
);
k++;
for (angle=1; angle<angle_end; angle+=angle_step)
{
arr[k] = new classPoint(
Math.round(c.x + a * Math.cos(d*k)),
Math.round(c.y + b * Math.sin(d*k))
);
k++;
}
cili, n bys zvolil tak 20-40, pro 10 uhelnik. A pak tenhle utvar vicemene nahrazuje elipsu.
Ale, nevim, zda ti to k necemu bude, prilis jsem nepromyslel, co s tim. Asi bych spocital delky stran, obvod a ten pak rozdelil pomoci n. Body by mohli kopirovat elipsu vicemene tak s 3% chybou.
#43 BDS
Jak už jsme ti tu psali tak neexistuje žádná exektní metoda jak toho docílit. bohužel. Existují pouze aproximativní numerické metody pro výpočet. takže pro tvoji danou elipsu s parametry a,b spočítáš celý obvod O tak že spočítáš 1/4 délky obvodu a vynásobíš 4. Pak obvod O vydělíš N a dostaneš 1/N délky. Pak si vytvoříš cyklus ve kterém se bude numericky počítat eliptický integrál s dolní mezí od Omega1 do úhlu Omega2 a integrál se bude muset rovnat číslu 1/N x O přičemž Omega1 se počítá od nuly a Omega2 je hodnota, kterou hledáme pomocí vhodné numerické metody - obecně se to řeší formou nekonečně řady. Do dalšího cyklu se zapíše Omega1=Omega2 a Omega2 opět hledáš. Takže sice bude vznikat aditivní chyba na pozici 0.00001, ale nic lepšího asi dohromady nedáme.
Tady je seznam v současné době dostupných numerických metod:
http://www.ebyte.it/library/docs/math05a/EllipsePerimeterApprox05.html
a pro výpočet celého obvodu O bych asi použil Ramanujanovu metodu. A následně pro výpočet Omega2 v cyklu si můžeš vybrat jakoukoliv jinou vhodnou.
Bohužel neexistuje zde jednoduché řešení.
https://www.cuemath.com/measurement/perimeter-of-ellipse/
https://math.stackexchange.com/questions/2108199/arc-length-of-an-ellipse-using-integration
Vše budeš muset řešit v polárních souřadnicích a s využitím nekonečných řad.
Pokud by ti stačilo poněkud "hruběji" aproximativní řešení, tak můžeš využít výpočet s využitím ohnisek elipsy:
https://math.etsu.edu/multicalc/prealpha/chap3/chap3-2/part4.htm
||r|| + ||r-2ci|| = 2a
kde vytváříš body P na obvodu elipsy a lineární vzdálenost mezi dvěma po sobě jdoucími body P je to co hledáš.
#44 JerryM
Rozdělením obvodu na N bodů, rozdělíš elipsu na N stejně dlouhých segmentů, ale propojením těch bodů úsečkami nevznikne pravidelný n-úhelník, protože každý segment je jinak křivý. Pokud chce BDS pravidelný polygon, tak tohle není cesta. Proto jsem se ptal.
#47 Pavel
To se pleteš ... špatně si to pochopil... když elipsu rozdělíš na N stejných dílů, tak d=lka každé části křivky je logicky stejná, ale odpovídá tomu jiný středový úhel. Chápeš jo ? :) A on musí najít ten středový úhel.
#44 JerryM
Já jsem si to zkusil i s tím dopočtem, ale těch kroků je strašně moc, i na celkem rychlém procesoru je to hodně náročná operace. A čím menší je rozlišení, tím větší se potřeba tolerance.
Myslím, že většina odkazů které jsi tu dal řeší rozdělení elipsy po délce křivky, tak nevznikne rovnostranný mnohoúhelník.
Hele ještě jednou po lopatě:
1/ spočítáš si délku elipsy pomocí vzorce:
O = PI * ( 1.5 * ( a + b ) - SQRT(a*b)
2/ Vypočítáš si 1/N z délky O a označíme ji jako F neboli O/N = F a N je třeba 20000.
3/ Iterativně počítáš pomocí parametrických rovnic elipsy úhel, kterému odpovídá hodnota F pro dva různé body na elipse. Rovnice jsou tady https://cs.wikipedia.org/…/Elipsa ; neboli
x = a * COS(t)
y = b * SIN(t)
takže v prvním kroku
x1 = a * COS(0) = 1
y1 = b * SIN(0) = 0
a tím dostaneš bod P1[x1=1,y1=0] který evidentně leží na ose X a v dalším kroku hledáš takové t, pro které platí, že d(P1,P2) = F neboli d(P1,P2) = SQRT((x1-x2)^2 + (y1-y2)^2) a hledáš tedy iterativně hodnotu t a bod P2 počítáš opět podle vzorců:
x2 = a * COS(t)
y2 = b * SIN(t)
takže hodnotu t asi počítáš třeba půlením intervalu tak dlouho dokud se d(P1,P2) nebude od požadované hodnoty F lišit o nějakou zanedbatelnou hodnotu např. 0.0001 atd. ... a tohle spočítat můžeš protože protože víš, že t bude ležet v určitém rozmezí úhlů ...
chápeš jo ? no a takhle to pokračuje pro body P2 - P3 a P3 - P4 atd...vždycky znáš jeden bod Px třeba P3 a k němu počítáš P4 pomocí odhadování t, které se logicky stále zvětšuje od 0 do 2PI ...
#55 JerryM
no moc to sice nechápu, ale chápu, že je tam zase dopočítávání.
U každého dopočítávání je problém, že při určitých kombinacích rozměru a poměru elipsy + počtu stran, může docházet k zacyklení nebo k velmi velkému počtu opakování.
Vypadá to, že na tento problém, ale jiné řešení není. A pokud opravdu není, budu muset od této funkce mé aplikace upustit, nechám ji pouze pro kruh.
bohužel jednoduššeji to už vysvětlit neumim .. eliptický integrál je velmi složitý a jeho řešení zatím stále není známo. pustil ses do řešení úlohy, která je opravdu VELMI složitá .... i když na první pohled to vypadá jednoduše...eliptické integrály a eliptické diferenciální rovnice se obvykle učí až ve 4. ročníku na vš na matfyzu ..
... k zacyklení opravdu dojít nemuže .. je tam obvykle limit 0.00001 nebo 0.01 to se musí odzkoušet. ano, metoda puleni intervalu zrovna neni ideální ale jak už sem psal musel bys použít nějaký výrozně výkonnější optimalizátor a to třeba algoritmus Diferenciální Evoluce nebo PSO. S tim PSO bych asi začal - protože je jednoduchej. Ten úhel t můžeš samozřejmě zvětšovat i s nějakým krokem např. 0.0001 a asi to bude taky fungovat .... místo metody půlení intervalu prostě v cyklu FOR budeš k t přidávat od 0 hodnotu 0.0001 a až se d(P1,P2) bude rovnat F (+/- tolerance) tak skončíš první krok iterace. říká se tomu metoda hrubé síly... fungovat to bude určitě ... otázka je jak dlouho to potrvá ten výpočet ... to neumim odhadnout
#57 JerryM
Já jsem původně nečekal, že je to takto složitý problém. Má původní představa byla, že to budu používat tak jako když v nějakém grafickém programu kreslíš kružnici nebo šestiúhelník. Když jsem se postupně dozvídal, že to tak jednoduché není, tak jsem myslel, že to vyřeším zadáním hodnot a stisknutím tlačítka. Ale protože jsem to testoval na elipse cca 400*150 a trvalo několik sekund a já bych to chtěl často používat na elipsách cca 5000*3000 i větších, tak padá i to.
A to co zde uvádíš (PSO apd.) je na někoho kdo už zapomněl hodně z matematiky základní školy trošku jiná dimenze.
hm padat to nemusí, jakmile jednou máš hotovej výpočet tak už ty vypočtený body pro daný a,b elipsy už můžeš používat pořád dokola chápeš jo ? nemusíš to počítat znova a znova .. stačí jednou ..
já bejt tebou bych zkusil tu metodu hrubý síly a uvidíš co se stane ...
#58 BDS
asi pro tvuj případ by se tedy dal napsat tento algoritmus využívající metodu hrubé síly a počítající 1/4 elipsy:
a = 200
b = 1000
N = 20000
O = PI * ( 1.5 * ( a + b ) - SQRT(a*b) ) // obvod cele elipsy
F = O / N // aproximace n-uhelnikem
t = 0
x1 = a * COS(t)
y1 = b * SIN(t)
P1 = (x1,y1)
while ( t <= 1.5707 ) // v radianech
exitstatus = false
while ( exitstatus == false ) {
t = t + 0.000017453 // v radianech
x2 = a * COS(t)
y2 = b * SIN(t)
P2 = (x2,y2)
L = d(P1,P2) = SQRT( (x2-x1)^2 + (y2-y1)^2 )
if ( L >= F ) { exitstatus = true }
} // while
P1 = P2 // neboli x1=x2, y1=y2
} // while
#48 JerryM
Já to chápu, ale když bude délka toho "eliptického oblouku" stejná, vezmeš souřadnice těch bodů a pythagorovou větou spočteš vzdálenosti mezi nimi (délky sečen), tak nebudou všechny stejné.
Když jsem si to udělal stejně jako tady, spočítal obvod elipsy a rozdělil na N bodů, tak ačkoliv byly segmenty stejně dlouhé, délka sečen nikoliv.
https://math.stackexchange.com/…-ellipse-arc
Ano, to je pravda proto se tomu říká aproximace :) jak sem už mnohokrát psal tak exaktní řešení neexistuje. Už se o to za posledních několik set let snaží/snažilo tisíce matematiků a zatim stále nic. Takže tady je seznam prozatim dostupných aproximací:
http://www.ebyte.it/library/docs/math05a/EllipsePerimeterApprox05.html
můžeš si vymyslet svoji aproximaci s využitím Taylorova rozvoje... fantazii se meze nekladou.
Jinak možná bych v tom mým algoritmu dal místo 0.000017453 asi spíš hodnotu 0.00000017453 tohle se musí odzkoušet ... je třeba si uvědomit, že vzdálenost bodů P1 a P2 v tom mým algoritmu se počítá s přesností cca 0.00001 lepší přesnost stejně asi ne normálním Pythonu nebo Csharp atd nedosáhneš.
Právě ta podmínka L >= F a krok v úhlu 0.000017453 určuje přesnost výpočtu. Jinak metoda hrubé síly je asi to nejhorší co se dá použít, ale fungovat to bude. Možná by byla lepší Ramanujanova I. nebo II. aproximace. To je potřeba odzkoušet.
Mne nejak unika, jak se ti to muze zacyklovat? To, ze se to zacykluje mne, je vec jina, ja to nemam dotazene. A navic to pocitam na pixelove care obvodu :) Pocitam ne uplne dobre. Coz jde videt prave u tech mensich n-uhelniku jako 3, 4, 5...Normalne spocitas priblizeni zleva, zprava a vystupem je nejpresnejsi. V okamziku, kdy se ti leva, prava nezmeni, tak cyklus ukoncis.
smin = Minimalni strana = obvod kruhu kratsi strany (a nebo b) / n
smax = Maximalni strana = obvod elipsy / n
Pak spocitas rozdil tech dvou a podelis dvema. Cili, postupne navysujes levou stranu o d, d/2, d/4
d = round((smax - smin) / 2)
right = smax
new = left + d
Kdyz se polygon s new vejde do elipsy, tak si left = new, a zkusis pridat opet d, new = left + d.
Kdyz se polygon s new nevejde do elipsy, a je-li new<right, pak right=new a d = d / 2.
A to opakujes, dokud je d>0 px. Takze se to nemuze preci zacyklit.
Vystupem je left a right a z tech vyberes to, co se do elipsy veslo nejlepe.
Je uplne jedno, jakym zpusobem vejiti do elipsy pocitas.
Samozrejme, uplne nejlepsi by bylo pocitat uhly a nebo prunik kruznice s elipsou o polomeru left.
---
Nebo se da smin urcit tez jako vepsany kosodelnik, pokud je n>=4
smin = 4 * odm(aa + bb)
A tim, ze pouzivas deleni intervalu, tak se vicemene dostanes k pruseciku do 7-14 kroku. Coz je porad lepsi nez me pixelove reseni, left +1 +1 +1
1000 500 250 125 63 32 16
Ikdyz... S tou kruznici a kosodelnikem, to min neni uplne ok. To zas plati pro n>neco. A pripade kosodelniku (kosoctverec) musi byt uhel=0 pro n=4. Kdyz to pootocis, jak to mas v zadani, tak ten polygon by mel byt mensi nez ten kosodelnik.
Ale, tak, vzdycky muzes jit opacnou cestou. Max je obvod elipsy / n. A od toho budes odecitat pulky, takze si vytvoris slejne left a right.
#64 peter
ten kód už jsem smáznul, ale myslím že se to zacyklilo (možná ne úplně jen těch operací bylo tolik, že by to trvalo několik minut), protože čím víc roztahováním stran polygonu se určitý bod dostává do oblasti kde je elipsa širší tím víc chybělo k dosažení rovnostrannosti.
Sudé n-úhelníky se spočítaly docela rychle.
Zkusím i ten Tvůj postup.
#62 Jerry
Ano, eliptický integrál se počítá pomocí nekonečné řady (případ pythonu a knihovy SciPy), Ramanujana nechme stranou. Tudíž, když spočeteš integrál s přesností na 5 desetiných míst, ale délky sečen se liší +- 0,5 pro malé polygony (s rostoucím počtem hran ta chyba klesá). Tak to není chybou aproximace ale tím, že stejně dlouhý segment neznamená stejně dlouhou sečnu, protože ta elipsa je splácnutá. Kdyby sis to místo opakování toho samého napsal, a pak sem dal obrázek a nějaké výsledky, tzn. délku oblouku pro daný počet stran, třeba 5-úhelník a pak délku jednotlivých stran.
#69 Pavel
...jo aha, tak mužete provést převzorkování na větší rozlišení ne ? místo rozměru a=20,b=100 dáte a=2000, b=10000... a fungovat to bude. Pořád nechápu co vám nejde nebo co máte s těma sečnama a tečnama ... tak to počítejte v přesnosti long double a je to .. to je podle IEEE754 přesnost na 80 bitů.
#70 Jerry
Tak obrázek no:
#74 Jerry
Jako že když jedna strana je 5 a druhá 4,3, tak je to jako malá chybka? Dyť je to 14%, a jeto dáno právě tím že to není kruh, takže to nelze řešit rovnoměrným dělením obvodu.
Asi by se dala hledat kružnice o vhodném poloměru, kterou budu cestovat po elipse a protínat ji, tak abych se na konci potkal ve stejném bodě, ale nebude to úplně sranda.
#77 Pavel
"...Asi by se dala hledat kružnice o vhodném poloměru,..." ne to asi taky nepude .. prostě elipsa je elipsa .. ježišmarjá to už si z Vš z matematický analýzy nic nepamatujete ? no a zkusili ste teda ten muj algoritmus ? ten přeci funguje ne ? ale to je přeci taky aproximace
#75 Jerry
ale chápete, že pravidelněj pětiúhelník na elipse vubec nemusí vyjít .. z důvodu geometrie... elipsa neni kružnice ..
Myslíš, že eliptický válec nemůžeš obehnat válečkovým řetězem (lépe vsadit řetěz do vnitř) řetězem o vhodné rozteči??
Ten n-úhelník nemusí být pravidelný, pouze rovnostranný.
https://mlich.zam.slu.cz/js-pol-to-el.htm
Trochu jsem tu funkci 1 prepsal, ted na 3. Mela by fungovat trochu lepe. Do konzoly pise pocet pokusu. Bezny n-uhelnik to najde na 8 pokusu.
Pouzil jsem vzorec v = (left + right) / 2, cili, vyberu vzdy stredovou hodnotu a pak urcim, zda ji pouzit pro left nebo right. Jenom to dal vykresluji do pixelove elipsy, coz muze byt brzda. Ale i na mem stroji v praci je to mzik, takze se mi to nece resit lepe :)
ArrayDrawPolygonToEllipse3(new classData(), 8, new classPoint(420,150), 400, 100, 'red2');
// posledni radky v kodu
5-uhelnik, o kterem je zminka, to nenajde, ale take skonci. U 5-uhelniku je ten problem, ze zvetseni strany o 1 px muze zalomit bod na dalsi ctvrtinu elipsy a dalsi bod se muze znacne posunout, klidne 199% delky strany.
Tezko rici, jak tohle resit :)
#71 Pavel No, pomer stran te elipsy mas spis 1:1, kruho-elipsu :) V takovem pripade se da pouzit to kruhove rozlozeni uhlu.
A nebo by slo pro kazdy pripad pouzit jinou metodu. Treba i pro ten 5 uhelnik. Proste se vi, ze to uplne nevyjde dobre, kdyz bude elipsa prilis sisata a tak pouzit metodu pravidelnymi s uhly. Sak ten program to muze spocitat obema, neni to pro nej zadna zatez. Pokud to nedela pro 50 elips najednou, treba.
A nebo se daji napocitat uhly pro ruzne pomery stran a ruzne n-uhelniky.
ostatne, zrovna ten 5-uhelnik mi vychazi kazdou tou funkci jinak
https://mlich.zam.slu.cz/js-pol-to-el-5uhelnik.htm
Nahore vpravo je videt, ze ty zelene krizky jsou jakoby dvojite. A ten 1 px stacil na to, aby to tahle uplne svihlo pres celou elipsu .
#83 peter
a to je právě problém, teď by bylo potřeba od bodu [b,0] (v protisměru hodin) přidat jeden dílek na první čtyři úseky, jenže tím se ten levý bod začne dostávat do míst kde je elipsa užší (udělá to asi víc než posuv u jiných bodů), tím se odebere z posledního úseku třeba 5 dílků. Takže zase něco odebereš.... a tak furt do kola.
Mě se pořád jeví, že by se na to mělo jít přes pravidelný rovnostranný pětiúhelník a ten zkreslit podle elipsy. Nebo kruh rozdělený na úhly a jednotlivé úhly pak zkreslit podle tvaru elipsy. Klidně bych oželel i možnost pootočení.
Nevim, zda se chapeme. Elipsu a polygon vykresluji od bodu x=+a, y=0, do bodu x=0, y=+b, atd, kvadrant 1, 2, 3, 4. V 1 je to ok. Bod 1 je ok, bod 2 je ok, ale v pripade modreho 5uhelniku je posunuty prave o 2px. A timpadem treti modry bod skoci kamsi dohaje proti tretimu cervenemu. A posledni bod se zobrazi u obou utvaru jinak. Cili, tady ti korekce o 2 px hraje velmi vyznamnou roli. A ani jeden z tech utvaru nema posledni stranu stejne velkou. Co s tim chces jako delat?
Jedine, co by slo, pouzit kruhove rozlozeni uhlu. A pak bude kazda strana jinak, jak je to videt na obrazku od pavla. V obou pripadech to proste bude jasne videt. Ale, mozna je to prave lepsi volba.
Zajimave by bylo videt, jak se zachova ten program na videu.
Jeste mne v praci napadlo vykreslit sinusovku na elipsu. Ale nevim, zda by to melo vysnam.
Nevim, no, pouzit kruhove rozlozeni uhlu a pridat tam procentualni posun pro zvetseni a zuzeni. Asi ziskany jako tangenta. A pouzit to jen v pripade licheho poctu nebo poctu nedelitelneho 4.
Mimochodem, v tom youtube videjku je tech zubu 20, cislo delitelne 4.
#87 peter
ono se to nezdá, ale eliptické ozubené kolo je děleno dle délky křivky. Nedělá de příliš eliptické a tak ten rozdíl není velký. Tady je kolo s 18 zuby. Jde o to, že rozteč zubů musí být stejná jako u sousedního kruhového kola.
No já jsem nic s kružítkem na nic kloudného nepřišel:) Jen na to, že v tom asi žádná běžná (lidská) logika není, stačí přidat hranu nebo trochu změnit poměr elipsy a je všechno jinak..
Takže z mého původního záměru asi nic nebude.
#88 JerryM
Ne ja, to tady BDS neco kuti. A posilal takovy odkaz na video, ktery je dost zasity v jeho textu a neumi ho spravne popsat (slova toto, zde a tu povazuji za nedostatecne). Tak mne napadlo zkusit spocitat zuby. Ze, jak to asi resi ten cad. #41 BDS
#89 BDS
Vis, ono, mozna nejdriv si vyrobis to elipso-kolo a az pak to kulate, kde snadneji muzes snadneji menit velikost zubu, pac to jde matematicky spocitat :)
Mimochodem, CAD asi pujde spustit jako comand-line. Ten system je tu leta a mohl by to mit vestavene.
Sak, on ti JerryM poslal odkaz na aproximace. Tam je jich asi 40 nejakych vzorecku :)
Jako, ona, priblizna delka strany se da odhadnout i tak, ze tam das pravidelne uhly, prunik s elipsou a pak vzdalenosti bodu zprumerujes. Ale, u toho 5 uhelniku to bude naprd, protoze ten tam prave potrebuje kazdou stranu jinou :)
Tez by to slo resit tak, ze vemes pravidelny n-uhelnik. 3d utvar, prstenec s pruznymi body (tkanina, jakoby) a nechas ho spadnout na kuzel s rozsirujici elipsou. On tam nejak spadne, nejak se to rozlozi a ty pak zjistis polohu bodu aze zhora a vzdalenost ze spoda bodu nejak zprumerujes a urcis velikost elipsy. A pak to proste zoomnes, jak potrebujes.
Nebo udelas n-uhelnik a pak v nem roztahujes elipsu. A nesmi se to pretrhnout. Cili, neco jako bridge builder.
Tobe jde proste jen o to, ze na konkretni pomer stran a/b potrebujes vypocitat uhly pro n-uhelnik. To si muzes predem pripravit tabulku a nasobky 4 tam aproximovat jako polovicku uhlu.
3 * 4 * 16 * 64...
4 * 4 * 16
5 * 4 * 16
6, 7 8, 9, 10, 11 (12 uz netreba, to je 3*4*...)
Pro 1 pomer a/b mas tak 1000 hodnotu. Tvuj alg. vybere, nejvhodnejsi tabulku a/b, vybere nejblizsi n-uhelnik a zbytek dopocita pulenim uhlu. Ale, musis predem stejne nejak vygenerovat tu tabulku :)
Proste, pouzij radeji nekterou z tech aproximaci, jak psal jerry. Jen se obavam, ze se v te strance nevyznas a nevis, co vlastne z ni chces :)
Oni z tech udaju a/b a n vypracovali nejakou krivku a na tu krivku pouzili aproximaci nejakou funkci. Podobne, jak se da treba sinusovka aproximovat nekolika parabolami, pokud te nezajima presnost na 0.0001 :)
#94 peter
No já se právě v těch složitých vzorcích vůbec nevyznám. Já pracuji z rozlišením 0.005 - 0.025, takže ta nepřesnost je v pohodě.
Ono by asi byla ta tabulka nejjednodušší, ale kdybych ji měl. Kdybych ji chtěl vyrobit metodou pokus-omyl, tak bych ji dělal do vánoc (maximální počet kroků bych chtěl mít alespoň 180)
jeste jsem nasel na jednom forku jeden pekny odkaz na wiki, pod nadpisem "Steiner generation" je ukazka generovani bodu na elipse. Treba to k nicemu nebude, ale pekne to je :) Zvlast nad tim, animovane zpusoby kresleni elips.
https://en.wikipedia.org/wiki/Ellipse#Polar_form_relative_to_center
Zkoušel jsem pro Jerryho tupý numerický přístup hledejme body na elipse, které jsou požadovaně daleko od sebe. Jsem jenom dělník a na základce jsme matematickou analýzu neměli. Nicméně, je to strašně citlivé na "zploštělost elipsy" a na počáteční nástřely. Někdy to funguje, ale je to zajímavý problém, přitom taková blbost.
#99 Pavel
Ale tohle nevypadá vůbec špatně. Nemyslím si, že někdo bude v mém sw příliš často potřebovat příliš ploché elipsy (když jo, tak ať si to udělá nějak ručně). Možná bych to omezil na sudý počet hran, s pevnými body na 3 a 9ti hodinách, pokud to pomůže.
Můžu se prosím zeptat, jak jsi přesně postupoval?
#100 BDS
Postup je celkem primocary, zvolil jsem pocatecni bod na elipse, nastrelil jsem vzdalenost mezi body jakozto polomer kruznice a hledal pruseciky. Pak jsem na konci hledal, jestli jsem za nebo pred pocatecnim bodem a upravil jsem nastrel polomeru metodou puleni intervalu. Ale jak rikam, je to strasne citlive na nastrely. Samotny vypocet (delam to v Pythonu) trva asi 0.2s. Vychazi pekne grafy, asi by se dal udelat nejaky fit na vypocet delky strany primo. Nicmene, jsem jenom delnik, nerad bych zbytecne popichoval analyticke matematiky.
V podstate, na tech krivkach je videt, ze nasobenim 2x dostanes tez zhruba dvojnasobne zakriveni. Takze ti vlastne staci ty krivky vypocitat jen pro prvocisla a urcit k nim nejake parabolicke prolozeni. A to myslim presne resi ten link Jerryho, vypocet ekcentricity.
#102 peter
Omlouvám se, ale absolutně nechápu. Vidím křivky, které ani moc parabolicky nevypadají.
Jinak tomu problému jsem se teď neměl čas věnovat. Udělal jsem sice pár pokusů, ale při některých parametrech mi to dělalo paseku a to mě štve. Proto teď řeším funkce na které stačím. Ale určitě se chci k tomu vrátit, hlavně z důvodu, že na to chci přijít. A taky by byla škoda, snad nejdelší vlákno v této diskuzi nedořešit.
Jeden clovek mi poradil program Zoner Callisto. Ale bliz jsem to nezkoumal. Odhadem je to jen program na upravu fotek, ktery umi ruzne efekty. Nevim, zda to umi generovat souradnice a ty elipsy :)
Zjistit počet nových příspěvků
Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku
© 2003–2024 Programujte.com
