1926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)/* 2926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) * Copyright (C) 2012 Adobe Systems Incorporated. All rights reserved. 3926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) * 4926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) * Redistribution and use in source and binary forms, with or without 5926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) * modification, are permitted provided that the following conditions 6926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) * are met: 7926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) * 8926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) * 1. Redistributions of source code must retain the above 9926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) * copyright notice, this list of conditions and the following 10926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) * disclaimer. 11926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) * 2. Redistributions in binary form must reproduce the above 12926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) * copyright notice, this list of conditions and the following 13926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) * disclaimer in the documentation and/or other materials 14926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) * provided with the distribution. 1502772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch * 16926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 19926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 20926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) * COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, 21926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 22926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 23926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 24926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 25926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 26926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 27926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) * OF THE POSSIBILITY OF SUCH DAMAGE. 28926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) */ 29926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 30926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)#include "config.h" 31f79f16f17ddc4f842d7b7a38603e280e94be826aTorne (Richard Coles)#include "platform/geometry/FloatPolygon.h" 32926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 337757ec2eadfa2dd8ac2aeed0a4399e9b07ec38cbBen Murdoch#include "wtf/MathExtras.h" 34926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 35c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)namespace blink { 36926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 37926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)static inline float determinant(const FloatSize& a, const FloatSize& b) 38926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles){ 39926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) return a.width() * b.height() - a.height() * b.width(); 40926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)} 41926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 42926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)static inline bool areCollinearPoints(const FloatPoint& p0, const FloatPoint& p1, const FloatPoint& p2) 43926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles){ 44926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) return !determinant(p1 - p0, p2 - p0); 45926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)} 46926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 47926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)static inline bool areCoincidentPoints(const FloatPoint& p0, const FloatPoint& p1) 48926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles){ 49926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) return p0.x() == p1.x() && p0.y() == p1.y(); 50926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)} 51926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 52926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)static inline bool isPointOnLineSegment(const FloatPoint& vertex1, const FloatPoint& vertex2, const FloatPoint& point) 53926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles){ 54926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) return point.x() >= std::min(vertex1.x(), vertex2.x()) 55926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) && point.x() <= std::max(vertex1.x(), vertex2.x()) 56926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) && areCollinearPoints(vertex1, vertex2, point); 57926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)} 58926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 59926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)static inline unsigned nextVertexIndex(unsigned vertexIndex, unsigned nVertices, bool clockwise) 60926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles){ 61926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) return ((clockwise) ? vertexIndex + 1 : vertexIndex - 1 + nVertices) % nVertices; 62926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)} 63926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 64926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)static unsigned findNextEdgeVertexIndex(const FloatPolygon& polygon, unsigned vertexIndex1, bool clockwise) 65926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles){ 66926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) unsigned nVertices = polygon.numberOfVertices(); 67926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) unsigned vertexIndex2 = nextVertexIndex(vertexIndex1, nVertices, clockwise); 68926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 69926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) while (vertexIndex2 && areCoincidentPoints(polygon.vertexAt(vertexIndex1), polygon.vertexAt(vertexIndex2))) 70926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) vertexIndex2 = nextVertexIndex(vertexIndex2, nVertices, clockwise); 71926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 72926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) while (vertexIndex2) { 73926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) unsigned vertexIndex3 = nextVertexIndex(vertexIndex2, nVertices, clockwise); 74926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) if (!areCollinearPoints(polygon.vertexAt(vertexIndex1), polygon.vertexAt(vertexIndex2), polygon.vertexAt(vertexIndex3))) 75926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) break; 76926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) vertexIndex2 = vertexIndex3; 77926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) } 78926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 79926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) return vertexIndex2; 80926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)} 81926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 82926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)FloatPolygon::FloatPolygon(PassOwnPtr<Vector<FloatPoint> > vertices, WindRule fillRule) 83926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) : m_vertices(vertices) 84926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) , m_fillRule(fillRule) 85926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles){ 86926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) unsigned nVertices = numberOfVertices(); 87926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) m_edges.resize(nVertices); 88926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) m_empty = nVertices < 3; 89926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 90926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) if (nVertices) 91926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) m_boundingBox.setLocation(vertexAt(0)); 92926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 93926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) if (m_empty) 94926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) return; 95926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 96926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) unsigned minVertexIndex = 0; 97926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) for (unsigned i = 1; i < nVertices; ++i) { 98926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) const FloatPoint& vertex = vertexAt(i); 99926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) if (vertex.y() < vertexAt(minVertexIndex).y() || (vertex.y() == vertexAt(minVertexIndex).y() && vertex.x() < vertexAt(minVertexIndex).x())) 100926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) minVertexIndex = i; 101926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) } 102926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) FloatPoint nextVertex = vertexAt((minVertexIndex + 1) % nVertices); 103926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) FloatPoint prevVertex = vertexAt((minVertexIndex + nVertices - 1) % nVertices); 104926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) bool clockwise = determinant(vertexAt(minVertexIndex) - prevVertex, nextVertex - prevVertex) > 0; 105926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 106926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) unsigned edgeIndex = 0; 107926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) unsigned vertexIndex1 = 0; 108926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) do { 109926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) m_boundingBox.extend(vertexAt(vertexIndex1)); 110926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) unsigned vertexIndex2 = findNextEdgeVertexIndex(*this, vertexIndex1, clockwise); 111926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) m_edges[edgeIndex].m_polygon = this; 112926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) m_edges[edgeIndex].m_vertexIndex1 = vertexIndex1; 113926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) m_edges[edgeIndex].m_vertexIndex2 = vertexIndex2; 114926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) m_edges[edgeIndex].m_edgeIndex = edgeIndex; 115926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) ++edgeIndex; 116926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) vertexIndex1 = vertexIndex2; 117926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) } while (vertexIndex1); 118926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 119926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) if (edgeIndex > 3) { 120926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) const FloatPolygonEdge& firstEdge = m_edges[0]; 121926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) const FloatPolygonEdge& lastEdge = m_edges[edgeIndex - 1]; 122926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) if (areCollinearPoints(lastEdge.vertex1(), lastEdge.vertex2(), firstEdge.vertex2())) { 123926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) m_edges[0].m_vertexIndex1 = lastEdge.m_vertexIndex1; 124926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) edgeIndex--; 125926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) } 126926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) } 127926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 128926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) m_edges.resize(edgeIndex); 129926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) m_empty = m_edges.size() < 3; 130926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 131926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) if (m_empty) 132926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) return; 133926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 134926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) for (unsigned i = 0; i < m_edges.size(); ++i) { 135926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) FloatPolygonEdge* edge = &m_edges[i]; 136926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) m_edgeTree.add(EdgeInterval(edge->minY(), edge->maxY(), edge)); 137926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) } 138926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)} 139926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 140926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)bool FloatPolygon::overlappingEdges(float minY, float maxY, Vector<const FloatPolygonEdge*>& result) const 141926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles){ 142926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) Vector<FloatPolygon::EdgeInterval> overlappingEdgeIntervals; 143926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) m_edgeTree.allOverlaps(FloatPolygon::EdgeInterval(minY, maxY, 0), overlappingEdgeIntervals); 144926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) unsigned overlappingEdgeIntervalsSize = overlappingEdgeIntervals.size(); 145926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) result.resize(overlappingEdgeIntervalsSize); 146926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) for (unsigned i = 0; i < overlappingEdgeIntervalsSize; ++i) { 147926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) const FloatPolygonEdge* edge = static_cast<const FloatPolygonEdge*>(overlappingEdgeIntervals[i].data()); 148926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) ASSERT(edge); 149926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) result[i] = edge; 150926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) } 151926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) return overlappingEdgeIntervalsSize > 0; 152926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)} 153926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 154926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)static inline float leftSide(const FloatPoint& vertex1, const FloatPoint& vertex2, const FloatPoint& point) 155926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles){ 156926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) return ((point.x() - vertex1.x()) * (vertex2.y() - vertex1.y())) - ((vertex2.x() - vertex1.x()) * (point.y() - vertex1.y())); 157926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)} 158926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 1599bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles)bool FloatPolygon::containsEvenOdd(const FloatPoint& point) const 160926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles){ 1619bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) unsigned crossingCount = 0; 1629bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) for (unsigned i = 0; i < numberOfEdges(); ++i) { 1639bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) const FloatPoint& vertex1 = edgeAt(i).vertex1(); 1649bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) const FloatPoint& vertex2 = edgeAt(i).vertex2(); 1659bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) if (isPointOnLineSegment(vertex1, vertex2, point)) 1669bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) return true; 1679bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) if ((vertex1.y() <= point.y() && vertex2.y() > point.y()) || (vertex1.y() > point.y() && vertex2.y() <= point.y())) { 1689bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) float vt = (point.y() - vertex1.y()) / (vertex2.y() - vertex1.y()); 1699bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) if (point.x() < vertex1.x() + vt * (vertex2.x() - vertex1.x())) 1709bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) ++crossingCount; 1719bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) } 1729bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) } 1739bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) return crossingCount & 1; 1749bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles)} 175926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 1769bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles)bool FloatPolygon::containsNonZero(const FloatPoint& point) const 1779bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles){ 178926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) int windingNumber = 0; 179926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) for (unsigned i = 0; i < numberOfEdges(); ++i) { 180926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) const FloatPoint& vertex1 = edgeAt(i).vertex1(); 181926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) const FloatPoint& vertex2 = edgeAt(i).vertex2(); 182926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) if (isPointOnLineSegment(vertex1, vertex2, point)) 183926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) return true; 18409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) if (vertex2.y() <= point.y()) { 185926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) if ((vertex1.y() > point.y()) && (leftSide(vertex1, vertex2, point) > 0)) 186926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) ++windingNumber; 18709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) } else if (vertex2.y() >= point.y()) { 188926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) if ((vertex1.y() <= point.y()) && (leftSide(vertex1, vertex2, point) < 0)) 189926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) --windingNumber; 190926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) } 191926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) } 192926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) return windingNumber; 193926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)} 194926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 1959bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles)bool FloatPolygon::contains(const FloatPoint& point) const 1969bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles){ 1979bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) if (!m_boundingBox.contains(point)) 1989bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) return false; 1999bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) return (fillRule() == RULE_NONZERO) ? containsNonZero(point) : containsEvenOdd(point); 2009bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles)} 2019bbd2f5e390b01907d97ecffde80aa1b06113aacTorne (Richard Coles) 202926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)bool VertexPair::intersection(const VertexPair& other, FloatPoint& point) const 203926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles){ 204926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) // See: http://paulbourke.net/geometry/pointlineplane/, "Intersection point of two lines in 2 dimensions" 205926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 206926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) const FloatSize& thisDelta = vertex2() - vertex1(); 207926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) const FloatSize& otherDelta = other.vertex2() - other.vertex1(); 208926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) float denominator = determinant(thisDelta, otherDelta); 209926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) if (!denominator) 210926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) return false; 211926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 212926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) // The two line segments: "this" vertex1,vertex2 and "other" vertex1,vertex2, have been defined 213926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) // in parametric form. Each point on the line segment is: vertex1 + u * (vertex2 - vertex1), 214926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) // when 0 <= u <= 1. We're computing the values of u for each line at their intersection point. 215926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 216926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) const FloatSize& vertex1Delta = vertex1() - other.vertex1(); 217926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) float uThisLine = determinant(otherDelta, vertex1Delta) / denominator; 218926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) float uOtherLine = determinant(thisDelta, vertex1Delta) / denominator; 219926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 220926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) if (uThisLine < 0 || uOtherLine < 0 || uThisLine > 1 || uOtherLine > 1) 221926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) return false; 222926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 223926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) point = vertex1() + uThisLine * thisDelta; 224926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) return true; 225926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)} 226926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 227c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)} // namespace blink 228