Comment faire pour déterminer si un point est à l'intérieur d'un quadrilatère

Objectif

Je veux déterminer si un point est dans un quadrilatère. Je vais probablement mettre en œuvre la solution dans Matlab, donc j'ai seulement besoin d'un pseudo-code.

Entrées

Coins du quadrilatère : (x1,y1) (x2,y2) (x3,y3) (x4,y4)

Point de Test : (xt, yt)

Sortie

1 - Si, dans le quadrilatère de la

0 - Sinon

Mise à jour

Il a été souligné que l'identification des sommets du quadrilatère n'est pas suffisant pour identifier de manière unique. Vous pouvez supposer que l'ordre des points détermine les côtés du quadrilatère (point 1 relie les 2, les 2 se connecte à 3, 3 se connecte à 4, 4 se connecte à 1)

Les points ne suffisent pas à identifier de manière unique un quadrilatère, à moins qu'il y a une contrainte supplémentaire qu'il est convexe, ou que les points sont définis dans un ordre donné. Est-ce un ou l'autre de ces contraintes existent (si oui, lequel)?
Par exemple, considérons un triangle équilatéral, avec un point supplémentaire dans le centre du triangle. Il suffit de savoir les points ne permet pas de savoir de quel bord du triangle a été tordu pour rencontrer le centre point.
Merci, mis à jour le problème pour le résoudre. Ce doit identifier de manière unique le quadrilatère.

OriginalL'auteur slykat | 2011-05-07

  1. 5

    Utilisation inpolygon. L'utilisation serait inpolygon(xt,yt,[x1 x2 x3 x4],[y1 y2 y3 y4])

    OriginalL'auteur Jacob

  2. 29

    Comment faire pour déterminer si un point est à l'intérieur d'un quadrilatère

    Vous pouvez tester le Point avec cette condition. Vous pouvez également traiter le quadrilatère que les 2 triangles pour calculer son aire.

    Cela fonctionne réellement? Son souffle mon esprit! Je suis en train de penser à un scénario, ceci ne fonctionnerait pas. Cela ne peut fonctionner que pour des quads trop à droite?! N'importe quelle forme. C'est trop génial.
    Merci. oui, Cela fonctionne pour n'importe quel polygone aussi !!!
    C'est une merveilleuse solution, mais il peut être facilement vu que cela ne fonctionne que pour les quadrilatères convexes.
    Peuvent travailler dans Matlab, mais d'autres langues comparer des nombres à virgule flottante se heurte à des questions d'arrondi. Mieux vaut utiliser pour tester si le point est sur le même côté de tous les rebords.

    OriginalL'auteur mili

  3. 2

    Puisque c'est un simple quadrilatère vous pouvez tester pour un point dans le triangle de chaque extrémité et un point dans le rectangle du milieu.

    MODIFIER Voici le pseudo-code pour point dans le triangle:

    function SameSide(p1,p2, a,b)
    cp1 = CrossProduct(b-a, p1-a)
    cp2 = CrossProduct(b-a, p2-a)
    if DotProduct(cp1, cp2) >= 0 then return true
    else return false

function PointInTriangle(p, a,b,c)
    if SameSide(p,a, b,c) and SameSide(p,b, a,c)
        and SameSide(p,c, a,b) then return true
    else return false

    Ou à l'aide de Barycentriques technique:

    A, B, et C sont le triangle, les points d'extrémité, P est le point en cours de test

    //Compute vectors        
v0 = C - A
v1 = B - A
v2 = P - A

//Compute dot products
dot00 = dot(v0, v0)
dot01 = dot(v0, v1)
dot02 = dot(v0, v2)
dot11 = dot(v1, v1)
dot12 = dot(v1, v2)

//Compute barycentric coordinates
invDenom = 1 /(dot00 * dot11 - dot01 * dot01)
u = (dot11 * dot02 - dot01 * dot12) * invDenom
v = (dot00 * dot12 - dot01 * dot02) * invDenom

//Check if point is in triangle
return (u > 0) && (v > 0) && (u + v < 1)

    OriginalL'auteur SRM

  4. 1

    en supposant que vous les coordonnées données sont disposées s.t.
    (x1,y1) = la plus à droite de coordonnées
    (x2,y2) = supérieure à coordonner
    (x3,y3) = de gauche à coordonner
    (x4,y4) = botoom-plus de coordonner

    Vous pouvez effectuer les opérations suivantes:

    1. calculate the 4 lines of the quadrilateral (we'll call these quad lines)
2. calculate 4 lines, from the (xt, yt) to every other coordinate (we'll call these new lines)
3. if any new line intersects any of the quad lines, then the coordinate is outside of the quadrilateral, otherwise it is inside.
    Cette solution ne fonctionne que pour les quadrilatères convexes.

    OriginalL'auteur Gal

  5. 1

    Si le but est de votre propre code de test, puis choisissez tout classique point dans le polygone d'essai à mettre en œuvre. Sinon, faire ce que Jacob suggère.

    OriginalL'auteur YXD

  6. 0

    Assumer A,B,C,D sont les sommets du quadrilatère et P est le point.
    Si P est à l'intérieur du quadrilatère puis tout point des produits dot(BP,BA), dot(BP,BC), dot(AP,AB), dot(AP,AD), dot(DP,DC), dot(DP,DA), dot(CP,CB) et dot(CP,CD) sera positif.
    Si P est en dehors du quadrilatère d'au moins un de ces produits sera négatif.

    OriginalL'auteur John Prospathopoulos