Dettagli

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;
}

Licenza

Io, detentore del copyright su quest'opera, dichiaro di pubblicarla con le seguenti licenze:

È permesso copiare, distribuire e/o modificare questo documento in base ai termini della GNU Free Documentation License, Versione 1.2 o successive pubblicata dalla Free Software Foundation; senza alcuna sezione non modificabile, senza testo di copertina e senza testo di quarta di copertina. Una copia della licenza è inclusa nella sezione intitolata Testo della GNU Free Documentation License.http://www.gnu.org/copyleft/fdl.htmlGFDLGNU Free Documentation Licensetruetrue

Questo file è disponibile in base alla licenza Creative Commons Attribuzione 3.0 Unported

Tu sei libero:

• di condividere – di copiare, distribuire e trasmettere quest'opera
• di modificare – di adattare l'opera

Alle seguenti condizioni:

• attribuzione – Devi fornire i crediti appropriati, un collegamento alla licenza e indicare se sono state apportate modifiche. Puoi farlo in qualsiasi modo ragionevole, ma non in alcun modo che suggerisca che il licenziante approvi te o il tuo uso.

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

Puoi scegliere la licenza che preferisci.