1 // Copyright (c) 2006,2007,2009,2010,2011 Tel-Aviv University (Israel).
2 // All rights reserved.
3 //
4 // This file is part of CGAL (www.cgal.org).
5 //
6 // $URL: https://github.com/CGAL/cgal/blob/v5.3/Arrangement_on_surface_2/include/CGAL/Arr_point_location/Arr_naive_point_location_impl.h $
7 // $Id: Arr_naive_point_location_impl.h 0779373 2020-03-26T13:31:46+01:00 Sébastien Loriot
8 // SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial
9 //
10 //
11 // Author(s) : Ron Wein <wein@post.tau.ac.il>
12 // (based on old version by Eyal Flato)
13 // Efi Fogel <efif@post.tau.ac.il>
14
15 #ifndef CGAL_ARR_NAIVE_POINT_LOCATION_FUNCTIONS_H
16 #define CGAL_ARR_NAIVE_POINT_LOCATION_FUNCTIONS_H
17
18 #include <CGAL/license/Arrangement_on_surface_2.h>
19
20
21 /*! \file
22 * Member-function definitions for the Arr_naive_point_location<Arrangement>
23 * class.
24 */
25
26 namespace CGAL {
27
28 //-----------------------------------------------------------------------------
29 // Locate the arrangement feature containing the given point.
30 //
31 template <class Arrangement>
32 typename Arr_naive_point_location<Arrangement>::Result_type
locate(const Point_2 & p)33 Arr_naive_point_location<Arrangement>::locate(const Point_2& p) const
34 {
35 // Go over the arrangement vertices and check whether one of them equals
36 // the query point.
37 typename Traits_adaptor_2::Equal_2 equal = geom_traits->equal_2_object();
38 typename Arrangement_2::Vertex_const_iterator vit;
39 Vertex_const_handle vh;
40
41 for (vit = p_arr->vertices_begin(); vit != p_arr->vertices_end(); ++vit) {
42 vh = vit;
43 if (equal(p, vh->point()))
44 return make_result(vh);
45 }
46
47 // Go over arrangement halfedges and check whether one of them contains
48 // the query point in its interior.
49 typename Traits_adaptor_2::Is_in_x_range_2 is_in_x_range =
50 geom_traits->is_in_x_range_2_object();
51 typename Traits_adaptor_2::Compare_y_at_x_2 compare_y_at_x =
52 geom_traits->compare_y_at_x_2_object();
53 typename Arrangement_2::Edge_const_iterator eit;
54 Halfedge_const_handle hh;
55
56 for (eit = p_arr->edges_begin(); eit != p_arr->edges_end(); ++eit) {
57 hh = eit;
58
59 if (is_in_x_range(hh->curve(), p) && compare_y_at_x(p, hh->curve()) == EQUAL)
60 return make_result(hh);
61 }
62
63 // Go over all faces an locate the innermost one that contains the query
64 // point in its interior.
65 typename Arrangement_2::Face_const_iterator fit;
66 Face_const_handle fh;
67 Face_const_handle f_inner;
68 const Face_const_handle invalid_f;
69
70 for (fit = p_arr->faces_begin(); fit != p_arr->faces_end(); ++fit) {
71 fh = fit;
72
73 if (top_traits->is_in_face(&(*fh), p, nullptr)) {
74 // The current face contains p in its interior.
75 if (f_inner == invalid_f ||
76 f_inner->is_unbounded() ||
77 f_inner->number_of_outer_ccbs() == 0)
78 {
79 // This is the first face that contains p we encounter:
80 f_inner = fh;
81 }
82 else if (! fh->is_unbounded() && fh->number_of_outer_ccbs() > 0)
83 {
84 // As we have already some other containing face, one face must be
85 // contained inside the other. To check that, we select a
86 // representative vertex of inner_f and check whether it is contained
87 // in our current face.
88
89 // This is a workaround for MSVC. For some reason the compiler barfs
90 // when the iterator is not saved in a variable and only then the
91 // source() of its value_type is accessed.
92 typename Arrangement_2::Outer_ccb_const_iterator it =
93 fh->outer_ccbs_begin();
94 Vertex_const_handle v = (*it)->source();
95
96 if (top_traits->is_in_face(&(*f_inner), v->point(), nullptr))
97 f_inner = fh;
98 }
99 }
100 }
101
102 // Return the innermost face.
103 CGAL_assertion(f_inner != invalid_f);
104 return make_result(f_inner);
105 }
106
107 } //namespace CGAL
108
109 #endif
110