Bezogen auf diese Frage .

Ein Raum ist definiert als ein (nicht notwendigerweise konvexes) nicht schneidendes Polygon, das als geordnete Liste von zweidimensionalen Koordinaten ausgedrückt wird. Eine ausreichend helle Glühbirne wird an einer bestimmten Stelle im Raum platziert und strahlt Licht in alle Richtungen aus. Ihre Aufgabe ist es, die gesamte beleuchtete Fläche des Raums zu finden. Sie können Eingaben in jedem vernünftigen Format vornehmen. Die Punkte auf dem Polygon / Raum sowie die Koordinaten der Lichtquelle sind rationale Zahlen. Sie können im oder gegen den Uhrzeigersinn aufgenommen werden, jedes Format ist in Ordnung. Der Testfall im Problem wird gegen den Uhrzeigersinn angegeben.

Das folgende Bild zeigt zwei Beispielräume, in denen der violette Punkt die Lichtquelle und der schattierte Bereich den beleuchteten Bereich darstellt.

Testfall:

(1/2, 18)
(1,3)
(5,1/2)
(7,5)
(12,7)
(16,3)
(15,11)
(8,19)
(3,7)
Light source located at (5,8)
Answer: 815523/6710 ≈ 121.538

Hier ist eine grafische Darstellung der Lösung für diesen Testfall. Die zwei Punkte, die die Lösung definieren, die sich nicht auf dem ursprünglichen Polygon befinden, sind (55/61, 363/61) und (856/55, 357/55).

Diese Formel kann bei der Berechnung der Fläche hilfreich sein.

Da es sich um Code-Golf , der kürzeste Code in Bytes gewinnt.

Python 3 , 388 398 408 409 415 417 493 Bytes

Erhöhen Sie, um die Genauigkeit zu erhöhen n

from random import*
u=uniform
c=lambda A,B,C:(C[1]-A[1])*(B[0]-A[0])>(B[1]-A[1])*(C[0]-A[0])
I=lambda A,B,C,D:c(A,C,D)!=c(B,C,D)and c(A,B,C)!=c(A,B,D)
def a(l,v,n=9**6,s=0):
 g=lambda i:(min(x[i]for x in v),max(x[i]for x in v))
 for _ in'x'*n:
  h=((u(*g(0)),u(*g(1))),l);s+=any([I(*f,*h)for f in list(zip(v,v[1:]+[v[0]]))])^1
 return(abs(g(0)[0]-g(0)[1])*abs(g(1)[0]-g(1)[1]))*float(s/n)

Grundlegender Monte-Carlo-Ansatz. Schritte unten aufgeführt.

1. Finden Sie die x- und y-Bereiche, die die Form einnimmt.
2. Erstellen Sie eine Liste von Kanten, die von den Scheitelpunkten erstellt wurden
3. Eine große Anzahl von Malen iterieren (je mehr desto besser)
4. Erstellen Sie einen zufälligen Punkt (j, k) innerhalb des x, y-Bereichs.
5. Überprüfen Sie, ob eine der Kanten mit dem durch das Licht und den zufälligen Punkt erzeugten Liniensegment zusammenfällt. Wenn eine der Kanten abfällt, erhöhen Sie die Variables
6. Teilen Sie sdurch die Gesamtzahl und multiplizieren Sie dann mit der gesamten Reichweite.

Ungolfed-Version:

import random

def ccw(A,B,C):
    return (C[1]-A[1])*(B[0]-A[0]) > (B[1]-A[1])*(C[0]-A[0])

def intersect(A,B,C,D):
    return ccw(A,C,D) != ccw(B,C,D) and ccw(A,B,C) != ccw(A,B,D)

def lit_area(light, vertices):
    # points: list of points
    # i     : x => i=0
    #       : y => i=1
    get_range = lambda i: (min(x[i] for x in vertices), max(x[i] for x in vertices))
    xr = abs(get_range(0)[0] - get_range(0)[1])
    yr = abs(get_range(1)[0] - get_range(1)[1])

    edges = list(zip(vertices, vertices[1:] + [vertices[0]]))

    num_sims = 1000000

    num_successes = 0
    for _ in range(num_sims):
        guess_x = random.uniform(*get_range(0))
        guess_y = random.uniform(*get_range(1))

        light_guess_line = ((guess_x, guess_y), light)

        if not any([intersect(*e, *light_guess_line) for e in edges]):
            num_successes += 1
    return float(num_successes / num_sims) * (xr * yr)


if __name__ == "__main__":
    points = [
    (1/2, 18),
    (1,3),
    (5,1/2),
    (7,5),
    (12,7),
    (16,3),
    (15,11),
    (8,19),
    (3,7)
    ]
    light_source = (5,8)
    print("Area lit by light: %f"% lit_area(light_source, points))

Probieren Sie es online!

Gutschrift für den Linienschnittalgorithmus

Wir danken auch allen hilfreichen Kommentatoren, die erklärt haben, wie Sie dies noch weiter verbessern können.

Haskell , 559 _{^{618 632}} Bytes

