[CSS Exclusions] Refactor the ExclusionPolygon class to enable storing multiple bound...
authorhmuller@adobe.com <hmuller@adobe.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 11 Mar 2013 22:12:19 +0000 (22:12 +0000)
committerhmuller@adobe.com <hmuller@adobe.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 11 Mar 2013 22:12:19 +0000 (22:12 +0000)
https://bugs.webkit.org/show_bug.cgi?id=111766

Reviewed by Dirk Schulze.

Refactored the ExclusionPolygon class to enable adding support for shape-margin and shape-padding.
Extracted a new FloatPolygon class which is now used by ExclusionPolygon to represent the shape's
boundary. It will be used to add m_paddedPolygon and m_marginPolygon members to ExclusionPolygon
in a subsequent patch.

No new tests. This is strictly a refactoring of the existing code.

* CMakeLists.txt:
* GNUmakefile.list.am:
* WebCore.gypi:
* WebCore.vcproj/WebCore.vcproj:
* WebCore.xcodeproj/project.pbxproj:
* platform/graphics/FloatPolygon.cpp: Factored out of Source/WebCore/rendering/ExclusionPolygon.cpp.
(WebCore::determinant):
(WebCore::areCollinearPoints):
(WebCore::areCoincidentPoints):
(WebCore::isPointOnLineSegment):
(WebCore::nextVertexIndex):
(WebCore::FloatPolygon::FloatPolygon):
(WebCore::FloatPolygon::findNextEdgeVertexIndex):
(WebCore::FloatPolygon::overlappingEdges):
(WebCore::leftSide):
(WebCore::FloatPolygon::contains):
(WebCore::VertexPair::overlapsRect):
(WebCore::VertexPair::intersection):
* platform/graphics/FloatPolygon.h: Factored out of Source/WebCore/rendering/ExclusionPolygon.h.
(FloatPolygon):
(WebCore::FloatPolygon::vertexAt):
(WebCore::FloatPolygon::numberOfVertices):
(WebCore::FloatPolygon::fillRule):
(WebCore::FloatPolygon::edgeAt):
(WebCore::FloatPolygon::numberOfEdges):
(WebCore::FloatPolygon::boundingBox):
(WebCore::FloatPolygon::isEmpty):
(VertexPair):
(WebCore::VertexPair::~VertexPair):
(WebCore::VertexPair::minX):
(WebCore::VertexPair::minY):
(WebCore::VertexPair::maxX):
(WebCore::VertexPair::maxY):
(FloatPolygonEdge):
(WebCore::FloatPolygonEdge::previousEdge):
(WebCore::FloatPolygonEdge::nextEdge):
(WebCore::FloatPolygonEdge::polygon):
(WebCore::FloatPolygonEdge::vertexIndex1):
(WebCore::FloatPolygonEdge::vertexIndex2):
(WebCore::FloatPolygonEdge::edgeIndex):
* rendering/ExclusionPolygon.cpp: Now depends on FloatPolygon.
(EdgeIntersection):
(WebCore::leftSide):
(WebCore::computeXIntersection):
(WebCore::getVertexIntersectionVertices):
(WebCore::computeXIntersections):
(WebCore::computeOverlappingEdgeXProjections):
(WebCore::ExclusionPolygon::getExcludedIntervals):
(WebCore::ExclusionPolygon::getIncludedIntervals):
(WebCore::firstFitRectInPolygon):
(WebCore::ExclusionPolygon::firstIncludedIntervalLogicalTop):
* rendering/ExclusionPolygon.h: Now depends on FloatPolygon.
(WebCore::OffsetPolygonEdge::OffsetPolygonEdge):
(ExclusionPolygon):
(WebCore::ExclusionPolygon::ExclusionPolygon):

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@145411 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Source/WebCore/CMakeLists.txt
Source/WebCore/ChangeLog
Source/WebCore/GNUmakefile.list.am
Source/WebCore/Target.pri
Source/WebCore/WebCore.gypi
Source/WebCore/WebCore.vcproj/WebCore.vcproj
Source/WebCore/WebCore.xcodeproj/project.pbxproj
Source/WebCore/platform/graphics/FloatPolygon.cpp [new file with mode: 0644]
Source/WebCore/platform/graphics/FloatPolygon.h [new file with mode: 0644]
Source/WebCore/rendering/ExclusionPolygon.cpp
Source/WebCore/rendering/ExclusionPolygon.h

