diff options
| -rw-r--r-- | circrect.py | 40 | ||||
| -rw-r--r-- | circrect.tex | 248 | ||||
| -rw-r--r-- | refs.bib | 15 |
3 files changed, 242 insertions, 61 deletions
diff --git a/circrect.py b/circrect.py new file mode 100644 index 0000000..e85ed77 --- /dev/null +++ b/circrect.py @@ -0,0 +1,40 @@ +from numbers import Number + +def clamp(low: Number, high: Number, num: Number) -> Number: + """Limit range of ``num`` between ``low`` and ``high``""" + return max(low, min(high, num)) + +def circrect(a: Number, b: tuple[Number, Number], c: tuple[Number, Number]) -> Number: + """ + Calculate the area of the overlap between a circle with radius ``a`` and a + rectangle defined by opposing corner points ``b`` and ``c``. + + Args: + a: circle radius + b: first corner coordinate of rectangle + c: second corner coordinate of rectangle (opposite of b) + + Returns: + Overlap area (square units) + """ + + # normalize input variables + a = abs(a) + b, c = ( + (min(b[0], c[0]), min(b[1], c[1])), + (max(b[0], c[0]), max(b[1], c[1])), + ) + b = (clamp(-a, a, b[0]), clamp(-a, a, b[1])) + c = (clamp(-a, a, c[0]), clamp(-a, a, c[1])) + + return 0 + +if __name__ == "__main__": + print( + circrect(1, (-1, -1), (1, 1)), # pi + circrect(1, (1, 1), (-1, -1)), # pi + circrect(-1, (-1, -1), (1, 1)), # pi + circrect(2, (10, 10), (11, 11)), # 0 + circrect(10, (0, 0), (1, 1)), # 1 + ) + diff --git a/circrect.tex b/circrect.tex index d48f3d5..f22a7aa 100644 --- a/circrect.tex +++ b/circrect.tex @@ -1,4 +1,4 @@ -\documentclass[dutch, a4paper]{article} +\documentclass[dutch, a4paper, twocolumn]{article} \usepackage{babel} \usepackage{hyperref} @@ -6,16 +6,26 @@ \usepackage{csquotes} \usepackage{microtype} \usepackage{enumitem} +\usepackage{listings} \usepackage[noabbrev]{cleveref} \usepackage[ backend=biber, bibencoding=utf8, ]{biblatex} +\usepackage{tikz} +\usetikzlibrary{patterns} +\lstset{ + numbers=left, + numberstyle=\tiny, + numbersep=10pt, + basicstyle=\ttfamily, +} \addbibresource{refs.bib} \setdescription{ labelwidth=3ex } +\DeclareMathOperator{\clamp}{clamp} \title{Exacte berekening van het gedeelde oppervlak van een cirkel en een rechthoek} \author{Loek Le Blansch} @@ -25,16 +35,16 @@ \maketitle \begin{abstract} -In dit document wordt beschreven hoe men het gedeelde oppervlak van een willekeurige -cirkel met een willekeurige rechthoek exact kan berekenen. Een interactief voorbeeld -is beschikbaar op Desmos \autocite{desmosimpl}, en een voorbeeldimplementatie van de -complete formule in de programmeertaal Python staat beschreven in de bijlage van dit -document. +Dit document beschrijft een functie waarmee het gedeelde oppervlak van een +willekeurige cirkel met een willekeurige rechthoek exact berekend kan worden. Een +interactief voorbeeld is beschikbaar op Desmos \autocite{circrect2}, en een +voorbeeldimplementatie van de complete formule in de programmeertaal Python is +beschikbaar in de bijlage van dit document (bijlage \ref{attach:python-impl}). \end{abstract} \section{Definities} -De volgende variabelen worden gebruikt in de berekeningen, met uitzondering van -functieparameters: +De volgende variabelen (met uitzondering van functieparameters) worden gebruikt in de +berekeningen. Deze variabelen zijn weergegeven in een diagram in \cref{fig:context}. \begin{description} \item[$a$] (de cirkel) @@ -50,74 +60,188 @@ functieparameters: \begin{description} \item[$c_x, c_y$] (de co\"ordinaten van punt $c$) \end{description} + \item[$o$] (het gedeelde oppervlak van $a$ en $bc$) \end{description} -\section{Berekening} +\begin{figure} + \centering + \begin{tikzpicture}[scale=1.25] + % draw area + \clip(-2.5,-0.5) rectangle (3.5,3.5); + + % axes + \draw[->] (-3,0) -- (3,0) node[right]{$x$}; + \draw[->] (0,-3) -- (0,3) node[above]{$y$}; + + % labeled points + % \node(-0.707,0.707) {$a_r$}; + \coordinate [label=225:$b$] (b) at (1,1); + \coordinate [label=45:$c$] (c) at (2,2); -Het interval waarmee de integraal wordt berekend is gedefini\"eerd door $[b_1, c_1]$. -\Cref{eq:var:d1,eq:var:d2} defini\"eren deze waarden als de $x$-co\"ordinaten van de -hoekpunten $b$ en $c$, begrensd tussen $[-a_r, a_r]$. -\begin{equation}\label{eq:var:d1} -b_1=\min\left(a_r,\max\left(-a_r,b_x\right)\right) + % draw rectangle, circle and line + \draw[thick] (b) rectangle (c); + \draw[thick] (0,0) circle (2); + % label a, b and c + \path[thick,<->] (0,0) edge node[below left] {$a_r$} (-1.414,1.414); + \node[fill,circle,inner sep=1.5pt] at (b) {}; + \node[fill,circle,inner sep=1.5pt] at (c) {}; + + % hatch overlapping area + \begin{scope} + \clip (0,0) circle (2); + \fill[pattern=north east lines] (b) rectangle (c); + \end{scope} + \end{tikzpicture} + \caption{Voorbeeldvisualisatie toepassing} + \label{fig:context} +\end{figure} + +Om de formules verder te vereenvoudigen worden de volgende eisen aan de +invoerwaarden gesteld: +\begin{equation}\label{eq:constrain:x} +-a_r \leq b_x \leq c_x \leq a_r \end{equation} -\begin{equation}\label{eq:var:d2} -c_1=\min\left(a_r,\max\left(-a_r,c_x\right)\right) +\begin{equation}\label{eq:constrain:y} +-a_r \leq b_y \leq c_y \leq a_r \end{equation} -\Cref{eq:fn:f} defini\"eert de functie $f$ als alleen de bovenste helft van cirkel -$a$. +\section{Aanpak} + +Mijn initi\"ele aanpak voor dit probleem was de integraal berekenen op het interval +$[b_x, c_x]$ van een kromme die een halfrond begrensde tussen $[b_y,c_y]$. Deze +aanpak werkte in de Desmos grafische rekenmachine \autocite{circrect1}, maar was niet +implementeerbaar in Python. + +Omdat de berekening van $o$ toegepast wordt in de context van een computerprogramma, +is het van belang dat de formule die deze waarde berekent constant is. Dit betekent +dat de (halfrond) functie die geprimitiveerd wordt niet de min, max of abs functies +kan gebruiken. + +\begin{figure} + \centering + \begin{tikzpicture}[scale=1.25] + % draw area + \clip(-0.25,-0.5) rectangle (3.5,3.5); + + % axes + \draw[->] (-3,0) -- (3,0) node[right]{$x$}; + + % labeled points + % \node(-0.707,0.707) {$a_r$}; + \coordinate (b) at (0.5,0.5); + \coordinate (c) at (2.5,1.5); + + % draw rectangle, circle and line + \draw[thick] (b) rectangle (c); + \begin{scope} + \clip (-3,0) rectangle (3,3); + \draw[thick] (0,0) circle (2); + \end{scope} + + % hatch overlapping area + \begin{scope} + \clip (0,0) circle (2); + \fill[pattern=north east lines] (0.5,5) rectangle (c); + \fill (b) rectangle (c); + \fill[pattern=crosshatch dots] (b) rectangle (2.5,0); + \end{scope} + + % labels + \node[anchor=east] at (0.5,1.75) {1}; + \node[anchor=east] at (0.5,1.00) {2}; + \node[anchor=east] at (0.5,0.25) {3}; + \end{tikzpicture} + \caption{Markering ongewenste gebieden} + (alleen het oppervlak van gebied 2 is gewenst) + \label{fig:unwanted-area} +\end{figure} + +De aanpak is als volgt: +\begin{enumerate} + \item\label{step:semicircfn} Defini\"eer de functie $f$ als alleen het bovenste + halfrond van cirkel $a$. + \item Beschouw alleen het domein $[b_x, c_x]$. Als de integraal van $f$ genomen zou + worden op dit interval, zou de uitkomst niet alleen het oppervlak van de overlap + met rechthoek $bc$ zijn, maar het oppervlak van de bovenste rand van de cirkel + tot de $x$-aslijn. Dit is ongewenst. + \item\label{step:regdelbelow} De regio tussen $[0, b_y]$ (regio 3 in + \cref{fig:unwanted-area}) kan worden verwijderd door een verticale translatie van + $-b_y$ toe te passen op $f$ v\'o\'or de integraal wordt berekend. Dit zorgt voor + problemen zodra punt $(b_x,b_y)$ of $(c_x,b_y)$ buiten cirkel $a$ valt. + \item\label{step:regdelabove} De regio tussen $[c_y, a_r]$ (regio 1 in + \cref{fig:unwanted-area}) kan worden verwijderd door deze te berekenen en af te + trekken van de resulterende regio uit stap \ref{step:regdelbelow}. Deze regio kan + worden berekend door een tweede integraal te berekenen, maar op $f$ met een + translatie van $-c_y$. Dit zorgt weer voor problemen, maar bij de punten + $(b_x,c_y)$ en $(c_x,c_y)$. + \item\label{step:limitintdomain} De tot nu toe genoemde problemen kunnen worden + opgelosd door de intervallen van de integralen te begrenzen tot het punt waar de + getransleerde functies de $x$-as snijden. +\end{enumerate} + +Deze stappen worden in detail beschreven in \cref{sec:calculation}. + +\section{Berekening} +\label{sec:calculation} + +Stap \ref{step:semicircfn} is beschreven in \cref{eq:fn:f}. Om later voor stap +\ref{step:limitintdomain} het domein van de integraal te begrenzen is ook de inverse +van functie $f$ nodig. Omdat de functie $f$ een cirkel beschrijft, is de inverse +functie gelijk aan functie $f$. \begin{equation}\label{eq:fn:f} -f\left(x\right)=\sqrt{a_r^2-x^2} +f\left(x\right) = \sqrt{a_r^2-x^2} \end{equation} -\Cref{eq:var:f1} defini\"eert $f_1$ als de laagste verticale co\"ordinaat van de -punten $b$ en $c$, begrensd tussen $[0, a_r]$. -\begin{equation}\label{eq:var:f1} -f_1=\min\left(a_r,\max\left(0,\min\left(b_y,c_y\right)\right)\right) -\end{equation} +Stappen \ref{step:regdelbelow} en \ref{step:regdelabove} zijn beschreven in +\cref{eq:fn:fb,eq:fn:fc}. +\begin{align} +\label{eq:fn:fb} f_b\left(x\right) &= f\left(x\right)-b_y\\ +\label{eq:fn:fc} f_c\left(x\right) &= f\left(x\right)-c_y +\end{align} -\Cref{eq:var:f2} defini\"eert $f_2$ als de absolute hoogte van rechthoek $bc$. -\begin{equation}\label{eq:var:f2} -f_2=\left|\max\left(0,b_y\right)-\max\left(c_y,0\right)\right| -\end{equation} +Stap \ref{step:limitintdomain} is beschreven in +\cref{eq:var:xb1,eq:var:xb2,eq:var:xc1,eq:var:xc2}. +\begin{align} +\label{eq:fn:clamp} \clamp\left(a,b,x\right) &= + \max\left(a, \min\left(b, c\right)\right)\\ +\label{eq:var:xb1} x_{b_1} &= + \clamp\left(b_x,c_x,-f\left(b_y\right)\right)\\ +\label{eq:var:xb2} x_{b_2} &= + \clamp\left(b_x,c_x, f\left(b_y\right)\right)\\ +\label{eq:var:xc1} x_{c_1} &= + \clamp\left(b_x,c_x,-f\left(c_y\right)\right)\\ +\label{eq:var:xc2} x_{c_2} &= + \clamp\left(b_x,c_x, f\left(c_y\right)\right) +\end{align} -\Cref{eq:fn:g} defini\"eert de functie $g$ als een transformatie van de functie $f$, -met een translatie van $f_1$ omlaag, en een begrenzing van het bereik van de functie -tot $[0, f_2]$. -\begin{equation}\label{eq:fn:g} -g\left(x\right)=\min\left(f_2,\max\left(0,f\left(x\right)-f_1\right)\right) -\end{equation} +Nu kunnen de integralen berekend worden volgens \cref{eq:var:ob,eq:var:oc,eq:var:o}. +\begin{align} +\label{eq:var:ob} o_b &= \int_{x_{b_1}}^{x_{b_2}}f_b\left(x\right)dx\\ +\label{eq:var:oc} o_c &= \int_{x_{c_1}}^{x_{c_2}}f_c\left(x\right)dx\\ +\label{eq:var:o} o &= o_b - o_c +\end{align} -\Cref{eq:var:o} defini\"eert $o$ als het gedeelde oppervlak van cirkel $a$ en -rechthoek $bc$ boven de $x$-as, door de integraal van de fucntie $g$ tussen het -interval $[b_1, c_1]$ te berekenen. De absolute waarde van de integraal wordt genomen -voor gevallen waar $b_x > c_x$. -\begin{equation}\label{eq:var:o} -o=\left|\int_{b_1}^{c_1}g\left(x\right)dx\right| -\end{equation} +\section{Uitbereiding} -\Cref{eq:fn:h} defini\"eert een functie die de waarde van $o$ uitrekent voor elke -willekeurige waarden voor $a$, $b$ en $c$. -\begin{equation}\label{eq:fn:h} -h(a,b,c) = \text{TODO} -\end{equation} +Om \cref{eq:var:o} als een constante formule te defini\"eren moet functie $f$ +geprimitiveerd worden. + +TODO: definieer functie $F$ als de primitieve van functie $f$ + +TODO: definieer functie $h$ (uitbereiding $o$ als functie) De complete oplossing bestaat uit de functie $h$ \'e\'en keer normaal berekenen, en nog een keer met de rechthoek $bc$ gespiegeld om de $x$-as (vermenigvuldig $b_y$ en -$c_y$ met $-1$). De som van deze twee waarden vormt het gewenste oppervlak +$c_y$ met $-1$). De som van deze twee waarden vormt oppervlak $o$. \begin{equation}\label{eq:fn:k} \begin{aligned}[c] - k\left(a,b,c\right) =\, - & h\left( - a, - \left(b_x, b_y\right), - \left(c_x, c_y\right) - \right) + \\ - & h\left( - a, - \left(b_x,-b_y\right), - \left(c_x,-c_y\right) - \right) + k\left(a,b,c\right) ={} + h\,(a, & \left(b_x,\max\left(0,b_y\right)\right),\\ + & \left(c_x, \max\left(0,c_y\right)\right) + ) + \\ + h\,(a, & \left(b_x,\max\left(0,-b_y\right)\right),\\ + & \left(c_x, \max\left(0,-c_y\right)\right) + ) \end{aligned} \end{equation} @@ -127,4 +251,12 @@ Ik heb geen wiskunde gestudeerd, en kan geen bewijs geven dat de methode die beschreven is in dit document foutloos is. \printbibliography + +\clearpage\pagestyle{empty} +\onecolumn\appendix +\section{Python implementatie} +\label{attach:python-impl} +\fontsize{8.5}{12}\selectfont +\lstinputlisting{circrect.py} + \end{document} @@ -1,7 +1,16 @@ -@online{desmosimpl, - title = {Gedeeld oppervlak van cirkel en rechthoek}, - url = {https://www.desmos.com/calculator/iolignkwgm}, +@online{circrect1, + title = {circrect1}, + url = {https://www.desmos.com/calculator/xyngh2g1zt}, author = {Loek Le Blansch}, date = {2024-01-06}, urldate = {2024-01-06}, } + +@online{circrect2, + title = {circrect2}, + url = {https://www.desmos.com/calculator/zudzhuj9yi}, + author = {Loek Le Blansch}, + date = {2024-01-07}, + urldate = {2024-01-07}, +} + |