Beschreibung

Source Code

The complete and dirty C++ generating source code:

/* Poincare Half-plane model (C)2007 Claudio Rocchini, the SHQN man */

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <assert.h>
#include <vector>

const double PI = 3.1415926535897932384626433832795;
const double EPS  = 1e-12; const double EPS2 = 1e-4;
const int dimx = 800; const int dimy = 400;
const int OX = dimx/2; const int OY = dimy;

namespace hp {

class point {
public:
	double x,y;
	point(){}
	point( double nx, double ny ) : x(nx),y(ny) {}
};

class line {
protected:
	void at_param( double t, point & q ) const;
	double param( const point & q ) const;
public:
	bool   di;		// direzione: diretta o rovesciata
	double ra;		// raggio: 0 = linea verticale
	double cx;		// centro vertice
	void from_points( const point & p, const point & q );
	void from_point_angle( const point & p, double a );
	void at_dist( const point & p, double d, bool dir, point & q ) const;
	double angle( const point & p ) const;
};

double dist(  const point & p, const point & q );

void line::from_points( const point & p, const point & q ) {
	if( fabs(p.x-q.x)<EPS ) {
		ra = 0; cx = 0.5*(p.x+q.x);
	} else {
		cx = 0.5*(q.x*q.x+q.y*q.y-p.x*p.x-p.y*p.y)/(q.x-p.x);
		ra = sqrt( (p.x-cx)*(p.x-cx)+p.y*p.y );
	}
	double ip = param(p); double iq = param(q);
	di = ip<iq;
}

void line::from_point_angle( const point & p, double a ){
	if( fabs(a-PI/2)<EPS || fabs(a-PI*3/2)<EPS ) { ra = 0; cx = p.x; }
	else {
		double b = a+PI/2;
		double co = cos(b); double si = sin(b);
		ra = fabs(p.y/si); cx = -(p.y*co-p.x*si)/si;
	}
	di = cos(a)>=0;
}

void line::at_param( double t, point & q ) const {
	if(ra==0) { q.x = cx; q.y = t; }
	else { q.x = ra*cos(t) + cx; q.y = ra*sin(t); }
}

double line::param( const point & q ) const {
	if(ra==0) return q.y;
	else return atan2(q.y,q.x-cx);
}

void line::at_dist( const point & p, double d, bool dir, point & q ) const {
	if(ra==0) {
		double tmi,tma,tmm;		
		if(dir!=di) {
			tmi = 0 + EPS; tma = param(p);
			for(;;) {
				tmm = (tmi+tma)/2; at_param(tmm,q);
				double ld = dist(p,q); if(ld>d) tmi = tmm; else tma = tmm;
				if(tma-tmi<EPS) break;
		}	}
		else {
			tmi = param(p); tma = tmi*100;
			for(;;) {
				tmm = (tmi+tma)/2; at_param(tmm,q);
				double ld = dist(p,q); if(ld<d) tmi = tmm; else tma = tmm;
				if(tma-tmi<EPS) break;
	}	}	}
	else {
		double tmi,tma,tmm;	
		if(dir!=di) {
			tmi = 0 + EPS; tma = param(p);
			for(;;) {
				tmm = (tmi+tma)/2; at_param(tmm,q);
				double ld = dist(p,q); if(ld>d) tmi = tmm; else tma = tmm;
				if(tma-tmi<EPS) break;
		}	}
		else {
			tmi = param(p); tma = PI-EPS;
			for(;;) {
				tmm = (tmi+tma)/2; at_param(tmm,q);
				double ld = dist(p,q); if(ld<d) tmi = tmm; else tma = tmm;
				if(tma-tmi<EPS) break;
	}	}	}
}

double line::angle( const point & p ) const {
	double a = 0;
	if(ra==0) a = PI/2;
	else a = atan2(p.y,p.x-cx) - PI/2;
	if(di) a += PI; return a;
}

double dist(  const point & p, const point & q ) {
	line l; l.from_points(p,q);
	if(l.ra!=0) 	{
		double A = l.cx - l.ra;
		double B = l.cx + l.ra;
		double PA = sqrt( (p.x-A)*(p.x-A)+p.y*p.y );
		double PB = sqrt( (p.x-B)*(p.x-B)+p.y*p.y );
		double QA = sqrt( (q.x-A)*(q.x-A)+q.y*q.y );
		double QB = sqrt( (q.x-B)*(q.x-B)+q.y*q.y );
		return fabs(log( (PA/PB) / (QA/QB) ));
	} else {
		double A = l.cx;
		double PA = sqrt( (p.x-A)*(p.x-A)+p.y*p.y );
		double QA = sqrt( (q.x-A)*(q.x-A)+q.y*q.y );
		return fabs(log( (PA/QA) ));
	}
}

void draw_point( FILE * fp, const point & p, double R ) {
	fprintf(fp,"<circle cx=\"%5.1lf\" cy=\"%5.1lf\" r=\"%g\"/>\n",p.x+OX,OY-p.y,R);
}

void draw_line( FILE * fp, const line & l ) {
	if(l.ra==0)
		fprintf(fp,"<line x1=\"%5.1lf\" y1=\"0\" x2=\"%5.1lf\" y2=\"%5.1lf\"/>"
			,OX+l.cx ,OX+l.cx ,double(dimy) );
	else
		fprintf(fp,"<path d=\"M %5.1lf,%5.1lf A %g,%g 0 0,1 %5.1lf,%5.1lf\"/>\n"
			,OX+l.cx-l.ra,double(dimy),l.ra,l.ra,OX+l.cx+l.ra,double(dimy) );
}

void draw_arc( FILE * fp, const line & l, const point & p, const point & q )
{
	if(l.ra==0)
		fprintf(fp,"<line x1=\"%5.1lf\" y1=\"%5.1lf\" x2=\"%5.1lf\" y2=\"%5.1lf\"/>\n"
			,OX+l.cx,OY-p.y,OX+l.cx,OY-q.y);
	else
		fprintf(fp,"<path d=\"M %5.1lf,%5.1lf A %g,%g 0 0,%d %5.1lf,%5.1lf\"/>\n"
			,OX+p.x,OY-p.y,l.ra,l.ra,p.x<q.x ? 1 : 0,OX+q.x,OY-q.y);
}

double e_dist( const point & p1, const point & p2 ){
	const double dx = p1.x - p2.x; const double dy = p1.y - p2.y;
	return sqrt(dx*dx+dy*dy);
}

}	// End namespace hp