index 942dec9..c202f23 100644 (file)
@@ -1920,6 +1920,7 @@ set(WebCore_SOURCES
     platform/graphics/CrossfadeGeneratedImage.cpp
     platform/graphics/FloatPoint.cpp
     platform/graphics/FloatPoint3D.cpp
+    platform/graphics/FloatPolygon.cpp
     platform/graphics/FloatQuad.cpp
     platform/graphics/FloatRect.cpp
     platform/graphics/FloatSize.cpp
index 195a40a..8fd04da 100644 (file)
@@ -1,3 +1,73 @@
+2013-03-11  Hans Muller  <hmuller@adobe.com>
+
+        [CSS Exclusions] Refactor the ExclusionPolygon class to enable storing multiple boundaries
+        https://bugs.webkit.org/show_bug.cgi?id=111766
+
+        Reviewed by Dirk Schulze.
+
+        Refactored the ExclusionPolygon class to enable adding support for shape-margin and shape-padding.
+        Extracted a new FloatPolygon class which is now used by ExclusionPolygon to represent the shape's
+        boundary. It will be used to add m_paddedPolygon and m_marginPolygon members to ExclusionPolygon
+        in a subsequent patch.
+
+        No new tests. This is strictly a refactoring of the existing code.
+
+        * CMakeLists.txt:
+        * GNUmakefile.list.am:
+        * WebCore.gypi:
+        * WebCore.vcproj/WebCore.vcproj:
+        * WebCore.xcodeproj/project.pbxproj:
+        * platform/graphics/FloatPolygon.cpp: Factored out of Source/WebCore/rendering/ExclusionPolygon.cpp.
+        (WebCore::determinant):
+        (WebCore::areCollinearPoints):
+        (WebCore::areCoincidentPoints):
+        (WebCore::isPointOnLineSegment):
+        (WebCore::nextVertexIndex):
+        (WebCore::FloatPolygon::FloatPolygon):
+        (WebCore::FloatPolygon::findNextEdgeVertexIndex):
+        (WebCore::FloatPolygon::overlappingEdges):
+        (WebCore::leftSide):
+        (WebCore::FloatPolygon::contains):
+        (WebCore::VertexPair::overlapsRect):
+        (WebCore::VertexPair::intersection):
+        * platform/graphics/FloatPolygon.h: Factored out of Source/WebCore/rendering/ExclusionPolygon.h.
+        (FloatPolygon):
+        (WebCore::FloatPolygon::vertexAt):
+        (WebCore::FloatPolygon::numberOfVertices):
+        (WebCore::FloatPolygon::fillRule):
+        (WebCore::FloatPolygon::edgeAt):
+        (WebCore::FloatPolygon::numberOfEdges):
+        (WebCore::FloatPolygon::boundingBox):
+        (WebCore::FloatPolygon::isEmpty):
+        (VertexPair):
+        (WebCore::VertexPair::~VertexPair):
+        (WebCore::VertexPair::minX):
+        (WebCore::VertexPair::minY):
+        (WebCore::VertexPair::maxX):
+        (WebCore::VertexPair::maxY):
+        (FloatPolygonEdge):
+        (WebCore::FloatPolygonEdge::previousEdge):
+        (WebCore::FloatPolygonEdge::nextEdge):
+        (WebCore::FloatPolygonEdge::polygon):
+        (WebCore::FloatPolygonEdge::vertexIndex1):
+        (WebCore::FloatPolygonEdge::vertexIndex2):
+        (WebCore::FloatPolygonEdge::edgeIndex):
+        * rendering/ExclusionPolygon.cpp: Now depends on FloatPolygon.
+        (EdgeIntersection):
+        (WebCore::leftSide):
+        (WebCore::computeXIntersection):
+        (WebCore::getVertexIntersectionVertices):
+        (WebCore::computeXIntersections):
+        (WebCore::computeOverlappingEdgeXProjections):
+        (WebCore::ExclusionPolygon::getExcludedIntervals):
+        (WebCore::ExclusionPolygon::getIncludedIntervals):
+        (WebCore::firstFitRectInPolygon):
+        (WebCore::ExclusionPolygon::firstIncludedIntervalLogicalTop):
+        * rendering/ExclusionPolygon.h: Now depends on FloatPolygon.
+        (WebCore::OffsetPolygonEdge::OffsetPolygonEdge):
+        (ExclusionPolygon):
+        (WebCore::ExclusionPolygon::ExclusionPolygon):
+
 2013-03-11  Alexey Proskuryakov  <ap@apple.com>
 
         Roll out part of r144671.
index e98375a..c8cd1ba 100644 (file)
@@ -5590,6 +5590,8 @@ webcore_platform_sources += \
        Source/WebCore/platform/graphics/FloatPoint3D.h \
        Source/WebCore/platform/graphics/FloatPoint.cpp \
        Source/WebCore/platform/graphics/FloatPoint.h \
+       Source/WebCore/platform/graphics/FloatPolygon.cpp \
+       Source/WebCore/platform/graphics/FloatPolygon.h \
        Source/WebCore/platform/graphics/FloatQuad.cpp \
        Source/WebCore/platform/graphics/FloatQuad.h \
        Source/WebCore/platform/graphics/FloatRect.cpp \
index 0cb1c66..7396d2c 100644 (file)
@@ -1007,6 +1007,7 @@ SOURCES += \
     platform/graphics/CrossfadeGeneratedImage.cpp \
     platform/graphics/FloatPoint3D.cpp \
     platform/graphics/FloatPoint.cpp \
+    platform/graphics/FloatPolygon.cpp \
     platform/graphics/FloatQuad.cpp \
     platform/graphics/FloatRect.cpp \
     platform/graphics/FloatSize.cpp \
@@ -2233,6 +2234,7 @@ HEADERS += \
     platform/graphics/filters/SourceGraphic.h \
     platform/graphics/FloatPoint3D.h \
     platform/graphics/FloatPoint.h \
+    platform/graphics/FloatPolygon.h \
     platform/graphics/FloatQuad.h \
     platform/graphics/FloatRect.h \
     platform/graphics/FloatSize.h \
index 1a32e82..80a50c0 100644 (file)
         ],
         'webcore_platform_geometry_files': [
             'platform/graphics/FloatPoint.cpp',
+            'platform/graphics/FloatPolygon.cpp',
             'platform/graphics/FloatPoint3D.cpp',
             'platform/graphics/FloatQuad.cpp',
             'platform/graphics/FloatRect.cpp',
index 96950e3..c88967b 100755 (executable)
                                        >
                                </File>
                                <File
+                                       RelativePath="..\platform\graphics\FloatPolygon.cpp"
+                                       >
+                               </File>
+                               <File
+                                       RelativePath="..\platform\graphics\FloatPolygon.h"
+                                       >
+                               </File>
+                               <File
                                        RelativePath="..\platform\graphics\FloatQuad.cpp"
                                        >
                                </File>
index a651d26..295ce9f 100644 (file)
                6EBF0E7612A9868800DB170A /* JSEXTDrawBuffers.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 6EBF0E7412A9868800DB170A /* JSEXTDrawBuffers.cpp */; };
                6EBF0E7712A9868800DB1709 /* JSOESTextureFloat.h in Headers */ = {isa = PBXBuildFile; fileRef = 6EBF0E7512A9868800DB1709 /* JSOESTextureFloat.h */; };
                6EBF0E7712A9868800DB170A /* JSEXTDrawBuffers.h in Headers */ = {isa = PBXBuildFile; fileRef = 6EBF0E7512A9868800DB170A /* JSEXTDrawBuffers.h */; };
+               6EC480A116EA638A00A48DCB /* FloatPolygon.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 6EC4809F16EA638A00A48DCB /* FloatPolygon.cpp */; };
+               6EC480A216EA638A00A48DCB /* FloatPolygon.h in Headers */ = {isa = PBXBuildFile; fileRef = 6EC480A016EA638A00A48DCB /* FloatPolygon.h */; settings = {ATTRIBUTES = (Private, ); }; };
                6ED878C4147493F4004C3597 /* RenderTableCaption.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 6ED878C2147493F4004C3597 /* RenderTableCaption.cpp */; };
                6ED878C5147493F4004C3597 /* RenderTableCaption.h in Headers */ = {isa = PBXBuildFile; fileRef = 6ED878C3147493F4004C3597 /* RenderTableCaption.h */; };
                6EE8A77210F803F3005A4A24 /* JSWebGLContextAttributes.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 6EE8A77010F803F3005A4A24 /* JSWebGLContextAttributes.cpp */; };
                6EBF0E7412A9868800DB170A /* JSEXTDrawBuffers.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = JSEXTDrawBuffers.cpp; sourceTree = "<group>"; };
                6EBF0E7512A9868800DB1709 /* JSOESTextureFloat.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = JSOESTextureFloat.h; sourceTree = "<group>"; };
                6EBF0E7512A9868800DB170A /* JSEXTDrawBuffers.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = JSEXTDrawBuffers.h; sourceTree = "<group>"; };
+               6EC4809F16EA638A00A48DCB /* FloatPolygon.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = FloatPolygon.cpp; sourceTree = "<group>"; };
+               6EC480A016EA638A00A48DCB /* FloatPolygon.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = FloatPolygon.h; sourceTree = "<group>"; };
                6ED878C2147493F4004C3597 /* RenderTableCaption.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = RenderTableCaption.cpp; sourceTree = "<group>"; };
                6ED878C3147493F4004C3597 /* RenderTableCaption.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = RenderTableCaption.h; sourceTree = "<group>"; };
                6EE8A77010F803F3005A4A24 /* JSWebGLContextAttributes.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = JSWebGLContextAttributes.cpp; sourceTree = "<group>"; };
                                6E67D2A81280E8BD008758F7 /* Extensions3D.h */,
                                B275353A0B053814002CE64F /* FloatPoint.cpp */,
                                B275353B0B053814002CE64F /* FloatPoint.h */,
+                               6EC4809F16EA638A00A48DCB /* FloatPolygon.cpp */,
+                               6EC480A016EA638A00A48DCB /* FloatPolygon.h */,
                                B2E27C9D0B0F2B0900F17C7B /* FloatPoint3D.cpp */,
                                B2E27C9E0B0F2B0900F17C7B /* FloatPoint3D.h */,
                                0FD723810EC8BD9300CA5DD7 /* FloatQuad.cpp */,
                        isa = PBXHeadersBuildPhase;
                        buildActionMask = 2147483647;
                        files = (
+                               6EC480A216EA638A00A48DCB /* FloatPolygon.h in Headers */,
                                FE115FAB167988CD00249134 /* AbstractDatabaseServer.h in Headers */,
                                FE9E89FC16E2DC0500A908F8 /* OriginLock.h in Headers */,
                                FE4AADEE16D2C37400026FFC /* AbstractSQLStatement.h in Headers */,
                                7E66E23316D6EB6C00F7E7FF /* WebGLCompressedTextureATC.cpp in Sources */,
                                7EA30F6916DFFE7500257D0B /* JSWebGLCompressedTextureATC.cpp in Sources */,
                                2D8287F616E4A0380086BD00 /* HitTestLocation.cpp in Sources */,
+                               6EC480A116EA638A00A48DCB /* FloatPolygon.cpp in Sources */,
                                A895709F16E9BD5900184E55 /* HTMLIdentifier.cpp in Sources */,
+
                        );
                        runOnlyForDeploymentPostprocessing = 0;
                };
