Está no polígono?

Question

O desafio

Dado um ponto e um caminho de pontos, diga se o ponto está ou não no polígono criado pelo caminho.

Retorne também truese o ponto estiver em uma aresta do polígono.

Entrada

Uma lista de pares de inteiros.

Os primeiros 2 inteiros representam o ponto.

Os pares restantes (3º e 4º, 5º e 6º etc.) representam os vértices do polígono.

As bordas estão na ordem dos pares de entrada.

Presume-se que o caminho retorne ao primeiro ponto do caminho.

A entrada é considerada válida.

Não há três pontos no caminho colineares.

ex. 123 82 84 01 83 42

Resultado

Um valor verdadeiro / falso.

Casos de teste

Entrada -> Saída

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

Este é o código de golfe . A resposta mais curta em bytes vence.

Answer 1

Carvão , 52 50 bytes

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

Experimente online! O link é para a versão detalhada do código. Explicação:

≔⪪Ａ²θ

Divida a entrada em pares de coordenadas.

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

Calcule a área de três polígonos: o formado tomando o último, primeiro e segundo pontos; aquele formado a partir de todos os pontos (incluindo o ponto de teste); aquele formado por todos os pontos exceto o ponto de teste.

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

Use a fórmula do cadarço para calcular a área desse polígono.

⁼⊟υΣυ

Verifique se a última área é igual à soma das duas primeiras. Se for esse o caso, o ponto está dentro do polígono.

Answer 2

Linguagem Wolfram (Mathematica) , 26 bytes

Polygon@#2~RegionMember~#&

Experimente online!

Answer 3

JavaScript (V8) , 123 bytes

(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
  )

O TIO parece estar fora do ar por enquanto, adicionarei um link quando puder (ou se outra pessoa fizer isso primeiro)

Answer 4

PostgreSQL 12, 91 bytes

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

O PostgreSQL possui polígonos e tipos de pontos embutidos@> , e um operador embutido (também escrito ~para salvar um byte) para testar a contenção.

... Isso é muito chato?

Answer 5

Java 10, 142 141 bytes

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]);}

Experimente online.

Explicação:

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 bytes

Se a entrada for um (Int, Int)e um List[(Int, Int)]que não precisa ser analisado, é um pouco mais fácil

(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

Experimente online!

Usando número de enrolamento, 140 bytes

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

Experimente online!

Usa o algoritmo descrito aqui

Com entrada como string, 186 bytes

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}

Experimente online!

Answer 7

C (gcc) , ^{171 \$\cdots\$ 129} 126 bytes

Economizei 13 19 35 bytes graças ao tetocat !!!
Economizei 2 5 bytes graças ao usuário !!!

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;}

Experimente online!

Usa o algoritmo do número de enrolamento: se o número de enrolamento for verdadeiro, o ponto fica dentro do polígono, caso contrário, é falso.

Answer 8

Python 3.8 (pré-lançamento) , 134 bytes

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

Experimente online!

Answer 9

R , 105 bytes

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),])))))

Experimente online!

Assume que não há três pontos colineares. Estende o algoritmo descrito, por exemplo, aqui .

Se chamarmos o ponto de consulta \$Q\$e os pontos ordenados do polígono \$P_1\dots P_n\$, isso atravessa os pontos do polígono, verificando de que lado do segmento está, calculando a área sinalizada do triângulo (usando o método do cadarço) formada por \$Q,P_{i},P_{i+1}\$: Um sinal positivo significa para a esquerda e negativo para a direita se você estiver indo no sentido anti-horário, caso contrário, é invertido. Se todos os sinais são iguais (ou seja, o desvio padrão dos sinais é 0), então o ponto está dentro do polígono.

^{Meu professor de geometria computacional ficaria um pouco envergonhado se levei quatro dias para me lembrar desse método de ponto no polígono. Se eu conseguir encontrar meu livro / notas, vou postar sua descrição do algoritmo ...}

Answer 10

> <> , 92 bytes

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

Implementa a técnica de fórmula do cadarço de Neil.

Answer 11

Python 3, 133 bytes

Pacotes espaciais para o resgate:

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

A operação geométrica a ser usada era uma pequena pegadinha. Polygon.contains(Point)não cobre os casos extremos.

Answer 12

R , 139 127 118 116 bytes

Editar: -23 bytes, melhorando os cálculos do cadarço graças ao estímulo 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))])

Experimente online!

Implementa a bela abordagem de Neils de testar se a 'fatia de bolo' formada pelo triângulo com o ponto de teste + dois pontos de perímetro como vértices é igual em área à área de todo o 'bolo' (o polígono de teste) menos a área de o 'bolo' com a 'fatia' removida (o polígono usando todos os pontos incluindo o ponto de teste).

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 bytes

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

Experimente online!

Retirado diretamente de um fragmento APLcart. Não tenho muita certeza do que está acontecendo nisso, e ficaria feliz se alguém pudesse dar uma explicação melhor.

A entrada é considerada como pontos complexos.

Pega o polígono à esquerda e aponta à direita.

Explicação

{⍵∊⍺: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)