CODEWITHSUNDEEP
javageometry
user472221
user472221

Reputation: 3114

creating many triangles with different points

I have a question that in this link

you will see pointInTriangle Method with 4 parameters .I want to know that how can I send those 3 last parameters to this method when we have n points? Is there any way to do this at O(n^3)

please help me thanks

Upvotes: 2

Views: 283

Answers (2)

Grodriguez
Grodriguez

Reputation: 21995

Your question is not completely clear, but assuming you just want to extend this solution to check for n points, I guess you can do something like this:

private static float sign(fPoint p1, fPoint p2, fPoint p3)
{
    return (p1.x - p3.x) * (p2.y - p3.y) - (p2.x - p3.x) * (p1.y - p3.y);
}

public static boolean[] pointsInTriangle(fPoint[] pt, fPoint v1, fPoint v2, fPoint v3)
{
    boolean b1, b2, b3;

    boolean[] ret = new boolean[pt.length];
    for (int i = 0; i < pt.length; i++)
    {
        b1 = sign(pt[i], v1, v2) < 0.0f;
        b2 = sign(pt[i], v2, v3) < 0.0f;
        b3 = sign(pt[i], v3, v1) < 0.0f;
        ret[i] = ((b1 == b2) && (b2 == b3)); 
    }
    return ret;
}

By the way, this is O(n).

Upvotes: 0

dacwe
dacwe

Reputation: 43504

Can you use Polygon.contains(Point) instead?

Upvotes: 1

Related Questions