107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com/* 207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * Copyright 2012 Google Inc. 307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * 407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * Use of this source code is governed by a BSD-style license that can be 507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * found in the LICENSE file. 607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com */ 707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#include "SkPathOpsLine.h" 807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comSkDLine SkDLine::subDivide(double t1, double t2) const { 1007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDVector delta = tangent(); 1107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDLine dst = {{{ 1207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com fPts[0].fX - t1 * delta.fX, fPts[0].fY - t1 * delta.fY}, { 1307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com fPts[0].fX - t2 * delta.fX, fPts[0].fY - t2 * delta.fY}}}; 1407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return dst; 1507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 1607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 1707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// may have this below somewhere else already: 1807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// copying here because I thought it was clever 1907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 2007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// Copyright 2001, softSurfer (www.softsurfer.com) 2107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// This code may be freely used and modified for any purpose 2207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// providing that this copyright notice is included with it. 2307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// SoftSurfer makes no warranty for this code, and cannot be held 2407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// liable for any real or imagined damage resulting from its use. 2507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// Users of this code must verify correctness for their application. 2607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 2707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// Assume that a class is already given for the object: 2807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// Point with coordinates {float x, y;} 2907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com//=================================================================== 3007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 3107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// isLeft(): tests if a point is Left|On|Right of an infinite line. 3207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// Input: three points P0, P1, and P2 3307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// Return: >0 for P2 left of the line through P0 and P1 3407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// =0 for P2 on the line 3507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// <0 for P2 right of the line 3607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// See: the January 2001 Algorithm on Area of Triangles 3707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// return (float) ((P1.x - P0.x)*(P2.y - P0.y) - (P2.x - P0.x)*(P1.y - P0.y)); 3807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comdouble SkDLine::isLeft(const SkDPoint& pt) const { 3907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDVector p0 = fPts[1] - fPts[0]; 4007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDVector p2 = pt - fPts[0]; 4107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return p0.cross(p2); 4207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 4307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 444fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.comSkDPoint SkDLine::ptAtT(double t) const { 454fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com if (0 == t) { 464fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com return fPts[0]; 474fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com } 484fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com if (1 == t) { 494fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com return fPts[1]; 504fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com } 5107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double one_t = 1 - t; 5207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDPoint result = { one_t * fPts[0].fX + t * fPts[1].fX, one_t * fPts[0].fY + t * fPts[1].fY }; 5307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return result; 5407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 55fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com 56fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.comdouble SkDLine::exactPoint(const SkDPoint& xy) const { 57fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com if (xy == fPts[0]) { // do cheapest test first 58fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com return 0; 59fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 60fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com if (xy == fPts[1]) { 61fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com return 1; 62fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 63fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com return -1; 64fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com} 65fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com 66dac1d17027dcaa5596885a9f333979418b35001ccaryclarkdouble SkDLine::nearPoint(const SkDPoint& xy, bool* unequal) const { 67fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com if (!AlmostBetweenUlps(fPts[0].fX, xy.fX, fPts[1].fX) 68fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com || !AlmostBetweenUlps(fPts[0].fY, xy.fY, fPts[1].fY)) { 69fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com return -1; 70fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 71fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com // project a perpendicular ray from the point to the line; find the T on the line 72fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com SkDVector len = fPts[1] - fPts[0]; // the x/y magnitudes of the line 73fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com double denom = len.fX * len.fX + len.fY * len.fY; // see DLine intersectRay 74fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com SkDVector ab0 = xy - fPts[0]; 75fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com double numer = len.fX * ab0.fX + ab0.fY * len.fY; 76fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com if (!between(0, numer, denom)) { 77fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com return -1; 78fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 79fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com double t = numer / denom; 804fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com SkDPoint realPt = ptAtT(t); 81570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com double dist = realPt.distance(xy); // OPTIMIZATION: can we compare against distSq instead ? 82fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com // find the ordinal in the original line with the largest unsigned exponent 83fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com double tiniest = SkTMin(SkTMin(SkTMin(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY); 84fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com double largest = SkTMax(SkTMax(SkTMax(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY); 85fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com largest = SkTMax(largest, -tiniest); 86fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com if (!AlmostEqualUlps(largest, largest + dist)) { // is the dist within ULPS tolerance? 87fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com return -1; 88fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 89dac1d17027dcaa5596885a9f333979418b35001ccaryclark if (unequal) { 90dac1d17027dcaa5596885a9f333979418b35001ccaryclark *unequal = (float) largest != (float) (largest + dist); 91dac1d17027dcaa5596885a9f333979418b35001ccaryclark } 9265b427cff9cd34a06ff060d65d00cc3615d8fd94caryclark t = SkPinT(t); // a looser pin breaks skpwww_lptemp_com_3 93fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com SkASSERT(between(0, t, 1)); 94fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com return t; 95fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com} 96fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com 97570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.combool SkDLine::nearRay(const SkDPoint& xy) const { 98570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com // project a perpendicular ray from the point to the line; find the T on the line 99570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com SkDVector len = fPts[1] - fPts[0]; // the x/y magnitudes of the line 100570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com double denom = len.fX * len.fX + len.fY * len.fY; // see DLine intersectRay 101570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com SkDVector ab0 = xy - fPts[0]; 102570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com double numer = len.fX * ab0.fX + ab0.fY * len.fY; 103570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com double t = numer / denom; 104570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com SkDPoint realPt = ptAtT(t); 105570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com double dist = realPt.distance(xy); // OPTIMIZATION: can we compare against distSq instead ? 106570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com // find the ordinal in the original line with the largest unsigned exponent 107570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com double tiniest = SkTMin(SkTMin(SkTMin(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY); 108570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com double largest = SkTMax(SkTMax(SkTMax(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY); 109570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com largest = SkTMax(largest, -tiniest); 110570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com return RoughlyEqualUlps(largest, largest + dist); // is the dist within ULPS tolerance? 111570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com} 112570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com 113570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com// Returns true if a ray from (0,0) to (x1,y1) is coincident with a ray (0,0) to (x2,y2) 114570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com// OPTIMIZE: a specialty routine could speed this up -- may not be called very often though 115570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.combool SkDLine::NearRay(double x1, double y1, double x2, double y2) { 116570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com double denom1 = x1 * x1 + y1 * y1; 117570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com double denom2 = x2 * x2 + y2 * y2; 118570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com SkDLine line = {{{0, 0}, {x1, y1}}}; 119570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com SkDPoint pt = {x2, y2}; 120570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com if (denom2 > denom1) { 121570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com SkTSwap(line[1], pt); 122570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 123570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com return line.nearRay(pt); 124570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com} 125570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com 126fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.comdouble SkDLine::ExactPointH(const SkDPoint& xy, double left, double right, double y) { 127fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com if (xy.fY == y) { 128fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com if (xy.fX == left) { 129fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com return 0; 130fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 131fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com if (xy.fX == right) { 132fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com return 1; 133fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 134fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 135fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com return -1; 136fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com} 137fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com 138fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.comdouble SkDLine::NearPointH(const SkDPoint& xy, double left, double right, double y) { 139570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com if (!AlmostBequalUlps(xy.fY, y)) { 140fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com return -1; 141fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 142fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com if (!AlmostBetweenUlps(left, xy.fX, right)) { 143fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com return -1; 144fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 145fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com double t = (xy.fX - left) / (right - left); 146fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com t = SkPinT(t); 147fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com SkASSERT(between(0, t, 1)); 148570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com double realPtX = (1 - t) * left + t * right; 149570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com SkDVector distU = {xy.fY - y, xy.fX - realPtX}; 150570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com double distSq = distU.fX * distU.fX + distU.fY * distU.fY; 151570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com double dist = sqrt(distSq); // OPTIMIZATION: can we compare against distSq instead ? 152570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com double tiniest = SkTMin(SkTMin(y, left), right); 153570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com double largest = SkTMax(SkTMax(y, left), right); 154570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com largest = SkTMax(largest, -tiniest); 155570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com if (!AlmostEqualUlps(largest, largest + dist)) { // is the dist within ULPS tolerance? 156570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com return -1; 157570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 158fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com return t; 159fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com} 160fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com 161fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.comdouble SkDLine::ExactPointV(const SkDPoint& xy, double top, double bottom, double x) { 162fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com if (xy.fX == x) { 163fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com if (xy.fY == top) { 164fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com return 0; 165fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 166fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com if (xy.fY == bottom) { 167fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com return 1; 168fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 169fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 170fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com return -1; 171fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com} 172fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com 173fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.comdouble SkDLine::NearPointV(const SkDPoint& xy, double top, double bottom, double x) { 174570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com if (!AlmostBequalUlps(xy.fX, x)) { 175fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com return -1; 176fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 177fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com if (!AlmostBetweenUlps(top, xy.fY, bottom)) { 178fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com return -1; 179fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 180fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com double t = (xy.fY - top) / (bottom - top); 181fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com t = SkPinT(t); 182fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com SkASSERT(between(0, t, 1)); 183570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com double realPtY = (1 - t) * top + t * bottom; 184570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com SkDVector distU = {xy.fX - x, xy.fY - realPtY}; 185570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com double distSq = distU.fX * distU.fX + distU.fY * distU.fY; 186570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com double dist = sqrt(distSq); // OPTIMIZATION: can we compare against distSq instead ? 187570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com double tiniest = SkTMin(SkTMin(x, top), bottom); 188570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com double largest = SkTMax(SkTMax(x, top), bottom); 189570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com largest = SkTMax(largest, -tiniest); 190570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com if (!AlmostEqualUlps(largest, largest + dist)) { // is the dist within ULPS tolerance? 191570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com return -1; 192570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 193fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com return t; 194fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com} 195