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