From cf3d9c5572abb19044e01b7bafb70df9fa34ca42 Mon Sep 17 00:00:00 2001 From: curt Date: Wed, 28 Apr 1999 22:18:19 +0000 Subject: [PATCH] Renamed tripoly.* to polygon.* First stab at multi-contour polygon support. --- Tools/Construct/Triangulate/Makefile.am | 2 +- .../Triangulate/{tripoly.cxx => polygon.cxx} | 79 ++++++------ Tools/Construct/Triangulate/polygon.hxx | 115 ++++++++++++++++++ Tools/Construct/Triangulate/triangle.cxx | 67 +++++----- Tools/Construct/Triangulate/triangle.hxx | 4 +- Tools/Construct/Triangulate/tripoly.hxx | 82 ------------- 6 files changed, 199 insertions(+), 150 deletions(-) rename Tools/Construct/Triangulate/{tripoly.cxx => polygon.cxx} (67%) create mode 100644 Tools/Construct/Triangulate/polygon.hxx delete mode 100644 Tools/Construct/Triangulate/tripoly.hxx diff --git a/Tools/Construct/Triangulate/Makefile.am b/Tools/Construct/Triangulate/Makefile.am index 34c320f91..e62d4405b 100644 --- a/Tools/Construct/Triangulate/Makefile.am +++ b/Tools/Construct/Triangulate/Makefile.am @@ -1,10 +1,10 @@ noinst_LIBRARIES = libTriangulate.a libTriangulate_a_SOURCES = \ + polygon.cxx polygon.hxx \ triangle.cxx triangle.hxx \ trieles.cxx trieles.hxx \ trinodes.cxx trinodes.hxx \ - tripoly.cxx tripoly.hxx \ trisegs.cxx trisegs.hxx INCLUDES += \ diff --git a/Tools/Construct/Triangulate/tripoly.cxx b/Tools/Construct/Triangulate/polygon.cxx similarity index 67% rename from Tools/Construct/Triangulate/tripoly.cxx rename to Tools/Construct/Triangulate/polygon.cxx index 55c92473e..5e8d6a6b8 100644 --- a/Tools/Construct/Triangulate/tripoly.cxx +++ b/Tools/Construct/Triangulate/polygon.cxx @@ -1,4 +1,4 @@ -// tripoly.cxx -- "Triangle" polygon management class +// polygon.cxx -- polygon (with holes) management class // // Written by Curtis Olson, started March 1999. // @@ -24,16 +24,16 @@ #include #include -#include "tripoly.hxx" +#include "polygon.hxx" // Constructor -FGTriPoly::FGTriPoly( void ) { +FGPolygon::FGPolygon( void ) { } // Destructor -FGTriPoly::~FGTriPoly( void ) { +FGPolygon::~FGPolygon( void ) { } @@ -82,9 +82,10 @@ static bool intersects( const Point3D& p0, const Point3D& p1, double x, } -// calculate an "arbitrary" point inside this polygon for assigning -// attribute areas -void FGTriPoly::calc_point_inside( const FGTriNodes& trinodes ) { +// calculate an "arbitrary" point inside the specified contour for +// assigning attribute areas +void FGPolygon::calc_point_inside( const int contour, + const FGTriNodes& trinodes ) { Point3D tmp, min, ln, p1, p2, p3, m, result; // 1. find point, min, with smallest y @@ -95,8 +96,8 @@ void FGTriPoly::calc_point_inside( const FGTriNodes& trinodes ) { int min_node_index = 0; int_list_iterator current, last; - current = poly.begin(); - last = poly.end(); + current = poly[contour].begin(); + last = poly[contour].end(); int counter = 0; for ( ; current != last; ++current ) { @@ -114,22 +115,22 @@ void FGTriPoly::calc_point_inside( const FGTriNodes& trinodes ) { ++counter; } cout << "min node index = " << min_node_index << endl; - cout << "min index = " << poly[min_node_index] - << " value = " << trinodes.get_node( poly[min_node_index] ) + cout << "min index = " << poly[contour][min_node_index] + << " value = " << trinodes.get_node( poly[contour][min_node_index] ) << " == " << min << endl; // 2. take midpoint, m, of min with neighbor having lowest // fabs(slope) if ( min_node_index == 0 ) { - p1 = trinodes.get_node( poly[1] ); - p2 = trinodes.get_node( poly[poly.size() - 1] ); - } else if ( min_node_index == (int)(poly.size()) - 1 ) { - p1 = trinodes.get_node( poly[0] ); - p2 = trinodes.get_node( poly[poly.size() - 1] ); + p1 = trinodes.get_node( poly[contour][1] ); + p2 = trinodes.get_node( poly[contour][poly.size() - 1] ); + } else if ( min_node_index == (int)(poly[contour].size()) - 1 ) { + p1 = trinodes.get_node( poly[contour][0] ); + p2 = trinodes.get_node( poly[contour][poly.size() - 1] ); } else { - p1 = trinodes.get_node( poly[min_node_index - 1] ); - p2 = trinodes.get_node( poly[min_node_index + 1] ); + p1 = trinodes.get_node( poly[contour][min_node_index - 1] ); + p2 = trinodes.get_node( poly[contour][min_node_index + 1] ); } double s1 = fabs( slope(min, p1) ); double s2 = fabs( slope(min, p2) ); @@ -143,38 +144,42 @@ void FGTriPoly::calc_point_inside( const FGTriNodes& trinodes ) { m.sety( (min.y() + ln.y()) / 2.0 ); cout << "low mid point = " << m << endl; - // 3. intersect vertical line through m and all other segments. - // save point, p3, with smallest y > m.y + // 3. intersect vertical line through m and all other segments of + // all other contours of this polygon. save point, p3, with + // smallest y > m.y p3.sety(100); - for ( int i = 0; i < (int)(poly.size()) - 1; ++i ) { - p1 = trinodes.get_node( poly[i] ); - p2 = trinodes.get_node( poly[i+1] ); - + + for ( int i = 0; i < (int)poly.size(); ++i ) { + for ( int j = 0; j < (int)(poly[i].size()) - 1; ++j ) { + p1 = trinodes.get_node( poly[contour][j] ); + p2 = trinodes.get_node( poly[contour][j+1] ); + + if ( intersects(p1, p2, m.x(), &result) ) { + // cout << "intersection = " << result << endl; + if ( ( result.y() < p3.y() ) && + ( fabs(result.y() - m.y()) > FG_EPSILON ) ) { + p3 = result; + } + } + } + p1 = trinodes.get_node( poly[contour][0] ); + p2 = trinodes.get_node( poly[contour][poly.size() - 1] ); if ( intersects(p1, p2, m.x(), &result) ) { // cout << "intersection = " << result << endl; if ( ( result.y() < p3.y() ) && - ( fabs(result.y() - m.y()) > FG_EPSILON ) ) { + ( fabs(result.y() - m.y()) > FG_EPSILON ) ) { p3 = result; } } } - p1 = trinodes.get_node( poly[0] ); - p2 = trinodes.get_node( poly[poly.size() - 1] ); - if ( intersects(p1, p2, m.x(), &result) ) { - // cout << "intersection = " << result << endl; - if ( ( result.y() < p3.y() ) && - ( fabs(result.y() - m.y()) > FG_EPSILON ) ) { - p3 = result; - } - } cout << "low intersection of other segment = " << p3 << endl; // 4. take midpoint of p2 && m as an arbitrary point inside polygon - inside.setx( (m.x() + p3.x()) / 2.0 ); - inside.sety( (m.y() + p3.y()) / 2.0 ); - cout << "inside point = " << inside << endl; + inside_list[contour].setx( (m.x() + p3.x()) / 2.0 ); + inside_list[contour].sety( (m.y() + p3.y()) / 2.0 ); + cout << "inside point = " << inside_list[contour] << endl; } diff --git a/Tools/Construct/Triangulate/polygon.hxx b/Tools/Construct/Triangulate/polygon.hxx new file mode 100644 index 000000000..ac21e0967 --- /dev/null +++ b/Tools/Construct/Triangulate/polygon.hxx @@ -0,0 +1,115 @@ +// polygon.hxx -- polygon (with holes) management class +// +// Written by Curtis Olson, started March 1999. +// +// Copyright (C) 1999 Curtis L. Olson - curt@flightgear.org +// +// This program is free software; you can redistribute it and/or +// modify it under the terms of the GNU General Public License as +// published by the Free Software Foundation; either version 2 of the +// License, or (at your option) any later version. +// +// This program is distributed in the hope that it will be useful, but +// WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// General Public License for more details. +// +// You should have received a copy of the GNU General Public License +// along with this program; if not, write to the Free Software +// Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. +// +// $Id$ + + +#ifndef _POLYGON_HXX +#define _POLYGON_HXX + + +#ifndef __cplusplus +# error This library requires C++ +#endif + + +#include + +#include + +#include
+ +#include "trinodes.hxx" + +FG_USING_STD(vector); + + +typedef vector < int_list > polytype; +typedef polytype::iterator polytype_iterator; +typedef polytype::const_iterator const_polytype_iterator; + + +class FGPolygon { + +private: + + polytype poly; // polygons + point_list inside_list; // point inside list + int_list hole_list; // hole flag list + +public: + + // Constructor and destructor + FGPolygon( void ); + ~FGPolygon( void ); + + // Add the specified node (index) to the polygon + inline void add_node( int contour, int index ) { + if ( contour >= (int)poly.size() ) { + // extend polygon + int_list empty_contour; + empty_contour.clear(); + for ( int i = 0; i < contour - (int)poly.size() + 1; ++i ) { + poly.push_back( empty_contour ); + inside_list.push_back( Point3D(0.0) ); + hole_list.push_back( 0 ); + } + } + poly[contour].push_back( index ); + } + + // return size + inline int contours() const { return poly.size(); } + inline int contour_size( int contour ) const { + return poly[contour].size(); + } + + // return the ith polygon point index from the specified contour + inline int get_pt_index( int contour, int i ) const { + return poly[contour][i]; + } + + // calculate an "arbitrary" point inside the specified contour for + // assigning attribute areas + void calc_point_inside( const int contour, const FGTriNodes& trinodes ); + inline Point3D get_point_inside( const int contour ) const { + return inside_list[contour]; + } + + // get and set hole flag + inline int get_hole_flag( const int contour ) const { + return hole_list[contour]; + } + inline void set_hole_flag( const int contour, const int flag ) { + hole_list[contour] = flag; + } + + inline void erase() { poly.clear(); } +}; + + +typedef vector < FGPolygon > poly_list; +typedef poly_list::iterator poly_list_iterator; +typedef poly_list::const_iterator const_poly_list_iterator; + + +#endif // _POLYGON_HXX + + diff --git a/Tools/Construct/Triangulate/triangle.cxx b/Tools/Construct/Triangulate/triangle.cxx index 4a36f2e31..2db6bc6b4 100644 --- a/Tools/Construct/Triangulate/triangle.cxx +++ b/Tools/Construct/Triangulate/triangle.cxx @@ -21,8 +21,8 @@ // $Id$ +#include "polygon.hxx" #include "triangle.hxx" -#include "tripoly.hxx" // Constructor FGTriangle::FGTriangle( void ) { @@ -40,7 +40,7 @@ FGTriangle::build( const point_list& corner_list, const point_list& fit_list, const FGgpcPolyList& gpc_polys ) { - FGTriPoly poly; + FGPolygon poly; int index; in_nodes.clear(); @@ -93,11 +93,13 @@ FGTriangle::build( const point_list& corner_list, // exit(-1); } - for ( int j = 0; j < gpc_poly->num_contours; j++ ) { - cout << " processing contour, nodes = " - << gpc_poly->contour[j].num_vertices << endl; + poly.erase(); + + int j; - poly.erase(); + for ( j = 0; j < gpc_poly->num_contours; j++ ) { + cout << " processing contour = " << j << ", nodes = " + << gpc_poly->contour[j].num_vertices << endl; // sprintf(junkn, "g.%d", junkc++); // junkfp = fopen(junkn, "w"); @@ -109,7 +111,7 @@ 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(index); + poly.add_node(j, index); // cout << index << endl; } // fprintf(junkfp, "%.4f %.4f\n", @@ -117,9 +119,12 @@ FGTriangle::build( const point_list& corner_list, // gpc_poly->contour[j].vertex[0].y); // fclose(junkfp); - poly.calc_point_inside( in_nodes ); + poly.set_hole_flag( j, gpc_poly->hole[j] ); + polylist[i].push_back( poly ); + } - polylist[i].push_back(poly); + for ( j = 0; j < gpc_poly->num_contours; j++ ) { + poly.calc_point_inside( j, in_nodes ); } } } @@ -145,7 +150,7 @@ FGTriangle::build( const point_list& corner_list, point_list node_list = in_nodes.get_node_list(); for ( int i = 0; i < FG_MAX_AREA_TYPES; ++i ) { // cout << "area type = " << i << endl; - tripoly_list_iterator tp_current, tp_last; + poly_list_iterator tp_current, tp_last; tp_current = polylist[i].begin(); tp_last = polylist[i].end(); @@ -153,16 +158,18 @@ FGTriangle::build( const point_list& corner_list, for ( ; tp_current != tp_last; ++tp_current ) { poly = *tp_current; - for ( int j = 0; j < (int)(poly.size()) - 1; ++j ) { - i1 = poly.get_pt_index( j ); - i2 = poly.get_pt_index( j + 1 ); + for ( int j = 0; j < (int)poly.contours(); ++j) { + for ( int k = 0; k < (int)(poly.contour_size(j)) - 1; ++k ) { + i1 = poly.get_pt_index( j, k ); + i2 = poly.get_pt_index( j, k + 1 ); + // calc_line_params(i1, i2, &m, &b); + trisegs.unique_divide_and_add( node_list, FGTriSeg(i1, i2) ); + } + i1 = poly.get_pt_index( j, 0 ); + i2 = poly.get_pt_index( j, poly.contour_size(j) - 1 ); // calc_line_params(i1, i2, &m, &b); trisegs.unique_divide_and_add( node_list, FGTriSeg(i1, i2) ); } - i1 = poly.get_pt_index( 0 ); - i2 = poly.get_pt_index( poly.size() - 1 ); - // calc_line_params(i1, i2, &m, &b); - trisegs.unique_divide_and_add( node_list, FGTriSeg(i1, i2) ); } } @@ -222,7 +229,7 @@ static void write_out_data(struct triangulateio *out) { // triangulate each of the polygon areas int FGTriangle::run_triangulate() { - FGTriPoly poly; + FGPolygon poly; Point3D p; struct triangulateio in, out, vorout; int counter; @@ -276,15 +283,17 @@ int FGTriangle::run_triangulate() { in.numberofholes = polylist[(int)AirportIgnoreArea].size(); in.holelist = (REAL *) malloc(in.numberofholes * 2 * sizeof(REAL)); - tripoly_list_iterator h_current, h_last; + poly_list_iterator h_current, h_last; h_current = polylist[(int)AirportIgnoreArea].begin(); h_last = polylist[(int)AirportIgnoreArea].end(); counter = 0; for ( ; h_current != h_last; ++h_current ) { poly = *h_current; - p = poly.get_point_inside(); - in.holelist[counter++] = p.x(); - in.holelist[counter++] = p.y(); + for ( int j = 0; j < poly.contours(); j++ ) { + p = poly.get_point_inside( j ); + in.holelist[counter++] = p.x(); + in.holelist[counter++] = p.y(); + } } // region list @@ -296,16 +305,18 @@ int FGTriangle::run_triangulate() { in.regionlist = (REAL *) malloc(in.numberofregions * 4 * sizeof(REAL)); counter = 0; for ( int i = 0; i < FG_MAX_AREA_TYPES; ++i ) { - tripoly_list_iterator h_current, h_last; + poly_list_iterator h_current, h_last; h_current = polylist[(int)i].begin(); h_last = polylist[(int)i].end(); for ( ; h_current != h_last; ++h_current ) { poly = *h_current; - p = poly.get_point_inside(); - in.regionlist[counter++] = p.x(); // x coord - in.regionlist[counter++] = p.y(); // y coord - in.regionlist[counter++] = i; // region attribute - in.regionlist[counter++] = -1.0; // area constraint (unused) + for ( int j = 0; j < poly.contours(); j++ ) { + p = poly.get_point_inside( j ); + in.regionlist[counter++] = p.x(); // x coord + in.regionlist[counter++] = p.y(); // y coord + in.regionlist[counter++] = i; // region attribute + in.regionlist[counter++] = -1.0; // area constraint (unused) + } } } diff --git a/Tools/Construct/Triangulate/triangle.hxx b/Tools/Construct/Triangulate/triangle.hxx index 4fe52b4ac..6037909ba 100644 --- a/Tools/Construct/Triangulate/triangle.hxx +++ b/Tools/Construct/Triangulate/triangle.hxx @@ -42,9 +42,9 @@ extern "C" { #include } +#include "polygon.hxx" #include "trieles.hxx" #include "trinodes.hxx" -#include "tripoly.hxx" #include "trisegs.hxx" @@ -60,7 +60,7 @@ private: FGTriSegments trisegs; // polygon list - tripoly_list polylist[FG_MAX_AREA_TYPES]; + poly_list polylist[FG_MAX_AREA_TYPES]; // triangle list triele_list elelist; diff --git a/Tools/Construct/Triangulate/tripoly.hxx b/Tools/Construct/Triangulate/tripoly.hxx deleted file mode 100644 index 9dc48257e..000000000 --- a/Tools/Construct/Triangulate/tripoly.hxx +++ /dev/null @@ -1,82 +0,0 @@ -// tripoly.hxx -- "Triangle" polygon management class -// -// Written by Curtis Olson, started March 1999. -// -// Copyright (C) 1999 Curtis L. Olson - curt@flightgear.org -// -// This program is free software; you can redistribute it and/or -// modify it under the terms of the GNU General Public License as -// published by the Free Software Foundation; either version 2 of the -// License, or (at your option) any later version. -// -// This program is distributed in the hope that it will be useful, but -// WITHOUT ANY WARRANTY; without even the implied warranty of -// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU -// General Public License for more details. -// -// You should have received a copy of the GNU General Public License -// along with this program; if not, write to the Free Software -// Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. -// -// $Id$ - - -#ifndef _TRIPOLY_HXX -#define _TRIPOLY_HXX - - -#ifndef __cplusplus -# error This library requires C++ -#endif - - -#include - -#include - -#include
- -#include "trinodes.hxx" - -FG_USING_STD(vector); - - -class FGTriPoly { - -private: - - int_list poly; - Point3D inside; - -public: - - // Constructor and destructor - FGTriPoly( void ); - ~FGTriPoly( void ); - - // Add the specified node (index) to the polygon - inline void add_node( int index ) { poly.push_back( index ); } - - // return size - inline int size() const { return poly.size(); } - - // return the ith polygon point index - inline int get_pt_index( int i ) const { return poly[i]; } - - // calculate an "arbitrary" point inside this polygon for - // assigning attribute areas - void calc_point_inside( const FGTriNodes& trinodes ); - inline Point3D get_point_inside() const { return inside; } - - inline void erase() { poly.erase( poly.begin(), poly.end() ); } -}; - - -typedef vector < FGTriPoly > tripoly_list; -typedef tripoly_list::iterator tripoly_list_iterator; -typedef tripoly_list::const_iterator const_tripoly_list_iterator; - - -#endif // _TRIPOLY_HXX - - -- 2.39.5