Pointe dans la coque convexe (2D)

10

Contexte

La coque convexe d'un nombre fini de points est le plus petit polygone convexe qui contient tous les points, soit sous forme de sommets, soit à l'intérieur. Pour plus d'informations, consultez cette question sur PGM qui la définit très bien .

Contribution

N+1Les coordonnées 2D ( N >= 3) sont passées STDIN(avec d'autres entrées de golf habituelles également autorisées) dans le format suivant (le nombre de décimales peut varier mais vous pouvez supposer qu'il reste "raisonnable" et chaque nombre peut être représenté comme un flottant):

0.00;0.00000
1;0.00
0.000;1.0000
-1.00;1.000000

Production

Une valeur véridique imprimée sur STDOUT(ou équivalent) si le premier point de la liste ( (0.00;0.00000)dans l'exemple ci-dessus) se trouve dans la coque convexe des N autres points, et une valeur fausse sinon.

Il s'agit de code-golf , donc la solution la plus courte en octets l'emporte.

  • Cas frontaliers : vous pouvez renvoyer n'importe quelle valeur (mais ne vous écrasez pas) si le point se trouve sur le bord de la coque convexe (c'est-à-dire sur un côté ou sur un sommet à la frontière extérieure de la coque), car il s'agit d'une probabilité nulle événement (selon toute probabilité raisonnable).

  • Interdit : tout (langage, opérateur, structure de données, intégré ou package) qui existe uniquement pour résoudre des problèmes géométriques (par exemple ConvexHull de Mathematica ). Les outils mathématiques à usage général (vecteurs, matrices, nombres complexes, etc.) sont autorisés.

Les tests

code-golf math geometry Alexandre Halm
la source
3
Qu'est-ce qu'une "structure de données ad hoc"?
DavidC
"fonctions / opérateurs élémentaires" est beaucoup trop vague.
xnor
@DavidCarraher: quelque chose comme un polygone, ou un triangle, ou un segment (tout ce qui existe uniquement pour résoudre des problèmes géométriques).
Alexandre Halm
2
@AlexandreHalm Votre montage a beaucoup aidé. Je pense que "élémentaire" n'est pas le bon mot. Je pensais que cela éliminerait les fonctions intégrées générales comme sortou round. Je pense qu'il est plus clair de simplement dire que rien de spécifiquement conçu pour la géométrie n'est autorisé. Mais qu'en est-il d'une fonction pour ajouter deux listes comme vecteurs? Ou une fonction pour trouver l'argument (angle) d'un nombre complexe?
xnor
1
C'est pourquoi les Diamants demandent aux gens d' utiliser le Sandbox avant de publier de nouveaux défis.
cat

Réponses:

9

J, 40 39 34 octets

3 :'(o.1)<(>./-<./)12 o.y*+{.y'@:-

Une fonction dyadique anonyme, prenant un point, p , comme l'un de ses arguments, et une liste de points, P , comme l'autre argument (peu importe quel argument est lequel), et renvoyant 0ou 1, si p est à l'extérieur ou à l'intérieur de la coque convexe de P , respectivement. Le point p et les points de P sont considérés comme des nombres complexes.

Exemple

  is_inside =: 3 :'(o.1)<(>./-<./)12 o.y*+{.y'@:-

  0.5j0.5  is_inside  0j0 0j1 1j0 1j1
1
  1.5j0.5  is_inside  0j0 0j1 1j0 1j1
0

ou...

Python 2, fonction, 121 103, programme complet, 162

Python 3, 149 octets

import sys,cmath as C
p,q,*P=[complex(*eval(l.replace(*";,")))for l in sys.stdin]
A=[C.phase((r-p)/(q-p+(q==p)))for r in P]
print(max(A)-min(A)>C.pi)

Prend l'entrée, dans le même format que le message d'origine, via STDIN, et imprime une valeur booléenne indiquant si p est dans la coque convexe de P

Explication

