Ist es im Polygon?

Question

Die Herausforderung

Geben Sie bei einem bestimmten Punkt und einem Pfad von Punkten an, ob sich der Punkt in dem vom Pfad erstellten Polygon befindet oder nicht.

Kehren Sie auch zurück, truewenn sich der Punkt auf einer Kante des Polygons befindet.

Eingang

Eine Liste von Ganzzahlpaaren.

Die ersten 2 ganzen Zahlen repräsentieren den Punkt.

Die verbleibenden Paare (3. und 4., 5. und 6. usw.) repräsentieren die Eckpunkte des Polygons.

Die Kanten liegen in der Reihenfolge der Eingangspaare.

Es wird angenommen, dass der Pfad zum ersten Punkt des Pfads zurückkehrt.

Die Eingabe wird als gültig angenommen.

Keine drei Punkte im Pfad sind kollinear.

Ex. 123 82 84 01 83 42

Ausgabe

Ein wahrer / falscher Wert.

Testfälle

Eingabe -> Ausgabe

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

Das ist Code-Golf . Die kürzeste Antwort in Bytes gewinnt.

Answer 1

Holzkohle , 52 50 Bytes

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

Probieren Sie es online aus! Der Link führt zur ausführlichen Version des Codes. Erläuterung:

≔⪪Ａ²θ

Teilen Sie die Eingabe in Koordinatenpaare auf.

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

Berechnen Sie die Fläche von drei Polygonen: dasjenige, das durch Nehmen des letzten, ersten und zweiten Punktes gebildet wird; die aus allen Punkten (einschließlich des Testpunkts) gebildete; die aus allen Punkten außer dem Testpunkt gebildete.

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

Verwenden Sie die Schnürsenkelformel, um die Fläche dieses Polygons zu berechnen.

⁼⊟υΣυ

Überprüfen Sie, ob der letzte Bereich der Summe der ersten beiden entspricht. Wenn dies der Fall ist, liegt der Punkt innerhalb des Polygons.

Answer 2

Wolfram Language (Mathematica) , 26 Bytes

Polygon@#2~RegionMember~#&

Probieren Sie es online aus!

Answer 3

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 scheint vorerst nicht verfügbar zu sein. Ich werde einen Link hinzufügen, wenn ich kann (oder wenn jemand anderes zuerst passiert).

Answer 4

PostgreSQL 12, 91 Bytes

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

PostgreSQL verfügt über integrierte Polygon- und Punkttypen sowie einen integrierten Operator@> (auch ~zum Speichern eines Bytes geschrieben) zum Testen der Eindämmung.

... Ist das zu langweilig?

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

Probieren Sie es online aus.

Erläuterung:

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

Wenn die Eingabe a (Int, Int)und a ist und List[(Int, Int)]nicht analysiert werden muss, ist es etwas einfacher

(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

Probieren Sie es online aus!

Unter Verwendung der Wicklungsnummer 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

Probieren Sie es online aus!

Verwendet den hier beschriebenen Algorithmus

Bei Eingabe als Zeichenfolge 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}

Probieren Sie es online aus!

Answer 7

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

Dank Ceilingcat satte 13 19 35 Bytes gespart !!! 2 5 Bytes dank Benutzer
gespeichert !!!

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

Probieren Sie es online aus!

Verwendet den Wicklungszahlenalgorithmus: Wenn die Wicklungszahl wahr ist, liegt der Punkt innerhalb des Polygons, andernfalls ist es falsch.

Answer 8

Python 3.8 (Vorabversion) , 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))

Probieren Sie es online aus!

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

Probieren Sie es online aus!

Angenommen, keine drei Punkte sind kollinear. Verlängert der Algorithmus beschrieben, zum Beispiel hier .

Wenn wir den Abfragepunkt \ aufrufen$Q\$und die geordneten Punkte des Polygons \$P_1\dots P_n\$Dabei werden die Punkte des Polygons durchlaufen und überprüft, auf welcher Seite des Segments es sich befindet, indem der durch \ gebildete vorzeichenbehaftete Bereich des Dreiecks (unter Verwendung der Schnürsenkelmethode) berechnet wird$Q,P_{i},P_{i+1}\$: Ein positives Vorzeichen bedeutet links und ein negatives Zeichen rechts, wenn Sie gegen den Uhrzeigersinn fahren, andernfalls ist es umgekehrt. Wenn alle Vorzeichen gleich sind (dh die Standardabweichung der Vorzeichen ist 0), liegt der Punkt innerhalb des Polygons.

^{Mein Professor für Computergeometrie würde sich etwas schämen. Ich brauchte vier Tage, um mich an diese Punkt-in-Polygon-Methode zu erinnern. Wenn ich mein Lehrbuch / meine Notizen finden kann, werde ich die Beschreibung des Algorithmus veröffentlichen ...}

Answer 10

> <> 92 Bytes

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

Implementiert Neils Schnürsenkelformeltechnik.

Answer 11

Python 3, 133 Bytes

Raumpakete zur Rettung:

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

Die zu verwendende geometrische Operation war eine kleine Gotcha. Polygon.contains(Point)deckt die Randfälle nicht ab.

Answer 12

R , 139 127 118 116 Bytes

Bearbeiten: -23 Bytes durch Verbesserung der Schnürsenkelberechnungen dank Stacheln von 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))])

Probieren Sie es online aus!

Implementiert Neils schönen Ansatz, um zu testen, ob das durch das Dreieck mit dem Testpunkt + zwei Umfangspunkten als Eckpunkte gebildete „Stück Kuchen“ flächenmäßig gleich der Fläche des gesamten „Kuchens“ (des Testpolygons) minus der Fläche von ist der 'Kuchen' mit dem 'Slice' entfernt (das Polygon unter Verwendung aller Punkte einschließlich des Testpunkts).

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∘⌽)⍺-⍵}

Probieren Sie es online aus!

Entnommen direkt aus einem APLcart-Snippet. Ich bin mir nicht ganz sicher, was los ist, und würde mich freuen, wenn jemand eine bessere Erklärung geben könnte.

Die Eingabe wird als komplexe Punkte verstanden.

Nimmt das Polygon links und zeigt nach rechts.

Erläuterung

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