]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Boost.Geometry (aka GGL, Generic Geometry Library) |
2 | ||
3 | // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands. | |
4 | // Copyright (c) 2008-2012 Bruno Lalande, Paris, France. | |
5 | // Copyright (c) 2009-2012 Mateusz Loskot, London, UK. | |
6 | ||
7 | // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library | |
8 | // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands. | |
9 | ||
10 | // Use, modification and distribution is subject to the Boost Software License, | |
11 | // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
12 | // http://www.boost.org/LICENSE_1_0.txt) | |
13 | ||
14 | #ifndef BOOST_GEOMETRY_STRATEGIES_CARTESIAN_POINT_IN_POLY_FRANKLIN_HPP | |
15 | #define BOOST_GEOMETRY_STRATEGIES_CARTESIAN_POINT_IN_POLY_FRANKLIN_HPP | |
16 | ||
17 | ||
18 | #include <boost/geometry/core/coordinate_type.hpp> | |
19 | #include <boost/geometry/util/select_calculation_type.hpp> | |
20 | ||
21 | ||
22 | namespace boost { namespace geometry | |
23 | { | |
24 | ||
25 | namespace strategy { namespace within | |
26 | { | |
27 | ||
28 | /*! | |
29 | \brief Within detection using cross counting | |
30 | \ingroup strategies | |
31 | \tparam Point \tparam_point | |
32 | \tparam PointOfSegment \tparam_segment_point | |
33 | \tparam CalculationType \tparam_calculation | |
34 | \author adapted from Randolph Franklin algorithm | |
35 | \author Barend and Maarten, 1995 | |
36 | \author Revised for templatized library, Barend Gehrels, 2007 | |
37 | \return true if point is in ring, works for closed rings in both directions | |
38 | \note Does NOT work correctly for point ON border | |
39 | ||
40 | \qbk{ | |
41 | [heading See also] | |
42 | [link geometry.reference.algorithms.within.within_3_with_strategy within (with strategy)] | |
43 | } | |
44 | */ | |
45 | ||
46 | template | |
47 | < | |
48 | typename Point, | |
49 | typename PointOfSegment = Point, | |
50 | typename CalculationType = void | |
51 | > | |
52 | class franklin | |
53 | { | |
54 | typedef typename select_calculation_type | |
55 | < | |
56 | Point, | |
57 | PointOfSegment, | |
58 | CalculationType | |
59 | >::type calculation_type; | |
60 | ||
61 | /*! subclass to keep state */ | |
62 | class crossings | |
63 | { | |
64 | bool crosses; | |
65 | ||
66 | public : | |
67 | ||
68 | friend class franklin; | |
69 | inline crossings() | |
70 | : crosses(false) | |
71 | {} | |
72 | }; | |
73 | ||
74 | public : | |
75 | ||
76 | typedef Point point_type; | |
77 | typedef PointOfSegment segment_point_type; | |
78 | typedef crossings state_type; | |
79 | ||
80 | static inline bool apply(Point const& point, | |
81 | PointOfSegment const& seg1, PointOfSegment const& seg2, | |
82 | crossings& state) | |
83 | { | |
84 | calculation_type const& px = get<0>(point); | |
85 | calculation_type const& py = get<1>(point); | |
86 | calculation_type const& x1 = get<0>(seg1); | |
87 | calculation_type const& y1 = get<1>(seg1); | |
88 | calculation_type const& x2 = get<0>(seg2); | |
89 | calculation_type const& y2 = get<1>(seg2); | |
90 | ||
91 | if ( | |
92 | ( (y2 <= py && py < y1) || (y1 <= py && py < y2) ) | |
93 | && (px < (x1 - x2) * (py - y2) / (y1 - y2) + x2) | |
94 | ) | |
95 | { | |
96 | state.crosses = ! state.crosses; | |
97 | } | |
98 | return true; | |
99 | } | |
100 | ||
101 | static inline int result(crossings const& state) | |
102 | { | |
103 | return state.crosses ? 1 : -1; | |
104 | } | |
105 | }; | |
106 | ||
107 | ||
108 | ||
109 | }} // namespace strategy::within | |
110 | ||
111 | ||
112 | ||
113 | ||
114 | ||
115 | }} // namespace boost::geometry | |
116 | ||
117 | ||
118 | #endif // BOOST_GEOMETRY_STRATEGIES_CARTESIAN_POINT_IN_POLY_FRANKLIN_HPP |