Can area-partitioning lose included points due to floating point precision?

Question

I'm currently partitioning a big area $A$ into $n$ areas $B_i$ such that $$\bigcup_{i=1}^n B_i = A$$

I have geo-coordinates which I know are in $A$ (also with the finite precision of floats).

Obviously, for every point $p$ in $A$ there has to be an area $B_i$ such that the point is in $B_i$. Formally:

$$p \in A \Rightarrow \exists i: p \in B_i$$

But due to floating point precision, I wonder if it could happen that for all $B_i$ the B_i.intersects(p) method returns false. Formally:

$$\forall i: \neg B_i.\texttt{intersects}(p)$$

All areas are polygons and neighboring polygons share some points which define the polygons.

If the answer is yes, then an example would be good. It would be awesome if one could also quantify the probability of this.

(In my current case, I use shapely.)

Answer 1

This is a problem for anyone making graphics cards: To draw an area, it will usually be split into triangles, and for many drawing methods it is important that every point is drawn exactly once.

At some point you'll have use an algorithm that decides whether a point x is on or above a line l, and at some other point you'll have an algorithm that decides whether x is below the line l. For good results, you need to design this algorithm carefully so it is guaranteed to say "YES" once and "NO" once. It doesn't matter too much whether the result is correct (not saying YES when the point is actually just a tiny bit below the curve), what's important is that the answer is "YES" exactly once and not twice.

Answer 2

Yes it is possible.

For example, look at this C code.

#include <stdio.h>

int main ()
 {
  float a=10.3346714;
  float b=10.3346711;
  printf("a=%.15f\nb=%.15f\n",a,b);
 }

It outputs the following upon execution.

a=10.334671020507812
b=10.334671020507812

Lets say your area $A$ was defined as $\{ -10.3346714 \lt x \lt 10.3346714, -20.6693428 \lt y \lt 20.6693428\}$
and it is divided into two equal regions by the line $x=0$
Lets call these two regions $B_{left},B_{right}$.
Now we have our point $p = (10.3346711,2.0000000)$.

From a purely mathematical point of view, we can see that $p \in A\space and \space p \in B_{right}$.
But if a computer were to perform this check using floating point numbers, for the region $B_{right}$, i.e $p \in B_{right}$, it would do so by comparing $p$ with the rightmost boundary of $B_{right}$ like $10.3346711\lt10.3346714$, which would be false, since both floating point numbers are the same when stored in memory.

The same would happen for checking $p \in A$. Which means $p \notin A \space and \space p \notin B_{right}$ (Atleast as per the computer).

Note
This check would fail only if $p$ lies very close to the boundary of $A$. Other interior points would ultimately reside on either sides of a boundary i.e. in either regions around a boundary.