// Copyright (c) 2006,2007,2009,2010,2011 Tel-Aviv University (Israel). // All rights reserved. // // This file is part of CGAL (www.cgal.org). // // $URL: https://github.com/CGAL/cgal/blob/v5.2/Surface_sweep_2/include/CGAL/Surface_sweep_2/Event_comparer.h $ // $Id: Event_comparer.h 0779373 2020-03-26T13:31:46+01:00 Sébastien Loriot // SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial // // Author(s) : Tali Zvi // Baruch Zukerman // Ron Wein // Efi Fogel #ifndef CGAL_SURFACE_SWEEP_2_EVENT_COMPARER_H #define CGAL_SURFACE_SWEEP_2_EVENT_COMPARER_H #include /*! \file * * Comparison functor of curves used by the surface-sweep algorithm. */ #include #include #include namespace CGAL { namespace Surface_sweep_2 { /*! \class * A functor used to compare events and event points in an xy-lexicographic * order. Used to maintain the order of the event queue (the X-structure) * in the sweep-line algorithm. */ template class Event_comparer { public: typedef GeometryTraits_2 Geometry_traits_2; typedef Event_ Event; private: typedef Geometry_traits_2 Gt2; public: typedef typename Gt2::Point_2 Point_2; typedef typename Gt2::X_monotone_curve_2 X_monotone_curve_2; // should be ok, as Gt2 is supposed to be the adaptor typedef typename Gt2::Left_side_category Left_side_category; typedef typename Gt2::Bottom_side_category Bottom_side_category; typedef typename Gt2::Top_side_category Top_side_category; typedef typename Gt2::Right_side_category Right_side_category; private: // Data members: const Gt2* m_traits; // The geometric-traits object. Arr_parameter_space m_ps_in_x; // Storing curve information when Arr_parameter_space m_ps_in_y; // comparing a curve end with Arr_curve_end m_index; // boundary conditions. public: /*! Cosntruct. */ Event_comparer(const Gt2* traits) : m_traits(traits) {} /*! Compare two existing events. * This operator is called by the multiset assertions only in * debug mode (to verify that event was inserted at the right place). */ Comparison_result operator()(const Event* e1, const Event* e2) const { const bool on_boundary1 = e1->is_on_boundary(); const bool on_boundary2 = e2->is_on_boundary(); if (! on_boundary1 && ! on_boundary2) { // Both events do not have boundary conditions - just compare the points. return m_traits->compare_xy_2_object()(e1->point(), e2->point()); } if (! on_boundary1) { // Compare the point associated with the first event with the second // boundary event. return this->operator()(e1->point(), e2); } if (! on_boundary2) { // Compare the point associated with the second event with the first // boundary event. return CGAL::opposite(this->operator()(e2->point(), e1)); } return _compare_curve_end_with_event(e1->curve(), _curve_end(e1), e1->parameter_space_in_x(), e1->parameter_space_in_y(), e2); } /*! Compare a point, which should be inserted into the event queue, * with an existing event point. */ Comparison_result operator()(const Point_2& pt, const Event* e2) const { const bool on_boundary2 = e2->is_on_boundary(); if (! on_boundary2) { // If e2 is a normal event, just compare pt and the event point. return m_traits->compare_xy_2_object() (pt, e2->point()); } // Get the sign of the event's boundary condition in x. Note that a valid // point is always larger than any negative boundary event and smaller // than any positive boundary event. Arr_parameter_space ps_x2 = e2->parameter_space_in_x(); if (ps_x2 == ARR_LEFT_BOUNDARY) return LARGER; else if (ps_x2 == ARR_RIGHT_BOUNDARY) return SMALLER; // Get the curve end that e2 represents, and compare the x-position of the // given point and this curve end. Arr_curve_end ind = _curve_end(e2); Comparison_result res = m_traits->compare_x_point_curve_end_2_object()(pt, e2->curve(), ind); if (res != EQUAL) return res; // The event and the point has the same x-position. Get the sign of the // event's boundary condition in y. Note that a valid point is always // larger than any negative boundary event and smaller than any positive // boundary event. Arr_parameter_space ps_y2 = e2->parameter_space_in_y(); CGAL_assertion (ps_y2 != ARR_INTERIOR); return (ps_y2 == ARR_BOTTOM_BOUNDARY) ? LARGER : SMALLER; } /*! Compare a curve end, which should be inserted into the event queue, * with an existing event point. * Note that the index of the curve end as well as its boundary conditions * must be set beforehand using set_index() and set_parameter_space_in_x/y(). */ Comparison_result operator()(const X_monotone_curve_2& cv, const Event* e2) const { return _compare_curve_end_with_event(cv, m_index, m_ps_in_x, m_ps_in_y, e2); } /// \name Set the boundary conditions of a curve end we are about to compare. //@{ void set_parameter_space_in_x(Arr_parameter_space bx) { m_ps_in_x = bx; } void set_parameter_space_in_y(Arr_parameter_space by) { m_ps_in_y = by; } void set_index(Arr_curve_end ind) { m_index = ind; } //@} private: /*! Compare a given curve end with an event. * \param cv The curve. * \param ind The curve end. * \param ps_x The boundary condition of the curve end in x. * \param ps_y The boundary condition of the curve end in y. * \param e2 The event, which may have boundary conditions. * \return The comparison result of the curve end with the event. */ Comparison_result _compare_curve_end_with_event(const X_monotone_curve_2& cv, Arr_curve_end ind, Arr_parameter_space ps_x, Arr_parameter_space ps_y, const Event* e2) const { // Check if the curve end has a boundary condition in x. if (ps_x == ARR_LEFT_BOUNDARY) { if (e2->parameter_space_in_x() == ARR_LEFT_BOUNDARY) { // Both defined on the left boundary - compare them there. CGAL_assertion (ind == ARR_MIN_END); return m_traits->compare_y_curve_ends_2_object() (cv, e2->curve(), ind); } // The curve end is obviously smaller. return SMALLER; } if (ps_x == ARR_RIGHT_BOUNDARY) { if (e2->parameter_space_in_x() == ARR_RIGHT_BOUNDARY) { // Both defined on the right boundary - compare them there. CGAL_assertion (ind == ARR_MAX_END); return m_traits->compare_y_curve_ends_2_object()(cv, e2->curve(), ind); } // The curve end is obviously larger. return LARGER; } // Check if the event has a boundary condition in x. Note that if it // has a negative boundary condition, the curve end is larger than it, // and if it has a positive boundary condition, the curve end is smaller. if (e2->parameter_space_in_x() == ARR_LEFT_BOUNDARY) return (LARGER); if (e2->parameter_space_in_x() == ARR_RIGHT_BOUNDARY) return (SMALLER); CGAL_assertion(ps_y != ARR_INTERIOR); Comparison_result res; Arr_curve_end ind2 = _curve_end(e2); // Act according to the boundary sign of the event. if (e2->parameter_space_in_y() == ARR_BOTTOM_BOUNDARY) { // Compare the x-positions of the two entities. res = m_traits->compare_x_curve_ends_2_object()(cv, ind, e2->curve(), ind2); if (res != EQUAL) return res; // In case of equal x-positions, the curve end is larger than the event, // which lies on the bottom boundary (unless it also lies on the bottom // boundary). if (ps_y == ARR_BOTTOM_BOUNDARY) return EQUAL; return (LARGER); } if (e2->parameter_space_in_y() == ARR_TOP_BOUNDARY) { // Compare the x-positions of the two entities. res = m_traits->compare_x_curve_ends_2_object()(cv, ind, e2->curve(), ind2); if (res != EQUAL) return res; // In case of equal x-positions, the curve end is smaller than the event, // which lies on the top boundary (unless it also lies on the top // boundary). if (ps_y == ARR_TOP_BOUNDARY) return EQUAL; return SMALLER; } // If we reached here, e2 is not a boundary event and is associated with // a valid point. We compare the x-position of this point with the curve // end. res = m_traits->compare_x_point_curve_end_2_object()(e2->point(), cv, ind); if (res != EQUAL) return CGAL::opposite(res); // In case of equal x-positions, is the curve end has a negative boundary // sign, then it lies on the bottom boundary below the event. Otherwise, // it lies on the top aboundary above the event e2. return (ps_y == ARR_BOTTOM_BOUNDARY) ? SMALLER : LARGER; } /*! Detemine if the given event represents a left or a right curve end. */ inline Arr_curve_end _curve_end(const Event* e) const { return (e->has_left_curves()) ? ((e->is_right_end()) ? ARR_MAX_END : ARR_MIN_END) : ((e->is_left_end()) ? ARR_MIN_END : ARR_MAX_END); } }; } // namespace Surface_sweep_2 } // namespace CGAL #endif