meer WIP

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},
+}
+