From 20e014a16e3fd18a1609339e44a30968a182d281 Mon Sep 17 00:00:00 2001 From: curt Date: Thu, 10 Jun 1999 02:01:09 +0000 Subject: [PATCH] Reversing the order of points causes the area calculation to return a negative number. Polygon holes are wound opposite of non-holes. I was throwing out holes with area < epsilon (i.e. all holes) ... enough said. --- Tools/Construct/Clipper/clipper.cxx | 6 +++- Tools/Construct/Triangulate/polygon.cxx | 26 ++++++++++++------ Tools/Construct/Triangulate/triangle.cxx | 35 ++++++++++++------------ 3 files changed, 41 insertions(+), 26 deletions(-) diff --git a/Tools/Construct/Clipper/clipper.cxx b/Tools/Construct/Clipper/clipper.cxx index db1bfeb7b..fc8ae0f5b 100644 --- a/Tools/Construct/Clipper/clipper.cxx +++ b/Tools/Construct/Clipper/clipper.cxx @@ -183,7 +183,7 @@ void FGClipper::move_slivers( FGPolygon& in, FGPolygon& out ) { cout << " area = " << area << endl; if ( ((min_angle < angle_cutoff) && (area < area_cutoff)) || - (area < area_cutoff / 10.0) ) + ( area < area_cutoff / 10.0) ) { cout << " WE THINK IT'S A SLIVER!" << endl; @@ -192,6 +192,7 @@ void FGClipper::move_slivers( FGPolygon& in, FGPolygon& out ) { if ( hole_flag ) { // just delete/eliminate/remove sliver holes + cout << "just deleting a sliver hole" << endl; in.delete_contour( i ); } else { // move sliver contour to out polygon @@ -259,6 +260,9 @@ void FGClipper::merge_slivers( FGPolyList& clipped, FGPolygon& slivers ) { } } } + if ( !done ) { + cout << "no suitable polys found for sliver merge" << endl; + } } } diff --git a/Tools/Construct/Triangulate/polygon.cxx b/Tools/Construct/Triangulate/polygon.cxx index 142f231f6..cc6ff9040 100644 --- a/Tools/Construct/Triangulate/polygon.cxx +++ b/Tools/Construct/Triangulate/polygon.cxx @@ -88,8 +88,19 @@ static double calc_angle(point2d a, point2d b, point2d c) { // the y value of a point on the line that intersects with the // verticle line through x. Return true if an intersection is found, // false otherwise. -static bool intersects( const Point3D& p0, const Point3D& p1, double x, - Point3D *result ) { +static bool intersects( Point3D p0, Point3D p1, double x, Point3D *result ) { + // sort the end points + if ( p0.x() > p1.x() ) { + Point3D tmp = p0; + p0 = p1; + p1 = tmp; + } + + if ( (x < p0.x()) || (x > p1.x()) ) { + // out of range of line segment, bail right away + return false; + } + // equation of a line through (x0,y0) and (x1,y1): // // y = y1 + (x - x1) * (y0 - y1) / (x0 - x1) @@ -206,7 +217,7 @@ void FGPolygon::calc_point_inside( const int contour, p2_index = trinodes.find( p2 ); if ( intersects(p1, p2, m.x(), &result) ) { - // cout << "intersection = " << result << endl; + cout << "intersection = " << result << endl; if ( ( result.y() < p3.y() ) && ( result.y() > m.y() ) && ( base_leg != FGTriSeg(p1_index, p2_index) ) ) { @@ -221,7 +232,7 @@ void FGPolygon::calc_point_inside( const int contour, p1_index = trinodes.find( p1 ); p2_index = trinodes.find( p2 ); if ( intersects(p1, p2, m.x(), &result) ) { - // cout << "intersection = " << result << endl; + cout << "intersection = " << result << endl; if ( ( result.y() < p3.y() ) && ( result.y() > m.y() ) && ( base_leg != FGTriSeg(p1_index, p2_index) ) ) { @@ -259,7 +270,9 @@ double FGPolygon::area_contour( const int contour ) { sum += c[(i+1)%size].x() * c[i].y() - c[i].x() * c[(i+1)%size].y(); } - return sum / 2.0; + // area can be negative or positive depending on the polygon + // winding order + return fabs(sum / 2.0); } @@ -454,6 +467,3 @@ FGPolygon polygon_xor( const FGPolygon& subject, const FGPolygon& clip ) { FGPolygon polygon_union( const FGPolygon& subject, const FGPolygon& clip ) { return polygon_clip( POLY_UNION, subject, clip ); } - - - diff --git a/Tools/Construct/Triangulate/triangle.cxx b/Tools/Construct/Triangulate/triangle.cxx index 88feafda0..a8e357235 100644 --- a/Tools/Construct/Triangulate/triangle.cxx +++ b/Tools/Construct/Triangulate/triangle.cxx @@ -41,7 +41,6 @@ FGTriangle::build( const point_list& corner_list, const FGPolyList& gpc_polys ) { int debug_counter = 0; - FGPolygon poly; int index; in_nodes.clear(); @@ -75,12 +74,13 @@ FGTriangle::build( const point_list& corner_list, for ( int i = 0; i < FG_MAX_AREA_TYPES; ++i ) { polylist[i].clear(); - // cout << "area type = " << i << endl; + cout << "area type = " << i << endl; debug_counter = 0; current = gpc_polys.polys[i].begin(); last = gpc_polys.polys[i].end(); for ( ; current != last; ++current ) { gpc_poly = *current; + cout << "processing a polygon, contours = " << gpc_poly.contours() << endl; @@ -89,10 +89,7 @@ FGTriangle::build( const point_list& corner_list, exit(-1); } - poly.erase(); - int j; - for ( j = 0; j < gpc_poly.contours(); ++j ) { cout << " processing contour = " << j << ", nodes = " << gpc_poly.contour_size( j ) << ", hole = " @@ -106,47 +103,49 @@ FGTriangle::build( const point_list& corner_list, index = in_nodes.unique_add( p ); // junkp = in_nodes.get_node( index ); // fprintf(junkfp, "%.4f %.4f\n", junkp.x(), junkp.y()); - poly.add_node(j, p); // cout << " - " << index << endl; } // fprintf(junkfp, "%.4f %.4f\n", // gpc_poly->contour[j].vertex[0].x, // gpc_poly->contour[j].vertex[0].y); // fclose(junkfp); - - poly.set_hole_flag( j, gpc_poly.get_hole_flag( j ) ); } for ( j = 0; j < gpc_poly.contours(); ++j ) { - poly.calc_point_inside( j, in_nodes ); + gpc_poly.calc_point_inside( j, in_nodes ); } + polylist[i].push_back( gpc_poly ); + #if 0 // temporary ... write out hole/polygon info for debugging - for ( j = 0; j < (int)poly.contours(); ++j ) { + for ( j = 0; j < (int)gpc_poly.contours(); ++j ) { char pname[256]; sprintf(pname, "poly%02d-%02d-%02d", i, debug_counter, j); + cout << "writing to " << pname << endl; FILE *fp = fopen( pname, "w" ); Point3D point; - for ( int k = 0; k < poly.contour_size( j ); ++k ) { - point = poly.get_pt( j, k ); + for ( int k = 0; k < gpc_poly.contour_size( j ); ++k ) { + point = gpc_poly.get_pt( j, k ); fprintf( fp, "%.6f %.6f\n", point.x(), point.y() ); } - point = poly.get_pt( j, 0 ); + point = gpc_poly.get_pt( j, 0 ); fprintf( fp, "%.6f %.6f\n", point.x(), point.y() ); fclose(fp); char hname[256]; sprintf(hname, "hole%02d-%02d-%02d", i, debug_counter, j); FILE *fh = fopen( hname, "w" ); - point = poly.get_point_inside( j ); + point = gpc_poly.get_point_inside( j ); fprintf( fh, "%.6f %.6f\n", point.x(), point.y() ); fclose(fh); } -#endif - - polylist[i].push_back( poly ); + // cout << "type a letter + enter to continue: "; + // string input; + // cin >> input; +#endif + ++debug_counter; } } @@ -172,6 +171,8 @@ FGTriangle::build( const point_list& corner_list, int i1, i2; Point3D p1, p2; point_list node_list = in_nodes.get_node_list(); + FGPolygon poly; + for ( int i = 0; i < FG_MAX_AREA_TYPES; ++i ) { cout << "area type = " << i << endl; poly_list_iterator tp_current, tp_last; -- 2.39.5