Le programme teste si la différence entre les angles maximum et minimum (signés) entre tout point r dans P , p et un point arbitraire fixe q dans P (nous utilisons simplement le premier point dans P ), est inférieure à 180 °. En d'autres termes, il teste si tous les points de P sont contenus dans un angle de 180 ° ou moins, autour de p . p est dans la coque convexe de P si et seulement si cette condition est fausse.

Au prix de quelques octets supplémentaires, nous pouvons utiliser une méthode similaire qui ne nous oblige pas à calculer explicitement les angles: Notez que la condition ci-dessus équivaut à dire que p est en dehors de la coque convexe de P si et seulement s'il existe une ligne l à p , de telle sorte que tous les points de P soient du même côté de l . Si une telle ligne existe, alors il y a aussi une telle ligne qui est incidente à un (ou plusieurs) des points de P (nous pouvons faire pivoter l jusqu'à ce qu'elle touche l'un des points de P ).

Pour (provisoirement) trouver cette ligne, nous commençons par laisser l être la ligne par p et le premier point P . Nous répétons ensuite le reste des points de P ; si l'un des points est à gauche de l (nous supposons que la directionnalité est partout, gauche ou droite n'a pas vraiment d'importance), nous remplaçons l par la ligne passant par p et ce point, et continuons. Après avoir itéré sur tout P , si (et seulement si) p est en dehors de la coque convexe, alors tous les points de P devraient être à droite de (ou sur) l . On vérifie qu'en utilisant un deuxième passage sur les points de P.

Python 2, 172 octets

import sys
P=[eval(l.replace(*";,"))for l in sys.stdin]
x,y=P.pop(0)
C=lambda(a,b),(c,d):(a-x)*(d-y)-(b-y)*(c-x)>0
l=reduce(lambda*x:x[C(*x)],P)
print any(C(l,q)for q in P)


Alternativement, pour faire la même chose en une seule passe, soit à gauche une représentation entre deux points quelconques, q et r , dans P , de telle sorte que q soit à gauche de r si q est à gauche de la ligne passant par p et r . On notera que to-the-gauche-de est une relation d'ordre sur P si et seulement si tous les points P sont du même côté d' une partie droite passant par p , qui est, si p est en dehors de l'enveloppe convexe de P . La procédure décrite ci-dessus trouve le point minimum dans Ppar rapport'a cet ordre, à savoir la « gauche » point P . Au lieu d'effectuer deux passes, nous pouvons trouver le maximum (c'est-à-dire, le point "le plus à droite"), ainsi que le minimum, les points en P par rapport au même ordre en une seule passe, et vérifier que le minimum est à gauche de la maximum, c'est-à-dire effectivement que celui de gauche est transitif.