diff --git a/Source/WebCore/platform/graphics/FloatPolygon.cpp b/Source/WebCore/platform/graphics/FloatPolygon.cpp
new file mode 100644 (file)
index 0000000..5106840
--- /dev/null
@@ -0,0 +1,234 @@
+/*
+ * Copyright (C) 2012 Adobe Systems Incorporated. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above
+ *    copyright notice, this list of conditions and the following
+ *    disclaimer.
+ * 2. Redistributions in binary form must reproduce the above
+ *    copyright notice, this list of conditions and the following
+ *    disclaimer in the documentation and/or other materials
+ *    provided with the distribution.
+ * 
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+ * COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
+ * OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "config.h"
+#include "FloatPolygon.h"
+
+#include <wtf/MathExtras.h>
+
+namespace WebCore {
+
+static inline float determinant(const FloatSize& a, const FloatSize& b)
+{
+    return a.width() * b.height() - a.height() * b.width();
+}
+
+static inline bool areCollinearPoints(const FloatPoint& p0, const FloatPoint& p1, const FloatPoint& p2)
+{
+    return !determinant(p1 - p0, p2 - p0);
+}
+
+static inline bool areCoincidentPoints(const FloatPoint& p0, const FloatPoint& p1)
+{
+    return p0.x() == p1.x() && p0.y() == p1.y();
+}
+
+static inline bool isPointOnLineSegment(const FloatPoint& vertex1, const FloatPoint& vertex2, const FloatPoint& point)
+{
+    return point.x() >= std::min(vertex1.x(), vertex2.x())
+        && point.x() <= std::max(vertex1.x(), vertex2.x())
+        && areCollinearPoints(vertex1, vertex2, point);
+}
+
+static inline unsigned nextVertexIndex(unsigned vertexIndex, unsigned nVertices, bool clockwise)
+{
+    return ((clockwise) ? vertexIndex + 1 : vertexIndex - 1 + nVertices) % nVertices;
+}
+
+static unsigned findNextEdgeVertexIndex(const FloatPolygon& polygon, unsigned vertexIndex1, bool clockwise)
+{
+    unsigned nVertices = polygon.numberOfVertices();
+    unsigned vertexIndex2 = nextVertexIndex(vertexIndex1, nVertices, clockwise);
+
+    while (vertexIndex2 && areCoincidentPoints(polygon.vertexAt(vertexIndex1), polygon.vertexAt(vertexIndex2)))
+        vertexIndex2 = nextVertexIndex(vertexIndex2, nVertices, clockwise);
+
+    while (vertexIndex2) {
+        unsigned vertexIndex3 = nextVertexIndex(vertexIndex2, nVertices, clockwise);
+        if (!areCollinearPoints(polygon.vertexAt(vertexIndex1), polygon.vertexAt(vertexIndex2), polygon.vertexAt(vertexIndex3)))
+            break;
+        vertexIndex2 = vertexIndex3;
+    }
+
+    return vertexIndex2;
+}
+
+FloatPolygon::FloatPolygon(PassOwnPtr<Vector<FloatPoint> > vertices, WindRule fillRule)
+    : m_vertices(vertices)
+    , m_fillRule(fillRule)
+{
+    unsigned nVertices = numberOfVertices();
+    m_edges.resize(nVertices);
+    m_empty = nVertices < 3;
+
+    if (nVertices)
+        m_boundingBox.setLocation(vertexAt(0));
+
+    if (m_empty)
+        return;
+
+    unsigned minVertexIndex = 0;
+    for (unsigned i = 1; i < nVertices; ++i) {
+        const FloatPoint& vertex = vertexAt(i);
+        if (vertex.y() < vertexAt(minVertexIndex).y() || (vertex.y() == vertexAt(minVertexIndex).y() && vertex.x() < vertexAt(minVertexIndex).x()))
+            minVertexIndex = i;
+    }
+    FloatPoint nextVertex = vertexAt((minVertexIndex + 1) % nVertices);
+    FloatPoint prevVertex = vertexAt((minVertexIndex + nVertices - 1) % nVertices);
+    bool clockwise = determinant(vertexAt(minVertexIndex) - prevVertex, nextVertex - prevVertex) > 0;
+
+    unsigned edgeIndex = 0;
+    unsigned vertexIndex1 = 0;
+    do {
+        m_boundingBox.extend(vertexAt(vertexIndex1));
+        unsigned vertexIndex2 = findNextEdgeVertexIndex(*this, vertexIndex1, clockwise);
+        m_edges[edgeIndex].m_polygon = this;
+        m_edges[edgeIndex].m_vertexIndex1 = vertexIndex1;
+        m_edges[edgeIndex].m_vertexIndex2 = vertexIndex2;
+        m_edges[edgeIndex].m_edgeIndex = edgeIndex;
+        ++edgeIndex;
+        vertexIndex1 = vertexIndex2;
+    } while (vertexIndex1);
+
+    if (edgeIndex > 3) {
+        const FloatPolygonEdge& firstEdge = m_edges[0];
+        const FloatPolygonEdge& lastEdge = m_edges[edgeIndex - 1];
+        if (areCollinearPoints(lastEdge.vertex1(), lastEdge.vertex2(), firstEdge.vertex2())) {
+            m_edges[0].m_vertexIndex1 = lastEdge.m_vertexIndex1;
+            edgeIndex--;
+        }
+    }
+
+    m_edges.resize(edgeIndex);
+    m_empty = m_edges.size() < 3;
+
+    if (m_empty)
+        return;
+
+    for (unsigned i = 0; i < m_edges.size(); ++i) {
+        FloatPolygonEdge* edge = &m_edges[i];
+        m_edgeTree.add(EdgeInterval(edge->minY(), edge->maxY(), edge));
+    }
+}
+
+bool FloatPolygon::overlappingEdges(float minY, float maxY, Vector<const FloatPolygonEdge*>& result) const
+{
+    Vector<FloatPolygon::EdgeInterval> overlappingEdgeIntervals;
+    m_edgeTree.allOverlaps(FloatPolygon::EdgeInterval(minY, maxY, 0), overlappingEdgeIntervals);
+    unsigned overlappingEdgeIntervalsSize = overlappingEdgeIntervals.size();
+    result.resize(overlappingEdgeIntervalsSize);
+    for (unsigned i = 0; i < overlappingEdgeIntervalsSize; ++i) {
+        const FloatPolygonEdge* edge = static_cast<const FloatPolygonEdge*>(overlappingEdgeIntervals[i].data());
+        ASSERT(edge);
+        result[i] = edge;
+    }
+    return overlappingEdgeIntervalsSize > 0;
+}
+
+static inline float leftSide(const FloatPoint& vertex1, const FloatPoint& vertex2, const FloatPoint& point)
+{
+    return ((point.x() - vertex1.x()) * (vertex2.y() - vertex1.y())) - ((vertex2.x() - vertex1.x()) * (point.y() - vertex1.y()));
+}
+
+bool FloatPolygon::contains(const FloatPoint& point) const
+{
+    if (!m_boundingBox.contains(point))
+        return false;
+
+    int windingNumber = 0;
+    for (unsigned i = 0; i < numberOfEdges(); ++i) {
+        const FloatPoint& vertex1 = edgeAt(i).vertex1();
+        const FloatPoint& vertex2 = edgeAt(i).vertex2();
+        if (isPointOnLineSegment(vertex1, vertex2, point))
+            return true;
+        if (vertex2.y() < point.y()) {
+            if ((vertex1.y() > point.y()) && (leftSide(vertex1, vertex2, point) > 0))
+                ++windingNumber;
+        } else if (vertex2.y() > point.y()) {
+            if ((vertex1.y() <= point.y()) && (leftSide(vertex1, vertex2, point) < 0))
+                --windingNumber;
+        }
+    }
+
+    return windingNumber;
+}
+
+bool VertexPair::overlapsRect(const FloatRect& rect) const
+{
+    bool boundsOverlap = (minX() < rect.maxX()) && (maxX() > rect.x()) && (minY() < rect.maxY()) && (maxY() > rect.y());
+    if (!boundsOverlap)
+        return false;
+
+    float leftSideValues[4] = {
+        leftSide(vertex1(), vertex2(), rect.minXMinYCorner()),
+        leftSide(vertex1(), vertex2(), rect.maxXMinYCorner()),
+        leftSide(vertex1(), vertex2(), rect.minXMaxYCorner()),
+        leftSide(vertex1(), vertex2(), rect.maxXMaxYCorner())
+    };
+
+    int currentLeftSideSign = 0;
+    for (unsigned i = 0; i < 4; ++i) {
+        if (!leftSideValues[i])
+            continue;
+        int leftSideSign = leftSideValues[i] > 0 ? 1 : -1;
+        if (!currentLeftSideSign)
+            currentLeftSideSign = leftSideSign;
+        else if (currentLeftSideSign != leftSideSign)
+            return true;
+    }
+
+    return false;
+}
+
+bool VertexPair::intersection(const VertexPair& other, FloatPoint& point) const
+{
+    // See: http://paulbourke.net/geometry/pointlineplane/, "Intersection point of two lines in 2 dimensions"
+
+    const FloatSize& thisDelta = vertex2() - vertex1();
+    const FloatSize& otherDelta = other.vertex2() - other.vertex1();
+    float denominator = determinant(thisDelta, otherDelta);
+    if (!denominator)
+        return false;
+
+    // The two line segments: "this" vertex1,vertex2 and "other" vertex1,vertex2, have been defined
+    // in parametric form. Each point on the line segment is: vertex1 + u * (vertex2 - vertex1),
+    // when 0 <= u <= 1. We're computing the values of u for each line at their intersection point.
+
+    const FloatSize& vertex1Delta = vertex1() - other.vertex1();
+    float uThisLine = determinant(otherDelta, vertex1Delta) / denominator;
+    float uOtherLine = determinant(thisDelta, vertex1Delta) / denominator;
+
+    if (uThisLine < 0 || uOtherLine < 0 || uThisLine > 1 || uOtherLine > 1)
+        return false;
+
+    point = vertex1() + uThisLine * thisDelta;
+    return true;
+}
+
+} // namespace WebCore
diff --git a/Source/WebCore/platform/graphics/FloatPolygon.h b/Source/WebCore/platform/graphics/FloatPolygon.h
new file mode 100644 (file)
index 0000000..8defe14
--- /dev/null
@@ -0,0 +1,150 @@
+/*
+ * Copyright (C) 2012 Adobe Systems Incorporated. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above
+ *    copyright notice, this list of conditions and the following
+ *    disclaimer.
+ * 2. Redistributions in binary form must reproduce the above
+ *    copyright notice, this list of conditions and the following
+ *    disclaimer in the documentation and/or other materials
+ *    provided with the distribution.
+ * 
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+ * COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
+ * OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef FloatPolygon_h
+#define FloatPolygon_h
+
+#include "FloatPoint.h"
+#include "FloatRect.h"
+#include "PODIntervalTree.h"
+#include "WindRule.h"
+#include <wtf/OwnPtr.h>
+#include <wtf/PassOwnPtr.h>
+#include <wtf/Vector.h>
+
+namespace WebCore {
+
+class FloatPolygonEdge;
+
+// This class is used by PODIntervalTree for debugging.
+#ifndef NDEBUG
+template <class> struct ValueToString;
+#endif
+
+class FloatPolygon {
+public:
+    FloatPolygon(PassOwnPtr<Vector<FloatPoint> > vertices, WindRule fillRule);
+
+    const FloatPoint& vertexAt(unsigned index) const { return (*m_vertices)[index]; }
+    unsigned numberOfVertices() const { return m_vertices->size(); }
+
+    WindRule fillRule() const { return m_fillRule; }
+
+    const FloatPolygonEdge& edgeAt(unsigned index) const { return m_edges[index]; }
+    unsigned numberOfEdges() const { return m_edges.size(); }
+
+    FloatRect boundingBox() const { return m_boundingBox; }
+    bool overlappingEdges(float minY, float maxY, Vector<const FloatPolygonEdge*>& result) const;
+    bool contains(const FloatPoint&) const;
+    bool isEmpty() const { return m_empty; }
+
+private:
+    typedef PODInterval<float, FloatPolygonEdge*> EdgeInterval;
+    typedef PODIntervalTree<float, FloatPolygonEdge*> EdgeIntervalTree;
+
+    OwnPtr<Vector<FloatPoint> > m_vertices;
+    WindRule m_fillRule;
+    FloatRect m_boundingBox;
+    bool m_empty;
+    Vector<FloatPolygonEdge> m_edges;
+    EdgeIntervalTree m_edgeTree; // Each EdgeIntervalTree node stores minY, maxY, and a ("UserData") pointer to a FloatPolygonEdge.
+
+};
+
+class VertexPair {
+public:
+    virtual ~VertexPair() { }
+
+    virtual const FloatPoint& vertex1() const = 0;
+    virtual const FloatPoint& vertex2() const = 0;
+
+    float minX() const { return std::min(vertex1().x(), vertex2().x()); }
+    float minY() const { return std::min(vertex1().y(), vertex2().y()); }
+    float maxX() const { return std::max(vertex1().x(), vertex2().x()); }
+    float maxY() const { return std::max(vertex1().y(), vertex2().y()); }
+
+    bool overlapsRect(const FloatRect&) const;
+    bool intersection(const VertexPair&, FloatPoint&) const;
+};
+
+class FloatPolygonEdge : public VertexPair {
+    friend class FloatPolygon;
+public:
+    virtual const FloatPoint& vertex1() const OVERRIDE
+    {
+        ASSERT(m_polygon);
+        return m_polygon->vertexAt(m_vertexIndex1);
+    }
+
+    virtual const FloatPoint& vertex2() const OVERRIDE
+    {
+        ASSERT(m_polygon);
+        return m_polygon->vertexAt(m_vertexIndex2);
+    }
+
+    const FloatPolygonEdge& previousEdge() const
+    {
+        ASSERT(m_polygon && m_polygon->numberOfEdges() > 1);
+        return m_polygon->edgeAt((m_edgeIndex + m_polygon->numberOfEdges() - 1) % m_polygon->numberOfEdges());
+    }
+
+    const FloatPolygonEdge& nextEdge() const
+    {
+        ASSERT(m_polygon && m_polygon->numberOfEdges() > 1);
+        return m_polygon->edgeAt((m_edgeIndex + 1) % m_polygon->numberOfEdges());
+    }
+
+    const FloatPolygon* polygon() const { return m_polygon; }
+    unsigned vertexIndex1() const { return m_vertexIndex1; }
+    unsigned vertexIndex2() const { return m_vertexIndex2; }
+    unsigned edgeIndex() const { return m_edgeIndex; }
+
+private:
+    // Edge vertex index1 is less than index2, except the last edge, where index2 is 0. When a polygon edge
+    // is defined by 3 or more colinear vertices, index2 can be the the index of the last colinear vertex.
+    unsigned m_vertexIndex1;
+    unsigned m_vertexIndex2;
+    unsigned m_edgeIndex;
+    const FloatPolygon* m_polygon;
+};
+
+// These structures are used by PODIntervalTree for debugging.
+#ifndef NDEBUG
+template <> struct ValueToString<float> {
+    static String string(const float value) { return String::number(value); }
+};
+
+template<> struct ValueToString<FloatPolygonEdge*> {
+    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()); }
+};
+#endif
+
+} // namespace WebCore
+
+#endif // FloatPolygon_h
index 1060c20..4dcee82 100644 (file)
@@ -42,118 +42,19 @@ enum EdgeIntersectionType {
 };
 
 struct EdgeIntersection {
-    const ExclusionPolygonEdge* edge;
+    const FloatPolygonEdge* edge;
     FloatPoint point;
     EdgeIntersectionType type;
 };
 
-static inline float determinant(const FloatSize& a, const FloatSize& b)
-{
-    return a.width() * b.height() - a.height() * b.width();
-}
-
-static inline bool areCollinearPoints(const FloatPoint& p0, const FloatPoint& p1, const FloatPoint& p2)
-{
-    return !determinant(p1 - p0, p2 - p0);
-}
-
-static inline bool areCoincidentPoints(const FloatPoint& p0, const FloatPoint& p1)
-{
-    return p0.x() == p1.x() && p0.y() == p1.y();
-}
-
-static inline bool isPointOnLineSegment(const FloatPoint& vertex1, const FloatPoint& vertex2, const FloatPoint& point)
-{
-    return point.x() >= std::min(vertex1.x(), vertex2.x())
-        && point.x() <= std::max(vertex1.x(), vertex2.x())
-        && areCollinearPoints(vertex1, vertex2, point);
-}
-
-static inline unsigned nextVertexIndex(unsigned vertexIndex, unsigned nVertices, bool clockwise)
-{
-    return ((clockwise) ? vertexIndex + 1 : vertexIndex - 1 + nVertices) % nVertices;
-}
-
-unsigned ExclusionPolygon::findNextEdgeVertexIndex(unsigned vertexIndex1, bool clockwise) const
-{
-    unsigned nVertices = numberOfVertices();
-    unsigned vertexIndex2 = nextVertexIndex(vertexIndex1, nVertices, clockwise);
-
-    while (vertexIndex2 && areCoincidentPoints(vertexAt(vertexIndex1), vertexAt(vertexIndex2)))
-        vertexIndex2 = nextVertexIndex(vertexIndex2, nVertices, clockwise);
-
-    while (vertexIndex2) {
-        unsigned vertexIndex3 = nextVertexIndex(vertexIndex2, nVertices, clockwise);
-        if (!areCollinearPoints(vertexAt(vertexIndex1), vertexAt(vertexIndex2), vertexAt(vertexIndex3)))
-            break;
-        vertexIndex2 = vertexIndex3;
-    }
-
-    return vertexIndex2;
-}
-
-ExclusionPolygon::ExclusionPolygon(PassOwnPtr<Vector<FloatPoint> > vertices, WindRule fillRule)
-    : ExclusionShape()
-    , m_vertices(vertices)
-    , m_fillRule(fillRule)
+static inline float leftSide(const FloatPoint& vertex1, const FloatPoint& vertex2, const FloatPoint& point)
 {
-    unsigned nVertices = numberOfVertices();
-    m_edges.resize(nVertices);
-    m_empty = nVertices < 3;
-
-    if (nVertices)
-        m_boundingBox.setLocation(vertexAt(0));
-
-    if (m_empty)
-        return;
-
-    unsigned minVertexIndex = 0;
-    for (unsigned i = 1; i < nVertices; ++i) {
-        const FloatPoint& vertex = vertexAt(i);
-        if (vertex.y() < vertexAt(minVertexIndex).y() || (vertex.y() == vertexAt(minVertexIndex).y() && vertex.x() < vertexAt(minVertexIndex).x()))
-            minVertexIndex = i;
-    }
-    FloatPoint nextVertex = vertexAt((minVertexIndex + 1) % nVertices);
-    FloatPoint prevVertex = vertexAt((minVertexIndex + nVertices - 1) % nVertices);
-    bool clockwise = determinant(vertexAt(minVertexIndex) - prevVertex, nextVertex - prevVertex) > 0;
-
-    unsigned edgeIndex = 0;
-    unsigned vertexIndex1 = 0;
-    do {
-        m_boundingBox.extend(vertexAt(vertexIndex1));
-        unsigned vertexIndex2 = findNextEdgeVertexIndex(vertexIndex1, clockwise);
-        m_edges[edgeIndex].m_polygon = this;
-        m_edges[edgeIndex].m_vertexIndex1 = vertexIndex1;
-        m_edges[edgeIndex].m_vertexIndex2 = vertexIndex2;
-        m_edges[edgeIndex].m_edgeIndex = edgeIndex;
-        ++edgeIndex;
-        vertexIndex1 = vertexIndex2;
-    } while (vertexIndex1);
-
-    if (edgeIndex > 3) {
-        const ExclusionPolygonEdge& firstEdge = m_edges[0];
-        const ExclusionPolygonEdge& lastEdge = m_edges[edgeIndex - 1];
-        if (areCollinearPoints(lastEdge.vertex1(), lastEdge.vertex2(), firstEdge.vertex2())) {
-            m_edges[0].m_vertexIndex1 = lastEdge.m_vertexIndex1;
-            edgeIndex--;
-        }
-    }
-
-    m_edges.resize(edgeIndex);
-    m_empty = m_edges.size() < 3;
-
-    if (m_empty)
-        return;
-
-    for (unsigned i = 0; i < m_edges.size(); ++i) {
-        ExclusionPolygonEdge* edge = &m_edges[i];
-        m_edgeTree.add(EdgeInterval(edge->minY(), edge->maxY(), edge));
-    }
+    return ((point.x() - vertex1.x()) * (vertex2.y() - vertex1.y())) - ((vertex2.x() - vertex1.x()) * (point.y() - vertex1.y()));
 }
 
-static bool computeXIntersection(const ExclusionPolygonEdge* edgePointer, float y, EdgeIntersection& result)
+static bool computeXIntersection(const FloatPolygonEdge* edgePointer, float y, EdgeIntersection& result)
 {
-    const ExclusionPolygonEdge& edge = *edgePointer;
+    const FloatPolygonEdge& edge = *edgePointer;
 
     if (edge.minY() > y || edge.maxY() < y)
         return false;
@@ -192,8 +93,8 @@ static inline bool getVertexIntersectionVertices(const EdgeIntersection& interse
         return false;
 
     ASSERT(intersection.edge && intersection.edge->polygon());
-    const ExclusionPolygon& polygon = *(intersection.edge->polygon());
-    const ExclusionPolygonEdge& thisEdge = *(intersection.edge);
+    const FloatPolygon& polygon = *(intersection.edge->polygon());
+    const FloatPolygonEdge& thisEdge = *(intersection.edge);
 
     if ((intersection.type == VertexMinY && (thisEdge.vertex1().y() < thisEdge.vertex2().y()))
         || (intersection.type == VertexMaxY && (thisEdge.vertex1().y() > thisEdge.vertex2().y()))) {
@@ -226,18 +127,19 @@ static bool compareEdgeIntersectionX(const EdgeIntersection& intersection1, cons
     return (x1 == x2) ? intersection1.type < intersection2.type : x1 < x2;
 }
 
-void ExclusionPolygon::computeXIntersections(float y, bool isMinY, Vector<ExclusionInterval>& result) const
+static void computeXIntersections(const FloatPolygon& polygon, float y, bool isMinY, Vector<ExclusionInterval>& result)
 {
-    Vector<ExclusionPolygon::EdgeInterval> overlappingEdges;
-    m_edgeTree.allOverlaps(ExclusionPolygon::EdgeInterval(y, y, 0), overlappingEdges);
+    Vector<const FloatPolygonEdge*> edges;
+    if (!polygon.overlappingEdges(y, y, edges))
+        return;
 
     Vector<EdgeIntersection> intersections;
     EdgeIntersection intersection;
-    for (unsigned i = 0; i < overlappingEdges.size(); ++i) {
-        ExclusionPolygonEdge* edge = static_cast<ExclusionPolygonEdge*>(overlappingEdges[i].data());
-        if (computeXIntersection(edge, y, intersection) && intersection.type != VertexYBoth)
+    for (unsigned i = 0; i < edges.size(); ++i) {
+        if (computeXIntersection(edges[i], y, intersection) && intersection.type != VertexYBoth)
             intersections.append(intersection);
     }
+
     if (intersections.size() < 2)
         return;
 
@@ -263,10 +165,10 @@ void ExclusionPolygon::computeXIntersections(float y, bool isMinY, Vector<Exclus
             }
         }
 
-        const ExclusionPolygonEdge& thisEdge = *thisIntersection.edge;
+        const FloatPolygonEdge& thisEdge = *thisIntersection.edge;
         bool evenOddCrossing = !windCount;
 
-        if (fillRule() == RULE_EVENODD) {
+        if (polygon.fillRule() == RULE_EVENODD) {
             windCount += (thisEdge.vertex2().y() > thisEdge.vertex1().y()) ? 1 : -1;
             evenOddCrossing = evenOddCrossing || !windCount;
         }
@@ -295,15 +197,15 @@ void ExclusionPolygon::computeXIntersections(float y, bool isMinY, Vector<Exclus
     }
 }
 
-// Return the X projections of the edges that overlap y1,y2.
-void ExclusionPolygon::computeEdgeIntersections(float y1, float y2, Vector<ExclusionInterval>& result) const
+static void computeOverlappingEdgeXProjections(const FloatPolygon& polygon, float y1, float y2, Vector<ExclusionInterval>& result)
 {
-    Vector<ExclusionPolygon::EdgeInterval> overlappingEdges;
-    m_edgeTree.allOverlaps(ExclusionPolygon::EdgeInterval(y1, y2, 0), overlappingEdges);
+    Vector<const FloatPolygonEdge*> edges;
+    if (!polygon.overlappingEdges(y1, y2, edges))
+        return;
 
     EdgeIntersection intersection;
-    for (unsigned i = 0; i < overlappingEdges.size(); ++i) {
-        const ExclusionPolygonEdge *edge = static_cast<ExclusionPolygonEdge*>(overlappingEdges[i].data());
+    for (unsigned i = 0; i < edges.size(); ++i) {
+        const FloatPolygonEdge *edge = edges[i];
         float x1;
         float x2;
 
@@ -338,14 +240,14 @@ void ExclusionPolygon::getExcludedIntervals(float logicalTop, float logicalHeigh
     float y2 = y1 + logicalHeight;
 
     Vector<ExclusionInterval> y1XIntervals, y2XIntervals;
-    computeXIntersections(y1, true, y1XIntervals);
-    computeXIntersections(y2, false, y2XIntervals);
+    computeXIntersections(m_polygon, y1, true, y1XIntervals);
+    computeXIntersections(m_polygon, y2, false, y2XIntervals);
 
     Vector<ExclusionInterval> mergedIntervals;
     mergeExclusionIntervals(y1XIntervals, y2XIntervals, mergedIntervals);
 
     Vector<ExclusionInterval> edgeIntervals;
-    computeEdgeIntersections(y1, y2, edgeIntervals);
+    computeOverlappingEdgeXProjections(m_polygon, y1, y2, edgeIntervals);
 
     Vector<ExclusionInterval> excludedIntervals;
     mergeExclusionIntervals(mergedIntervals, edgeIntervals, excludedIntervals);
@@ -365,14 +267,14 @@ void ExclusionPolygon::getIncludedIntervals(float logicalTop, float logicalHeigh
     float y2 = y1 + logicalHeight;
 
     Vector<ExclusionInterval> y1XIntervals, y2XIntervals;
-    computeXIntersections(y1, true, y1XIntervals);
-    computeXIntersections(y2, false, y2XIntervals);
+    computeXIntersections(m_polygon, y1, true, y1XIntervals);
+    computeXIntersections(m_polygon, y2, false, y2XIntervals);
 
     Vector<ExclusionInterval> commonIntervals;
     intersectExclusionIntervals(y1XIntervals, y2XIntervals, commonIntervals);
 
     Vector<ExclusionInterval> edgeIntervals;
-    computeEdgeIntersections(y1, y2, edgeIntervals);
+    computeOverlappingEdgeXProjections(m_polygon, y1, y2, edgeIntervals);
 
     Vector<ExclusionInterval> includedIntervals;
     subtractExclusionIntervals(commonIntervals, edgeIntervals, includedIntervals);
@@ -383,98 +285,19 @@ void ExclusionPolygon::getIncludedIntervals(float logicalTop, float logicalHeigh
     }
 }
 
-static inline float leftSide(const FloatPoint& vertex1, const FloatPoint& vertex2, const FloatPoint& point)
-{
-    return ((point.x() - vertex1.x()) * (vertex2.y() - vertex1.y())) - ((vertex2.x() - vertex1.x()) * (point.y() - vertex1.y()));
-}
-
-bool ExclusionPolygon::contains(const FloatPoint& point) const
-{
-    if (!m_boundingBox.contains(point))
-        return false;
-
-    int windingNumber = 0;
-    for (unsigned i = 0; i < numberOfEdges(); ++i) {
-        const FloatPoint& vertex1 = edgeAt(i).vertex1();
-        const FloatPoint& vertex2 = edgeAt(i).vertex2();
-        if (isPointOnLineSegment(vertex1, vertex2, point))
-            return true;
-        if (vertex2.y() < point.y()) {
-            if ((vertex1.y() > point.y()) && (leftSide(vertex1, vertex2, point) > 0))
-                ++windingNumber;
-        } else if (vertex2.y() > point.y()) {
-            if ((vertex1.y() <= point.y()) && (leftSide(vertex1, vertex2, point) < 0))
-                --windingNumber;
-        }
-    }
-
-    return windingNumber;
-}
-
-bool VertexPair::overlapsRect(const FloatRect& rect) const
-{
-    bool boundsOverlap = (minX() < rect.maxX()) && (maxX() > rect.x()) && (minY() < rect.maxY()) && (maxY() > rect.y());
-    if (!boundsOverlap)
-        return false;
-
-    float leftSideValues[4] = {
-        leftSide(vertex1(), vertex2(), rect.minXMinYCorner()),
-        leftSide(vertex1(), vertex2(), rect.maxXMinYCorner()),
-        leftSide(vertex1(), vertex2(), rect.minXMaxYCorner()),
-        leftSide(vertex1(), vertex2(), rect.maxXMaxYCorner())
-    };
-
-    int currentLeftSideSign = 0;
-    for (unsigned i = 0; i < 4; ++i) {
-        if (!leftSideValues[i])
-            continue;
-        int leftSideSign = leftSideValues[i] > 0 ? 1 : -1;
-        if (!currentLeftSideSign)
-            currentLeftSideSign = leftSideSign;
-        else if (currentLeftSideSign != leftSideSign)
-            return true;
-    }
-
-    return false;
-}
-
 static inline bool isReflexVertex(const FloatPoint& prevVertex, const FloatPoint& vertex, const FloatPoint& nextVertex)
 {
     return leftSide(prevVertex, nextVertex, vertex) < 0;
 }
 
-bool VertexPair::intersection(const VertexPair& other, FloatPoint& point) const
-{
-    // See: http://paulbourke.net/geometry/pointlineplane/, "Intersection point of two lines in 2 dimensions"
-
-    const FloatSize& thisDelta = vertex2() - vertex1();
-    const FloatSize& otherDelta = other.vertex2() - other.vertex1();
-    float denominator = determinant(thisDelta, otherDelta);
-    if (!denominator)
-        return false;
-
-    // The two line segments: "this" vertex1,vertex2 and "other" vertex1,vertex2, have been defined
-    // in parametric form. Each point on the line segment is: vertex1 + u * (vertex2 - vertex1),
-    // when 0 <= u <= 1. We're computing the values of u for each line at their intersection point.
-
-    const FloatSize& vertex1Delta = vertex1() - other.vertex1();
-    float uThisLine = determinant(otherDelta, vertex1Delta) / denominator;
-    float uOtherLine = determinant(thisDelta, vertex1Delta) / denominator;
-
-    if (uThisLine < 0 || uOtherLine < 0 || uThisLine > 1 || uOtherLine > 1)
-        return false;
-
-    point = vertex1() + uThisLine * thisDelta;
-    return true;
-}
-
-bool ExclusionPolygon::firstFitRectInPolygon(const FloatRect& rect, unsigned offsetEdgeIndex1, unsigned offsetEdgeIndex2) const
+static inline bool firstFitRectInPolygon(const FloatPolygon& polygon, const FloatRect& rect, unsigned offsetEdgeIndex1, unsigned offsetEdgeIndex2)
 {
-    Vector<ExclusionPolygon::EdgeInterval> overlappingEdges;
-    m_edgeTree.allOverlaps(ExclusionPolygon::EdgeInterval(rect.y(), rect.maxY(), 0), overlappingEdges);
+    Vector<const FloatPolygonEdge*> edges;
+    if (!polygon.overlappingEdges(rect.y(), rect.maxY(), edges))
+        return true;
 
-    for (unsigned i = 0; i < overlappingEdges.size(); ++i) {
-        const ExclusionPolygonEdge* edge = static_cast<ExclusionPolygonEdge*>(overlappingEdges[i].data());
+    for (unsigned i = 0; i < edges.size(); ++i) {
+        const FloatPolygonEdge* edge = edges[i];
         if (edge->edgeIndex() != offsetEdgeIndex1 && edge->edgeIndex() != offsetEdgeIndex2 && edge->overlapsRect(rect))
             return false;
     }
@@ -493,24 +316,25 @@ static inline bool aboveOrToTheLeft(const FloatRect& r1, const FloatRect& r2)
 
 bool ExclusionPolygon::firstIncludedIntervalLogicalTop(float minLogicalIntervalTop, const FloatSize& minLogicalIntervalSize, float& result) const
 {
-    if (minLogicalIntervalSize.width() > m_boundingBox.width())
+    const FloatRect boundingBox = m_polygon.boundingBox();
+    if (minLogicalIntervalSize.width() > boundingBox.width())
         return false;
 
-    float minY = std::max(m_boundingBox.y(), minLogicalIntervalTop);
+    float minY = std::max(boundingBox.y(), minLogicalIntervalTop);
     float maxY = minY + minLogicalIntervalSize.height();
 
-    if (maxY > m_boundingBox.maxY())
+    if (maxY > boundingBox.maxY())
         return false;
 
-    Vector<ExclusionPolygon::EdgeInterval> overlappingEdges;
-    m_edgeTree.allOverlaps(ExclusionPolygon::EdgeInterval(minLogicalIntervalTop, m_boundingBox.maxY(), 0), overlappingEdges);
+    Vector<const FloatPolygonEdge*> edges;
+    m_polygon.overlappingEdges(minLogicalIntervalTop, boundingBox.maxY(), edges);
 
     float dx = minLogicalIntervalSize.width() / 2;
     float dy = minLogicalIntervalSize.height() / 2;
     Vector<OffsetPolygonEdge> offsetEdges;
 
-    for (unsigned i = 0; i < overlappingEdges.size(); ++i) {
-        const ExclusionPolygonEdge& edge = *static_cast<ExclusionPolygonEdge*>(overlappingEdges[i].data());
+    for (unsigned i = 0; i < edges.size(); ++i) {
+        const FloatPolygonEdge& edge = *(edges[i]);
         const FloatPoint& vertex0 = edge.previousEdge().vertex1();
         const FloatPoint& vertex1 = edge.vertex1();
         const FloatPoint& vertex2 = edge.vertex2();
@@ -540,7 +364,7 @@ bool ExclusionPolygon::firstIncludedIntervalLogicalTop(float minLogicalIntervalT
                 offsetEdges.append(offsetEdgeBuffer[j]);
     }
 
-    offsetEdges.append(OffsetPolygonEdge(*this, minLogicalIntervalTop, FloatSize(0, dy)));
+    offsetEdges.append(OffsetPolygonEdge(m_polygon, minLogicalIntervalTop, FloatSize(0, dy)));
 
     FloatPoint offsetEdgesIntersection;
     FloatRect firstFitRect;
@@ -553,8 +377,8 @@ bool ExclusionPolygon::firstIncludedIntervalLogicalTop(float minLogicalIntervalT
                 FloatRect potentialFirstFitRect(potentialFirstFitLocation, minLogicalIntervalSize);
                 if ((potentialFirstFitLocation.y() >= minLogicalIntervalTop)
                     && (!firstFitFound || aboveOrToTheLeft(potentialFirstFitRect, firstFitRect))
-                    && contains(offsetEdgesIntersection)
-                    && firstFitRectInPolygon(potentialFirstFitRect, offsetEdges[i].edgeIndex(), offsetEdges[j].edgeIndex())) {
+                    && m_polygon.contains(offsetEdgesIntersection)
+                    && firstFitRectInPolygon(m_polygon, potentialFirstFitRect, offsetEdges[i].edgeIndex(), offsetEdges[j].edgeIndex())) {
                     firstFitFound = true;
                     firstFitRect = potentialFirstFitRect;
                 }
index 62e1971..2332ee4 100644 (file)
 
 #include "ExclusionInterval.h"
 #include "ExclusionShape.h"
-#include "FloatPoint.h"
-#include "FloatRect.h"
-#include "PODIntervalTree.h"
-#include "WindRule.h"
-#include <wtf/MathExtras.h>
-#include <wtf/OwnPtr.h>
-#include <wtf/PassOwnPtr.h>
-#include <wtf/Vector.h>
+#include "FloatPolygon.h"
 
 namespace WebCore {
 
-class ExclusionPolygonEdge;
-
-// This class is used by PODIntervalTree for debugging.
-#ifndef NDEBUG
-template <class> struct ValueToString;
-#endif
-
-class ExclusionPolygon : public ExclusionShape {
-    WTF_MAKE_NONCOPYABLE(ExclusionPolygon);
-public:
-    ExclusionPolygon(PassOwnPtr<Vector<FloatPoint> > vertices, WindRule fillRule);
-
-    const FloatPoint& vertexAt(unsigned index) const { return (*m_vertices)[index]; }
-    unsigned numberOfVertices() const { return m_vertices->size(); }
-    WindRule fillRule() const { return m_fillRule; }
-
-    const ExclusionPolygonEdge& edgeAt(unsigned index) const { return m_edges[index]; }
-    unsigned numberOfEdges() const { return m_edges.size(); }
-
-    bool contains(const FloatPoint&) const;
-
-    virtual FloatRect shapeLogicalBoundingBox() const OVERRIDE { return m_boundingBox; }
-    virtual bool isEmpty() const OVERRIDE { return m_empty; }
-    virtual void getExcludedIntervals(float logicalTop, float logicalHeight, SegmentList&) const OVERRIDE;
-    virtual void getIncludedIntervals(float logicalTop, float logicalHeight, SegmentList&) const OVERRIDE;
-    virtual bool firstIncludedIntervalLogicalTop(float minLogicalIntervalTop, const FloatSize& minLogicalIntervalSize, float&) const OVERRIDE;
-
-private:
-    void computeXIntersections(float y, bool isMinY, Vector<ExclusionInterval>&) const;
-    void computeEdgeIntersections(float minY, float maxY, Vector<ExclusionInterval>&) const;
-    unsigned findNextEdgeVertexIndex(unsigned vertexIndex1, bool clockwise) const;
-    bool firstFitRectInPolygon(const FloatRect&, unsigned offsetEdgeIndex1, unsigned offsetEdgeIndex) const;
-
-    typedef PODInterval<float, ExclusionPolygonEdge*> EdgeInterval;
-    typedef PODIntervalTree<float, ExclusionPolygonEdge*> EdgeIntervalTree;
-
-    OwnPtr<Vector<FloatPoint> > m_vertices;
-    WindRule m_fillRule;
-    FloatRect m_boundingBox;
-    Vector<ExclusionPolygonEdge> m_edges;
-    EdgeIntervalTree m_edgeTree;
-    bool m_empty;
-};
-
-class VertexPair {
-public:
-    virtual ~VertexPair() { }
-
-    virtual const FloatPoint& vertex1() const = 0;
-    virtual const FloatPoint& vertex2() const = 0;
-
-    float minX() const { return std::min(vertex1().x(), vertex2().x()); }
-    float minY() const { return std::min(vertex1().y(), vertex2().y()); }
-    float maxX() const { return std::max(vertex1().x(), vertex2().x()); }
-    float maxY() const { return std::max(vertex1().y(), vertex2().y()); }
-
-    bool overlapsRect(const FloatRect&) const;
-    bool intersection(const VertexPair&, FloatPoint&) const;
-};
-
-// EdgeIntervalTree nodes store minY, maxY, and a ("UserData") pointer to an ExclusionPolygonEdge. Edge vertex
-// index1 is less than index2, except the last edge, where index2 is 0. When a polygon edge is defined by 3
-// or more colinear vertices, index2 can be the the index of the last colinear vertex.
-class ExclusionPolygonEdge : public VertexPair {
-    friend class ExclusionPolygon;
-public:
-    virtual const FloatPoint& vertex1() const OVERRIDE
-    {
-        ASSERT(m_polygon);
-        return m_polygon->vertexAt(m_vertexIndex1);
-    }
-
-    virtual const FloatPoint& vertex2() const OVERRIDE
-    {
-        ASSERT(m_polygon);
-        return m_polygon->vertexAt(m_vertexIndex2);
-    }
-
-    const ExclusionPolygonEdge& previousEdge() const
-    {
-        ASSERT(m_polygon && m_polygon->numberOfEdges() > 1);
-        return m_polygon->edgeAt((m_edgeIndex + m_polygon->numberOfEdges() - 1) % m_polygon->numberOfEdges());
-    }
-
-    const ExclusionPolygonEdge& nextEdge() const
-    {
-        ASSERT(m_polygon && m_polygon->numberOfEdges() > 1);
-        return m_polygon->edgeAt((m_edgeIndex + 1) % m_polygon->numberOfEdges());
-    }
-
-    const ExclusionPolygon* polygon() const { return m_polygon; }
-    unsigned vertexIndex1() const { return m_vertexIndex1; }
-    unsigned vertexIndex2() const { return m_vertexIndex2; }
-    unsigned edgeIndex() const { return m_edgeIndex; }
-
-private:
-    const ExclusionPolygon* m_polygon;
-    unsigned m_vertexIndex1;
-    unsigned m_vertexIndex2;
-    unsigned m_edgeIndex;
-};
-
-// These structures are used by PODIntervalTree for debugging.1
-#ifndef NDEBUG
-template <> struct ValueToString<float> {
-    static String string(const float value) { return String::number(value); }
-};
-
-template<> struct ValueToString<ExclusionPolygonEdge*> {
-    static String string(const ExclusionPolygonEdge* edge) { return String::format("%p (%f,%f %f,%f)", edge, edge->vertex1().x(), edge->vertex1().y(), edge->vertex2().x(), edge->vertex2().y()); }
-};
-#endif
-
 class OffsetPolygonEdge : public VertexPair {
 public:
-    OffsetPolygonEdge(const ExclusionPolygonEdge& edge, const FloatSize& offset)
+    OffsetPolygonEdge(const FloatPolygonEdge& edge, const FloatSize& offset)
         : m_vertex1(edge.vertex1() + offset)
         , m_vertex2(edge.vertex2() + offset)
         , m_edgeIndex(edge.edgeIndex())
@@ -172,9 +52,9 @@ public:
     {
     }
 
-    OffsetPolygonEdge(const ExclusionPolygon& polygon, float minLogicalIntervalTop, const FloatSize& offset)
-        : m_vertex1(FloatPoint(polygon.shapeLogicalBoundingBox().x(), minLogicalIntervalTop) + offset)
-        , m_vertex2(FloatPoint(polygon.shapeLogicalBoundingBox().maxX(), minLogicalIntervalTop) + offset)
+    OffsetPolygonEdge(const FloatPolygon& polygon, float minLogicalIntervalTop, const FloatSize& offset)
+        : m_vertex1(FloatPoint(polygon.boundingBox().x(), minLogicalIntervalTop) + offset)
+        , m_vertex2(FloatPoint(polygon.boundingBox().maxX(), minLogicalIntervalTop) + offset)
         , m_edgeIndex(-1)
     {
     }
@@ -189,6 +69,25 @@ private:
     int m_edgeIndex;
 };
 
+class ExclusionPolygon : public ExclusionShape {
+    WTF_MAKE_NONCOPYABLE(ExclusionPolygon);
+public:
+    ExclusionPolygon(PassOwnPtr<Vector<FloatPoint> > vertices, WindRule fillRule)
+        : ExclusionShape()
+        , m_polygon(vertices, fillRule)
+    {
+    }
+
+    virtual FloatRect shapeLogicalBoundingBox() const OVERRIDE { return m_polygon.boundingBox(); }
+    virtual bool isEmpty() const OVERRIDE { return m_polygon.isEmpty(); }
+    virtual void getExcludedIntervals(float logicalTop, float logicalHeight, SegmentList&) const OVERRIDE;
+    virtual void getIncludedIntervals(float logicalTop, float logicalHeight, SegmentList&) const OVERRIDE;
+    virtual bool firstIncludedIntervalLogicalTop(float minLogicalIntervalTop, const FloatSize& minLogicalIntervalSize, float&) const OVERRIDE;
+
+private:
+    FloatPolygon m_polygon;
+};
+
 } // namespace WebCore
 
 #endif // ExclusionPolygon_h