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;
330 Q_UNUSED( delta_width );
338 double cost = 0.0001;
341 double xdiff = -labelW / 2.0;
342 double ydiff = -labelH / 2.0;
360 double xd = xdiff * cos( angle ) - ydiff * sin( angle );
361 double yd = xdiff * sin( angle ) + ydiff * cos( angle );
379 double lx = x + xdiff;
380 double ly = y + ydiff;
382 ( *lPos )[0] =
new LabelPosition(
id, lx, ly, labelW, labelH, angle, cost,
this,
false, quadrantFromOffset() );
390 std::cout <<
"SetPosition (point) : " << layer->name <<
"/" << uid << std::endl;
403 dpi, scale, delta_width );
408 dpi, scale, delta_width );
419 double beta = 2 *
M_PI / nbp;
428 layer->pal->map_unit,
429 dpi, scale, delta_width );
435 double a90 =
M_PI / 2;
437 double a270 = a180 + a90;
438 double a360 = 2 *
M_PI;
441 double gamma1, gamma2;
445 gamma1 = atan2( yrm / 2, distlabel + xrm / 2 );
446 gamma2 = atan2( xrm / 2, distlabel + yrm / 2 );
450 gamma1 = gamma2 = a90 / 3.0;
454 if ( gamma1 > a90 / 3.0 )
457 if ( gamma2 > a90 / 3.0 )
461 if ( gamma1 == 0 || gamma2 == 0 )
463 std::cout <<
"Oups... label size error..." << std::endl;
468 for ( i = 0, alpha =
M_PI / 4; i < nbp; i++, alpha += beta )
478 if ( alpha < gamma1 || alpha > a360 - gamma1 )
481 double iota = ( alpha + gamma1 );
482 if ( iota > a360 - gamma1 )
486 ly += -yrm + yrm * iota / ( 2 * gamma1 );
490 else if ( alpha < a90 - gamma2 )
492 lx += distlabel * cos( alpha );
493 ly += distlabel * sin( alpha );
496 else if ( alpha < a90 + gamma2 )
499 lx += -xrm * ( alpha - a90 + gamma2 ) / ( 2 * gamma2 );
503 else if ( alpha < a180 - gamma1 )
505 lx += distlabel * cos( alpha ) - xrm;
506 ly += distlabel * sin( alpha );
509 else if ( alpha < a180 + gamma1 )
511 lx += -distlabel - xrm;
513 ly += - ( alpha - a180 + gamma1 ) * yrm / ( 2 * gamma1 );
516 else if ( alpha < a270 - gamma2 )
518 lx += distlabel * cos( alpha ) - xrm;
519 ly += distlabel * sin( alpha ) - yrm;
522 else if ( alpha < a270 + gamma2 )
524 ly += -distlabel - yrm;
526 lx += -xrm + ( alpha - a270 + gamma2 ) * xrm / ( 2 * gamma2 );
529 else if ( alpha < a360 )
531 lx += distlabel * cos( alpha );
532 ly += distlabel * sin( alpha ) - yrm;
541 cost = 0.0001 + 0.0020 * double( icost ) / double( nbp - 1 );
543 ( *lPos )[i] =
new LabelPosition( i, lx, ly, xrm, yrm, angle, cost,
this,
false, quadrant );
552 else if ( icost > nbp )
567 std::cout <<
"SetPosition (line) : " << layer->name <<
"/" << uid << std::endl;
577 dpi, scale, delta_width );
582 dpi, scale, delta_width );
588 layer->pal->map_unit,
589 dpi, scale, delta_width );
597 double bx, by, ex, ey;
618 std::cout <<
"New line of " << line->
nbPoints <<
" points with label " << xrm <<
"x" << yrm << std::endl;
625 d =
new double[nbPoints-1];
629 for ( i = 0; i < line->
nbPoints - 1; i++ )
634 ad[i] = ad[i-1] + d[i-1];
636 d[i] =
dist_euc2d( x[i], y[i], x[i+1], y[i+1] );
643 nbls = ( int )( ll / xrm );
646 std::cout <<
"line length :" << ll << std::endl;
647 std::cout <<
"nblp :" << nbls << std::endl;
658 dist =
min( yrm, xrm );
662 l = - ( xrm - ll ) / 2.0;
672 std::cout << l <<
" / " << ll - xrm << std::endl;
674 while ( l < ll - xrm )
677 line->
getPoint( d, ad, l, &bx, &by );
679 line->
getPoint( d, ad, l + xrm, &ex, &ey );
683 birdfly = sqrt(( x[nbPoints-1] - x[0] ) * ( x[nbPoints-1] - x[0] )
684 + ( y[nbPoints-1] - y[0] ) * ( y[nbPoints-1] - y[0] ) );
686 birdfly = sqrt(( ex - bx ) * ( ex - bx ) + ( ey - by ) * ( ey - by ) );
688 cost = birdfly / xrm;
692 cost = ( 1 - cost ) / 100;
695 double costCenter =
vabs( ll / 2 - ( l + xrm / 2 ) ) / ll;
696 cost += costCenter / 1000;
700 std::cout <<
"EPSILON " <<
EPSILON << std::endl;
701 std::cout <<
"b: " << bx <<
";" << by << std::endl;
702 std::cout <<
"e: " << ex <<
";" << ey << std::endl;
706 alpha = atan2( ey - by, ex - bx );
708 beta = alpha +
M_PI / 2;
711 std::cout <<
" Create new label" << std::endl;
716 bool isRightToLeft = ( alpha >
M_PI / 2 || alpha <= -
M_PI / 2 );
724 positions->push_back(
new LabelPosition( i, bx + cos( beta ) *distlabel, by + sin( beta ) *distlabel, xrm, yrm, alpha, cost,
this, isRightToLeft ) );
726 positions->push_back(
new LabelPosition( i, bx - cos( beta ) *( distlabel + yrm ), by - sin( beta ) *( distlabel + yrm ), xrm, yrm, alpha, cost,
this, isRightToLeft ) );
728 positions->push_back(
new LabelPosition( i, bx - yrm*cos( beta ) / 2, by - yrm*sin( beta ) / 2, xrm, yrm, alpha, cost,
this, isRightToLeft ) );
732 positions->push_back(
new LabelPosition( i, bx - xrm / 2, by - yrm / 2, xrm, yrm, 0, cost,
this ) );
753 int nbp = positions->size();
756 while ( positions->size() > 0 )
758 ( *lPos )[i] = positions->pop_front();
771 while ( distance < 0 && index > 1 )
774 distance += path_distances[
index];
777 if ( index <= 1 && distance < 0 )
783 while ( index < path_positions->
nbPoints && distance > path_distances[index] )
785 distance -= path_distances[
index];
788 if ( index >= path_positions->
nbPoints )
794 int initial_index =
index;
795 double initial_distance = distance;
798 double old_x = path_positions->
x[index-1];
799 double old_y = path_positions->
y[index-1];
801 double new_x = path_positions->
x[
index];
802 double new_y = path_positions->
y[
index];
804 double dx = new_x - old_x;
805 double dy = new_y - old_y;
807 double segment_length = path_distances[
index];
808 if ( segment_length == 0 )
817 double angle = atan2( -dy, dx );
819 bool orientation_forced = ( orientation != 0 );
820 if ( !orientation_forced )
821 orientation = ( angle > 0.55 *
M_PI || angle < -0.45 *
M_PI ? -1 : 1 );
823 int upside_down_char_count = 0;
827 double last_character_angle =
angle;
833 if ( segment_length == 0 )
840 double start_x = old_x + dx * distance / segment_length;
841 double start_y = old_y + dy * distance / segment_length;
847 if ( segment_length - distance >= ci.
width )
850 distance += ci.
width;
851 end_x = old_x + dx * distance / segment_length;
852 end_y = old_y + dy * distance / segment_length;
863 if ( index >= path_positions->
nbPoints )
868 new_x = path_positions->
x[
index];
869 new_y = path_positions->
y[
index];
872 segment_length = path_distances[
index];
877 while ( sqrt( pow( start_x - new_x, 2 ) + pow( start_y - new_y, 2 ) ) < ci.
width );
883 distance = sqrt( pow( old_x - end_x, 2 ) + pow( old_y - end_y, 2 ) );
887 angle = atan2( start_y - end_y, end_x - start_x );
893 double angle_delta = last_character_angle -
angle;
895 while ( angle_delta >
M_PI ) angle_delta -= 2 *
M_PI;
896 while ( angle_delta < -
M_PI ) angle_delta += 2 *
M_PI;
900 && angle_delta < f->labelInfo->max_char_angle_outside*(
M_PI / 180 ) ) )
906 double render_angle =
angle;
908 double render_x = start_x;
909 double render_y = start_y;
915 if ( orientation < 0 )
918 render_x += ci.
width * cos( render_angle );
919 render_y -= ci.
width * sin( render_angle );
920 render_angle +=
M_PI;
936 while ( render_angle >= 2*
M_PI ) render_angle -= 2 *
M_PI;
937 while ( render_angle < 0 ) render_angle += 2 *
M_PI;
939 if ( render_angle >
M_PI / 2 && render_angle < 1.5*
M_PI )
940 upside_down_char_count++;
948 if ( !orientation_forced )
950 orientation = -orientation;
979 double* path_distances =
new double[mapShape->
nbPoints];
980 double total_distance = 0;
981 double old_x = -1.0, old_y = -1.0;
982 for (
int i = 0; i < mapShape->
nbPoints; i++ )
985 path_distances[i] = 0;
987 path_distances[i] = sqrt( pow( old_x - mapShape->
x[i], 2 ) + pow( old_y - mapShape->
y[i], 2 ) );
988 old_x = mapShape->
x[i];
989 old_y = mapShape->
y[i];
991 total_distance += path_distances[i];
994 if ( total_distance == 0 )
996 delete[] path_distances;
1008 for (
int i = 0; i*delta < total_distance; i++ )
1015 double angle_diff = 0.0, angle_last = 0.0, diff;
1017 double sin_avg = 0, cos_avg = 0;
1022 diff = fabs( tmp->
getAlpha() - angle_last );
1023 if ( diff > 2*
M_PI ) diff -= 2 *
M_PI;
1024 diff =
min( diff, 2 *
M_PI - diff );
1035 double cost = angle_diff_avg / 100;
1036 if ( cost < 0.0001 ) cost = 0.0001;
1039 double labelCenter = ( i * delta ) +
f->
label_x / 2;
1040 double costCenter =
vabs( total_distance / 2 - labelCenter ) / total_distance;
1041 cost += costCenter / 1000;
1062 int nbp = positions->size();
1064 for (
int i = 0; i < nbp; i++ )
1066 ( *lPos )[i] = positions->pop_front();
1069 delete[] path_distances;
1093 std::cout <<
"SetPosition (polygon) : " << layer->name <<
"/" << uid << std::endl;
1105 f->
layer->
pal->dpi, scale, delta_width );
1110 f->
layer->
pal->dpi, scale, delta_width );
1124 shapes_toProcess->push_back( mapShape );
1129 delete shapes_toProcess;
1133 if ( shapes_final->size() > 0 )
1145 double diago = sqrt( xrm * xrm / 4.0 + yrm * yrm / 4 );
1151 while ( shapes_final->size() > 0 )
1153 PointSet *shape = shapes_final->pop_front();
1171 for ( bbid = 0; bbid < j; bbid++ )
1177 std::cout <<
"Very Large BBOX (should never occur : bug-report please)" << std::endl;
1178 std::cout <<
" Box size: " << box->
length <<
"/" << box->
width << std::endl;
1179 std::cout <<
" Alpha: " << alpha <<
" " << alpha * 180 /
M_PI << std::endl;
1180 std::cout <<
" Dx;Dy: " << dx <<
" " << dy << std::endl;
1181 std::cout <<
" LabelSizerm: " << xrm <<
" " << yrm << std::endl;
1182 std::cout <<
" LabelSizeUn: " <<
f->
label_x <<
" " <<
f->
label_y << std::endl;
1187 std::cout <<
"New BBox : " << bbid << std::endl;
1188 for ( i = 0; i < 4; i++ )
1190 std::cout << box->
x[i] <<
"\t" << box->
y[i] << std::endl;
1194 bool enoughPlace =
false;
1198 px = ( box->
x[0] + box->
x[2] ) / 2 - xrm;
1199 py = ( box->
y[0] + box->
y[2] ) / 2 - yrm;
1205 for ( rx = px, i = 0; i < 2; rx = rx + 2 * xrm, i++ )
1207 for ( ry = py, j = 0; j < 2; ry = ry + 2 * yrm, j++ )
1212 enoughPlace =
false;
1228 else if ( box->
length > 1.5*xrm && box->
width > 1.5*xrm )
1248 beta = atan2( yrm, xrm ) + alpha;
1254 dlx = cos( beta ) * diago;
1255 dly = sin( beta ) * diago;
1260 px0 = box->
width / 2.0;
1263 px0 -= ceil( px0 / dx ) * dx;
1264 py0 -= ceil( py0 / dy ) * dy;
1266 for ( px = px0; px <= box->
width; px += dx )
1268 for ( py = py0; py <= box->
length; py += dy )
1281 positions->push_back(
new LabelPosition(
id++, rx - dlx, ry - dly, xrm, yrm, alpha, 0.0001,
this ) );
1287 nbp = positions->size();
1295 while ( nbp == 0 && num_try < max_try );
1297 nbp = positions->size();
1300 for ( i = 0; i < nbp; i++ )
1302 ( *lPos )[i] = positions->pop_front();
1305 for ( bbid = 0; bbid < j; bbid++ )
1318 delete shapes_final;
1321 std::cout <<
"NbLabelPosition: " << nbp << std::endl;
1329 std::cout <<
"Geometry id : " <<
f->
uid << std::endl;
1330 std::cout <<
"Type: " <<
type << std::endl;
1334 std::cout <<
x[i] <<
", " <<
y[i] << std::endl;
1335 std::cout <<
"Obstacle: " <<
nbHoles << std::endl;
1336 for ( i = 0; i <
nbHoles; i++ )
1338 std::cout <<
" obs " << i << std::endl;
1341 std::cout <<
holes[i]->
x[j] <<
";" <<
holes[i]->
y[j] << std::endl;
1346 std::cout << std::endl;
1350 double bbox_min[2],
double bbox_max[2],
1353 , std::ofstream &svgmap
1362 int dpi = layer->pal->getDpi();
1365 bbox[0] = bbox_min[0];
1366 bbox[1] = bbox_min[1];
1367 bbox[2] = bbox_max[0];
1368 bbox[3] = bbox_max[1];
1370 double delta = bbox_max[0] - bbox_min[0];
1389 case GEOS_LINESTRING:
1421 for ( i = 0; i < nbp; i++ )
1423 bool outside =
false;
1425 outside = !( *lPos )[i]->isIntersect( bbox );
1427 outside = !( *lPos )[i]->isInside( bbox );
1431 ( *lPos )[i]->setCost( DBL_MAX );
1435 ( *lPos )[i]->insertIntoIndex( candidates );
1441 for ( i = rnbp; i < nbp; i++ )
1452 int geomType = GEOSGeomTypeId_r( ctxt,
the_geom );
1454 double sizeCost = 0;
1455 if ( geomType == GEOS_LINESTRING )
1458 if ( GEOSLength_r( ctxt,
the_geom, &length ) != 1 )
1460 double bbox_length =
max( bbx[2] - bbx[0], bby[2] - bby[0] );
1461 if ( length >= bbox_length / 4 )
1464 sizeCost = 1 - ( length / ( bbox_length / 4 ) );
1466 else if ( geomType == GEOS_POLYGON )
1469 if ( GEOSArea_r( ctxt,
the_geom, &area ) != 1 )
1471 double bbox_area = ( bbx[2] - bbx[0] ) * ( bby[2] - bby[0] );
1472 if ( area >= bbox_area / 16 )
1475 sizeCost = 1 - ( area / ( bbox_area / 16 ) );
1483 for (
int i = 0; i < nbp; i++ )
1485 lPos[i]->
setCost( lPos[i]->getCost() + sizeCost / 100 );
1497 GEOSGeometry* g1 = GEOSGeom_clone_r( ctxt,
the_geom );
1498 GEOSGeometry* g2 = GEOSGeom_clone_r( ctxt, other->
the_geom );
1499 GEOSGeometry* geoms[2] = { g1, g2 };
1500 GEOSGeometry* g = GEOSGeom_createCollection_r( ctxt, GEOS_MULTILINESTRING, geoms, 2 );
1501 GEOSGeometry* gTmp = GEOSLineMerge_r( ctxt, g );
1502 GEOSGeom_destroy_r( ctxt, g );
1504 if ( GEOSGeomTypeId_r( ctxt, gTmp ) != GEOS_LINESTRING )
1507 GEOSGeom_destroy_r( ctxt, gTmp );
1512 GEOSGeom_destroy_r( ctxt,
the_geom );
Arrangement arrangement
optional flags used for some placement methods
void getCentroid(double &px, double &py, bool forceInside=false)
int reorderPolygon(int nbPoints, double *x, double *y)
double max_char_angle_outside
static void splitPolygons(LinkedList< PointSet * > *shapes_toProcess, LinkedList< PointSet * > *shapes_final, double xrm, double yrm, char *uid)
void setCost(double newCost)
Modify candidate's cost.
A layer of spacial entites.
bool ptrPSetCompare(PointSet *a, PointSet *b)
void offsetPosition(double xOffset, double yOffset)
shift the label by specified offset
friend class LabelPosition
static LabelPosition * _createCurvedCandidate(LabelPosition *lp, double angle, double dist)
static bool costGrow(void *l, void *r)
CHullBox * compute_chull_bbox()
void removeDuplicatePoints()
find duplicate (or nearly duplicate points) and remove them.
Layer * getLayer()
return the layer that feature belongs to
int setPositionOverPoint(double x, double y, double scale, LabelPosition ***lPos, double delta_width, double angle)
generate one candidate over specified point
Feature(Layer *l, const char *geom_id, PalGeometry *userG, double lx, double ly)
void addSizePenalty(int nbp, LabelPosition **lPos, double bbx[4], double bby[4])
bool getCentroidInside() const
arranges candidates around a point (centroid for polygon)
bool isPointInPolygon(int npol, double *xp, double *yp, double x, double y)
CharacterInfo * char_info
int setPositionForLine(double scale, LabelPosition ***lPos, PointSet *mapShape, double delta_width)
generate candidates for line feature Generate candidates for line features
double unit_convert(double x, Units from, Units to, int dpi, double scale, double delta_canvas_width)
FeaturePart(Feature *feat, const GEOSGeometry *geom)
create a new generic feature
virtual ~FeaturePart()
Delete the feature.
bool mergeWithFeaturePart(FeaturePart *other)
merge other (connected) part with this one and save the result in this part (other is unchanged)...
double getAlpha() const
get alpha
int setPosition(double scale, LabelPosition ***lPos, double bbox_min[2], double bbox_max[2], PointSet *mapShape, RTree< LabelPosition *, double, 2, double > *candidates)
generic method to generate candidates This method will call either setPositionFromPoint(), setPositionFromLine or setPositionFromPolygon
void print()
Print feature information Print feature unique id, geometry type, points, and holes on screen...
int setPositionForLineCurved(LabelPosition ***lPos, PointSet *mapShape)
Generate curved candidates for line features.
double dist_euc2d(double x1, double y1, double x2, double y2)
bool isConnected(FeaturePart *p2)
check whether this part is connected with some other part
arranges candidates over a point (centroid for polygon)
Only for lines, labels along the line.
LabelPosition * getNextPart() const
GEOSContextHandle_t geosContext()
Get GEOS context handle to be used in all GEOS library calls with reentrant API.
const char * getUID()
get the unique id of the feature
Main class to handle feature.
int setPositionForPoint(double x, double y, double scale, LabelPosition ***lPos, double delta_width, double angle)
generate candidates for point feature Generate candidates for point features
Arrangement getArrangement()
get arrangement policy
double ANALYSIS_EXPORT angle(Point3D *p1, Point3D *p2, Point3D *p3, Point3D *p4)
Calculates the angle between two segments (in 2 dimension, z-values are ignored)
void extractCoords(const GEOSGeometry *geom)
read coordinates from a GEOS geom
int setPositionForPolygon(double scale, LabelPosition ***lPos, PointSet *mapShape, double delta_width)
generate candidates for point feature Generate candidates for point features
LabelPosition * curvedPlacementAtOffset(PointSet *path_positions, double *path_distances, int orientation, int index, double distance)
bool getShowPartial()
Get flag show partial label.
void sort(double *heap, int *x, int *y, int N)
void setNextPart(LabelPosition *next)
bool ptrLPosCompare(LabelPosition *a, LabelPosition *b)
double max_char_angle_inside
void getPoint(double *d, double *ad, double dl, double *px, double *py)
Only for polygon, arranges candidates with respect of polygon orientation.
void findLineCircleIntersection(double cx, double cy, double radius, double x1, double y1, double x2, double y2, double &xRes, double &yRes)
LabelPosition is a candidate feature label position.
Quadrant
Position of label candidate relative to feature.
Interface that allows Pal to access user's geometries.
bool fixedPosition() const
unsigned long getArrangementFlags() const