È nel poligono?

Aug 24 2020

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 truese 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

11 Neil Aug 24 2020 at 06:30

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.

10 J42161217 Aug 24 2020 at 12:26

Wolfram Language (Mathematica) , 26 byte

Polygon@#2~RegionMember~#&

Provalo online!

6 MatthewJensen Aug 24 2020 at 10:11

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)

4 pxeger Aug 25 2020 at 15:42

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?

3 KevinCruijssen Aug 24 2020 at 14:32

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
2 user Aug 24 2020 at 08:15

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!

2 Noodle9 Aug 24 2020 at 20:00

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.

2 user Aug 28 2020 at 07:00

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!

2 Giuseppe Aug 28 2020 at 08:05

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 ...

1 SE-stopfiringthegoodguys Aug 24 2020 at 19:48

> <> , 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.

1 ojdo Aug 24 2020 at 22:22

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.

1 DominicvanEssen Aug 24 2020 at 18:27

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?
}
1 Razetime Nov 13 2020 at 23:04

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)