r(a:b)=b++[a]
s=zip<*>r
(?)a=sum.zipWith(*)a
o(a,b)=r a?b-a?r b
(a,b)!(c,d)=(c-a,d-b)
(a,b)#(c,d)=a*d-b*c
x i a@(e,f)b j c d|let k@(g,h)=a!b;l=c!d;m=c!a;n=l#k;o=m#l/n;p=m#k/n;q|i>0=o<0||o>1|let=o<=0||o>=1;r|n==0||q||p<0||p*j>1=[]|let=[(e+o*g,f+o*h)]=r
(a&b)(c:e@(d:_))|let(f,g)=span(/=d)b;h=zip f$r$f++[d]=concat[[k,l]|(i,j)<-h,[[k],[l]]<-[x 1 i j 0 a<$>[c,d]],and[x 0 m n 1 a o==[]|o<-[k,l],(m,n)<-h,(m,n)/=(i,j)]]++(a&g)e
(_&_)_=[]
z a b=sum[o$unzip[c,a,d]|e@(f:_)<-[[c|c<-b,and[all(==c)$x 1 d e 1 a c|(d,e)<-s b]]],(c,d)<-s$a&until((f==).head)r b$e++[f]]/2

Genaue Lösung (außer bei Fehlern). Haskell hat eine exakte rationale Arithmetik eingebaut. Probieren Sie es online!

Beachten Sie, dass dies 815523/6710nicht 814643/6710für den Beispielraum gilt und der erste Wandschnitt wie folgt berechnet wird (55/61, 363/61). Ich bin mir ziemlich sicher, dass dies richtig ist, da der Monte-Carlo-Eintrag (langsam) zum gleichen Ergebnis konvergiert.

Legende:

z light roomPoints
    -- Main function, returns lit area.
    -- Compute list of visible corners in the room, then calls (&).
(&) light roomPoints' visibleCorners
    -- Compute visibility polygon. visibleCorners is the subset of points
    -- that are visible from the light. The first point of roomPoints'
    -- must coincide with the first visibleCorner.
x pEndpoints p1 p2 qSegment q1 q2
    -- Intersect line segments (p1, p2) and (q1, q2).
    -- If pEndpoints, exclude endpoints p1, p2.
    -- If not qSegment, allow intersection to extend past q2 (i.e. raycast).
