2010-11-18 39 views
2

我有一個問題,在這個link創建具有不同點的多個三角形

你會看到pointInTriangle方法有4個參數。我想知道,我怎麼能這3名最後的參數發送給此方法時,我們有N點?有什麼辦法在爲O(n^3)要做到這一點

請幫我謝謝

+0

三角形不超過三(3)個點。你是否想要一個函數來檢查一個點是否位於O(n^3)的** a _Polygon_中? – dacwe 2010-11-18 07:30:16

+0

@dacwe我假設他的意思是檢查n個點是否在三角形內,而不是檢查一個點是否在n邊多邊形內。 – Grodriguez 2010-11-18 07:36:32

+0

但看着他的鏈接,最後三個參數是三角點.. – dacwe 2010-11-18 07:39:57

回答

0

你的問題並不完全清楚,但假設你只是想延長this solution檢查n個點,我想你可以做這樣的事情:

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; 
} 

順便說一句,這是O(n )。