• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Koch Curve ( krzywa kocha ). Program w SFML.

VPS Starter Arubacloud
0 głosów
588 wizyt
pytanie zadane 26 lipca 2019 w C i C++ przez Jakub 0 Pasjonat (23,120 p.)

Witam, ostatnio napisałem program generujący tytułowy fraktal. Oto kod:

#include <SFML/Graphics.hpp>
#include <vector>
#include <array>
#include <cstddef>
#include <cmath>

//-----------------------------------------------------------------------------------

constexpr float PI = 3.14159265359f;
constexpr float DegreesToRadians = PI / 180.f; 
inline float toRad(float d) {
	return d * DegreesToRadians;
}

//-----------------------------------------------------------------------------------

const unsigned SurfaceWidth = sf::VideoMode::getDesktopMode().width;
const unsigned SurfaceHeight = sf::VideoMode::getDesktopMode().height;

//-----------------------------------------------------------------------------------

///settings...
const std::size_t RecursionDeepth = 7;
const sf::PrimitiveType CurveType = sf::Lines; // or sf::Triangles
const sf::Color Color(82, 187, 243);

//-----------------------------------------------------------------------------------

constexpr std::size_t CstPower(std::size_t value, std::size_t pow) {
	if (pow == 0)
		return 1;
	return value * CstPower(value, pow - 1);
}

//-----------------------------------------------------------------------------------

constexpr std::size_t getFillCurveVertexAmount(std::size_t rdeetph) {
	std::size_t res = 1;
	for (std::size_t i = 0; i < rdeetph; ++i) {
		res = res * 4;
	}
	return res * 3; 
}

constexpr std::size_t getOutlineCurveVertexAmount(std::size_t rdeetph) {
	if (!rdeetph)
		return 0; 
	std::size_t res = 1;
	for (std::size_t i = 0; i < rdeetph; ++i) {
		res = res * 4;
	}
	return res * 6;
}

//-----------------------------------------------------------------------------------

template <typename Canvas, typename Container>
inline void drawOn(Canvas& canvas, const Container& container, sf::PrimitiveType type) {
	canvas.clear(sf::Color(0, 0, 0));
	if(container.size())
		canvas.draw(&container[0], container.size(), type);
	canvas.display(); 
}

//-----------------------------------------------------------------------------------

sf::Vector2f getMissingTriangleVertex(sf::Vector2f av, sf::Vector2f bv, float dangle) {
	sf::Vector2f vertex; 
	float angle = toRad(-dangle);
	vertex.x = ((bv.x - av.x) * std::cos(angle)) - ((bv.y - av.y) * std::sin(angle)) + av.x;
	vertex.y = ((bv.x - av.x) * std::sin(angle)) + ((bv.y - av.y) * std::cos(angle)) + av.y;
	return vertex; 
}

//-----------------------------------------------------------------------------------

void generateFillKochCurve(std::vector<sf::Vertex>& points, std::pair<sf::Vector2f, sf::Vector2f> stretch, std::size_t deepth) {
	if (deepth <= 0)
		return;

	float xlength = stretch.second.x - stretch.first.x;
	float ylength = stretch.first.y - stretch.second.y;

	float fxlength = stretch.first.x + ( xlength * (1.f / 3.f));
	float sxlength = stretch.first.x + ( xlength * (2.f / 3.f));
	float fylength = stretch.first.y - ( ylength * (1.f / 3.f));
	float sylength = stretch.first.y - ( ylength * (2.f / 3.f));

	sf::Vector2f fb(fxlength, fylength);
	sf::Vector2f sb(sxlength, sylength);
	sf::Vector2f missingVertex = getMissingTriangleVertex(fb, sb, 60.f);

	points.emplace_back(fb, Color);
	points.emplace_back(missingVertex, Color);
	points.emplace_back(sb, Color);

	generateFillKochCurve(points, std::make_pair(stretch.first, fb), deepth - 1);
	generateFillKochCurve(points, std::make_pair(fb, missingVertex), deepth - 1);
	generateFillKochCurve(points, std::make_pair(missingVertex, sb), deepth - 1);
	generateFillKochCurve(points, std::make_pair(sb, stretch.second), deepth - 1);
}

//-----------------------------------------------------------------------------------

