Est-ce dans le polygone?

Question

Le défi

Un point donné et un chemin de points, indiquez si le point se trouve ou non dans le polygone créé par le chemin.

Renvoie également truesi le point est sur une arête du polygone.

Contribution

Une liste de paires d'entiers.

Les 2 premiers entiers représentent le point.

Les paires restantes (3e et 4e, 5e et 6e etc.) représentent les sommets du polygone.

Les arêtes sont dans l'ordre des paires d'entrée.

Le chemin est supposé revenir au premier point du chemin.

L'entrée est supposée valide.

Trois points du tracé ne sont pas colinéaires.

ex. 123 82 84 01 83 42

Production

Une valeur vraie / fausse.

Cas de test

Entrée -> Sortie

0 0 10 10 10 -1 -5 0 -> true

5 5 10 10 10 50 50 20 -> false

5 5 0 0 0 10 1 20 6 30 10 -40 -> true

C'est du code-golf . La réponse la plus courte en octets l'emporte.

Answer 1

Charbon , 52 50 octets

≔⪪Ａ²θＦ⟦Ｅ³§θ⊖ιθ✂θ¹⟧⊞υ↔ΣＥι⁻קκ⁰§§ι⊕λ¹×§κ¹§§ι⊕λ⁰⁼⊟υΣυ

Essayez-le en ligne! Le lien est vers la version verbeuse du code. Explication:

≔⪪Ａ²θ

Divisez l'entrée en paires de coordonnées.

Ｆ⟦Ｅ³§θ⊖ιθ✂θ¹⟧

Calculez l'aire de trois polygones: celui formé en prenant le dernier, le premier et le deuxième points; celui formé de tous les points (y compris le point de test); celui formé de tous les points sauf le point de test.

⊞υ↔ΣＥι⁻קκ⁰§§ι⊕λ¹×§κ¹§§ι⊕λ⁰

Utilisez la formule des lacets pour calculer l'aire de ce polygone.

⁼⊟υΣυ

Vérifiez si la dernière zone correspond à la somme des deux premières. Si tel est le cas, le point se trouve dans le polygone.

Answer 2

Wolfram Language (Mathematica) , 26 octets

Polygon@#2~RegionMember~#&

Essayez-le en ligne!

Answer 3

JavaScript (V8) , 123 octets

(x,y,...p)=>p.map((_,i)=>p.concat(p).slice(i,i+4)).reduce((n,[a,b,c,d],i)=>i%2<1&&a<x!=c<x&&y<b+(d-b)*(x-a)/(c-a)?!n:n,!1)

Non golfées

(x, y, ...p)=>
  p.map((_, i) => p.concat(p).slice(i, i + 4)) // Group points into edges
  .reduce(
    (n, [a, b, c, d], i)=>                     // for every edge
      i % 2 < 1 &&                             // if it's actually an edge
      a < x != c < x &&                        // and x of point is within bounds
      y < b + (d - b) * (x - a) / (c - a) ?    // and point is below the line
      !n : n,                                  // then invert whether it's inside
    false
  )

TIO semble être en panne pour l'instant, j'ajouterai un lien quand je le pourrai (ou si quelqu'un d'autre arrive en premier)

Answer 4

PostgreSQL 12, 91 octets

create function f(a polygon,b point,out o bool)as $$begin return a~b;end$$language plpgsql;

PostgreSQL a des types de polygones et de points intégrés@> , et un opérateur intégré (également orthographié ~pour enregistrer un octet) pour tester le confinement.

... Est-ce trop ennuyeux?

Answer 5

Java 10, 142 141 octets

a->{var p=new java.awt.geom.Path2D.Float();p.moveTo(a[2],a[3]);for(int i=3;++i<a.length;)p.lineTo(a[i],a[++i]);return p.contains(a[0],a[1]);}

Essayez-le en ligne.

Explication:

a->{                         // Method with integer-array parameter and boolean return-type
  var p=new java.awt.geom.Path2D.Float();
                             //  Create a Path2D object
  p.moveTo(a[2],a[3]);       //  Set the starting position to the third and fourth values in the list
  for(int i=3;++i<a.length;) //  Loop `i` in the range (3, length):
    p.lineTo(                //   Draw a line to:
             a[i],           //    x = the `i`'th value in the array
             a[++i]);        //    y = the `i+1`'th value in the array
                             //        (by first increasing `i` by 1 with `++i`)
  return p.contains(a[0],a[1]);}
                             //  Check if the polygon contains the first two values as x,y

Answer 6

Scala , 139 octets

Si l'entrée est a (Int, Int)et a List[(Int, Int)]qui n'a pas besoin d'être analysée, c'est un peu plus facile

(x,p)=>(p.last->p.head::p.zip(p.tail)count{q=>(q._1._2<=x._2&x._2<=q._2._2|q._1._2>=x._2&x._2>=q._2._2)&(x._1<=q._1._1|x._1<=q._2._1)})%2>0

Essayez-le en ligne!

Utilisation du numéro d'enroulement, 140 octets

x=>y=>_.sliding(2).map{case Seq((a,b),(c,d))=>val(e,f,l)=(b>y,d>y,(a-x)*(d-y)-(c-x)*(b-y))
if(!e&f&l>0)1 else if(e& !f&l<0)-1 else 0}.sum!=0

Essayez-le en ligne!

Utilise l'algorithme décrit ici

Avec entrée sous forme de chaîne, 186 octets

i=>{val x::p=i split " "map(_.toInt)grouped 2 toList;(p.last->p.head::p.zip(p.tail)count{q=>(q._1(1)<=x(1)&x(1)<=q._2(1)|q._1(1)>=x(1)&x(1)>=q._2(1))&(x(0)<=q._1(0)|x(0)<=q._2(0))})%2>0}

