34 #define _CRT_SECURE_NO_DEPRECATE
37 #if defined(_VERBOSE_) || (_DEBUG_)
50 #include "linkedlist.hpp"
59 #define M_PI 3.14159265358979323846
80 , fixedRotation( false )
85 assert( finite( lx ) && finite( ly ) );
87 uid =
new char[strlen( geom_id ) +1];
88 strcpy(
uid, geom_id );
99 : f( feat ), nbHoles( 0 ), holes( NULL )
102 the_geom =
const_cast<GEOSGeometry*
>( geom );
108 for (
int i = 0; i <
nbHoles; i++ )
121 for (
int i = 0; i <
nbHoles; i++ )
142 const GEOSCoordSequence *coordSeq;
145 type = GEOSGeomTypeId_r( geosctxt, geom );
147 if (
type == GEOS_POLYGON )
149 if ( GEOSGetNumInteriorRings_r( geosctxt, geom ) > 0 )
152 nbHoles = GEOSGetNumInteriorRings_r( geosctxt, geom );
155 for ( i = 0; i <
nbHoles; i++ )
160 const GEOSGeometry* interior = GEOSGetInteriorRingN_r( geosctxt, geom, i );
161 holes[i]->
nbPoints = GEOSGetNumCoordinates_r( geosctxt, interior );
163 holes[i]->y =
new double[holes[i]->nbPoints];
165 holes[i]->xmin = holes[i]->ymin = DBL_MAX;
166 holes[i]->xmax = holes[i]->ymax = -DBL_MAX;
168 coordSeq = GEOSGeom_getCoordSeq_r( geosctxt, interior );
170 for ( j = 0; j < holes[i]->nbPoints; j++ )
172 GEOSCoordSeq_getX_r( geosctxt, coordSeq, j, &holes[i]->
x[j] );
173 GEOSCoordSeq_getY_r( geosctxt, coordSeq, j, &holes[i]->
y[j] );
175 holes[i]->xmax = holes[i]->x[j] > holes[i]->xmax ? holes[i]->x[j] : holes[i]->xmax;
176 holes[i]->xmin = holes[i]->x[j] < holes[i]->xmin ? holes[i]->x[j] : holes[i]->xmin;
178 holes[i]->ymax = holes[i]->y[j] > holes[i]->ymax ? holes[i]->y[j] : holes[i]->ymax;
179 holes[i]->ymin = holes[i]->y[j] < holes[i]->ymin ? holes[i]->y[j] : holes[i]->ymin;
187 geom = GEOSGetExteriorRing_r( geosctxt, geom );
196 nbPoints = GEOSGetNumCoordinates_r( geosctxt, geom );
197 coordSeq = GEOSGeom_getCoordSeq_r( geosctxt, geom );
209 GEOSCoordSeq_getX_r( geosctxt, coordSeq, i, &
x[i] );
210 GEOSCoordSeq_getY_r( geosctxt, coordSeq, i, &
y[i] );
224 bool *ok =
new bool[new_nbPoints];
230 j = ( i + 1 ) % nbPoints;
233 if (
vabs(
x[i] -
x[j] ) < 0.0000001 &&
vabs(
y[i] -
y[j] ) < 0.0000001 )
240 if ( new_nbPoints < nbPoints )
242 double *new_x =
new double[new_nbPoints];
243 double *new_y =
new double[new_nbPoints];
244 for ( i = 0, j = 0; i <
nbPoints; i++ )
258 nbPoints = new_nbPoints;
281 Q_UNUSED( delta_width );
295 double cost = 0.0001;
298 xdiff -= label_x / 2.0;
299 ydiff -= label_y / 2.0;
305 double xd = xdiff * cos( angle ) - ydiff * sin( angle );
306 double yd = xdiff * sin( angle ) + ydiff * cos( angle );
317 double amin[2], amax[2];
319 labelW = amax[0] - amin[0];
320 labelH = amax[1] - amin[1];
352 ( *lPos )[0] =
new LabelPosition(
id, lx, ly, label_x, label_y, angle, cost,
this );
360 std::cout <<
"SetPosition (point) : " << layer->name <<
"/" << uid << std::endl;
373 dpi, scale, delta_width );
378 dpi, scale, delta_width );
389 double beta = 2 *
M_PI / nbp;
398 layer->pal->map_unit,
399 dpi, scale, delta_width );
405 double a90 =
M_PI / 2;
407 double a270 = a180 + a90;
408 double a360 = 2 *
M_PI;
411 double gamma1, gamma2;
415 gamma1 = atan2( yrm / 2, distlabel + xrm / 2 );
416 gamma2 = atan2( xrm / 2, distlabel + yrm / 2 );
420 gamma1 = gamma2 = a90 / 3.0;
424 if ( gamma1 > a90 / 3.0 )
427 if ( gamma2 > a90 / 3.0 )
431 if ( gamma1 == 0 || gamma2 == 0 )
433 std::cout <<
"Oups... label size error..." << std::endl;
438 for ( i = 0, alpha =
M_PI / 4; i < nbp; i++, alpha += beta )
446 if ( alpha < gamma1 || alpha > a360 - gamma1 )
449 double iota = ( alpha + gamma1 );
450 if ( iota > a360 - gamma1 )
454 ly += -yrm + yrm * iota / ( 2 * gamma1 );
456 else if ( alpha < a90 - gamma2 )
458 lx += distlabel * cos( alpha );
459 ly += distlabel * sin( alpha );
461 else if ( alpha < a90 + gamma2 )
464 lx += -xrm * ( alpha - a90 + gamma2 ) / ( 2 * gamma2 );
467 else if ( alpha < a180 - gamma1 )
469 lx += distlabel * cos( alpha ) - xrm;
470 ly += distlabel * sin( alpha );
472 else if ( alpha < a180 + gamma1 )
474 lx += -distlabel - xrm;
476 ly += - ( alpha - a180 + gamma1 ) * yrm / ( 2 * gamma1 );
478 else if ( alpha < a270 - gamma2 )
480 lx += distlabel * cos( alpha ) - xrm;
481 ly += distlabel * sin( alpha ) - yrm;
483 else if ( alpha < a270 + gamma2 )
485 ly += -distlabel - yrm;
487 lx += -xrm + ( alpha - a270 + gamma2 ) * xrm / ( 2 * gamma2 );
489 else if ( alpha < a360 )
491 lx += distlabel * cos( alpha );
492 ly += distlabel * sin( alpha ) - yrm;
500 cost = 0.0001 + 0.0020 * double( icost ) / double( nbp - 1 );
502 ( *lPos )[i] =
new LabelPosition( i, lx, ly, xrm, yrm, angle, cost,
this );
511 else if ( icost > nbp )
526 std::cout <<
"SetPosition (line) : " << layer->name <<
"/" << uid << std::endl;
536 dpi, scale, delta_width );
541 dpi, scale, delta_width );
547 layer->pal->map_unit,
548 dpi, scale, delta_width );
556 double bx, by, ex, ey;
569 LinkedList<LabelPosition*> *positions =
new LinkedList<LabelPosition*> (
ptrLPosCompare );
577 std::cout <<
"New line of " << line->
nbPoints <<
" points with label " << xrm <<
"x" << yrm << std::endl;
584 d =
new double[nbPoints-1];
588 for ( i = 0; i < line->
nbPoints - 1; i++ )
593 ad[i] = ad[i-1] + d[i-1];
595 d[i] =
dist_euc2d( x[i], y[i], x[i+1], y[i+1] );
602 nbls = ( int )( ll / xrm );
605 std::cout <<
"line length :" << ll << std::endl;
606 std::cout <<
"nblp :" << nbls << std::endl;
617 dist =
min( yrm, xrm );
621 l = - ( xrm - ll ) / 2.0;
631 std::cout << l <<
" / " << ll - xrm << std::endl;
633 while ( l < ll - xrm )
636 line->
getPoint( d, ad, l, &bx, &by );
638 line->
getPoint( d, ad, l + xrm, &ex, &ey );
642 birdfly = sqrt(( x[nbPoints-1] - x[0] ) * ( x[nbPoints-1] - x[0] )
643 + ( y[nbPoints-1] - y[0] ) * ( y[nbPoints-1] - y[0] ) );
645 birdfly = sqrt(( ex - bx ) * ( ex - bx ) + ( ey - by ) * ( ey - by ) );
647 cost = birdfly / xrm;
651 cost = ( 1 - cost ) / 100;
654 double costCenter =
vabs( ll / 2 - ( l + xrm / 2 ) ) / ll;
655 cost += costCenter / 1000;
659 std::cout <<
"EPSILON " <<
EPSILON << std::endl;
660 std::cout <<
"b: " << bx <<
";" << by << std::endl;
661 std::cout <<
"e: " << ex <<
";" << ey << std::endl;
665 alpha = atan2( ey - by, ex - bx );
667 beta = alpha +
M_PI / 2;
670 std::cout <<
" Create new label" << std::endl;
675 bool isRightToLeft = ( alpha >
M_PI / 2 || alpha <= -
M_PI / 2 );
683 positions->push_back(
new LabelPosition( i, bx + cos( beta ) *distlabel, by + sin( beta ) *distlabel, xrm, yrm, alpha, cost,
this, isRightToLeft ) );
685 positions->push_back(
new LabelPosition( i, bx - cos( beta ) *( distlabel + yrm ), by - sin( beta ) *( distlabel + yrm ), xrm, yrm, alpha, cost,
this, isRightToLeft ) );
687 positions->push_back(
new LabelPosition( i, bx - yrm*cos( beta ) / 2, by - yrm*sin( beta ) / 2, xrm, yrm, alpha, cost,
this, isRightToLeft ) );
691 positions->push_back(
new LabelPosition( i, bx - xrm / 2, by - yrm / 2, xrm, yrm, 0, cost,
this ) );
712 int nbp = positions->size();
715 while ( positions->size() > 0 )
717 ( *lPos )[i] = positions->pop_front();
730 while ( distance < 0 && index > 1 )
733 distance += path_distances[
index];
736 if ( index <= 1 && distance < 0 )
742 while ( index < path_positions->
nbPoints && distance > path_distances[index] )
744 distance -= path_distances[
index];
747 if ( index >= path_positions->
nbPoints )
753 int initial_index =
index;
754 double initial_distance = distance;
757 double old_x = path_positions->
x[index-1];
758 double old_y = path_positions->
y[index-1];
760 double new_x = path_positions->
x[
index];
761 double new_y = path_positions->
y[
index];
763 double dx = new_x - old_x;
764 double dy = new_y - old_y;
766 double segment_length = path_distances[
index];
767 if ( segment_length == 0 )
776 double angle = atan2( -dy, dx );
778 bool orientation_forced = ( orientation != 0 );
779 if ( !orientation_forced )
780 orientation = ( angle > 0.55 *
M_PI || angle < -0.45 *
M_PI ? -1 : 1 );
782 int upside_down_char_count = 0;
786 double last_character_angle =
angle;
792 if ( segment_length == 0 )
799 double start_x = old_x + dx * distance / segment_length;
800 double start_y = old_y + dy * distance / segment_length;
806 if ( segment_length - distance >= ci.
width )
809 distance += ci.
width;
810 end_x = old_x + dx * distance / segment_length;
811 end_y = old_y + dy * distance / segment_length;
822 if ( index >= path_positions->
nbPoints )
827 new_x = path_positions->
x[
index];
828 new_y = path_positions->
y[
index];
831 segment_length = path_distances[
index];
836 while ( sqrt( pow( start_x - new_x, 2 ) + pow( start_y - new_y, 2 ) ) < ci.
width );
842 distance = sqrt( pow( old_x - end_x, 2 ) + pow( old_y - end_y, 2 ) );
846 angle = atan2( start_y - end_y, end_x - start_x );
852 double angle_delta = last_character_angle -
angle;
854 while ( angle_delta >
M_PI ) angle_delta -= 2 *
M_PI;
855 while ( angle_delta < -
M_PI ) angle_delta += 2 *
M_PI;
859 && angle_delta < f->labelInfo->max_char_angle_outside*(
M_PI / 180 ) ) )
865 double render_angle =
angle;
867 double render_x = start_x;
868 double render_y = start_y;
874 if ( orientation < 0 )
877 render_x += ci.
width * cos( render_angle );
878 render_y -= ci.
width * sin( render_angle );
879 render_angle +=
M_PI;
895 while ( render_angle >= 2*
M_PI ) render_angle -= 2 *
M_PI;
896 while ( render_angle < 0 ) render_angle += 2 *
M_PI;
898 if ( render_angle >
M_PI / 2 && render_angle < 1.5*
M_PI )
899 upside_down_char_count++;
907 if ( !orientation_forced )
909 orientation = -orientation;
938 double* path_distances =
new double[mapShape->
nbPoints];
939 double total_distance = 0;
940 double old_x = -1.0, old_y = -1.0;
941 for (
int i = 0; i < mapShape->
nbPoints; i++ )
944 path_distances[i] = 0;
946 path_distances[i] = sqrt( pow( old_x - mapShape->
x[i], 2 ) + pow( old_y - mapShape->
y[i], 2 ) );
947 old_x = mapShape->
x[i];
948 old_y = mapShape->
y[i];
950 total_distance += path_distances[i];
953 if ( total_distance == 0 )
955 delete[] path_distances;
959 LinkedList<LabelPosition*> *positions =
new LinkedList<LabelPosition*> (
ptrLPosCompare );
967 for (
int i = 0; i*delta < total_distance; i++ )
974 double angle_diff = 0.0, angle_last = 0.0, diff;
976 double sin_avg = 0, cos_avg = 0;
981 diff = fabs( tmp->
getAlpha() - angle_last );
982 if ( diff > 2*
M_PI ) diff -= 2 *
M_PI;
983 diff =
min( diff, 2 *
M_PI - diff );
994 double cost = angle_diff_avg / 100;
995 if ( cost < 0.0001 ) cost = 0.0001;
998 double labelCenter = ( i * delta ) +
f->
label_x / 2;
999 double costCenter =
vabs( total_distance / 2 - labelCenter ) / total_distance;
1000 cost += costCenter / 1000;
1021 int nbp = positions->size();
1023 for (
int i = 0; i < nbp; i++ )
1025 ( *lPos )[i] = positions->pop_front();
1028 delete[] path_distances;
1052 std::cout <<
"SetPosition (polygon) : " << layer->name <<
"/" << uid << std::endl;
1064 f->
layer->
pal->dpi, scale, delta_width );
1069 f->
layer->
pal->dpi, scale, delta_width );
1074 LinkedList<PointSet*> *shapes_toProcess;
1075 LinkedList<PointSet*> *shapes_final;
1083 shapes_toProcess->push_back( mapShape );
1088 delete shapes_toProcess;
1092 if ( shapes_final->size() > 0 )
1094 LinkedList<LabelPosition*> *positions =
new LinkedList<LabelPosition*> (
ptrLPosCompare );
1104 double diago = sqrt( xrm * xrm / 4.0 + yrm * yrm / 4 );
1110 while ( shapes_final->size() > 0 )
1112 PointSet *shape = shapes_final->pop_front();
1130 for ( bbid = 0; bbid < j; bbid++ )
1136 std::cout <<
"Very Large BBOX (should never occur : bug-report please)" << std::endl;
1137 std::cout <<
" Box size: " << box->
length <<
"/" << box->
width << std::endl;
1138 std::cout <<
" Alpha: " << alpha <<
" " << alpha * 180 /
M_PI << std::endl;
1139 std::cout <<
" Dx;Dy: " << dx <<
" " << dy << std::endl;
1140 std::cout <<
" LabelSizerm: " << xrm <<
" " << yrm << std::endl;
1141 std::cout <<
" LabelSizeUn: " <<
f->
label_x <<
" " <<
f->
label_y << std::endl;
1146 std::cout <<
"New BBox : " << bbid << std::endl;
1147 for ( i = 0; i < 4; i++ )
1149 std::cout << box->
x[i] <<
"\t" << box->
y[i] << std::endl;
1153 bool enoughPlace =
false;
1157 px = ( box->
x[0] + box->
x[2] ) / 2 - xrm;
1158 py = ( box->
y[0] + box->
y[2] ) / 2 - yrm;
1164 for ( rx = px, i = 0; i < 2; rx = rx + 2 * xrm, i++ )
1166 for ( ry = py, j = 0; j < 2; ry = ry + 2 * yrm, j++ )
1171 enoughPlace =
false;
1187 else if ( box->
length > 1.5*xrm && box->
width > 1.5*xrm )
1207 beta = atan2( yrm, xrm ) + alpha;
1213 dlx = cos( beta ) * diago;
1214 dly = sin( beta ) * diago;
1219 px0 = box->
width / 2.0;
1222 px0 -= ceil( px0 / dx ) * dx;
1223 py0 -= ceil( py0 / dy ) * dy;
1225 for ( px = px0; px <= box->
width; px += dx )
1227 for ( py = py0; py <= box->
length; py += dy )
1240 positions->push_back(
new LabelPosition(
id++, rx - dlx, ry - dly, xrm, yrm, alpha, 0.0001,
this ) );
1246 nbp = positions->size();
1254 while ( nbp == 0 && num_try < max_try );
1256 nbp = positions->size();
1259 for ( i = 0; i < nbp; i++ )
1261 ( *lPos )[i] = positions->pop_front();
1264 for ( bbid = 0; bbid < j; bbid++ )
1277 delete shapes_final;
1280 std::cout <<
"NbLabelPosition: " << nbp << std::endl;
1288 std::cout <<
"Geometry id : " <<
f->
uid << std::endl;
1289 std::cout <<
"Type: " <<
type << std::endl;
1293 std::cout <<
x[i] <<
", " <<
y[i] << std::endl;
1294 std::cout <<
"Obstacle: " <<
nbHoles << std::endl;
1295 for ( i = 0; i <
nbHoles; i++ )
1297 std::cout <<
" obs " << i << std::endl;
1300 std::cout <<
holes[i]->
x[j] <<
";" <<
holes[i]->
y[j] << std::endl;
1305 std::cout << std::endl;
1309 double bbox_min[2],
double bbox_max[2],
1310 PointSet *mapShape, RTree<LabelPosition*, double, 2, double> *candidates
1312 , std::ofstream &svgmap
1321 int dpi = layer->pal->getDpi();
1324 bbox[0] = bbox_min[0];
1325 bbox[1] = bbox_min[1];
1326 bbox[2] = bbox_max[0];
1327 bbox[3] = bbox_max[1];
1329 double delta = bbox_max[0] - bbox_min[0];
1348 case GEOS_LINESTRING:
1380 for ( i = 0; i < nbp; i++ )
1382 bool outside =
false;
1384 outside = !( *lPos )[i]->isIntersect( bbox );
1386 outside = !( *lPos )[i]->isInside( bbox );
1390 ( *lPos )[i]->setCost( DBL_MAX );
1394 ( *lPos )[i]->insertIntoIndex( candidates );
1400 for ( i = rnbp; i < nbp; i++ )
1411 int geomType = GEOSGeomTypeId_r( ctxt,
the_geom );
1413 double sizeCost = 0;
1414 if ( geomType == GEOS_LINESTRING )
1417 if ( GEOSLength_r( ctxt,
the_geom, &length ) != 1 )
1419 double bbox_length =
max( bbx[2] - bbx[0], bby[2] - bby[0] );
1420 if ( length >= bbox_length / 4 )
1423 sizeCost = 1 - ( length / ( bbox_length / 4 ) );
1425 else if ( geomType == GEOS_POLYGON )
1428 if ( GEOSArea_r( ctxt,
the_geom, &area ) != 1 )
1430 double bbox_area = ( bbx[2] - bbx[0] ) * ( bby[2] - bby[0] );
1431 if ( area >= bbox_area / 16 )
1434 sizeCost = 1 - ( area / ( bbox_area / 16 ) );
1442 for (
int i = 0; i < nbp; i++ )
1444 lPos[i]->
setCost( lPos[i]->getCost() + sizeCost / 100 );
1456 GEOSGeometry* g1 = GEOSGeom_clone_r( ctxt,
the_geom );
1457 GEOSGeometry* g2 = GEOSGeom_clone_r( ctxt, other->
the_geom );
1458 GEOSGeometry* geoms[2] = { g1, g2 };
1459 GEOSGeometry* g = GEOSGeom_createCollection_r( ctxt, GEOS_MULTILINESTRING, geoms, 2 );
1460 GEOSGeometry* gTmp = GEOSLineMerge_r( ctxt, g );
1461 GEOSGeom_destroy_r( ctxt, g );
1463 if ( GEOSGeomTypeId_r( ctxt, gTmp ) != GEOS_LINESTRING )
1466 GEOSGeom_destroy_r( ctxt, gTmp );
1471 GEOSGeom_destroy_r( ctxt,
the_geom );