This source file includes following definitions.
- determinant
- areCollinearPoints
- areCoincidentPoints
- isPointOnLineSegment
- nextVertexIndex
- findNextEdgeVertexIndex
- m_fillRule
- overlappingEdges
- leftSide
- containsEvenOdd
- containsNonZero
- contains
- overlapsRect
- intersection
#include "config.h"
#include "platform/geometry/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::containsEvenOdd(const FloatPoint& point) const
{
unsigned crossingCount = 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 ((vertex1.y() <= point.y() && vertex2.y() > point.y()) || (vertex1.y() > point.y() && vertex2.y() <= point.y())) {
float vt = (point.y() - vertex1.y()) / (vertex2.y() - vertex1.y());
if (point.x() < vertex1.x() + vt * (vertex2.x() - vertex1.x()))
++crossingCount;
}
}
return crossingCount & 1;
}
bool FloatPolygon::containsNonZero(const FloatPoint& point) const
{
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 FloatPolygon::contains(const FloatPoint& point) const
{
if (!m_boundingBox.contains(point))
return false;
return (fillRule() == RULE_NONZERO) ? containsNonZero(point) : containsEvenOdd(point);
}
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
{
const FloatSize& thisDelta = vertex2() - vertex1();
const FloatSize& otherDelta = other.vertex2() - other.vertex1();
float denominator = determinant(thisDelta, otherDelta);
if (!denominator)
return false;
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;
}
}