Essayez-le en ligne!

Answer 7

C (gcc) , ^{171 \$\cdots\$ 129126} octets

Sauvegardé un énorme 13 19 35 octets grâce à plafonnier !!!
Sauvé 2 5 octets grâce à l' utilisateur !!!

W,i,l;f(x,y,V,n)int*V;{for(W=i=0;i<n-2;W+=V[i-2]>y^V[i]>y?(l>0)-(l<0):0)l=(V[i++]-x)*(V[i+2]-y)-(V[i++]-y)*(V[i]-x);return W;}

Essayez-le en ligne!

Utilise l'algorithme du nombre d'enroulement: si le nombre d'enroulement est vrai, le point se trouve à l'intérieur du polygone, sinon il est faux.

Answer 8

Python 3.8 (pré-version) , 134 octets

lambda x,y,p:sum((p[i+3]>y)^(p[i+1]>y)and(0<(l:=(p[i+2]-p[i])*(y-p[i+1])-(x-p[i])*(p[i+3]-p[i+1])))-(l<0)for i in range(0,len(p)-2,2))

Essayez-le en ligne!

Answer 9

R , 105 octets

function(P,m=matrix(c(P,P[3:4]),,2,T))!sd(sapply(3:nrow(m)-1,function(k)sign(det(diff(m[c(1,k+0:1),])))))

Essayez-le en ligne!

Suppose que trois points ne sont pas colinéaires. Étend l'algorithme décrit, par exemple ici .

Si nous appelons le point de requête \$Q\$et les points ordonnés du polygone \$P_1\dots P_n\$, cela traverse les points du polygone, vérifiant de quel côté du segment il se trouve en calculant la zone signée du triangle (en utilisant la méthode du lacet) formée par \$Q,P_{i},P_{i+1}\$: Un signe positif signifie à gauche, et négatif à droite si vous allez dans le sens antihoraire, sinon il est inversé. Si tous les signes sont identiques (c'est-à-dire que l'écart type des signes est de 0), alors le point est dans le polygone.

^{Mon professeur de géométrie informatique aurait un peu honte qu'il m'ait fallu quatre jours pour me souvenir de cette méthode point-dans-polygone. Si je peux trouver mon manuel / mes notes, je posterai sa description de l'algorithme ...}

Answer 10

> <> , 92 octets

l[l0$21.>&-0=n; {$&:2-&?!v{:{:{:@*{:}@@}@@}@@*-@@+
:0$0(?$-v>]
3pl2-00.>&08
{{{{600.>&-&084p

Implémente la technique de formule des lacets de Neil.

Answer 11

Python 3, 133 octets

Des packages spatiaux à la rescousse:

from shapely.geometry import*
def f(s):
 c=list(map(int,s.split()))
 o,*p=zip(c[::2],c[1::2])
 return Point(o).intersects(Polygon(p))

L'opération géométrique à utiliser était un petit piège. Polygon.contains(Point)ne couvre pas les cas de bord.

Answer 12

R , 139 127 118 116 octets

Edit: -23 octets en améliorant les calculs de lacets grâce à l'aiguillage de Giuseppe

function(i,S=function(m)abs(sum(m*c(1,-1)*m[2:1,c(2:ncol(m),1)])))S(P<-matrix(i,2))==S(P[,-1])-S(P[,c(1:2,ncol(P))])

Essayez-le en ligne!

Implémente la belle approche de Neils consistant à tester si la `` tranche de gâteau '' formée par le triangle avec le point de test + deux points de périmètre en tant que sommets est égale en surface à la surface du `` gâteau '' entier (le polygone de test) moins la surface de le «gâteau» avec la «tranche» supprimée (le polygone utilisant tous les points, y compris le point de test).

inside=
function(i)
    {                                           # S is helper function to calculate 2x the cake area using 
                                                # the 'shoelace' formula:
    S=function(m)abs(sum(m*c(1,-1)*m[2:1,c(2:ncol(m),1)])/2)            
    P=matrix(i,2)                               # 'cake with missing slice' = polygon including test point
    T=P[,c(1:2,ncol(P))]                        # 'slice of cake' = triangle of test point + adjacent polygon vertices
    O=P[,-1]                                    # 'the cake' = outer polygon excluding test point
    S(P)==S(O)-S(T)                             # do the areas add-up?
}

Answer 13

APL (Dyalog Unicode) , 63 octets

{⍵∊⍺:1⋄(¯1∊×d)∨1<|+/⍟d←(⊢÷1∘⌽)⍺-⍵}

Essayez-le en ligne!

Tiré directement d'un extrait APLcart. Je ne suis pas très sûr de ce qui se passe, et je serais heureux si quelqu'un pouvait donner une meilleure explication.

L'entrée est considérée comme des points complexes.

Prend un polygone à gauche et pointe à droite.

Explication

{⍵∊⍺:1⋄(¯1∊×d)∨1<|+/⍟d←(⊢÷1∘⌽)⍺-⍵}
{⍵∊⍺:1                           } return 1 if point is in list, otherwise:
      ⋄                       ⍺-⍵  subtract the point from each edge
                                   (gives all lines to from vertices to the point)
                       (⊢÷1∘⌽)     divide it by itself rotated by 1
                     d←            save it in d
                    ⍟              take the natural logarithm of each point
                  +/               and sum the vectors
                 |                 take the modulus
                                   (I think this gets the sum of angles)
               1<                  check if 1 is lesser than it
              ∨                    or
       (¯1∊×d)                     any of the points' signums equal (-1,0)