67e0916a0e7b948e30d8adfb7958a1ec4ea4cef3
[WebKit-https.git] / Source / WebCore / platform / graphics / FloatPolygon.h
1 /*
2  * Copyright (C) 2012 Adobe Systems Incorporated. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  *
8  * 1. Redistributions of source code must retain the above
9  *    copyright notice, this list of conditions and the following
10  *    disclaimer.
11  * 2. Redistributions in binary form must reproduce the above
12  *    copyright notice, this list of conditions and the following
13  *    disclaimer in the documentation and/or other materials
14  *    provided with the distribution.
15  * 
16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
19  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
20  * COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
21  * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
22  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
23  * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
25  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
26  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
27  * OF THE POSSIBILITY OF SUCH DAMAGE.
28  */
29
30 #ifndef FloatPolygon_h
31 #define FloatPolygon_h
32
33 #include "FloatPoint.h"
34 #include "FloatRect.h"
35 #include "PODIntervalTree.h"
36 #include "WindRule.h"
37 #include <wtf/OwnPtr.h>
38 #include <wtf/PassOwnPtr.h>
39 #include <wtf/Vector.h>
40
41 namespace WebCore {
42
43 class FloatPolygonEdge;
44
45 // This class is used by PODIntervalTree for debugging.
46 #ifndef NDEBUG
47 template <class> struct ValueToString;
48 #endif
49
50 class FloatPolygon {
51 public:
52     FloatPolygon(PassOwnPtr<Vector<FloatPoint>> vertices, WindRule fillRule);
53
54     const FloatPoint& vertexAt(unsigned index) const { return (*m_vertices)[index]; }
55     unsigned numberOfVertices() const { return m_vertices->size(); }
56
57     WindRule fillRule() const { return m_fillRule; }
58
59     const FloatPolygonEdge& edgeAt(unsigned index) const { return m_edges[index]; }
60     unsigned numberOfEdges() const { return m_edges.size(); }
61
62     FloatRect boundingBox() const { return m_boundingBox; }
63     bool overlappingEdges(float minY, float maxY, Vector<const FloatPolygonEdge*>& result) const;
64     bool contains(const FloatPoint&) const;
65     bool isEmpty() const { return m_empty; }
66
67 private:
68     typedef PODInterval<float, FloatPolygonEdge*> EdgeInterval;
69     typedef PODIntervalTree<float, FloatPolygonEdge*> EdgeIntervalTree;
70
71     bool containsNonZero(const FloatPoint&) const;
72     bool containsEvenOdd(const FloatPoint&) const;
73
74     OwnPtr<Vector<FloatPoint>> m_vertices;
75     WindRule m_fillRule;
76     FloatRect m_boundingBox;
77     bool m_empty;
78     Vector<FloatPolygonEdge> m_edges;
79     EdgeIntervalTree m_edgeTree; // Each EdgeIntervalTree node stores minY, maxY, and a ("UserData") pointer to a FloatPolygonEdge.
80
81 };
82
83 class VertexPair {
84 public:
85     virtual ~VertexPair() { }
86
87     virtual const FloatPoint& vertex1() const = 0;
88     virtual const FloatPoint& vertex2() const = 0;
89
90     float minX() const { return std::min(vertex1().x(), vertex2().x()); }
91     float minY() const { return std::min(vertex1().y(), vertex2().y()); }
92     float maxX() const { return std::max(vertex1().x(), vertex2().x()); }
93     float maxY() const { return std::max(vertex1().y(), vertex2().y()); }
94
95     bool overlapsRect(const FloatRect&) const;
96     bool intersection(const VertexPair&, FloatPoint&) const;
97 };
98
99 class FloatPolygonEdge : public VertexPair {
100     friend class FloatPolygon;
101 public:
102     virtual const FloatPoint& vertex1() const OVERRIDE
103     {
104         ASSERT(m_polygon);
105         return m_polygon->vertexAt(m_vertexIndex1);
106     }
107
108     virtual const FloatPoint& vertex2() const OVERRIDE
109     {
110         ASSERT(m_polygon);
111         return m_polygon->vertexAt(m_vertexIndex2);
112     }
113
114     const FloatPolygonEdge& previousEdge() const
115     {
116         ASSERT(m_polygon && m_polygon->numberOfEdges() > 1);
117         return m_polygon->edgeAt((m_edgeIndex + m_polygon->numberOfEdges() - 1) % m_polygon->numberOfEdges());
118     }
119
120     const FloatPolygonEdge& nextEdge() const
121     {
122         ASSERT(m_polygon && m_polygon->numberOfEdges() > 1);
123         return m_polygon->edgeAt((m_edgeIndex + 1) % m_polygon->numberOfEdges());
124     }
125
126     const FloatPolygon* polygon() const { return m_polygon; }
127     unsigned vertexIndex1() const { return m_vertexIndex1; }
128     unsigned vertexIndex2() const { return m_vertexIndex2; }
129     unsigned edgeIndex() const { return m_edgeIndex; }
130
131 private:
132     // Edge vertex index1 is less than index2, except the last edge, where index2 is 0. When a polygon edge
133     // is defined by 3 or more colinear vertices, index2 can be the the index of the last colinear vertex.
134     unsigned m_vertexIndex1;
135     unsigned m_vertexIndex2;
136     unsigned m_edgeIndex;
137     const FloatPolygon* m_polygon;
138 };
139
140 // These structures are used by PODIntervalTree for debugging.
141 #ifndef NDEBUG
142 template <> struct ValueToString<float> {
143     static String string(const float value) { return String::number(value); }
144 };
145
146 template<> struct ValueToString<FloatPolygonEdge*> {
147     static String string(const FloatPolygonEdge* edge) { return String::format("%p (%f,%f %f,%f)", edge, edge->vertex1().x(), edge->vertex1().y(), edge->vertex2().x(), edge->vertex2().y()); }
148 };
149 #endif
150
151 } // namespace WebCore
152
153 #endif // FloatPolygon_h