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#pragma once
31
32#include "FloatPoint.h"
33#include "FloatRect.h"
34#include "PODIntervalTree.h"
35#include "WindRule.h"
36#include <memory>
37#include <wtf/Vector.h>
38
39namespace WebCore {
40
41class FloatPolygonEdge;
42
43class FloatPolygon {
44public:
45 FloatPolygon(std::unique_ptr<Vector<FloatPoint>> vertices, WindRule fillRule);
46
47 const FloatPoint& vertexAt(unsigned index) const { return (*m_vertices)[index]; }
48 unsigned numberOfVertices() const { return m_vertices->size(); }
49
50 WindRule fillRule() const { return m_fillRule; }
51
52 const FloatPolygonEdge& edgeAt(unsigned index) const { return m_edges[index]; }
53 unsigned numberOfEdges() const { return m_edges.size(); }
54
55 FloatRect boundingBox() const { return m_boundingBox; }
56 bool overlappingEdges(float minY, float maxY, Vector<const FloatPolygonEdge*>& result) const;
57 bool contains(const FloatPoint&) const;
58 bool isEmpty() const { return m_empty; }
59
60private:
61 typedef PODInterval<float, FloatPolygonEdge*> EdgeInterval;
62 typedef PODIntervalTree<float, FloatPolygonEdge*> EdgeIntervalTree;
63
64 bool containsNonZero(const FloatPoint&) const;
65 bool containsEvenOdd(const FloatPoint&) const;
66
67 std::unique_ptr<Vector<FloatPoint>> m_vertices;
68 WindRule m_fillRule;
69 FloatRect m_boundingBox;
70 bool m_empty;
71 Vector<FloatPolygonEdge> m_edges;
72 EdgeIntervalTree m_edgeTree; // Each EdgeIntervalTree node stores minY, maxY, and a ("UserData") pointer to a FloatPolygonEdge.
73
74};
75
76class VertexPair {
77public:
78 virtual ~VertexPair() = default;
79
80 virtual const FloatPoint& vertex1() const = 0;
81 virtual const FloatPoint& vertex2() const = 0;
82
83 float minX() const { return std::min(vertex1().x(), vertex2().x()); }
84 float minY() const { return std::min(vertex1().y(), vertex2().y()); }
85 float maxX() const { return std::max(vertex1().x(), vertex2().x()); }
86 float maxY() const { return std::max(vertex1().y(), vertex2().y()); }
87
88 bool overlapsRect(const FloatRect&) const;
89 bool intersection(const VertexPair&, FloatPoint&) const;
90};
91
92class FloatPolygonEdge : public VertexPair {
93 friend class FloatPolygon;
94public:
95 const FloatPoint& vertex1() const override
96 {
97 ASSERT(m_polygon);
98 return m_polygon->vertexAt(m_vertexIndex1);
99 }
100
101 const FloatPoint& vertex2() const override
102 {
103 ASSERT(m_polygon);
104 return m_polygon->vertexAt(m_vertexIndex2);
105 }
106
107 const FloatPolygonEdge& previousEdge() const
108 {
109 ASSERT(m_polygon && m_polygon->numberOfEdges() > 1);
110 return m_polygon->edgeAt((m_edgeIndex + m_polygon->numberOfEdges() - 1) % m_polygon->numberOfEdges());
111 }
112
113 const FloatPolygonEdge& nextEdge() const
114 {
115 ASSERT(m_polygon && m_polygon->numberOfEdges() > 1);
116 return m_polygon->edgeAt((m_edgeIndex + 1) % m_polygon->numberOfEdges());
117 }
118
119 const FloatPolygon* polygon() const { return m_polygon; }
120 unsigned vertexIndex1() const { return m_vertexIndex1; }
121 unsigned vertexIndex2() const { return m_vertexIndex2; }
122 unsigned edgeIndex() const { return m_edgeIndex; }
123
124 String debugString() const;
125
126private:
127 // Edge vertex index1 is less than index2, except the last edge, where index2 is 0. When a polygon edge
128 // is defined by 3 or more colinear vertices, index2 can be the index of the last colinear vertex.
129 unsigned m_vertexIndex1;
130 unsigned m_vertexIndex2;
131 unsigned m_edgeIndex;
132 const FloatPolygon* m_polygon;
133};
134
135} // namespace WebCore
136
137#ifndef NDEBUG
138
139namespace WTF {
140
141// This structure is used by PODIntervalTree for debugging.
142template<> struct ValueToString<WebCore::FloatPolygonEdge*> {
143 static String string(const WebCore::FloatPolygonEdge* edge) { return edge->debugString(); }
144};
145
146}
147
148#endif
149