Relacionado con esta pregunta .

Una habitación se define como un polígono no intersecante (no necesariamente convexo), expresado como una lista ordenada de coordenadas bidimensionales. Se coloca una bombilla suficientemente brillante en un punto específico dentro de la habitación y emite luz en todas las direcciones. Su tarea es encontrar el área iluminada total de la habitación. Puede recibir información en cualquier formato razonable. Los puntos en el polígono / habitación, así como las coordenadas de la fuente de luz, son números racionales. Se pueden tomar en sentido horario o antihorario, cualquiera de los formatos está bien. El caso de prueba en el problema se da en sentido antihorario.

La siguiente imagen muestra dos salas de ejemplo, donde el punto púrpura representa la fuente de luz y la región sombreada representa el área iluminada.

Caso de prueba:

(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

Aquí hay una representación gráfica de la solución a ese caso de prueba. Los dos puntos que definen la solución que no están en el polígono original son (55/61, 363/61) y (856/55, 357/55).

Esta fórmula puede ser útil para calcular el área.

Como se trata de código golf , gana el código más corto en bytes.

Python 3 , 388 398 408 409 415 417 493 bytes

Para hacerlo más preciso, aumente 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)

Enfoque básico de Montecarlo. Pasos enumerados a continuación.

1. Encuentra los rangos x e y que ocupa la forma.
2. Crea una lista de aristas creadas por los vértices
3. Iterar muchas veces (cuanto más, mejor)
4. Cree un punto aleatorio (j, k) dentro del rango x, y.
5. Compruebe si alguno de los bordes intercepta con el segmento de línea creado por la luz y el punto aleatorio. Si alguno de los bordes intercepta, incremente la variables
6. Divida sentre los números totales, luego multiplique por el área de rango total.

Versión sin golf:

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

Pruébalo en línea!

Crédito por algoritmo de intersección de línea

Además, agradezca a todos los comentaristas útiles sobre cómo jugar golf aún más.

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

Solución exacta (salvo errores). Haskell tiene una aritmética racional exacta incorporada. Pruébalo en línea!

Tenga en cuenta que esto da 815523/6710, no 814643/6710, para la sala de ejemplo, y la primera intersección de la pared se calcula como (55/61, 363/61). Estoy bastante seguro de que esto es correcto porque la entrada de Monte Carlo (lentamente) converge al mismo resultado.

Leyenda:

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: GUI brillante para pruebas. Haga clic al lado de los puntos para moverlos.

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

Esta es una versión no golfista de este interesante desafío que ofrezco para demostrar mi lógica. Mi versión antigua de APL + WIN no se adapta bien a las estructuras de control anidadas de golf. Las APL más modernas podrían hacerlo mejor: ¿desafío?

Si los lectores validan la lógica, intentaré jugar esta solución. Si la lógica es incorrecta, simplemente eliminaré.

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 , 296255 bytes

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)

Pruébalo en línea!

Esta es una versión más reducida de la respuesta de Python . El método central de Monte Carlo es el mismo, pero reorganicé algunas de las funciones para acortarlas. En mi primera iteración, había sido demasiado agresivo en la reorganización, y luego me di cuenta de que podía optimizar tanto la longitud como la velocidad al volver a una versión del algoritmo de intersección más cercano a la pitón.

Aquí hay una versión sin golf que también traza los resultados:

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)