void generateOutlineKochCurve(std::vector<sf::Vertex>& points, std::pair<sf::Vector2f, sf::Vector2f> stretch, std::size_t deepth) {
	if (deepth <= 0)
		return;

	float xlength = stretch.second.x - stretch.first.x;
	float ylength = stretch.first.y - stretch.second.y;

	float fxlength = stretch.first.x + (xlength * (1.f / 3.f));
	float sxlength = stretch.first.x + (xlength * (2.f / 3.f));
	float fylength = stretch.first.y - (ylength * (1.f / 3.f));
	float sylength = stretch.first.y - (ylength * (2.f / 3.f));

	sf::Vector2f fb(fxlength, fylength);
	sf::Vector2f sb(sxlength, sylength);
	sf::Vector2f missingVertex = getMissingTriangleVertex(fb, sb, 60.f);

	if (deepth == 1) {
		points.emplace_back(stretch.first, Color);
		points.emplace_back(fb, Color);
		points.emplace_back(fb, Color);
		points.emplace_back(missingVertex, Color);
		points.emplace_back(missingVertex, Color);
		points.emplace_back(sb, Color);
		points.emplace_back(sb, Color);
		points.emplace_back(stretch.second, Color);
	}

	generateOutlineKochCurve(points, std::make_pair(stretch.first, fb), deepth - 1);
	generateOutlineKochCurve(points, std::make_pair(fb, missingVertex), deepth - 1);
	generateOutlineKochCurve(points, std::make_pair(missingVertex, sb), deepth - 1);
	generateOutlineKochCurve(points, std::make_pair(sb, stretch.second), deepth - 1);
}

//-----------------------------------------------------------------------------------

int main() {
	sf::RenderWindow window(sf::VideoMode(SurfaceWidth,SurfaceHeight), "Koch Curve", sf::Style::Close); 
	window.setKeyRepeatEnabled(false);
	window.setFramerateLimit(60);

	sf::RenderTexture surface;
	surface.create(SurfaceWidth, SurfaceHeight);
	surface.setSmooth(false);
	sf::View v = window.getView();

	std::array<sf::Vector2f, 3> startedVertex = { {
		{ 0.f, 0.f },
		{ static_cast<float>(SurfaceWidth), 0.f },
		{ window.getSize().x / 2.f, static_cast<float>(window.getSize().y) }
	}};

	///----------------------------------------------------------------------------------

	std::vector<sf::Vertex> kochCurve;
	void(*curveGenerator)(
		std::vector<sf::Vertex>&,
		std::pair<sf::Vector2f, sf::Vector2f>,
		std::size_t) = nullptr;

	if (CurveType == sf::Triangles) {
		kochCurve.reserve(getFillCurveVertexAmount(RecursionDeepth));
		kochCurve.emplace_back(startedVertex[0], Color);
		kochCurve.emplace_back(startedVertex[1], Color);
		kochCurve.emplace_back(startedVertex[2], Color);
		curveGenerator = generateFillKochCurve;
	} else if (CurveType == sf::Lines) {
		kochCurve.reserve(getOutlineCurveVertexAmount(RecursionDeepth));
		curveGenerator = generateOutlineKochCurve;
	}

	if (curveGenerator != nullptr) {
		curveGenerator(kochCurve, std::make_pair(startedVertex[0], startedVertex[1]), RecursionDeepth);
		curveGenerator(kochCurve, std::make_pair(startedVertex[1], startedVertex[2]), RecursionDeepth);
		curveGenerator(kochCurve, std::make_pair(startedVertex[2], startedVertex[0]), RecursionDeepth);
	}

	///----------------------------------------------------------------------------------

	float deltaTime = 1/60.f;
    sf::Clock clock;

    while (window.isOpen()) { 

		float frameStart = clock.getElapsedTime().asSeconds(); 

		sf::Event event;
		while (window.pollEvent(event)) {

			if (event.type == sf::Event::Closed)
				window.close();

			if (event.type == sf::Event::KeyPressed) {

				if (event.key.code == sf::Keyboard::S) { //screenshot
					surface.setView(v); 
					drawOn(surface, kochCurve, CurveType);
					surface.getTexture().copyToImage().saveToFile("result.jpg");
				}
			}
		}

		if (sf::Keyboard::isKeyPressed(sf::Keyboard::A)) {
			v.zoom(0.9f);
			window.setView(v);
		} if (sf::Keyboard::isKeyPressed(sf::Keyboard::D)) {
			v.zoom(1.1f);
			window.setView(v);
		}

		static constexpr float speed = 100; 
		if (sf::Keyboard::isKeyPressed(sf::Keyboard::Left)) {
			v.move(sf::Vector2f(-speed, 0) * deltaTime);
			window.setView(v);
		} if (sf::Keyboard::isKeyPressed(sf::Keyboard::Right)) {
			v.move(sf::Vector2f(speed, 0) * deltaTime);
			window.setView(v);
		} if (sf::Keyboard::isKeyPressed(sf::Keyboard::Up)) {
			v.move(sf::Vector2f(0, -speed) * deltaTime);
			window.setView(v);
		} if (sf::Keyboard::isKeyPressed(sf::Keyboard::Down)) {
			v.move(sf::Vector2f(0, speed) * deltaTime);
			window.setView(v);
		}

		drawOn(window, kochCurve, CurveType);

		deltaTime = clock.getElapsedTime().asSeconds() - frameStart;
	}
}

Wiem że całość może się wydawać dość złożona, ale to tylko dlatego że są dwie funkcje od generowania fraktala. W wersji wypełnionej kiedy ustawimy stałą CurveType na sf::Triangles i sam obrys dla sf::Lines. Przykłady:

Mówiąc szczerzę to wiem że pytanie się o jakość moich algorytmów generujących kształt było by dość naiwne.