r   -- Rotate list by one, used to construct closed loops etc.
s   -- Construct closed loop
(!) -- Vector between two points
(?) -- Dot product
(#) -- Cross product
o   -- Polygon area

Bonus: Gloss GUI zum Testen. Klicken Sie neben Punkte, um sie zu verschieben.

import qualified Graphics.Gloss as G
import qualified Graphics.Gloss.Interface.IO.Interact as GI

solnPoly a b|let c@(d:_)=[c|c<-b,and[all(==c)$x 1 d e 1 a c|(d,e)<-s b]]=a&until((d==).head)r b$c++[d]
solnArea = z

main =
  let fromRatP (x, y) = (fromRational x, fromRational y)
      displayScale = 10
      scalePoints = G.scale (fromInteger displayScale) (fromInteger displayScale)
      displayMode = G.InWindow "" (512, 512) (0, 0)
      drawBasePoly pointSz ps =
          mconcat $ G.lineLoop ps :
                    [G.translate x y (G.circleSolid pointSz) | (x, y) <- ps]
      drawVisPolyOf light ps =
          G.color G.blue $ drawBasePoly 0.2 $ map fromRatP $ solnPoly light ps
      drawLight (x, y) =
          G.translate x y $
          G.color G.yellow (G.circleSolid 0.5) <> G.circle 0.5
      draw (light, ps) =
          mconcat [
              scalePoints $ drawLight (fromRatP light),
              scalePoints $ drawBasePoly 0.4 (map fromRatP ps),
              scalePoints $ drawVisPolyOf light ps,
              G.translate (-200) (-50) $ G.scale 0.2 0.2 $
                G.color G.blue $ G.text $ "Lit area: " ++ show (solnArea light ps)
          ]
      event (GI.EventKey (GI.MouseButton GI.LeftButton) GI.Down _ (curx_, cury_)) (light, ps) =
          let dist (x,y) (x',y') = (x'-x)^2 + (y'-y)^2
              curx = curx_ / fromInteger displayScale
              cury = cury_ / fromInteger displayScale
              cursorR = (fromInteger$round curx, fromInteger$round cury)
              maxDist = 3
              snapAmount = 1
              (d, i) = minimum [(dist p cursorR, i) | (p, i) <- zip (light : ps) [0..]]
              snapTo n a = fromInteger$n*round(a/fromInteger n)
              snapCursor = (snapTo snapAmount curx, snapTo snapAmount cury)
              light' | i == 0 && d < maxDist^2 = snapCursor
                     | otherwise = light
              ps' | i > 0 && d < maxDist^2 = take (i-1) ps ++ [snapCursor] ++ drop i ps
                  | otherwise = ps
          in (light', ps')
      event _ state = state
      state0 =
        ((2, 2), [(0, 0), (10, 0), (10, 5), (20, 0), (20, 20), (15, 5),
                  (10, 10), (6, 10), (10, 12), (0, 12), (4, 10), (0, 10)])
  in G.play displayMode G.white 60
            state0
            draw
            event
            (\_ -> id)

APL + WIN

Dies ist eine ungelöste Version dieser interessanten Herausforderung, die ich anbiete, um meine Logik zu demonstrieren. Meine alte Version von APL + WIN eignet sich nicht gut zum Golfen von verschachtelten Kontrollstrukturen. Modernere APLs könnten es besser machen - herausfordern?

Wenn die Leser die Logik bestätigen, werde ich versuchen, diese Lösung zu nutzen. Wenn die Logik falsch ist, werde ich einfach löschen.

r←b Room v

⍝Separate x and y coordinates of vertices               
x←v[;1] ⋄ y←v[;2]

⍝Intercept and slope of each line segment and ray through each vertex
s←(y,¨1⌽y)⌹¨(1E¯9+1,[1.1]¨x,¨1⌽1E¯9+x)
l←(y,¨b[2])⌹¨(1E¯9+1,[1.1]¨x,¨b[1]+1E¯9)                          

⍝Coordinates of vertices
x←x,¨1⌽x ⋄ y←y,¨1⌽y                                                  

⍝Initialise intersection matrix
r←((⍴s),0)⍴0

⍝Evaluate intersection matrix 
:for i :in ⍳⍴l 
    t←0⍴0
    :for j :in ⍳⍴s
        t←t,⍎1⍕∊((↑∊l[i])-↑∊s[j])÷((1↓∊s[j])-1↓∊l[i]) 
    :endfor
    z←r←r,t
:endfor 

⍝Identify x coordinates of valid intersections in the direction of the ray
:for i :in ⍳⍴l 
    t←(r[i;i])
    :for j :in ⍳⍴s
        :if t<b[1] 
            r[j;i]←r[j;i]×(r[j;i]<t)^r[j;i]>⌊/∊x[i]
        :else
            r[j;i]←r[j;i]×(r[j;i]>t)^r[j;i]<⌈/∊x[i]
        :endif
    :endfor
 :endfor

⍝Identify the edges intersected
e←(+/r≠0)/⍳⍴l 

⍝Intersection x coordinates
cx←(+/r)[e]

⍝Intersection y coordinates
cy←⍎1⍕+/¨(s[e])× 1,¨(+/r)[e]

⍝Replace original coordinates that are in shadow
x[e]←(1↓¨x[e]),¨cx
y[e]←(1↓¨y[e]),¨cy

⍝Calculate lit area
r←+/.5×(|-/¨x)×|-/¨y                                               

R , 296 255 Byte

function(s,l,u=cbind(s,s[,1]),d=t(diff(t(u))),q=l-u,r=apply(s,1,range),g=c(diff(r)))mean(replicate(1e6,!any((q[i<-1:ncol(s)*2]*(p=runif(2)*g+r[1,]-u)[j<-i-1]>p[i]*q[j])!=(q[i+2]*p[i+1]>q[i+1]*p[i+2])&(p[i]*d[j]>p[j]*d[i])!=(q[i]*d[j]>q[j]*d[i]))))*prod(g)

Probieren Sie es online!

Dies ist eine weiter reduzierte Version der Python-Antwort . Die Monte-Carlo-Kernmethode ist dieselbe, aber ich habe einige Funktionen neu angeordnet, um sie kürzer zu machen. In meiner ersten Iteration war ich bei der Neuanordnung zu aggressiv gewesen, und dann wurde mir klar, dass ich sowohl Länge als auch Geschwindigkeit optimieren konnte, indem ich zu einer Version des Schnittalgorithmus zurückkehrte, die näher am Python lag.

Hier ist eine ungolfed Version, die auch die Ergebnisse aufzeichnet:

find_lit_ungolf <- function(shape, light, plot = TRUE) {
  lines <- cbind(shape ,shape[,1])
  diffs <- t(diff(t(lines)))
  light_minus_lines <- light - lines
  shape_range <- apply(s,1,range)
  shape_range_diff <- c(diff(shape_range))
  successes <- t(replicate(
    n = 1e5,
    {
      random_point <- runif(2) * shape_range_diff + shape_range[1, ]
      random_minus_lines <- random_point - lines
      q <- light_minus_lines
      p <- random_minus_lines
      d <- diffs
      i <- 1:ncol(s)*2
      success <-
        !any((q[i]*p[i-1]>p[i]*q[i-1])!=(q[i+2]*p[i+1]>q[i+1]*p[i+2])&(p[i]*d[i-1]>p[i-1]*d[i])!=(q[i]*d[i-1]>q[i-1]*d[i]))
      c(random_point, success)
    }))
  colnames(successes) <- c("x", "y", "success")
  if (plot) {
    shape <- t(shape)
    colnames(shape) <- c("x", "y")
    print(ggplot(as_tibble(successes), aes(x, y)) +
      geom_point(aes(colour = factor(success)), alpha = 0.3) +
      geom_polygon(data = as_tibble(shape), alpha = 0.2) +
      annotate("point", light[1], light[2], col = "yellow"))
  }
  mean(successes[, 3]) * prod(shape_range_diff)
}
find_lit_ungolf(s, l)