]>
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_CROSSINGS_MULTIPLY_HPP | |
15 | #define BOOST_GEOMETRY_STRATEGIES_CARTESIAN_POINT_IN_POLY_CROSSINGS_MULTIPLY_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 | \see http://tog.acm.org/resources/GraphicsGems/gemsiv/ptpoly_haines/ptinpoly.c | |
35 | \note Does NOT work correctly for point ON border | |
36 | \qbk{ | |
37 | [heading See also] | |
38 | [link geometry.reference.algorithms.within.within_3_with_strategy within (with strategy)] | |
39 | } | |
40 | */ | |
41 | ||
42 | template | |
43 | < | |
44 | typename Point, | |
45 | typename PointOfSegment = Point, | |
46 | typename CalculationType = void | |
47 | > | |
48 | class crossings_multiply | |
49 | { | |
50 | typedef typename select_calculation_type | |
51 | < | |
52 | Point, | |
53 | PointOfSegment, | |
54 | CalculationType | |
55 | >::type calculation_type; | |
56 | ||
57 | class flags | |
58 | { | |
59 | bool inside_flag; | |
60 | bool first; | |
61 | bool yflag0; | |
62 | ||
63 | public : | |
64 | ||
65 | friend class crossings_multiply; | |
66 | ||
67 | inline flags() | |
68 | : inside_flag(false) | |
69 | , first(true) | |
70 | , yflag0(false) | |
71 | {} | |
72 | }; | |
73 | ||
74 | public : | |
75 | ||
76 | typedef Point point_type; | |
77 | typedef PointOfSegment segment_point_type; | |
78 | typedef flags state_type; | |
79 | ||
80 | static inline bool apply(Point const& point, | |
81 | PointOfSegment const& seg1, PointOfSegment const& seg2, | |
82 | flags& state) | |
83 | { | |
84 | calculation_type const tx = get<0>(point); | |
85 | calculation_type const ty = get<1>(point); | |
86 | calculation_type const x0 = get<0>(seg1); | |
87 | calculation_type const y0 = get<1>(seg1); | |
88 | calculation_type const x1 = get<0>(seg2); | |
89 | calculation_type const y1 = get<1>(seg2); | |
90 | ||
91 | if (state.first) | |
92 | { | |
93 | state.first = false; | |
94 | state.yflag0 = y0 >= ty; | |
95 | } | |
96 | ||
97 | ||
98 | bool yflag1 = y1 >= ty; | |
99 | if (state.yflag0 != yflag1) | |
100 | { | |
101 | if ( ((y1-ty) * (x0-x1) >= (x1-tx) * (y0-y1)) == yflag1 ) | |
102 | { | |
103 | state.inside_flag = ! state.inside_flag; | |
104 | } | |
105 | } | |
106 | state.yflag0 = yflag1; | |
107 | return true; | |
108 | } | |
109 | ||
110 | static inline int result(flags const& state) | |
111 | { | |
112 | return state.inside_flag ? 1 : -1; | |
113 | } | |
114 | }; | |
115 | ||
116 | ||
117 | ||
118 | }} // namespace strategy::within | |
119 | ||
120 | ||
121 | }} // namespace boost::geometry | |
122 | ||
123 | ||
124 | #endif // BOOST_GEOMETRY_STRATEGIES_CARTESIAN_POINT_IN_POLY_CROSSINGS_MULTIPLY_HPP |