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
Exact solution (barring bugs). Haskell has built-in exact rational arithmetic. Try it online!
Note that this gives 815523/6710
, not 814643/6710
, for the example room, and the first wall intersection is calculated as (55/61, 363/61)
. I'm fairly sure this is correct because the Monte Carlo entry (slowly) converges to the same result.
Legend:
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 for testing. Click next to points to move them.
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)
![Screenshot](../../I/static/images/2a411a128c6d690d164d666ba24dee0c7eb50ee5dc36bb390b3e3391f374ada2.png)
For those curious, part 2 might take a while to post because it'll take me forever to draw the pictures, and I also don't know how to solve it. – rigged – 2019-02-14T21:01:14.150
The points on the polygon/room as well as the coordinates of the light source are rational numbers. – rigged – 2019-02-14T21:05:54.627
Is there an upper bound on the number of vertices or should your program theoretically be able to handle an unlimited number? Also, your code-golf tag is broken. it's
[tag:code-golf]
– Veskah – 2019-02-14T21:20:18.943Your program or at least your algorithm should theoretically be able to handle an unlimited number, I can't think of a reason to arbitrarily limit the number of vertices (but I'm open to changing this if you have a specific reason why) – rigged – 2019-02-14T21:23:24.170
3
Ah, the good old shoelace formula! By the way, we actually have MathJax so you needn't embed the formula as an image.
– Giuseppe – 2019-02-14T21:23:44.050it's stolen from wikipedia, do you have a link that shows how to use MathJax? – rigged – 2019-02-14T21:27:07.567
Meta post on finally getting MathJax back!! – Giuseppe – 2019-02-14T22:52:38.650
Here's a mathjax version of your image (right click > show math as > TeX commands): $$\begin{align} \mathbf{A}&=\frac{1}{2}\left|\sum_{i=1}^{n-1}x_{i}y_{i+1}+x_{n}y_{1}-\sum_{i=1}^{n-1}x_{i+1}y_{i}-x_{1}y_{n}\right|\ &=\frac{1}{2}\left|x_{1}y_{2}+x_{2}y_{3}+\cdots+x_{n-1}y_{n}-x_{2}y_{1}-x_{3}y_{2}-\cdots-x_{n}y_{n-1}-x_{1}y_{n}\right| \end{align}$$ You can use https://www.codecogs.com/latex/eqneditor.php as an editor and a way to get used to mathjax, and there's this tutorial which can help
– Conor O'Brien – 2019-02-15T00:44:57.060Are the points guaranteed to be ordered clockwise? – feersum – 2019-02-15T01:18:13.340
Yes, they are ordered (an unordered set of points don't form a unique nonconvex polygon) – rigged – 2019-02-15T01:22:03.520
But they could also be ordered counterclockwise. A list of points still defines the same polygon following rotation or reversal of the list. – feersum – 2019-02-15T17:03:40.433
1Yes, they can be guaranteed to be ordered clockwise, then. The test case is ordered counterclockwise, but I think this falls under “any reasonable format.” – rigged – 2019-02-15T17:15:23.330
OK, I had wondered this about the first Monte Carlo answer, but now that we have a second one: should these even be considered as valid answers? It seems they are solving a slightly different challenge than the one described. – japh – 2019-02-26T10:47:36.143
I also wondered this, but I thought it wasn't my place to comment on that because I don't know very much about what this community considers acceptable. – rigged – 2019-02-27T00:02:26.247
@bushdid911 I think you can decide; it's your challenge. For example, you could require a minimum accuracy in a given time limit. (Maybe not for this challenge, but for part 2.) – japh – 2019-02-27T08:20:19.700