1ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com
28a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/*
3ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Copyright 2008 The Android Open Source Project
48a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com *
5ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Use of this source code is governed by a BSD-style license that can be
6ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * found in the LICENSE file.
78a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com */
88a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com
9ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com
10936b73424f7393994be832376287da988a52b993caryclark#include "SkMathPriv.h"
118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "SkPoint.h"
128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com
138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comvoid SkIPoint::rotateCW(SkIPoint* dst) const {
148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    SkASSERT(dst);
158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com
168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    // use a tmp in case this == dst
178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    int32_t tmp = fX;
188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    dst->fX = -fY;
198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    dst->fY = tmp;
208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com}
218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com
228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comvoid SkIPoint::rotateCCW(SkIPoint* dst) const {
238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    SkASSERT(dst);
248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com
258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    // use a tmp in case this == dst
268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    int32_t tmp = fX;
278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    dst->fX = fY;
288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    dst->fY = -tmp;
298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com}
308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com
318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com///////////////////////////////////////////////////////////////////////////////
328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com
337744c205f20b5617e83d4af8f97b5771bfa8d671reed@google.comvoid SkPoint::setIRectFan(int l, int t, int r, int b, size_t stride) {
347744c205f20b5617e83d4af8f97b5771bfa8d671reed@google.com    SkASSERT(stride >= sizeof(SkPoint));
35fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com
36fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com    ((SkPoint*)((intptr_t)this + 0 * stride))->set(SkIntToScalar(l),
377744c205f20b5617e83d4af8f97b5771bfa8d671reed@google.com                                                   SkIntToScalar(t));
38fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com    ((SkPoint*)((intptr_t)this + 1 * stride))->set(SkIntToScalar(l),
397744c205f20b5617e83d4af8f97b5771bfa8d671reed@google.com                                                   SkIntToScalar(b));
40fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com    ((SkPoint*)((intptr_t)this + 2 * stride))->set(SkIntToScalar(r),
417744c205f20b5617e83d4af8f97b5771bfa8d671reed@google.com                                                   SkIntToScalar(b));
42fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com    ((SkPoint*)((intptr_t)this + 3 * stride))->set(SkIntToScalar(r),
437744c205f20b5617e83d4af8f97b5771bfa8d671reed@google.com                                                   SkIntToScalar(t));
447744c205f20b5617e83d4af8f97b5771bfa8d671reed@google.com}
457744c205f20b5617e83d4af8f97b5771bfa8d671reed@google.com
467744c205f20b5617e83d4af8f97b5771bfa8d671reed@google.comvoid SkPoint::setRectFan(SkScalar l, SkScalar t, SkScalar r, SkScalar b,
477744c205f20b5617e83d4af8f97b5771bfa8d671reed@google.com                         size_t stride) {
487744c205f20b5617e83d4af8f97b5771bfa8d671reed@google.com    SkASSERT(stride >= sizeof(SkPoint));
49fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com
507744c205f20b5617e83d4af8f97b5771bfa8d671reed@google.com    ((SkPoint*)((intptr_t)this + 0 * stride))->set(l, t);
517744c205f20b5617e83d4af8f97b5771bfa8d671reed@google.com    ((SkPoint*)((intptr_t)this + 1 * stride))->set(l, b);
527744c205f20b5617e83d4af8f97b5771bfa8d671reed@google.com    ((SkPoint*)((intptr_t)this + 2 * stride))->set(r, b);
537744c205f20b5617e83d4af8f97b5771bfa8d671reed@google.com    ((SkPoint*)((intptr_t)this + 3 * stride))->set(r, t);
547744c205f20b5617e83d4af8f97b5771bfa8d671reed@google.com}
557744c205f20b5617e83d4af8f97b5771bfa8d671reed@google.com
568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comvoid SkPoint::rotateCW(SkPoint* dst) const {
578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    SkASSERT(dst);
588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com
598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    // use a tmp in case this == dst
608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    SkScalar tmp = fX;
618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    dst->fX = -fY;
628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    dst->fY = tmp;
638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com}
648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com
658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comvoid SkPoint::rotateCCW(SkPoint* dst) const {
668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    SkASSERT(dst);
678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com
688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    // use a tmp in case this == dst
698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    SkScalar tmp = fX;
708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    dst->fX = fY;
718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    dst->fY = -tmp;
728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com}
738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com
748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comvoid SkPoint::scale(SkScalar scale, SkPoint* dst) const {
758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    SkASSERT(dst);
768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    dst->set(SkScalarMul(fX, scale), SkScalarMul(fY, scale));
778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com}
788a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com
798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.combool SkPoint::normalize() {
808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    return this->setLength(fX, fY, SK_Scalar1);
818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com}
828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com
838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.combool SkPoint::setNormalize(SkScalar x, SkScalar y) {
848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    return this->setLength(x, y, SK_Scalar1);
858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com}
868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com
878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.combool SkPoint::setLength(SkScalar length) {
888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    return this->setLength(fX, fY, length);
898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com}
908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com
9194fa43c6255906660c2ff001fb462b6492cbdc07epoger@google.com// Returns the square of the Euclidian distance to (dx,dy).
9294fa43c6255906660c2ff001fb462b6492cbdc07epoger@google.comstatic inline float getLengthSquared(float dx, float dy) {
9394fa43c6255906660c2ff001fb462b6492cbdc07epoger@google.com    return dx * dx + dy * dy;
9494fa43c6255906660c2ff001fb462b6492cbdc07epoger@google.com}
9594fa43c6255906660c2ff001fb462b6492cbdc07epoger@google.com
9694fa43c6255906660c2ff001fb462b6492cbdc07epoger@google.com// Calculates the square of the Euclidian distance to (dx,dy) and stores it in
9794fa43c6255906660c2ff001fb462b6492cbdc07epoger@google.com// *lengthSquared.  Returns true if the distance is judged to be "nearly zero".
9894fa43c6255906660c2ff001fb462b6492cbdc07epoger@google.com//
9994fa43c6255906660c2ff001fb462b6492cbdc07epoger@google.com// This logic is encapsulated in a helper method to make it explicit that we
10094fa43c6255906660c2ff001fb462b6492cbdc07epoger@google.com// always perform this check in the same manner, to avoid inconsistencies
10194fa43c6255906660c2ff001fb462b6492cbdc07epoger@google.com// (see http://code.google.com/p/skia/issues/detail?id=560 ).
10294fa43c6255906660c2ff001fb462b6492cbdc07epoger@google.comstatic inline bool isLengthNearlyZero(float dx, float dy,
10394fa43c6255906660c2ff001fb462b6492cbdc07epoger@google.com                                      float *lengthSquared) {
10494fa43c6255906660c2ff001fb462b6492cbdc07epoger@google.com    *lengthSquared = getLengthSquared(dx, dy);
10594fa43c6255906660c2ff001fb462b6492cbdc07epoger@google.com    return *lengthSquared <= (SK_ScalarNearlyZero * SK_ScalarNearlyZero);
10694fa43c6255906660c2ff001fb462b6492cbdc07epoger@google.com}
10794fa43c6255906660c2ff001fb462b6492cbdc07epoger@google.com
108ac753098e8af4a17e5df97b3a4dd0ce123f8d70creed@android.comSkScalar SkPoint::Normalize(SkPoint* pt) {
1095a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com    float x = pt->fX;
1105a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com    float y = pt->fY;
11194fa43c6255906660c2ff001fb462b6492cbdc07epoger@google.com    float mag2;
1125a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com    if (isLengthNearlyZero(x, y, &mag2)) {
1135a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com        return 0;
114ac753098e8af4a17e5df97b3a4dd0ce123f8d70creed@android.com    }
1155a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com
1165a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com    float mag, scale;
1175a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com    if (SkScalarIsFinite(mag2)) {
1185a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com        mag = sk_float_sqrt(mag2);
1195a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com        scale = 1 / mag;
1205a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com    } else {
1215a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com        // our mag2 step overflowed to infinity, so use doubles instead.
1225a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com        // much slower, but needed when x or y are very large, other wise we
1235a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com        // divide by inf. and return (0,0) vector.
1245a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com        double xx = x;
1255a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com        double yy = y;
1265a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com        double magmag = sqrt(xx * xx + yy * yy);
1275a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com        mag = (float)magmag;
1285a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com        // we perform the divide with the double magmag, to stay exactly the
1295a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com        // same as setLength. It would be faster to perform the divide with
1305a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com        // mag, but it is possible that mag has overflowed to inf. but still
1315a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com        // have a non-zero value for scale (thanks to denormalized numbers).
1325a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com        scale = (float)(1 / magmag);
1335a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com    }
1345a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com    pt->set(x * scale, y * scale);
1355a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com    return mag;
136ac753098e8af4a17e5df97b3a4dd0ce123f8d70creed@android.com}
137ac753098e8af4a17e5df97b3a4dd0ce123f8d70creed@android.com
1381fd56dc6e189ea0e94b5df9af959c243573f8883epoger@google.comSkScalar SkPoint::Length(SkScalar dx, SkScalar dy) {
1395a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com    float mag2 = dx * dx + dy * dy;
1405a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com    if (SkScalarIsFinite(mag2)) {
1415a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com        return sk_float_sqrt(mag2);
1425a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com    } else {
1435a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com        double xx = dx;
1445a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com        double yy = dy;
1455a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com        return (float)sqrt(xx * xx + yy * yy);
1465a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com    }
1471fd56dc6e189ea0e94b5df9af959c243573f8883epoger@google.com}
1481fd56dc6e189ea0e94b5df9af959c243573f8883epoger@google.com
1495a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com/*
1505a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com *  We have to worry about 2 tricky conditions:
1515a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com *  1. underflow of mag2 (compared against nearlyzero^2)
1525a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com *  2. overflow of mag2 (compared w/ isfinite)
1535a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com *
1545a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com *  If we underflow, we return false. If we overflow, we compute again using
1555a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com *  doubles, which is much slower (3x in a desktop test) but will not overflow.
1565a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com */
1578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.combool SkPoint::setLength(float x, float y, float length) {
15894fa43c6255906660c2ff001fb462b6492cbdc07epoger@google.com    float mag2;
1595a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com    if (isLengthNearlyZero(x, y, &mag2)) {
1605a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com        return false;
1615a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com    }
1625a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com
1635a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com    float scale;
1645a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com    if (SkScalarIsFinite(mag2)) {
1655a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com        scale = length / sk_float_sqrt(mag2);
1665a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com    } else {
1675a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com        // our mag2 step overflowed to infinity, so use doubles instead.
1685a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com        // much slower, but needed when x or y are very large, other wise we
1695a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com        // divide by inf. and return (0,0) vector.
1705a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com        double xx = x;
1715a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com        double yy = y;
172936b73424f7393994be832376287da988a52b993caryclark    #ifdef SK_DISCARD_DENORMALIZED_FOR_SPEED
173936b73424f7393994be832376287da988a52b993caryclark        // The iOS ARM processor discards small denormalized numbers to go faster.
174936b73424f7393994be832376287da988a52b993caryclark        // Casting this to a float would cause the scale to go to zero. Keeping it
175936b73424f7393994be832376287da988a52b993caryclark        // as a double for the multiply keeps the scale non-zero.
176936b73424f7393994be832376287da988a52b993caryclark        double dscale = length / sqrt(xx * xx + yy * yy);
177936b73424f7393994be832376287da988a52b993caryclark        fX = x * dscale;
178936b73424f7393994be832376287da988a52b993caryclark        fY = y * dscale;
179936b73424f7393994be832376287da988a52b993caryclark        return true;
180936b73424f7393994be832376287da988a52b993caryclark    #else
1815a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com        scale = (float)(length / sqrt(xx * xx + yy * yy));
182936b73424f7393994be832376287da988a52b993caryclark    #endif
1838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    }
1845a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com    fX = x * scale;
1855a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com    fY = y * scale;
1865a5fe58595e881965c1a395885165eaccf2d44c5reed@google.com    return true;
1878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com}
1888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com
18911e5b972a984c7b4e09ba4dfeacc7bd805107c5acommit-bot@chromium.orgbool SkPoint::setLengthFast(float length) {
19011e5b972a984c7b4e09ba4dfeacc7bd805107c5acommit-bot@chromium.org    return this->setLengthFast(fX, fY, length);
1918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com}
1928a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com
19311e5b972a984c7b4e09ba4dfeacc7bd805107c5acommit-bot@chromium.orgbool SkPoint::setLengthFast(float x, float y, float length) {
19411e5b972a984c7b4e09ba4dfeacc7bd805107c5acommit-bot@chromium.org    float mag2;
19511e5b972a984c7b4e09ba4dfeacc7bd805107c5acommit-bot@chromium.org    if (isLengthNearlyZero(x, y, &mag2)) {
19611e5b972a984c7b4e09ba4dfeacc7bd805107c5acommit-bot@chromium.org        return false;
1978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    }
1988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com
19911e5b972a984c7b4e09ba4dfeacc7bd805107c5acommit-bot@chromium.org    float scale;
20011e5b972a984c7b4e09ba4dfeacc7bd805107c5acommit-bot@chromium.org    if (SkScalarIsFinite(mag2)) {
20111e5b972a984c7b4e09ba4dfeacc7bd805107c5acommit-bot@chromium.org        scale = length * sk_float_rsqrt(mag2);  // <--- this is the difference
2028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    } else {
20311e5b972a984c7b4e09ba4dfeacc7bd805107c5acommit-bot@chromium.org        // our mag2 step overflowed to infinity, so use doubles instead.
20411e5b972a984c7b4e09ba4dfeacc7bd805107c5acommit-bot@chromium.org        // much slower, but needed when x or y are very large, other wise we
20511e5b972a984c7b4e09ba4dfeacc7bd805107c5acommit-bot@chromium.org        // divide by inf. and return (0,0) vector.
20611e5b972a984c7b4e09ba4dfeacc7bd805107c5acommit-bot@chromium.org        double xx = x;
20711e5b972a984c7b4e09ba4dfeacc7bd805107c5acommit-bot@chromium.org        double yy = y;
20811e5b972a984c7b4e09ba4dfeacc7bd805107c5acommit-bot@chromium.org        scale = (float)(length / sqrt(xx * xx + yy * yy));
2098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    }
21011e5b972a984c7b4e09ba4dfeacc7bd805107c5acommit-bot@chromium.org    fX = x * scale;
21111e5b972a984c7b4e09ba4dfeacc7bd805107c5acommit-bot@chromium.org    fY = y * scale;
2128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    return true;
2138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com}
2148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com
2158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com
2167744c205f20b5617e83d4af8f97b5771bfa8d671reed@google.com///////////////////////////////////////////////////////////////////////////////
2177744c205f20b5617e83d4af8f97b5771bfa8d671reed@google.com
218647a804c3dd53b6743091ec97dd12111f90efec3bsalomon@google.comSkScalar SkPoint::distanceToLineBetweenSqd(const SkPoint& a,
219647a804c3dd53b6743091ec97dd12111f90efec3bsalomon@google.com                                           const SkPoint& b,
220647a804c3dd53b6743091ec97dd12111f90efec3bsalomon@google.com                                           Side* side) const {
221647a804c3dd53b6743091ec97dd12111f90efec3bsalomon@google.com
222647a804c3dd53b6743091ec97dd12111f90efec3bsalomon@google.com    SkVector u = b - a;
223647a804c3dd53b6743091ec97dd12111f90efec3bsalomon@google.com    SkVector v = *this - a;
224fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com
225647a804c3dd53b6743091ec97dd12111f90efec3bsalomon@google.com    SkScalar uLengthSqd = u.lengthSqd();
226647a804c3dd53b6743091ec97dd12111f90efec3bsalomon@google.com    SkScalar det = u.cross(v);
22749f085dddff10473b6ebf832a974288300224e60bsalomon    if (side) {
228647a804c3dd53b6743091ec97dd12111f90efec3bsalomon@google.com        SkASSERT(-1 == SkPoint::kLeft_Side &&
229647a804c3dd53b6743091ec97dd12111f90efec3bsalomon@google.com                  0 == SkPoint::kOn_Side &&
230647a804c3dd53b6743091ec97dd12111f90efec3bsalomon@google.com                  1 == kRight_Side);
231647a804c3dd53b6743091ec97dd12111f90efec3bsalomon@google.com        *side = (Side) SkScalarSignAsInt(det);
232647a804c3dd53b6743091ec97dd12111f90efec3bsalomon@google.com    }
233647a804c3dd53b6743091ec97dd12111f90efec3bsalomon@google.com    return SkScalarMulDiv(det, det, uLengthSqd);
234647a804c3dd53b6743091ec97dd12111f90efec3bsalomon@google.com}
235647a804c3dd53b6743091ec97dd12111f90efec3bsalomon@google.com
236647a804c3dd53b6743091ec97dd12111f90efec3bsalomon@google.comSkScalar SkPoint::distanceToLineSegmentBetweenSqd(const SkPoint& a,
2377744c205f20b5617e83d4af8f97b5771bfa8d671reed@google.com                                                  const SkPoint& b) const {
2387744c205f20b5617e83d4af8f97b5771bfa8d671reed@google.com    // See comments to distanceToLineBetweenSqd. If the projection of c onto
239fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com    // u is between a and b then this returns the same result as that
2407744c205f20b5617e83d4af8f97b5771bfa8d671reed@google.com    // function. Otherwise, it returns the distance to the closer of a and
2417744c205f20b5617e83d4af8f97b5771bfa8d671reed@google.com    // b. Let the projection of v onto u be v'.  There are three cases:
2427744c205f20b5617e83d4af8f97b5771bfa8d671reed@google.com    //    1. v' points opposite to u. c is not between a and b and is closer
2437744c205f20b5617e83d4af8f97b5771bfa8d671reed@google.com    //       to a than b.
2447744c205f20b5617e83d4af8f97b5771bfa8d671reed@google.com    //    2. v' points along u and has magnitude less than y. c is between
2457744c205f20b5617e83d4af8f97b5771bfa8d671reed@google.com    //       a and b and the distance to the segment is the same as distance
2467744c205f20b5617e83d4af8f97b5771bfa8d671reed@google.com    //       to the line ab.
2477744c205f20b5617e83d4af8f97b5771bfa8d671reed@google.com    //    3. v' points along u and has greater magnitude than u. c is not
2487744c205f20b5617e83d4af8f97b5771bfa8d671reed@google.com    //       not between a and b and is closer to b than a.
249fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com    // v' = (u dot v) * u / |u|. So if (u dot v)/|u| is less than zero we're
2507744c205f20b5617e83d4af8f97b5771bfa8d671reed@google.com    // in case 1. If (u dot v)/|u| is > |u| we are in case 3. Otherwise
251fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com    // we're in case 2. We actually compare (u dot v) to 0 and |u|^2 to
2527744c205f20b5617e83d4af8f97b5771bfa8d671reed@google.com    // avoid a sqrt to compute |u|.
253fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com
2547744c205f20b5617e83d4af8f97b5771bfa8d671reed@google.com    SkVector u = b - a;
2557744c205f20b5617e83d4af8f97b5771bfa8d671reed@google.com    SkVector v = *this - a;
256fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com
2577744c205f20b5617e83d4af8f97b5771bfa8d671reed@google.com    SkScalar uLengthSqd = u.lengthSqd();
2587744c205f20b5617e83d4af8f97b5771bfa8d671reed@google.com    SkScalar uDotV = SkPoint::DotProduct(u, v);
259fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com
2607744c205f20b5617e83d4af8f97b5771bfa8d671reed@google.com    if (uDotV <= 0) {
2617744c205f20b5617e83d4af8f97b5771bfa8d671reed@google.com        return v.lengthSqd();
2627744c205f20b5617e83d4af8f97b5771bfa8d671reed@google.com    } else if (uDotV > uLengthSqd) {
2637744c205f20b5617e83d4af8f97b5771bfa8d671reed@google.com        return b.distanceToSqd(*this);
2647744c205f20b5617e83d4af8f97b5771bfa8d671reed@google.com    } else {
2657744c205f20b5617e83d4af8f97b5771bfa8d671reed@google.com        SkScalar det = u.cross(v);
2667744c205f20b5617e83d4af8f97b5771bfa8d671reed@google.com        return SkScalarMulDiv(det, det, uLengthSqd);
2677744c205f20b5617e83d4af8f97b5771bfa8d671reed@google.com    }
2687744c205f20b5617e83d4af8f97b5771bfa8d671reed@google.com}
269