summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--circrect.py40
-rw-r--r--circrect.tex248
-rw-r--r--refs.bib15
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}
diff --git a/refs.bib b/refs.bib
index bfbb2aa..5473a7e 100644
--- a/refs.bib
+++ b/refs.bib
@@ -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},
+}
+