creating many triangles with different points

Question

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

A triangle does not have more than three (3) points. Do you want a function that checks if a point is **within** a _Polygon_ in O(n^3)? — dacwe, Nov 18 '10 at 07:30
@dacwe I assume he means checking whether n points are inside a triangle, rather than checking whether one point is inside a n-side polygon. — Grodriguez, Nov 18 '10 at 07:36
But looking at his link the last three parameters are the triangle points.. — dacwe, Nov 18 '10 at 07:39
@dacwe: Yes, the question is not completely clear. However since both the title and the tags mention "triangles", I believe he means checking n points against a triangle, instead of one point against a polygon -- but of course I could be wrong. — Grodriguez, Nov 18 '10 at 07:47
@user472221: Perhaps you should clarify the question instead of us trying to find out what you actually meant :-) — Grodriguez, Nov 18 '10 at 07:49

dacwe · Accepted Answer · 2010-11-18T07:27:37.200

1

Can you use Polygon.contains(Point) instead?

edited Nov 18 '10 at 07:27

answered Nov 18 '10 at 06:42

dacwe

43,066
12
116
140

Polygon does it in O(n), that's way better! :) – dacwe Nov 18 '10 at 08:04

score 0 · Answer 2 · edited May 23 '17 at 12:18

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).

creating many triangles with different points

2 Answers2