Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2026-08-15 08:46:59 

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002 
0003 // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
0004 
0005 // This file was modified by Oracle on 2014-2024.
0006 // Modifications copyright (c) 2014-2024 Oracle and/or its affiliates.
0007 
0008 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
0009 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
0010 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0011 
0012 // Use, modification and distribution is subject to the Boost Software License,
0013 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0014 // http://www.boost.org/LICENSE_1_0.txt)
0015 
0016 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_INTERSECTION_INSERT_HPP
0017 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_INTERSECTION_INSERT_HPP
0018 
0019 
0020 #include <cstddef>
0021 #include <deque>
0022 #include <type_traits>
0023 
0024 #include <boost/range/begin.hpp>
0025 #include <boost/range/end.hpp>
0026 #include <boost/range/size.hpp>
0027 
0028 #include <boost/geometry/algorithms/convert.hpp>
0029 #include <boost/geometry/algorithms/detail/point_on_border.hpp>
0030 #include <boost/geometry/algorithms/detail/overlay/clip_linestring.hpp>
0031 #include <boost/geometry/algorithms/detail/overlay/follow.hpp>
0032 #include <boost/geometry/algorithms/detail/overlay/get_intersection_points.hpp>
0033 #include <boost/geometry/algorithms/detail/overlay/linear_linear.hpp>
0034 #include <boost/geometry/algorithms/detail/overlay/overlay.hpp>
0035 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
0036 #include <boost/geometry/algorithms/detail/overlay/pointlike_areal.hpp>
0037 #include <boost/geometry/algorithms/detail/overlay/pointlike_linear.hpp>
0038 #include <boost/geometry/algorithms/detail/overlay/pointlike_pointlike.hpp>
0039 #include <boost/geometry/algorithms/detail/overlay/range_in_geometry.hpp>
0040 #include <boost/geometry/algorithms/detail/overlay/segment_as_subrange.hpp>
0041 
0042 #include <boost/geometry/core/point_order.hpp>
0043 #include <boost/geometry/core/reverse_dispatch.hpp>
0044 #include <boost/geometry/core/static_assert.hpp>
0045 #include <boost/geometry/core/tag_cast.hpp>
0046 
0047 #include <boost/geometry/geometries/concepts/check.hpp>
0048 
0049 #include <boost/geometry/strategies/default_strategy.hpp>
0050 #include <boost/geometry/strategies/detail.hpp>
0051 #include <boost/geometry/strategies/relate/services.hpp>
0052 
0053 #include <boost/geometry/views/segment_view.hpp>
0054 #include <boost/geometry/views/detail/boundary_view.hpp>
0055 
0056 #if defined(BOOST_GEOMETRY_DEBUG_FOLLOW)
0057 #include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
0058 #include <boost/geometry/io/wkt/wkt.hpp>
0059 #include <boost/geometry/views/enumerate_view.hpp>
0060 #endif
0061 
0062 namespace boost { namespace geometry
0063 {
0064 
0065 #ifndef DOXYGEN_NO_DETAIL
0066 namespace detail { namespace intersection
0067 {
0068 
0069 template <typename PointOut>
0070 struct intersection_segment_segment_point
0071 {
0072     template
0073     <
0074         typename Segment1, typename Segment2,
0075         typename OutputIterator, typename Strategy
0076     >
0077     static inline OutputIterator apply(Segment1 const& segment1,
0078             Segment2 const& segment2,
0079             OutputIterator out,
0080             Strategy const& strategy)
0081     {
0082         using point_type = point_type_t<PointOut>;
0083         using intersection_return_type = segment_intersection_points<point_type>;
0084         using policy_type = policies::relate::segments_intersection_points
0085             <
0086                 intersection_return_type
0087             >;
0088 
0089         // Get the intersection point (or two points)
0090         detail::segment_as_subrange<Segment1> sub_range1(segment1);
0091         detail::segment_as_subrange<Segment2> sub_range2(segment2);
0092 
0093         intersection_return_type
0094             is = strategy.relate().apply(sub_range1, sub_range2, policy_type());
0095 
0096         for (std::size_t i = 0; i < is.count; i++)
0097         {
0098             PointOut p;
0099             geometry::convert(is.intersections[i], p);
0100             *out++ = p;
0101         }
0102         return out;
0103     }
0104 };
0105 
0106 template <typename PointOut>
0107 struct intersection_linestring_linestring_point
0108 {
0109     template
0110     <
0111         typename Linestring1, typename Linestring2,
0112         typename OutputIterator,
0113         typename Strategy
0114     >
0115     static inline OutputIterator apply(Linestring1 const& linestring1,
0116             Linestring2 const& linestring2,
0117             OutputIterator out,
0118             Strategy const& strategy)
0119     {
0120         using turn_info = detail::overlay::turn_info<PointOut>;
0121         std::deque<turn_info> turns;
0122 
0123         geometry::get_intersection_points(linestring1, linestring2,
0124                                           turns, strategy);
0125 
0126         for (auto const& turn : turns)
0127         {
0128             PointOut p;
0129             geometry::convert(turn.point, p);
0130             *out++ = p;
0131         }
0132         return out;
0133     }
0134 };
0135 
0136 /*!
0137 \brief Version of linestring with an areal feature (polygon or multipolygon)
0138 */
0139 template
0140 <
0141     bool ReverseAreal,
0142     typename GeometryOut,
0143     overlay_type OverlayType,
0144     bool FollowIsolatedPoints
0145 >
0146 struct intersection_of_linestring_with_areal
0147 {
0148 #if defined(BOOST_GEOMETRY_DEBUG_FOLLOW)
0149     template <typename Turn, typename Operation>
0150     static inline void debug_follow(Turn const& turn, Operation op,
0151                                     int index)
0152     {
0153         std::cout << index
0154                   << " at " << op.seg_id
0155                   << " meth: " << method_char(turn.method)
0156                   << " op: " << operation_char(op.operation)
0157                   << " of:  " << operation_char(turn.operations[0].operation)
0158                   << operation_char(turn.operations[1].operation)
0159                   << " " << geometry::wkt(turn.point)
0160                   << std::endl;
0161     }
0162 
0163     template <typename Turn>
0164     static inline void debug_turn(Turn const& t, bool non_crossing)
0165     {
0166         std::cout << "checking turn @"
0167                   << geometry::wkt(t.point)
0168                   << "; " << method_char(t.method)
0169                   << ":" << operation_char(t.operations[0].operation)
0170                   << "/" << operation_char(t.operations[1].operation)
0171                   << "; non-crossing? "
0172                   << std::boolalpha << non_crossing << std::noboolalpha
0173                   << std::endl;
0174     }
0175 #endif
0176 
0177     template <typename Linestring, typename Areal, typename Strategy, typename Turns>
0178     static inline bool simple_turns_analysis(Linestring const& linestring,
0179                                              Areal const& areal,
0180                                              Strategy const& strategy,
0181                                              Turns const& turns,
0182                                              int & inside_value)
0183     {
0184         using namespace overlay;
0185 
0186         bool found_continue = false;
0187         bool found_intersection = false;
0188         bool found_union = false;
0189         bool found_front = false;
0190 
0191         for (auto const& turn : turns)
0192         {
0193             method_type const method = turn.method;
0194             operation_type const op = turn.operations[0].operation;
0195 
0196             if (method == method_crosses)
0197             {
0198                 return false;
0199             }
0200             else if (op == operation_intersection)
0201             {
0202                 found_intersection = true;
0203             }
0204             else if (op == operation_union)
0205             {
0206                 found_union = true;
0207             }
0208             else if (op == operation_continue)
0209             {
0210                 found_continue = true;
0211             }
0212 
0213             if ((found_intersection || found_continue) && found_union)
0214             {
0215                 return false;
0216             }
0217 
0218             if (turn.operations[0].position == position_front)
0219             {
0220                 found_front = true;
0221             }
0222         }
0223 
0224         if (found_front)
0225         {
0226             if (found_intersection)
0227             {
0228                 inside_value = 1; // inside
0229             }
0230             else if (found_union)
0231             {
0232                 inside_value = -1; // outside
0233             }
0234             else // continue and blocked
0235             {
0236                 inside_value = 0;
0237             }
0238             return true;
0239         }
0240 
0241         // if needed analyse points of a linestring
0242         // NOTE: range_in_geometry checks points of a linestring
0243         // until a point inside/outside areal is found
0244         // TODO: Could be replaced with point_in_geometry() because found_front is false
0245         inside_value = range_in_geometry(linestring, areal, strategy);
0246 
0247         if ( (found_intersection && inside_value == -1) // going in from outside
0248           || (found_continue && inside_value == -1) // going on boundary from outside
0249           || (found_union && inside_value == 1) ) // going out from inside
0250         {
0251             return false;
0252         }
0253 
0254         return true;
0255     }
0256 
0257     template
0258     <
0259         typename LineString, typename Areal,
0260         typename OutputIterator, typename Strategy
0261     >
0262     static inline OutputIterator apply(LineString const& linestring, Areal const& areal,
0263             OutputIterator out,
0264             Strategy const& strategy)
0265     {
0266         if (boost::size(linestring) == 0)
0267         {
0268             return out;
0269         }
0270 
0271         using follower = detail::overlay::follow
0272                 <
0273                     GeometryOut,
0274                     LineString,
0275                     Areal,
0276                     OverlayType,
0277                     false, // do not remove spikes for linear geometries
0278                     FollowIsolatedPoints
0279                 >;
0280 
0281         using linear = typename geometry::detail::output_geometry_access
0282             <
0283                 GeometryOut, linestring_tag, linestring_tag
0284             >;
0285 
0286         using point_type = point_type_t<typename linear::type>;
0287 
0288         using ratio_type = geometry::segment_ratio
0289             <
0290                 coordinate_type_t<point_type>
0291             >;
0292 
0293         using turn_info = detail::overlay::turn_info
0294             <
0295                 point_type,
0296                 ratio_type,
0297                 detail::overlay::turn_operation_linear
0298                     <
0299                         point_type,
0300                         ratio_type
0301                     >
0302             >;
0303 
0304         std::deque<turn_info> turns;
0305 
0306         detail::get_turns::no_interrupt_policy policy;
0307 
0308         using turn_policy = detail::overlay::get_turn_info_linear_areal
0309             <
0310                 detail::overlay::assign_null_policy
0311             >;
0312 
0313         dispatch::get_turns
0314             <
0315                 geometry::tag_t<LineString>,
0316                 geometry::tag_t<Areal>,
0317                 LineString,
0318                 Areal,
0319                 false,
0320                 (OverlayType == overlay_intersection ? ReverseAreal : !ReverseAreal),
0321                 turn_policy
0322             >::apply(0, linestring, 1, areal,
0323                      strategy,
0324                      turns, policy);
0325 
0326         int inside_value = 0;
0327         if (simple_turns_analysis(linestring, areal, strategy, turns, inside_value))
0328         {
0329             // No crossing the boundary, it is either
0330             // inside (interior + borders)
0331             // or outside (exterior + borders)
0332             // or on boundary
0333 
0334             // add linestring to the output if conditions are met
0335             if (follower::included(inside_value))
0336             {
0337                 typename linear::type copy;
0338                 geometry::convert(linestring, copy);
0339                 *linear::get(out)++ = copy;
0340             }
0341 
0342             return out;
0343         }
0344 
0345 #if defined(BOOST_GEOMETRY_DEBUG_FOLLOW)
0346         for (auto const& item : util::enumerate(turns))
0347         {
0348             auto const& turn = item.value;
0349             debug_follow(turn, turn.operations[0], item.index);
0350         }
0351 #endif
0352 
0353         return follower::apply
0354                 (
0355                     linestring, areal,
0356                     geometry::detail::overlay::operation_intersection,
0357                     turns, out, strategy
0358                 );
0359     }
0360 };
0361 
0362 
0363 template <typename Turns, typename OutputIterator>
0364 inline OutputIterator intersection_output_turn_points(Turns const& turns,
0365                                                       OutputIterator out)
0366 {
0367     for (auto const& turn : turns)
0368     {
0369         *out++ = turn.point;
0370     }
0371 
0372     return out;
0373 }
0374 
0375 template <typename PointOut>
0376 struct intersection_areal_areal_point
0377 {
0378     template
0379     <
0380         typename Geometry1, typename Geometry2,
0381         typename OutputIterator,
0382         typename Strategy
0383     >
0384     static inline OutputIterator apply(Geometry1 const& geometry1,
0385                                        Geometry2 const& geometry2,
0386                                        OutputIterator out,
0387                                        Strategy const& strategy)
0388     {
0389         using turn_info = detail::overlay::turn_info
0390             <
0391                 PointOut,
0392                 typename segment_ratio_type<PointOut>::type
0393             >;
0394         std::vector<turn_info> turns;
0395 
0396         detail::get_turns::no_interrupt_policy policy;
0397 
0398         geometry::get_turns
0399             <
0400                 false, false, detail::overlay::assign_null_policy
0401             >(geometry1, geometry2, strategy, turns, policy);
0402 
0403         return intersection_output_turn_points(turns, out);
0404     }
0405 };
0406 
0407 template <typename PointOut>
0408 struct intersection_linear_areal_point
0409 {
0410     template
0411     <
0412         typename Geometry1, typename Geometry2,
0413         typename OutputIterator,
0414         typename Strategy
0415     >
0416     static inline OutputIterator apply(Geometry1 const& geometry1,
0417                                        Geometry2 const& geometry2,
0418                                        OutputIterator out,
0419                                        Strategy const& strategy)
0420     {
0421         using ratio_type = geometry::segment_ratio<geometry::coordinate_type_t<PointOut>>;
0422 
0423         using turn_info = detail::overlay::turn_info
0424             <
0425                 PointOut,
0426                 ratio_type,
0427                 detail::overlay::turn_operation_linear
0428                     <
0429                         PointOut,
0430                         ratio_type
0431                     >
0432             >;
0433 
0434         using turn_policy = detail::overlay::get_turn_info_linear_areal
0435             <
0436                 detail::overlay::assign_null_policy
0437             >;
0438 
0439         std::vector<turn_info> turns;
0440 
0441         detail::get_turns::no_interrupt_policy interrupt_policy;
0442 
0443         dispatch::get_turns
0444             <
0445                 geometry::tag_t<Geometry1>,
0446                 geometry::tag_t<Geometry2>,
0447                 Geometry1,
0448                 Geometry2,
0449                 false,
0450                 false,
0451                 turn_policy
0452             >::apply(0, geometry1, 1, geometry2,
0453                      strategy,
0454                      turns, interrupt_policy);
0455 
0456         return intersection_output_turn_points(turns, out);
0457     }
0458 };
0459 
0460 template <typename PointOut>
0461 struct intersection_areal_linear_point
0462 {
0463     template
0464     <
0465         typename Geometry1, typename Geometry2,
0466         typename OutputIterator,
0467         typename Strategy
0468     >
0469     static inline OutputIterator apply(Geometry1 const& geometry1,
0470                                        Geometry2 const& geometry2,
0471                                        OutputIterator out,
0472                                        Strategy const& strategy)
0473     {
0474         return intersection_linear_areal_point
0475             <
0476                 PointOut
0477             >::apply(geometry2, geometry1, out, strategy);
0478     }
0479 };
0480 
0481 
0482 }} // namespace detail::intersection
0483 #endif // DOXYGEN_NO_DETAIL
0484 
0485 
0486 
0487 #ifndef DOXYGEN_NO_DISPATCH
0488 namespace dispatch
0489 {
0490 
0491 template
0492 <
0493     // real types
0494     typename Geometry1,
0495     typename Geometry2,
0496     typename GeometryOut,
0497     overlay_type OverlayType,
0498     // orientation
0499     bool Reverse1 = detail::overlay::do_reverse<geometry::point_order<Geometry1>::value>::value,
0500     bool Reverse2 = detail::overlay::do_reverse<geometry::point_order<Geometry2>::value>::value,
0501     // tag dispatching:
0502     typename TagIn1 = tag_t<Geometry1>,
0503     typename TagIn2 = tag_t<Geometry2>,
0504     typename TagOut = typename detail::setop_insert_output_tag<GeometryOut>::type,
0505     // metafunction finetuning helpers:
0506     typename CastedTagIn1 = tag_cast_t<TagIn1, areal_tag, linear_tag, pointlike_tag>,
0507     typename CastedTagIn2 = tag_cast_t<TagIn2, areal_tag, linear_tag, pointlike_tag>,
0508     typename CastedTagOut = tag_cast_t<TagOut, areal_tag, linear_tag, pointlike_tag>
0509 >
0510 struct intersection_insert
0511 {
0512     BOOST_GEOMETRY_STATIC_ASSERT_FALSE(
0513         "Not or not yet implemented for these Geometry types or their order.",
0514         Geometry1, Geometry2, GeometryOut,
0515         std::integral_constant<overlay_type, OverlayType>);
0516 };
0517 
0518 
0519 template
0520 <
0521     typename Geometry1, typename Geometry2,
0522     typename GeometryOut,
0523     overlay_type OverlayType,
0524     bool Reverse1, bool Reverse2,
0525     typename TagIn1, typename TagIn2, typename TagOut
0526 >
0527 struct intersection_insert
0528     <
0529         Geometry1, Geometry2,
0530         GeometryOut,
0531         OverlayType,
0532         Reverse1, Reverse2,
0533         TagIn1, TagIn2, TagOut,
0534         areal_tag, areal_tag, areal_tag
0535     > : detail::overlay::overlay
0536         <
0537             Geometry1, Geometry2, Reverse1, Reverse2,
0538             detail::overlay::do_reverse<geometry::point_order<GeometryOut>::value>::value,
0539             GeometryOut, OverlayType
0540         >
0541 {};
0542 
0543 
0544 // Any areal type with box:
0545 template
0546 <
0547     typename Geometry, typename Box,
0548     typename GeometryOut,
0549     overlay_type OverlayType,
0550     bool Reverse1, bool Reverse2,
0551     typename TagIn, typename TagOut
0552 >
0553 struct intersection_insert
0554     <
0555         Geometry, Box,
0556         GeometryOut,
0557         OverlayType,
0558         Reverse1, Reverse2,
0559         TagIn, box_tag, TagOut,
0560         areal_tag, areal_tag, areal_tag
0561     > : detail::overlay::overlay
0562         <
0563             Geometry, Box, Reverse1, Reverse2,
0564             detail::overlay::do_reverse<geometry::point_order<GeometryOut>::value>::value,
0565             GeometryOut, OverlayType
0566         >
0567 {};
0568 
0569 
0570 template
0571 <
0572     typename Segment1, typename Segment2,
0573     typename GeometryOut,
0574     overlay_type OverlayType,
0575     bool Reverse1, bool Reverse2
0576 >
0577 struct intersection_insert
0578     <
0579         Segment1, Segment2,
0580         GeometryOut,
0581         OverlayType,
0582         Reverse1, Reverse2,
0583         segment_tag, segment_tag, point_tag,
0584         linear_tag, linear_tag, pointlike_tag
0585     > : detail::intersection::intersection_segment_segment_point<GeometryOut>
0586 {};
0587 
0588 
0589 template
0590 <
0591     typename Linestring1, typename Linestring2,
0592     typename GeometryOut,
0593     overlay_type OverlayType,
0594     bool Reverse1, bool Reverse2
0595 >
0596 struct intersection_insert
0597     <
0598         Linestring1, Linestring2,
0599         GeometryOut,
0600         OverlayType,
0601         Reverse1, Reverse2,
0602         linestring_tag, linestring_tag, point_tag,
0603         linear_tag, linear_tag, pointlike_tag
0604     > : detail::intersection::intersection_linestring_linestring_point<GeometryOut>
0605 {};
0606 
0607 
0608 template
0609 <
0610     typename Linestring, typename Box,
0611     typename GeometryOut,
0612     bool Reverse1, bool Reverse2
0613 >
0614 struct intersection_insert
0615     <
0616         Linestring, Box,
0617         GeometryOut,
0618         overlay_intersection,
0619         Reverse1, Reverse2,
0620         linestring_tag, box_tag, linestring_tag,
0621         linear_tag, areal_tag, linear_tag
0622     >
0623 {
0624     template <typename OutputIterator, typename Strategy>
0625     static inline OutputIterator apply(Linestring const& linestring,
0626             Box const& box,
0627             OutputIterator out, Strategy const& )
0628     {
0629         strategy::intersection::liang_barsky<Box, point_type_t<GeometryOut>> lb_strategy;
0630         return detail::intersection::clip_range_with_box
0631             <GeometryOut>(box, linestring, out, lb_strategy);
0632     }
0633 };
0634 
0635 
0636 template
0637 <
0638     typename Linestring, typename Polygon,
0639     typename GeometryOut,
0640     overlay_type OverlayType,
0641     bool ReverseLinestring, bool ReversePolygon
0642 >
0643 struct intersection_insert
0644     <
0645         Linestring, Polygon,
0646         GeometryOut,
0647         OverlayType,
0648         ReverseLinestring, ReversePolygon,
0649         linestring_tag, polygon_tag, linestring_tag,
0650         linear_tag, areal_tag, linear_tag
0651     > : detail::intersection::intersection_of_linestring_with_areal
0652             <
0653                 ReversePolygon,
0654                 GeometryOut,
0655                 OverlayType,
0656                 false
0657             >
0658 {};
0659 
0660 
0661 template
0662 <
0663     typename Linestring, typename Ring,
0664     typename GeometryOut,
0665     overlay_type OverlayType,
0666     bool ReverseLinestring, bool ReverseRing
0667 >
0668 struct intersection_insert
0669     <
0670         Linestring, Ring,
0671         GeometryOut,
0672         OverlayType,
0673         ReverseLinestring, ReverseRing,
0674         linestring_tag, ring_tag, linestring_tag,
0675         linear_tag, areal_tag, linear_tag
0676     > : detail::intersection::intersection_of_linestring_with_areal
0677             <
0678                 ReverseRing,
0679                 GeometryOut,
0680                 OverlayType,
0681                 false
0682             >
0683 {};
0684 
0685 template
0686 <
0687     typename Segment, typename Box,
0688     typename GeometryOut,
0689     overlay_type OverlayType,
0690     bool Reverse1, bool Reverse2
0691 >
0692 struct intersection_insert
0693     <
0694         Segment, Box,
0695         GeometryOut,
0696         OverlayType,
0697         Reverse1, Reverse2,
0698         segment_tag, box_tag, linestring_tag,
0699         linear_tag, areal_tag, linear_tag
0700     >
0701 {
0702     template <typename OutputIterator, typename Strategy>
0703     static inline OutputIterator apply(Segment const& segment,
0704             Box const& box,
0705             OutputIterator out, Strategy const& )
0706     {
0707         geometry::segment_view<Segment> range(segment);
0708 
0709         strategy::intersection::liang_barsky<Box, point_type_t<GeometryOut>> lb_strategy;
0710         return detail::intersection::clip_range_with_box
0711             <GeometryOut>(box, range, out, lb_strategy);
0712     }
0713 };
0714 
0715 template
0716 <
0717     typename Geometry1, typename Geometry2,
0718     typename PointOut,
0719     overlay_type OverlayType,
0720     bool Reverse1, bool Reverse2,
0721     typename Tag1, typename Tag2
0722 >
0723 struct intersection_insert
0724     <
0725         Geometry1, Geometry2,
0726         PointOut,
0727         OverlayType,
0728         Reverse1, Reverse2,
0729         Tag1, Tag2, point_tag,
0730         areal_tag, areal_tag, pointlike_tag
0731     >
0732     : public detail::intersection::intersection_areal_areal_point
0733         <
0734             PointOut
0735         >
0736 {};
0737 
0738 template
0739 <
0740     typename Geometry1, typename Geometry2,
0741     typename PointOut,
0742     overlay_type OverlayType,
0743     bool Reverse1, bool Reverse2,
0744     typename Tag1, typename Tag2
0745 >
0746 struct intersection_insert
0747     <
0748         Geometry1, Geometry2,
0749         PointOut,
0750         OverlayType,
0751         Reverse1, Reverse2,
0752         Tag1, Tag2, point_tag,
0753         linear_tag, areal_tag, pointlike_tag
0754     >
0755     : public detail::intersection::intersection_linear_areal_point
0756         <
0757             PointOut
0758         >
0759 {};
0760 
0761 template
0762 <
0763     typename Geometry1, typename Geometry2,
0764     typename PointOut,
0765     overlay_type OverlayType,
0766     bool Reverse1, bool Reverse2,
0767     typename Tag1, typename Tag2
0768 >
0769 struct intersection_insert
0770     <
0771         Geometry1, Geometry2,
0772         PointOut,
0773         OverlayType,
0774         Reverse1, Reverse2,
0775         Tag1, Tag2, point_tag,
0776         areal_tag, linear_tag, pointlike_tag
0777     >
0778     : public detail::intersection::intersection_areal_linear_point
0779         <
0780             PointOut
0781         >
0782 {};
0783 
0784 template
0785 <
0786     typename Geometry1, typename Geometry2, typename GeometryOut,
0787     overlay_type OverlayType,
0788     bool Reverse1, bool Reverse2
0789 >
0790 struct intersection_insert_reversed
0791 {
0792     template <typename OutputIterator, typename Strategy>
0793     static inline OutputIterator apply(Geometry1 const& g1,
0794                 Geometry2 const& g2,
0795                 OutputIterator out,
0796                 Strategy const& strategy)
0797     {
0798         return intersection_insert
0799             <
0800                 Geometry2, Geometry1, GeometryOut,
0801                 OverlayType,
0802                 Reverse2, Reverse1
0803             >::apply(g2, g1, out, strategy);
0804     }
0805 };
0806 
0807 
0808 // dispatch for intersection(areal, areal, linear)
0809 template
0810 <
0811     typename Geometry1, typename Geometry2,
0812     typename LinestringOut,
0813     bool Reverse1, bool Reverse2,
0814     typename Tag1, typename Tag2
0815 >
0816 struct intersection_insert
0817     <
0818         Geometry1, Geometry2,
0819         LinestringOut,
0820         overlay_intersection,
0821         Reverse1, Reverse2,
0822         Tag1, Tag2, linestring_tag,
0823         areal_tag, areal_tag, linear_tag
0824     >
0825 {
0826     template
0827     <
0828         typename OutputIterator, typename Strategy
0829     >
0830     static inline OutputIterator apply(Geometry1 const& geometry1,
0831                                        Geometry2 const& geometry2,
0832                                        OutputIterator oit,
0833                                        Strategy const& strategy)
0834     {
0835         detail::boundary_view<Geometry1 const> view1(geometry1);
0836         detail::boundary_view<Geometry2 const> view2(geometry2);
0837 
0838         return detail::overlay::linear_linear_linestring
0839             <
0840                 detail::boundary_view<Geometry1 const>,
0841                 detail::boundary_view<Geometry2 const>,
0842                 LinestringOut,
0843                 overlay_intersection
0844             >::apply(view1, view2, oit, strategy);
0845     }
0846 };
0847 
0848 // dispatch for difference/intersection of linear geometries
0849 template
0850 <
0851     typename Linear1, typename Linear2, typename LineStringOut,
0852     overlay_type OverlayType,
0853     bool Reverse1, bool Reverse2,
0854     typename TagIn1, typename TagIn2
0855 >
0856 struct intersection_insert
0857     <
0858         Linear1, Linear2, LineStringOut, OverlayType,
0859         Reverse1, Reverse2,
0860         TagIn1, TagIn2, linestring_tag,
0861         linear_tag, linear_tag, linear_tag
0862     > : detail::overlay::linear_linear_linestring
0863         <
0864             Linear1, Linear2, LineStringOut, OverlayType
0865         >
0866 {};
0867 
0868 template
0869 <
0870     typename Linear1, typename Linear2, typename TupledOut,
0871     overlay_type OverlayType,
0872     bool Reverse1, bool Reverse2,
0873     typename TagIn1, typename TagIn2
0874 >
0875 struct intersection_insert
0876     <
0877         Linear1, Linear2, TupledOut, OverlayType,
0878         Reverse1, Reverse2,
0879         TagIn1, TagIn2, detail::tupled_output_tag,
0880         linear_tag, linear_tag, detail::tupled_output_tag
0881     >
0882     : detail::expect_output
0883         <
0884             Linear1, Linear2, TupledOut,
0885             // NOTE: points can be the result only in case of intersection.
0886             std::conditional_t
0887                 <
0888                     (OverlayType == overlay_intersection),
0889                     point_tag,
0890                     void
0891                 >,
0892             linestring_tag
0893         >
0894 {
0895     // NOTE: The order of geometries in TupledOut tuple/pair must correspond to the order
0896     // iterators in OutputIterators tuple/pair.
0897     template
0898     <
0899         typename OutputIterators, typename Strategy
0900     >
0901     static inline OutputIterators apply(Linear1 const& linear1,
0902                                         Linear2 const& linear2,
0903                                         OutputIterators oit,
0904                                         Strategy const& strategy)
0905     {
0906         return detail::overlay::linear_linear_linestring
0907             <
0908                 Linear1, Linear2, TupledOut, OverlayType
0909             >::apply(linear1, linear2, oit, strategy);
0910     }
0911 };
0912 
0913 
0914 // dispatch for difference/intersection of point-like geometries
0915 
0916 template
0917 <
0918     typename Point1, typename Point2, typename PointOut,
0919     overlay_type OverlayType,
0920     bool Reverse1, bool Reverse2
0921 >
0922 struct intersection_insert
0923     <
0924         Point1, Point2, PointOut, OverlayType,
0925         Reverse1, Reverse2,
0926         point_tag, point_tag, point_tag,
0927         pointlike_tag, pointlike_tag, pointlike_tag
0928     > : detail::overlay::point_point_point
0929         <
0930             Point1, Point2, PointOut, OverlayType
0931         >
0932 {};
0933 
0934 
0935 template
0936 <
0937     typename MultiPoint, typename Point, typename PointOut,
0938     overlay_type OverlayType,
0939     bool Reverse1, bool Reverse2
0940 >
0941 struct intersection_insert
0942     <
0943         MultiPoint, Point, PointOut, OverlayType,
0944         Reverse1, Reverse2,
0945         multi_point_tag, point_tag, point_tag,
0946         pointlike_tag, pointlike_tag, pointlike_tag
0947     > : detail::overlay::multipoint_point_point
0948         <
0949             MultiPoint, Point, PointOut, OverlayType
0950         >
0951 {};
0952 
0953 
0954 template
0955 <
0956     typename Point, typename MultiPoint, typename PointOut,
0957     overlay_type OverlayType,
0958     bool Reverse1, bool Reverse2
0959 >
0960 struct intersection_insert
0961     <
0962         Point, MultiPoint, PointOut, OverlayType,
0963         Reverse1, Reverse2,
0964         point_tag, multi_point_tag, point_tag,
0965         pointlike_tag, pointlike_tag, pointlike_tag
0966     > : detail::overlay::point_multipoint_point
0967         <
0968             Point, MultiPoint, PointOut, OverlayType
0969         >
0970 {};
0971 
0972 
0973 template
0974 <
0975     typename MultiPoint1, typename MultiPoint2, typename PointOut,
0976     overlay_type OverlayType,
0977     bool Reverse1, bool Reverse2
0978 >
0979 struct intersection_insert
0980     <
0981         MultiPoint1, MultiPoint2, PointOut, OverlayType,
0982         Reverse1, Reverse2,
0983         multi_point_tag, multi_point_tag, point_tag,
0984         pointlike_tag, pointlike_tag, pointlike_tag
0985     > : detail::overlay::multipoint_multipoint_point
0986         <
0987             MultiPoint1, MultiPoint2, PointOut, OverlayType
0988         >
0989 {};
0990 
0991 
0992 template
0993 <
0994     typename PointLike1, typename PointLike2, typename TupledOut,
0995     overlay_type OverlayType,
0996     bool Reverse1, bool Reverse2,
0997     typename TagIn1, typename TagIn2
0998 >
0999 struct intersection_insert
1000     <
1001         PointLike1, PointLike2, TupledOut, OverlayType,
1002         Reverse1, Reverse2,
1003         TagIn1, TagIn2, detail::tupled_output_tag,
1004         pointlike_tag, pointlike_tag, detail::tupled_output_tag
1005     >
1006     : detail::expect_output<PointLike1, PointLike2, TupledOut, point_tag>
1007 {
1008     // NOTE: The order of geometries in TupledOut tuple/pair must correspond to the order
1009     // of iterators in OutputIterators tuple/pair.
1010     template
1011     <
1012         typename OutputIterators, typename Strategy
1013     >
1014     static inline OutputIterators apply(PointLike1 const& pointlike1,
1015                                         PointLike2 const& pointlike2,
1016                                         OutputIterators oits,
1017                                         Strategy const& strategy)
1018     {
1019         namespace bgt = boost::geometry::tuples;
1020 
1021         static const bool out_point_index = bgt::find_index_if
1022             <
1023                 TupledOut, geometry::detail::is_tag_same_as_pred<point_tag>::template pred
1024             >::value;
1025 
1026         bgt::get<out_point_index>(oits) = intersection_insert
1027             <
1028                 PointLike1, PointLike2,
1029                 typename bgt::element
1030                     <
1031                         out_point_index, TupledOut
1032                     >::type,
1033                 OverlayType
1034             >::apply(pointlike1, pointlike2,
1035                      bgt::get<out_point_index>(oits),
1036                      strategy);
1037 
1038         return oits;
1039     }
1040 };
1041 
1042 
1043 // dispatch for difference/intersection of pointlike-linear geometries
1044 template
1045 <
1046     typename Point, typename Linear, typename PointOut,
1047     overlay_type OverlayType,
1048     bool Reverse1, bool Reverse2,
1049     typename Tag
1050 >
1051 struct intersection_insert
1052     <
1053         Point, Linear, PointOut, OverlayType,
1054         Reverse1, Reverse2,
1055         point_tag, Tag, point_tag,
1056         pointlike_tag, linear_tag, pointlike_tag
1057     > : detail_dispatch::overlay::pointlike_linear_point
1058         <
1059             Point, Linear, PointOut, OverlayType,
1060             point_tag, tag_cast_t<Tag, segment_tag, linear_tag>
1061         >
1062 {};
1063 
1064 
1065 template
1066 <
1067     typename MultiPoint, typename Linear, typename PointOut,
1068     overlay_type OverlayType,
1069     bool Reverse1, bool Reverse2,
1070     typename Tag
1071 >
1072 struct intersection_insert
1073     <
1074         MultiPoint, Linear, PointOut, OverlayType,
1075         Reverse1, Reverse2,
1076         multi_point_tag, Tag, point_tag,
1077         pointlike_tag, linear_tag, pointlike_tag
1078     > : detail_dispatch::overlay::pointlike_linear_point
1079         <
1080             MultiPoint, Linear, PointOut, OverlayType,
1081             multi_point_tag,
1082             tag_cast_t<Tag, segment_tag, linear_tag>
1083         >
1084 {};
1085 
1086 
1087 // This specialization is needed because intersection() reverses the arguments
1088 // for MultiPoint/Linestring combination.
1089 template
1090 <
1091     typename Linestring, typename MultiPoint, typename PointOut,
1092     bool Reverse1, bool Reverse2
1093 >
1094 struct intersection_insert
1095     <
1096         Linestring, MultiPoint, PointOut, overlay_intersection,
1097         Reverse1, Reverse2,
1098         linestring_tag, multi_point_tag, point_tag,
1099         linear_tag, pointlike_tag, pointlike_tag
1100     >
1101 {
1102     template <typename OutputIterator, typename Strategy>
1103     static inline OutputIterator apply(Linestring const& linestring,
1104                                        MultiPoint const& multipoint,
1105                                        OutputIterator out,
1106                                        Strategy const& strategy)
1107     {
1108         return detail_dispatch::overlay::pointlike_linear_point
1109             <
1110                 MultiPoint, Linestring, PointOut, overlay_intersection,
1111                 multi_point_tag, linear_tag
1112             >::apply(multipoint, linestring, out, strategy);
1113     }
1114 };
1115 
1116 
1117 template
1118 <
1119     typename PointLike, typename Linear, typename TupledOut,
1120     overlay_type OverlayType,
1121     bool Reverse1, bool Reverse2,
1122     typename TagIn1, typename TagIn2
1123 >
1124 struct intersection_insert
1125     <
1126         PointLike, Linear, TupledOut, OverlayType,
1127         Reverse1, Reverse2,
1128         TagIn1, TagIn2, detail::tupled_output_tag,
1129         pointlike_tag, linear_tag, detail::tupled_output_tag
1130     >
1131     // Reuse the implementation for PointLike/PointLike.
1132     : intersection_insert
1133         <
1134             PointLike, Linear, TupledOut, OverlayType,
1135             Reverse1, Reverse2,
1136             TagIn1, TagIn2, detail::tupled_output_tag,
1137             pointlike_tag, pointlike_tag, detail::tupled_output_tag
1138         >
1139 {};
1140 
1141 
1142 // This specialization is needed because intersection() reverses the arguments
1143 // for MultiPoint/Linestring combination.
1144 template
1145 <
1146     typename Linestring, typename MultiPoint, typename TupledOut,
1147     bool Reverse1, bool Reverse2
1148 >
1149 struct intersection_insert
1150     <
1151         Linestring, MultiPoint, TupledOut, overlay_intersection,
1152         Reverse1, Reverse2,
1153         linestring_tag, multi_point_tag, detail::tupled_output_tag,
1154         linear_tag, pointlike_tag, detail::tupled_output_tag
1155     >
1156 {
1157     template <typename OutputIterators, typename Strategy>
1158     static inline OutputIterators apply(Linestring const& linestring,
1159                                         MultiPoint const& multipoint,
1160                                         OutputIterators out,
1161                                         Strategy const& strategy)
1162     {
1163         return intersection_insert
1164             <
1165                 MultiPoint, Linestring, TupledOut, overlay_intersection
1166             >::apply(multipoint, linestring, out, strategy);
1167     }
1168 };
1169 
1170 
1171 // dispatch for difference/intersection of pointlike-areal geometries
1172 template
1173 <
1174     typename Point, typename Areal, typename PointOut,
1175     overlay_type OverlayType,
1176     bool Reverse1, bool Reverse2,
1177     typename ArealTag
1178 >
1179 struct intersection_insert
1180     <
1181         Point, Areal, PointOut, OverlayType,
1182         Reverse1, Reverse2,
1183         point_tag, ArealTag, point_tag,
1184         pointlike_tag, areal_tag, pointlike_tag
1185     > : detail_dispatch::overlay::pointlike_areal_point
1186         <
1187             Point, Areal, PointOut, OverlayType,
1188             point_tag, ArealTag
1189         >
1190 {};
1191 
1192 template
1193 <
1194     typename MultiPoint, typename Areal, typename PointOut,
1195     overlay_type OverlayType,
1196     bool Reverse1, bool Reverse2,
1197     typename ArealTag
1198 >
1199 struct intersection_insert
1200     <
1201         MultiPoint, Areal, PointOut, OverlayType,
1202         Reverse1, Reverse2,
1203         multi_point_tag, ArealTag, point_tag,
1204         pointlike_tag, areal_tag, pointlike_tag
1205     > : detail_dispatch::overlay::pointlike_areal_point
1206         <
1207             MultiPoint, Areal, PointOut, OverlayType,
1208             multi_point_tag, ArealTag
1209         >
1210 {};
1211 
1212 // This specialization is needed because intersection() reverses the arguments
1213 // for MultiPoint/Ring and MultiPoint/Polygon combinations.
1214 template
1215 <
1216     typename Areal, typename MultiPoint, typename PointOut,
1217     bool Reverse1, bool Reverse2,
1218     typename ArealTag
1219 >
1220 struct intersection_insert
1221     <
1222         Areal, MultiPoint, PointOut, overlay_intersection,
1223         Reverse1, Reverse2,
1224         ArealTag, multi_point_tag, point_tag,
1225         areal_tag, pointlike_tag, pointlike_tag
1226     >
1227 {
1228     template <typename OutputIterator, typename Strategy>
1229     static inline OutputIterator apply(Areal const& areal,
1230                                        MultiPoint const& multipoint,
1231                                        OutputIterator out,
1232                                        Strategy const& strategy)
1233     {
1234         return detail_dispatch::overlay::pointlike_areal_point
1235             <
1236                 MultiPoint, Areal, PointOut, overlay_intersection,
1237                 multi_point_tag, ArealTag
1238             >::apply(multipoint, areal, out, strategy);
1239     }
1240 };
1241 
1242 
1243 template
1244 <
1245     typename PointLike, typename Areal, typename TupledOut,
1246     overlay_type OverlayType,
1247     bool Reverse1, bool Reverse2,
1248     typename TagIn1, typename TagIn2
1249 >
1250 struct intersection_insert
1251     <
1252         PointLike, Areal, TupledOut, OverlayType,
1253         Reverse1, Reverse2,
1254         TagIn1, TagIn2, detail::tupled_output_tag,
1255         pointlike_tag, areal_tag, detail::tupled_output_tag
1256     >
1257     // Reuse the implementation for PointLike/PointLike.
1258     : intersection_insert
1259         <
1260             PointLike, Areal, TupledOut, OverlayType,
1261             Reverse1, Reverse2,
1262             TagIn1, TagIn2, detail::tupled_output_tag,
1263             pointlike_tag, pointlike_tag, detail::tupled_output_tag
1264         >
1265 {};
1266 
1267 
1268 // This specialization is needed because intersection() reverses the arguments
1269 // for MultiPoint/Ring and MultiPoint/Polygon combinations.
1270 template
1271 <
1272     typename Areal, typename MultiPoint, typename TupledOut,
1273     bool Reverse1, bool Reverse2,
1274     typename TagIn1
1275 >
1276 struct intersection_insert
1277     <
1278         Areal, MultiPoint, TupledOut, overlay_intersection,
1279         Reverse1, Reverse2,
1280         TagIn1, multi_point_tag, detail::tupled_output_tag,
1281         areal_tag, pointlike_tag, detail::tupled_output_tag
1282     >
1283 {
1284     template <typename OutputIterators, typename Strategy>
1285     static inline OutputIterators apply(Areal const& areal,
1286                                         MultiPoint const& multipoint,
1287                                         OutputIterators out,
1288                                         Strategy const& strategy)
1289     {
1290         return intersection_insert
1291             <
1292                 MultiPoint, Areal, TupledOut, overlay_intersection
1293             >::apply(multipoint, areal, out, strategy);
1294     }
1295 };
1296 
1297 
1298 template
1299 <
1300     typename Linestring, typename Polygon,
1301     typename TupledOut,
1302     overlay_type OverlayType,
1303     bool ReverseLinestring, bool ReversePolygon
1304 >
1305 struct intersection_insert
1306     <
1307         Linestring, Polygon,
1308         TupledOut,
1309         OverlayType,
1310         ReverseLinestring, ReversePolygon,
1311         linestring_tag, polygon_tag, detail::tupled_output_tag,
1312         linear_tag, areal_tag, detail::tupled_output_tag
1313     > : detail::intersection::intersection_of_linestring_with_areal
1314             <
1315                 ReversePolygon,
1316                 TupledOut,
1317                 OverlayType,
1318                 true
1319             >
1320 {};
1321 
1322 template
1323 <
1324     typename Linestring, typename Ring,
1325     typename TupledOut,
1326     overlay_type OverlayType,
1327     bool ReverseLinestring, bool ReverseRing
1328 >
1329 struct intersection_insert
1330     <
1331         Linestring, Ring,
1332         TupledOut,
1333         OverlayType,
1334         ReverseLinestring, ReverseRing,
1335         linestring_tag, ring_tag, detail::tupled_output_tag,
1336         linear_tag, areal_tag, detail::tupled_output_tag
1337     > : detail::intersection::intersection_of_linestring_with_areal
1338             <
1339                 ReverseRing,
1340                 TupledOut,
1341                 OverlayType,
1342                 true
1343             >
1344 {};
1345 
1346 
1347 } // namespace dispatch
1348 #endif // DOXYGEN_NO_DISPATCH
1349 
1350 
1351 #ifndef DOXYGEN_NO_DETAIL
1352 namespace detail { namespace intersection
1353 {
1354 
1355 
1356 template
1357 <
1358     typename GeometryOut,
1359     bool ReverseSecond,
1360     overlay_type OverlayType,
1361     typename Geometry1, typename Geometry2,
1362     typename OutputIterator,
1363     typename Strategy
1364 >
1365 inline OutputIterator insert(Geometry1 const& geometry1,
1366             Geometry2 const& geometry2,
1367             OutputIterator out,
1368             Strategy const& strategy)
1369 {
1370     return std::conditional_t
1371         <
1372             geometry::reverse_dispatch<Geometry1, Geometry2>::type::value,
1373             geometry::dispatch::intersection_insert_reversed
1374             <
1375                 Geometry1, Geometry2,
1376                 GeometryOut,
1377                 OverlayType,
1378                 overlay::do_reverse<geometry::point_order<Geometry1>::value>::value,
1379                 overlay::do_reverse<geometry::point_order<Geometry2>::value, ReverseSecond>::value
1380             >,
1381             geometry::dispatch::intersection_insert
1382             <
1383                 Geometry1, Geometry2,
1384                 GeometryOut,
1385                 OverlayType,
1386                 geometry::detail::overlay::do_reverse<geometry::point_order<Geometry1>::value>::value,
1387                 geometry::detail::overlay::do_reverse<geometry::point_order<Geometry2>::value, ReverseSecond>::value
1388             >
1389         >::apply(geometry1, geometry2, out, strategy);
1390 }
1391 
1392 
1393 /*!
1394 \brief \brief_calc2{intersection} \brief_strategy
1395 \ingroup intersection
1396 \details \details_calc2{intersection_insert, spatial set theoretic intersection}
1397     \brief_strategy. \details_insert{intersection}
1398 \tparam GeometryOut \tparam_geometry{\p_l_or_c}
1399 \tparam Geometry1 \tparam_geometry
1400 \tparam Geometry2 \tparam_geometry
1401 \tparam OutputIterator \tparam_out{\p_l_or_c}
1402 \tparam Strategy \tparam_strategy_overlay
1403 \param geometry1 \param_geometry
1404 \param geometry2 \param_geometry
1405 \param out \param_out{intersection}
1406 \param strategy \param_strategy{intersection}
1407 \return \return_out
1408 
1409 \qbk{distinguish,with strategy}
1410 \qbk{[include reference/algorithms/intersection.qbk]}
1411 */
1412 template
1413 <
1414     typename GeometryOut,
1415     typename Geometry1,
1416     typename Geometry2,
1417     typename OutputIterator,
1418     typename Strategy
1419 >
1420 inline OutputIterator intersection_insert(Geometry1 const& geometry1,
1421             Geometry2 const& geometry2,
1422             OutputIterator out,
1423             Strategy const& strategy)
1424 {
1425     concepts::check<Geometry1 const>();
1426     concepts::check<Geometry2 const>();
1427 
1428     return detail::intersection::insert
1429         <
1430             GeometryOut, false, overlay_intersection
1431         >(geometry1, geometry2, out, strategy);
1432 }
1433 
1434 
1435 /*!
1436 \brief \brief_calc2{intersection}
1437 \ingroup intersection
1438 \details \details_calc2{intersection_insert, spatial set theoretic intersection}.
1439     \details_insert{intersection}
1440 \tparam GeometryOut \tparam_geometry{\p_l_or_c}
1441 \tparam Geometry1 \tparam_geometry
1442 \tparam Geometry2 \tparam_geometry
1443 \tparam OutputIterator \tparam_out{\p_l_or_c}
1444 \param geometry1 \param_geometry
1445 \param geometry2 \param_geometry
1446 \param out \param_out{intersection}
1447 \return \return_out
1448 
1449 \qbk{[include reference/algorithms/intersection.qbk]}
1450 */
1451 template
1452 <
1453     typename GeometryOut,
1454     typename Geometry1,
1455     typename Geometry2,
1456     typename OutputIterator
1457 >
1458 inline OutputIterator intersection_insert(Geometry1 const& geometry1,
1459             Geometry2 const& geometry2,
1460             OutputIterator out)
1461 {
1462     concepts::check<Geometry1 const>();
1463     concepts::check<Geometry2 const>();
1464 
1465     using strategy_type = typename strategies::relate::services::default_strategy
1466         <
1467             Geometry1, Geometry2
1468         >::type;
1469 
1470     return intersection_insert<GeometryOut>(geometry1, geometry2, out,
1471                                             strategy_type());
1472 }
1473 
1474 }} // namespace detail::intersection
1475 #endif // DOXYGEN_NO_DETAIL
1476 
1477 
1478 
1479 }} // namespace boost::geometry
1480 
1481 
1482 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_INTERSECTION_INSERT_HPP
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.3.7 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!