Wersja wypełniona to po prostu mnóstwo trójkątów narysowanych jeden na drugim, generowanie samego obrysu działa podobnie tyle że brane są pod uwagę jedynie wierzchołki wyliczone podczas ostatniej kopii funkcji wywołanej rekursywnie ( i do tego łączymy punkty w inny sposób ).

Dla przykładu dla siedmiu wywołań rekursywnych wypełniony kształt składa się z 49152 punktów, a sam obrys z 98304 punktów. Obrys "waży" więcej z jednego ważnego powodu. Jeden punkt musi być opisany przez kilka zmiennych ( używam sf::Lines, czyli obrys to po prostu wiele odcinków ). Planowałem to zrobić na inne wydajniejsze sposoby, na przykład żeby całość była spójną figurą narysowaną z punktów ustawionych zgodnie ze wskazówkami zegara... jednak nic z tego.

Nawet kiedy próbuję analizować całość na kartce papieru to widzę tylko rekurencję jako jedyny sposób rozwiązania tego.

Czy mimo tych wad całość obecnego kodu jest w miarę w porządku? Czy macie jakiś pomysł na inne rozwiązanie tego problemu?

Bardzo dziękuje za odpowiedzi i pozdrawiam serdecznie :)

komentarz 26 lipca 2019 przez adrian17 Ekspert (344,100 p.)

 wypełniony kształt składa się z 49152 punktów, a sam obrys z 98304 punktów. Obrys "waży" więcej z jednego ważnego powodu. Jeden punkt musi być opisany przez kilka zmiennych ( używam sf::Lines, czyli obrys to po prostu wiele odcinków ). 

Nie zrozumiałem tej części.

komentarz 27 lipca 2019 przez Jakub 0 Pasjonat (23,120 p.)
ale co dokładnie nie zrozumiałeś? Znasz SFML?
1
komentarz 27 lipca 2019 przez adrian17 Ekspert (344,100 p.)

Dobra, przemyślałem i ma sens ;)

Planowałem to zrobić na inne wydajniejsze sposoby, na przykład żeby całość była spójną figurą narysowaną z punktów ustawionych zgodnie ze wskazówkami zegara... jednak nic z tego.

Możesz rekurencyjnie wygenerować zbiór punktów, ale ustawić je w dobrej kolejności i użyć sf::LinesStrip.

komentarz 27 lipca 2019 przez mokrowski Mędrzec (155,460 p.)
edycja 27 lipca 2019 przez mokrowski

@Jakub 0,   zupełnie na marginesie... rekurencja fajna rzecz. Ale ani C ani C++ nie ma tego ujętego w standardzie. Optymalizacja "ogonowa" (tail recursion), to wyłącznie dobra wola producentów kompilatorów. Nie każdy producent ma "dobrą wolę". Pamiętaj o tym.

W 24 linii wybierasz rodzaj rysowanego fraktala a w 164 i 170, wybierasz sposób rysowania. Sugeruję przerobienie na if constexpr. Nie każdy kompilator może się połapać że jedno z rozgałęzień jest martwe. Dostępne od C++17.

W wywołaniach w stylu:

generateFillKochCurve(points, std::make_pair(stretch.first, fb), deepth - 1);

.. możesz się tak nie znęcać nad tą parą. Wystarczy (o ile nie masz antycznego kompilatora < C++17):

generateFillKochCurve(points, {stretch.first, fb}, deepth - 1);

Kompilator sam wie że to para.

(dopisane)

Zauważ że argument std::sin(...) i std::cos(...) w Twojej implementacji jest zawsze stały bo wynosi 60 stopni. W zasadzie więc .... mnożysz przez stałe, więc nie ma sensu ich liczyć :-) (zmartwię Cię... niestety nie ma implementacji constexpr std::sin(...) i std::cos(...) w bibliotece standardowej).

komentarz 27 lipca 2019 przez adrian17 Ekspert (344,100 p.)

Optymalizacja "ogonowa" (tail recursion), to wyłącznie dobra wola producentów kompilatorów. Nie każdy producent ma "dobrą wolę". Pamiętaj o tym.

Ten kod i tak nie używałby tail recursion, więc raczej bez związku ;)

komentarz 27 lipca 2019 przez mokrowski Mędrzec (155,460 p.)
A ze związkiem. To że nawet przerobił by na tail recursion (bo chciałby trzymać się rekurencji jak pijany płotu), nie dało by gwarancji że optymalizacja była by używana.

Zaloguj lub zarejestruj się, aby odpowiedzieć na to pytanie.

Podobne pytania

0 głosów
1 odpowiedź 607 wizyt
pytanie zadane 26 marca 2017 w C i C++ przez szym3ns Użytkownik (860 p.)
0 głosów
4 odpowiedzi 484 wizyt
0 głosów
1 odpowiedź 199 wizyt
pytanie zadane 11 lutego 2016 w C i C++ przez Pixel040 Gaduła (3,020 p.)

92,453 zapytań

141,262 odpowiedzi

319,086 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...