Cela fonctionnerait bien si p est en dehors de la coque convexe de P , auquel cas à gauche est en fait une relation d'ordre, mais peut se casser lorsque p est à l'intérieur de la coque convexe (par exemple, essayez de comprendre ce qui va arriver si nous avons exécuté cet algorithme où les points dans P sont les sommets d'un pentagone régulier, dans le sens inverse des aiguilles d'une montre, et p est son centre.) Pour s'adapter, nous modifions légèrement l'algorithme: Nous sélectionnons un point q dans P , et bissectons P le long de la ligne passant par p et q (c'est-à-dire que nous partitionnons P autour de qpar rapport à gauche.) Nous avons maintenant une "partie gauche" et une "partie droite" de P , chacune contenue dans un demi-plan, de sorte que à gauche est une relation d'ordre sur chacune; nous trouvons le minimum de la partie gauche et le maximum de la partie droite et les comparons comme décrit ci-dessus. Bien sûr, nous n'avons pas à diviser physiquement P , nous pouvons simplement classer chaque point dans P en recherchant le minimum et le maximum, en une seule passe.

Python 2, 194 octets

import sys
P=[eval(l.replace(*";,"))for l in sys.stdin]
x,y=P.pop(0)
C=lambda(a,b),(c,d):(a-x)*(d-y)-(b-y)*(c-x)>0
l=r=P[0]
for q in P:
 if C(P[0],q):l=q*C(l,q)or l
 elif C(q,r):r=q
print C(l,r)
Aune
la source
Y a-t-il une chance que vous puissiez faire vos solutions (au moins celle de Python, je n'ai aucune idée si J peut le faire) prendre des entrées de STDIN? Je trouve qu'il serait plus facile de comparer des solutions avec des règles du jeu équitables. En supposant que l'entrée est déjà un ensemble préformaté de nombres ou de points complexes, c'est un peu un IMO extensible.
Alexandre Halm
@AlexandreHalm Ajout du programme complet.
Ell
Vous devez diviser vos solutions en une seule réponse par langue.
Mego
4

Octave, 82 72 octets

d=dlmread(0,";");i=2:rows(d);~isna(glpk(i,[d(i,:)';~~i],[d(1,:)';1]))&&1

L'idée est de vérifier si le programme linéaire min {c'x: Ax = b, e'x = 1, x> = 0} a une solution, où e est un vecteur de tous, les colonnes de A sont les coordonnées de le nuage de points, et b est le point de test, et c est arbitraire. En d'autres termes, nous essayons de représenter b comme une combinaison convexe de colonnes de A.

Pour exécuter le script, utilisez octave -f script.m <input.dat

han
la source
2

R, 207 octets

d=read.csv(file("stdin"),F,";")
q=function(i,j,k)abs(det(as.matrix(cbind(d[c(i,j,k),],1))))
t=function(i,j,k)q(i,j,k)==q(1,i,j)+q(1,i,k)+q(1,j,k)
any(apply(combn(2:nrow(d),3),2,function(v)t(v[1],v[2],v[3])))

Le script prend ses entrées de STDIN, par exemple Rscript script.R < inputFile.

Il génère tous les triangles à partir des Nderniers points (la dernière ligne apply(combn(...) et vérifie si le premier point est dans le triangle à l'aide de la tfonction.

tutilise la méthode area pour décider si Uest dans ABC: (écrire (ABC)pour la zone de ABC) Uest dans ABCiff (ABC) == (ABU) + (ACU) + (BCU). De plus, les surfaces sont calculées en utilisant la formule déterminante (voir ici pour une belle démo de Wolfram).

Je soupçonne que cette solution est plus sujette aux erreurs numériques que mon autre, mais elle fonctionne sur mes cas de test.

Alexandre Halm
la source
0

R, 282 octets

d=read.csv(file("stdin"),F,";")
p=function(a,b)a[1]*b[1]+a[2]*b[2]
t=function(a,b,c){A=d[a,];
U=d[1,]-A
B=d[b,]-A
C=d[c,]-A
f=p(C,C)
g=p(B,C)
h=p(U,C)
i=p(B,B)
j=p(U,B)
k=f*i-g*g
u=i*h-g*j
v=f*j-g*h
min(u*k,v*k,k-u-v)>0}
any(apply(combn(2:nrow(d),3),2,function(v)t(v[1],v[2],v[3])))

Le script prend ses entrées de STDIN, par exemple Rscript script.R < inputFile.

Il génère tous les triangles à partir des Nderniers points (la dernière ligne apply(combn(...) et vérifie si le premier point est dans le triangle à l'aide de la tfonction.

tutilise la méthode barycentrique pour décider si Uest en ABC: (écriture XYpour le Xau Yvecteur) depuis (AB,AC)une base pour le plan ( à l' exception des cas dégénérés où A, B, C sont alignés), AUpeut être écrite comme AU = u.AB + v.ACet Uest dans le triangle ssi u > 0 && v > 0 && u+v < 1. Voir par exemple ici pour une explication plus détaillée et un joli graphique interactif. NB: pour enregistrer quelques caractères et éviter les erreurs DIV0, nous calculons uniquement un raccourci vers uet vet un test modifié ( min(u*k,v*k,k-u-v)>0).

Les seuls opérateurs mathématiques utilisés sont +, -, *, min()>0.

Alexandre Halm
la source