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
41namespace WebCore {
42
43class FloatPolygonEdge;
44
45// This class is used by PODIntervalTree for debugging.
46#ifndef NDEBUG
47template <class> struct ValueToString;
48#endif
49
50class FloatPolygon {
51public:
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
67private:
68    typedef PODInterval<float, FloatPolygonEdge*> EdgeInterval;
69    typedef PODIntervalTree<float, FloatPolygonEdge*> EdgeIntervalTree;
70
71    OwnPtr<Vector<FloatPoint> > m_vertices;
72    WindRule m_fillRule;
73    FloatRect m_boundingBox;
74    bool m_empty;
75    Vector<FloatPolygonEdge> m_edges;
76    EdgeIntervalTree m_edgeTree; // Each EdgeIntervalTree node stores minY, maxY, and a ("UserData") pointer to a FloatPolygonEdge.
77
78};
79
80class VertexPair {
81public:
82    virtual ~VertexPair() { }
83
84    virtual const FloatPoint& vertex1() const = 0;
85    virtual const FloatPoint& vertex2() const = 0;
86
87    float minX() const { return std::min(vertex1().x(), vertex2().x()); }
88    float minY() const { return std::min(vertex1().y(), vertex2().y()); }
89    float maxX() const { return std::max(vertex1().x(), vertex2().x()); }
90    float maxY() const { return std::max(vertex1().y(), vertex2().y()); }
91
92    bool overlapsRect(const FloatRect&) const;
93    bool intersection(const VertexPair&, FloatPoint&) const;
94};
95
96class FloatPolygonEdge : public VertexPair {
97    friend class FloatPolygon;
98public:
99    virtual const FloatPoint& vertex1() const OVERRIDE
100    {
101        ASSERT(m_polygon);
102        return m_polygon->vertexAt(m_vertexIndex1);
103    }
104
105    virtual const FloatPoint& vertex2() const OVERRIDE
106    {
107        ASSERT(m_polygon);
108        return m_polygon->vertexAt(m_vertexIndex2);
109    }
110
111    const FloatPolygonEdge& previousEdge() const
112    {
113        ASSERT(m_polygon && m_polygon->numberOfEdges() > 1);
114        return m_polygon->edgeAt((m_edgeIndex + m_polygon->numberOfEdges() - 1) % m_polygon->numberOfEdges());
115    }
116
117    const FloatPolygonEdge& nextEdge() const
118    {
119        ASSERT(m_polygon && m_polygon->numberOfEdges() > 1);
120        return m_polygon->edgeAt((m_edgeIndex + 1) % m_polygon->numberOfEdges());
121    }
122
123    const FloatPolygon* polygon() const { return m_polygon; }
124    unsigned vertexIndex1() const { return m_vertexIndex1; }
125    unsigned vertexIndex2() const { return m_vertexIndex2; }
126    unsigned edgeIndex() const { return m_edgeIndex; }
127
128private:
129    // Edge vertex index1 is less than index2, except the last edge, where index2 is 0. When a polygon edge
130    // is defined by 3 or more colinear vertices, index2 can be the the index of the last colinear vertex.
131    unsigned m_vertexIndex1;
132    unsigned m_vertexIndex2;
133    unsigned m_edgeIndex;
134    const FloatPolygon* m_polygon;
135};
136
137// These structures are used by PODIntervalTree for debugging.
138#ifndef NDEBUG
139template <> struct ValueToString<float> {
140    static String string(const float value) { return String::number(value); }
141};
142
143template<> struct ValueToString<FloatPolygonEdge*> {
144    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()); }
145};
146#endif
147
148} // namespace WebCore
149
150#endif // FloatPolygon_h
151