1/*
2 * Copyright (C) 2012 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16package android.webkit;
17
18import android.graphics.PointF;
19
20/**
21 * A quadrilateral, determined by four points, clockwise order. Typically
22 * p1 is "top-left" and p4 is "bottom-left" following webkit's rectangle-to-
23 * FloatQuad conversion.
24 */
25class QuadF {
26    public PointF p1;
27    public PointF p2;
28    public PointF p3;
29    public PointF p4;
30
31    public QuadF() {
32        p1 = new PointF();
33        p2 = new PointF();
34        p3 = new PointF();
35        p4 = new PointF();
36    }
37
38    public void offset(float dx, float dy) {
39        p1.offset(dx, dy);
40        p2.offset(dx, dy);
41        p3.offset(dx, dy);
42        p4.offset(dx, dy);
43    }
44
45    /**
46     * Determines if the quadrilateral contains the given point. This does
47     * not work if the quadrilateral is self-intersecting or if any inner
48     * angle is reflex (greater than 180 degrees).
49     */
50    public boolean containsPoint(float x, float y) {
51        return isPointInTriangle(x, y, p1, p2, p3) ||
52                isPointInTriangle(x, y, p1, p3, p4);
53    }
54
55    @Override
56    public String toString() {
57        StringBuilder s = new StringBuilder("QuadF(");
58        s.append(p1.x).append(",").append(p1.y);
59        s.append(" - ");
60        s.append(p2.x).append(",").append(p2.y);
61        s.append(" - ");
62        s.append(p3.x).append(",").append(p3.y);
63        s.append(" - ");
64        s.append(p4.x).append(",").append(p4.y);
65        s.append(")");
66        return s.toString();
67    }
68
69    private static boolean isPointInTriangle(float x0, float y0,
70            PointF r1, PointF r2, PointF r3) {
71        // Use the barycentric technique
72        float x13 = r1.x - r3.x;
73        float y13 = r1.y - r3.y;
74        float x23 = r2.x - r3.x;
75        float y23 = r2.y - r3.y;
76        float x03 = x0 - r3.x;
77        float y03 = y0 - r3.y;
78
79        float determinant = (y23 * x13) - (x23 * y13);
80        float lambda1 = ((y23 * x03) - (x23 * y03))/determinant;
81        float lambda2 = ((x13 * y03) - (y13 * x03))/determinant;
82        float lambda3 = 1 - lambda1 - lambda2;
83        return lambda1 >= 0.0f && lambda2 >= 0.0f && lambda3 >= 0.0f;
84    }
85}
86