Çokgende mi?
Meydan okuma
Verilen nokta ve bir nokta yolu, noktanın yol tarafından oluşturulan çokgende olup olmadığını söyleyin.
Ayrıca truenokta çokgenin bir kenarındaysa geri dönün .
Giriş
Tam sayı çiftlerinin listesi.
İlk 2 tam sayı noktayı temsil eder.
Kalan çiftler (3. ve 4., 5. ve 6. vb.) Çokgenin köşelerini temsil eder.
Kenarlar giriş çiftleri sırasındadır.
Yolun, yolun ilk noktasına geri döndüğü varsayılır.
Girişin geçerli olduğu varsayılır.
Yoldaki üç nokta eşdoğrusal değildir.
ör. 123 82 84 01 83 42
Çıktı
Doğru / yanlış bir değer.
Test durumları
Giriş -> Çıkış
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
Bu kod golfü . Bayt cinsinden en kısa cevap kazanır.
Yanıtlar
Kömür , 52 50 bayt
≔⪪Ａ²θＦ⟦Ｅ³§θ⊖ιθ✂θ¹⟧⊞υ↔ΣＥι⁻קκ⁰§§ι⊕λ¹×§κ¹§§ι⊕λ⁰⁼⊟υΣυ
Çevrimiçi deneyin! Bağlantı, kodun ayrıntılı sürümüne yöneliktir. Açıklama:
≔⪪Ａ²θ
Girişi koordinat çiftlerine bölün.
Ｆ⟦Ｅ³§θ⊖ιθ✂θ¹⟧
Üç çokgenin alanını hesaplayın: son, birinci ve ikinci noktaları alarak oluşturulan; tüm noktalardan oluşan (test noktası dahil); test noktası hariç tüm noktalardan oluşturulmuş olanı.
⊞υ↔ΣＥι⁻קκ⁰§§ι⊕λ¹×§κ¹§§ι⊕λ⁰
Bu çokgenin alanını hesaplamak için ayakkabı bağı formülünü kullanın.
⁼⊟υΣυ
Son alanın ilk ikisinin toplamına eşit olup olmadığını kontrol edin. Durum böyleyse, nokta çokgen içinde yer alır.
Wolfram Dili (Mathematica) , 26 bayt
Polygon@#2~RegionMember~#&
Çevrimiçi deneyin!
JavaScript (V8) , 123 bayt
(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)
Golfsüz
(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 şimdilik kapalı görünüyor, yapabildiğimde bir bağlantı ekleyeceğim (veya ilk önce başka biri olursa)
PostgreSQL 12, 91 bayt
create function f(a polygon,b point,out o bool)as $$begin return a~b;end$$language plpgsql;
PostgreSQL'de yerleşik çokgen ve nokta türleri ve kapsamı test etmek için yerleşik bir operatör@> ( ~bayt kaydetmek için de yazılır ) vardır.
... bu çok mu sıkıcı?
Java 10, 142 141 bayt
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]);}
Çevrimiçi deneyin.
Açıklama:
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 bayt
Girdi, ayrıştırılması gerekmeyen bir (Int, Int)ve a List[(Int, Int)]ise, biraz daha kolaydır
(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
Çevrimiçi deneyin!
Sargı numarası kullanarak, 140 bayt
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
Çevrimiçi deneyin!
Burada açıklanan algoritmayı kullanır
Dize olarak girdi ile 186 bayt
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}
Çevrimiçi deneyin!
C (gcc) , 171 \$\cdots\$ 129 126 bayt
Bir kuyruklu Kaydedilen 13 19 -e doğru 35 bayt sayesinde ceilingcat !!! Kullanıcı sayesinde 2 5 bayt
tasarruf sağladı !!!
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;}
Çevrimiçi deneyin!
Sargı numarası algoritmasını kullanır: sargı numarası doğru ise, nokta çokgenin içinde, aksi takdirde yanlıştır.
Python 3.8 (yayın öncesi) , 134 bayt
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))
Çevrimiçi deneyin!
R , 105 bayt
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),])))))
Çevrimiçi deneyin!
Üç noktanın eşdoğrusal olmadığını varsayar. Örneğin burada açıklanan algoritmayı genişletir .
Sorgu noktasını çağırırsak \$Q\$ve çokgenin sıralı noktaları \$P_1\dots P_n\$Bu oluşturduğu (bağı yöntemini kullanarak) üçgenin imza alanı bilgisayar ile on segmentinin hangi tarafı görmek için kontrol, çokgenin noktaları erişir \$Q,P_{i},P_{i+1}\$: Pozitif bir işaret sola, saat yönünün tersine gidiyorsanız sağa negatif anlamına gelir, aksi takdirde tersine çevrilir. Tüm işaretler aynıysa (yani, işaretlerin standart sapması 0 ise), o zaman nokta çokgen içindedir.
Hesaplamalı geometri profesörüm, bu çokgen içinde nokta yöntemini hatırlamamın benim için dört gün sürmesinden biraz utanırdı. Ders kitabımı / notlarımı bulabilirsem, algoritmanın açıklamasını göndereceğim ...
> <> , 92 bayt
l[l0$21.>&-0=n; {$&:2-&?!v{:{:{:@*{:}@@}@@}@@*-@@+
:0$0(?$-v>]
3pl2-00.>&08
{{{{600.>&-&084p
Neil'in ayakkabı bağı formül tekniğini uygular.
Python 3, 133 bayt
Kurtarmaya yönelik mekansal paketler:
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))
Kullanılacak geometrik işlem küçük bir şeydi. Polygon.contains(Point)uç durumları kapsamaz.
R , 139 127 118 116 bayt
Düzenleme: Giuseppe'nin goading sayesinde ayakkabı bağı hesaplamalarını iyileştirerek -23 bayt
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))])
Çevrimiçi deneyin!
Neils , test noktası + köşeler olarak iki çevre noktası olan üçgenin oluşturduğu 'pasta diliminin', alan olarak tüm 'kek' (test poligonu) eksi alanıyla eşit olup olmadığını test etmek için güzel bir yaklaşım uygular . 'dilim' kaldırılmış 'kek' (test noktası dahil tüm noktaları kullanan çokgen).
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 bayt
{⍵∊⍺:1⋄(¯1∊×d)∨1<|+/⍟d←(⊢÷1∘⌽)⍺-⍵}
Çevrimiçi deneyin!
Doğrudan bir APLcart snippet'inden alınmıştır. Neler olup bittiğinden pek emin değilim ve birisi daha iyi bir açıklama yapabilirse çok sevinirim.
Girdi, karmaşık noktalar olarak alınır.
Solda çokgeni alır ve sağda gösterir.
Açıklama
{⍵∊⍺: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)