[Ipe-discuss] closed regions defined by a trajectory

[Mathias Rav]

On Mon, Jan 6, 2025, at 10:40 AM, Mandar Mitra via Ipe-discuss wrote:
> Consider piece-wise linear trajectories, as shown in the attached 
> diagram. I'd like to compute the total area of all closed regions 
> defined by the trajectory. 
>
> I've marked the regions that I have in mind in green (the intuition 
> behind what I'm calling a "closed region" seems easy enough, but I have 
> not thought about defining it in a technical / precise way).

It seems to me like you want to identify the union of the bounded faces of the planar decomposition defined by the curve with its self-intersections.

> If I choose the stroke-and-fill option in IPE, I get the yellow region.
>
> Question: is there a pointer (other than the code) to 
>
> (i) the algorithm that IPE uses to determine the region to be filled 
> for a path? 

I'm pretty sure IPE uses the standard even-odd fill-rule, see e.g. the CSS specification for "fill-rule=evenodd".
For non-closed paths, first the path is closed by adding the segment from the last vertex to the first vertex (used only for the fill, not the stroke). Then, each point p is considered "inside" (filled in) if and only if a ray shooting out from p crosses an *odd* number of edges. The other option in CSS is fill-rule=nonzero, where the point is filled in if a ray crosses *any* edge - but I don't think IPE implements this and it wouldn't help in your case anyway.

> (ii) any algorithm for determining the closed region in my (possibly 
> layperson's) sense?

You could compute all self-intersections (e.g. with Bentley-Ottmann), construct the planar decomposition to a DCEL representation, trim the degree-one ends of the curve, and then traverse the outline of the unbounded face. This is a conceptually straightforward algorithm but it will probably require either a good computational geometry library or quite a few lines of code. There might be some simpler, more direct approach that I'm not seeing though - perhaps one that computes the total area directly instead of first constructing the planar decomposition.

Cheers,
Mathias