È nel poligono?
La sfida
Dato un punto e un percorso di punti, dite se il punto si trova o meno nel poligono creato dal percorso.
Restituisce anche true
se il punto si trova su un bordo del poligono.
Ingresso
Un elenco di coppie di numeri interi.
I primi 2 numeri interi rappresentano il punto.
Le coppie rimanenti (3a e 4a, 5a e 6a ecc.) Rappresentano i vertici del poligono.
I bordi sono nell'ordine delle coppie di input.
Si presume che il percorso ritorni al primo punto del percorso.
Si presume che l'input sia valido.
Non ci sono tre punti nel percorso collineari.
ex. 123 82 84 01 83 42
Produzione
Un valore vero / falso.
Casi test
Ingresso -> Uscita
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
Questo è il golf in codice . La risposta più breve in byte vince.
Risposte
Carboncino , 52 50 byte
≔⪪A²θF⟦E³§θ⊖ιθ✂θ¹⟧⊞υ↔ΣEι⁻×§κ⁰§§ι⊕λ¹×§κ¹§§ι⊕λ⁰⁼⊟υΣυ
Provalo online! Il collegamento è alla versione dettagliata del codice. Spiegazione:
≔⪪A²θ
Dividi l'input in coppie di coordinate.
F⟦E³§θ⊖ιθ✂θ¹⟧
Calcola l'area di tre poligoni: quello formato prendendo l'ultimo, il primo e il secondo punto; quello formato da tutti i punti (compreso il punto di prova); quello formato da tutti i punti tranne il punto di prova.
⊞υ↔ΣEι⁻×§κ⁰§§ι⊕λ¹×§κ¹§§ι⊕λ⁰
Usa la formula del laccio per calcolare l'area di quel poligono.
⁼⊟υΣυ
Controlla se l'ultima area è uguale alla somma delle prime due. Se questo è il caso, il punto si trova all'interno del poligono.
Wolfram Language (Mathematica) , 26 byte
Polygon@#2~RegionMember~#&
Provalo online!
JavaScript (V8) , 123 byte
(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)
Ungolfed
(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 sembra essere inattivo per ora, aggiungerò un collegamento quando posso (o se prima capita qualcun altro)
PostgreSQL 12, 91 byte
create function f(a polygon,b point,out o bool)as $$begin return a~b;end$$language plpgsql;
PostgreSQL ha poligoni e tipi di punto incorporati@> e un operatore incorporato (anche scritto ~
per salvare un byte) per testare il contenimento.
... è troppo noioso?
Java 10, 142 141 byte
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]);}
Provalo online.
Spiegazione:
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
Scala , 139 byte
Se l'input è un (Int, Int)
e un List[(Int, Int)]
che non deve essere analizzato, è un po 'più semplice
(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
Provalo online!
Utilizzando il numero di avvolgimento, 140 byte
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
Provalo online!
Utilizza l'algoritmo qui descritto
Con input come stringa, 186 byte
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}
Provalo online!
C (gcc) , 171 \$\cdots\$ 129 126 byte
Ho risparmiato ben 13 19 35 byte grazie a Ceilingcat !!!
Salvato 2 5 byte grazie all'utente !!!
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;}
Provalo online!
Utilizza l'algoritmo del numero di avvolgimento: se il numero di avvolgimento è vero, il punto si trova all'interno del poligono, altrimenti è falso.
Python 3.8 (pre-rilascio) , 134 byte
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))
Provalo online!
R , 105 byte
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),])))))
Provalo online!
Presuppone che non ci siano tre punti collineari. Estende l'algoritmo descritto, ad esempio, qui .
Se chiamiamo il punto di interrogazione \$Q\$e i punti ordinati del poligono \$P_1\dots P_n\$, questo attraversa i punti del poligono, controllando per vedere su quale lato del segmento si trova calcolando l'area segnata del triangolo (usando il metodo dei lacci) formata da \$Q,P_{i},P_{i+1}\$: Un segno positivo significa a sinistra e negativo a destra se stai andando in senso antiorario, altrimenti è invertito. Se tutti i segni sono uguali (ovvero, la deviazione standard dei segni è 0), il punto si trova all'interno del poligono.
Il mio professore di geometria computazionale si vergognerebbe un po 'se mi ci sono voluti quattro giorni per ricordare questo metodo point-in-polygon. Se riesco a trovare il mio libro di testo / note, posterò la sua descrizione dell'algoritmo ...
> <> , 92 byte
l[l0$21.>&-0=n; {$&:2-&?!v{:{:{:@*{:}@@}@@}@@*-@@+
:0$0(?$-v>]
3pl2-00.>&08
{{{{600.>&-&084p
Implementa la tecnica della formula dei lacci delle scarpe di Neil.
Python 3, 133 byte
Pacchetti spaziali in soccorso:
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'operazione geometrica da utilizzare è stata un piccolo trucco. Polygon.contains(Point)
non copre i casi limite.
R , 139 127 118 116 byte
Modifica: -23 byte migliorando i calcoli dei lacci delle scarpe grazie alla pungolata di 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))])
Provalo online!
Implementa il bellissimo approccio di Neils per verificare se la 'fetta di torta' formata dal triangolo con il punto di prova + due punti perimetrali come vertici è uguale in area all'area dell'intera 'torta' (il poligono di prova) meno l'area di la "torta" con la "fetta" rimossa (il poligono che utilizza tutti i punti compreso il punto di prova).
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?
}
APL (Dyalog Unicode) , 63 byte
{⍵∊⍺:1⋄(¯1∊×d)∨1<|+/⍟d←(⊢÷1∘⌽)⍺-⍵}
Provalo online!
Tratto direttamente da uno snippet di APLcart. Non sono del tutto sicuro di cosa stia succedendo e sarei felice se qualcuno potesse dare una spiegazione migliore.
L'input è considerato come punti complessi.
Prende il poligono a sinistra e punta a destra.
Spiegazione
{⍵∊⍺: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)