class edge
{
public:
	int i[2];
	edge(){}
	edge( int i0, int i1 ) { i[0]=i0; i[1]=i1; }
	inline operator== ( const edge & e ) const {
		return (i[0]==e.i[0] && i[1]==e.i[1]) ||
			   (i[0]==e.i[1] && i[1]==e.i[0]) ;
	}
};

int main(){
	const double R = 2;
	const int L = 7;
	const double qangle = 2*PI/3;	// Angolo di tassellazione

	std::vector<hp::point> nodes;
	std::vector< edge >    edges; std::vector< edge >    edges2;
	int i;
		// Ricerca lato
	hp::point q[L];
	hp::point c(dimx/2-502.5,dimy/2);
	const double sangle = 0;
	
	double lato = 0; double milato = 1e-4; double malato = 5; const int D = 2;
	for(;;) {
		lato = (milato+malato)/2;
		q[0] = c;
		hp::line k; k.from_point_angle(c,sangle);
		k.at_dist(c,lato,false,q[1]);
		for(i=1;i<L-1;++i) {
			hp::line l; l.from_points(q[i-1],q[i]);
			double a0 = l.angle(q[i]); a0 -= PI-qangle;
			hp::line l1; l1.from_point_angle(q[i],a0);
			l1.at_dist(q[i],lato,false,q[i+1]);
		}
		double d = hp::dist(q[0],q[L-1]);
		if(d<lato) milato = lato; else malato = lato;
		if( malato-milato<EPS) {
			lato = (milato+malato)/2; break;
		}
	}
	std::vector< int > openedges;	
	q[0] = c;
	hp::line k; k.from_point_angle(c,sangle);
	k.at_dist(c,lato,false,q[1]);
	for(i=1;i<L-1;++i) {
		hp::line l; l.from_points(q[i-1],q[i]);
		double a0 = l.angle(q[i]); a0 -= PI-qangle;
		hp::line l1; l1.from_point_angle(q[i],a0);
		l1.at_dist(q[i],lato,false,q[i+1]);
	}
	for(i=0;i<L;++i) {
		nodes.push_back(q[i]);
		edges.push_back( edge(i,(i+1)%L) );
		openedges.push_back( edges.size()-1 );
	}
	for(i=0;i<L;++i)
		edges2.push_back( edge(i,(i+D)%L) );
		// Ciclo di espansione
	int nn = 0; int maxn = 3000;
	while( !openedges.empty() ) {
		int e = openedges.front(); //openedges.erase( openedges.begin() );
		int ip1 = edges[e].i[0]; int ip0 = edges[e].i[1];
		hp::point p0 = nodes[ ip0 ]; hp::point p1 = nodes[ ip1 ];
		int eee[L];
		for(i=0;i<L;++i) {
			eee[i] = ip0;
			hp::line l; l.from_points(p0,p1);
			double a0 = l.angle(p1); a0 -= PI-qangle;
			hp::line l1;  l1.from_point_angle(p1,a0);
			hp::point p2; l1.at_dist(p1,lato,false,p2);

			int ip2 = -1;
			for(ip2=0;ip2<nodes.size();++ip2)
				if( hp::e_dist(nodes[ip2],p2)<EPS2 )
					break;
			if(ip2==nodes.size()) nodes.push_back(p2);

			edge e(ip1,ip2);
			std::vector< int >::iterator jj;
			for(jj=openedges.begin();jj!=openedges.end();++jj)
				if(edges[*jj]==e)
					break;
			if(jj==openedges.end()) {
				openedges.push_back(edges.size());
				edges.push_back(e);
			}
			else openedges.erase(jj);
			p0 = p1; ip0 = ip1;
			p1 = p2; ip1 = ip2;
		}
		for(i=0;i<L;++i)
			edges2.push_back( edge(eee[i],eee[(i+D)%L]) );
		if(++nn>=maxn) break;
	}

	FILE * fp = fopen("hp.svg","w");
	fprintf(fp,
		"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n"
		"<!-- Created with svg-rocco-library v1.0 -->\n"
		"<svg\n"
		"xmlns:svg=\"http://www.w3.org/2000/svg\"\n"
		"xmlns=\"http://www.w3.org/2000/svg\"\n"
		"xmlns:xlink=\"http://www.w3.org/1999/xlink\"\n"
		"version=\"1.0\"\n"
		"width=\"%d\"\n"
		"height=\"%d\"\n"
		"id=\"rocco\"\n"
		">\n"
		,dimx,dimy
	);

	const double MINDIST = 1; const double MINDIST2 = 4;
	fprintf(fp,"<g id=\"arc_s\" style=\"fill:none;stroke:#0000E0;stroke-width:1;stroke-opacity:0.95;stroke-dasharray:none\">\n");
	std::vector< edge >::iterator jj;
	for(jj=edges2.begin();jj!=edges2.end();++jj){
		if( (nodes[ jj->i[0]].x<-dimx/2 || nodes[ jj->i[0]].x>dimx/2 ||
			 nodes[ jj->i[0]].y<0       || nodes[ jj->i[0]].y>dimy   ) &&
			(nodes[ jj->i[1]].x<-dimx/2 || nodes[ jj->i[1]].x>dimx/2 ||
			 nodes[ jj->i[1]].y<0       || nodes[ jj->i[1]].y>dimy   ) )
			continue;
		double dd = hp::e_dist( nodes[ jj->i[0]], nodes[ jj->i[1]] );
		if(dd<MINDIST2) continue;
		hp::line l; l.from_points( nodes[ jj->i[0]], nodes[ jj->i[1]] );
		hp::draw_arc(fp,l,nodes[ jj->i[0]], nodes[ jj->i[1]] );
	}
	fprintf(fp,"</g>\n");
	fprintf(fp,"<g id=\"arc_s\" style=\"fill:none;stroke:#000000;stroke-width:2;stroke-opacity:0.95;stroke-dasharray:none\">\n");
	for(jj=edges.begin();jj!=edges.end();++jj){
		if( (nodes[ jj->i[0]].x<-dimx/2 || nodes[ jj->i[0]].x>dimx/2 ||
			 nodes[ jj->i[0]].y<0       || nodes[ jj->i[0]].y>dimy   ) &&
			(nodes[ jj->i[1]].x<-dimx/2 || nodes[ jj->i[1]].x>dimx/2 ||
			 nodes[ jj->i[1]].y<0       || nodes[ jj->i[1]].y>dimy   ) )
			continue;
		double dd = hp::e_dist( nodes[ jj->i[0]], nodes[ jj->i[1]] );
		if(dd<MINDIST) continue;
		hp::line l;l.from_points( nodes[ jj->i[0]], nodes[ jj->i[1]] );
		hp::draw_arc(fp,l,nodes[ jj->i[0]], nodes[ jj->i[1]] );
	}
	fprintf(fp,"</g>\n");
	fprintf(fp,"</svg>\n");
	fclose(fp);
	return 0;
}

Lizenz

Ich, der Urheberrechtsinhaber dieses Werkes, veröffentliche es hiermit unter der folgenden Lizenz:

Es ist erlaubt, die Datei unter den Bedingungen der GNU-Lizenz für freie Dokumentation, Version 1.2 oder einer späteren Version, veröffentlicht von der Free Software Foundation, zu kopieren, zu verbreiten und/oder zu modifizieren; es gibt keine unveränderlichen Abschnitte, keinen vorderen und keinen hinteren Umschlagtext. Der vollständige Text der Lizenz ist im Kapitel GNU-Lizenz für freie Dokumentation verfügbar.http://www.gnu.org/copyleft/fdl.htmlGFDLGNU Free Documentation Licensetruetrue

Diese Datei ist unter der Creative-Commons-Lizenz „Namensnennung 3.0 nicht portiert“ lizenziert.

Dieses Werk darf von dir

• verbreitet werden – vervielfältigt, verbreitet und öffentlich zugänglich gemacht werden
• neu zusammengestellt werden – abgewandelt und bearbeitet werden

Zu den folgenden Bedingungen:

• Namensnennung – Du musst angemessene Urheber- und Rechteangaben machen, einen Link zur Lizenz beifügen und angeben, ob Änderungen vorgenommen wurden. Diese Angaben dürfen in jeder angemessenen Art und Weise gemacht werden, allerdings nicht so, dass der Eindruck entsteht, der Lizenzgeber unterstütze gerade dich oder deine Nutzung besonders.

https://creativecommons.org/licenses/by/3.0CC BY 3.0 Creative Commons Attribution 3.0 truetrue

Du darfst es unter einer der obigen Lizenzen deiner Wahl verwenden.