Finite Element Grid I

Question

Introduction

Don't worry - no knowledge in mathematics is needed. It is possible to just skip the motivation part, but I think it is nice if a puzzle has a background story. Since the title contains the number I there will be more puzzles of this kind, if you like them. Feedback is highly appreciated. I hope you have fun with this puzzle! :)

Sandbox-Answer

---

Motivation

Many processes in the real life can be modelled with differential equations. A differential equation is an equation contain some differential expression, e.g.

x'(t) = λx(t)

This is a ordinary (= 1D) differential equation (ODE). And the solution to this is simply x(t) = x₀e^{λt} for any x₀∈ℝ. This ODE can be used as model for population growth (rabbits multiplying exponentially) or radiation decay. In both cases x̧₀ is the initial population / initial amount of material.

Now not everything in the world of physics can be modelled with ODEs. Since we live in a multidimensional world there should be differential equations with more than just one component, right?
These equations are named partial differential equations (PDE).

For example flow fields can (in some cases) be modelled using the Stokes Equation:

-Δv + ∇p = f in Ω
     ∇∘v = 0 in Ω

where v is the velocity and p is the pressure of the flow. And Ω⊂ℝ² is just the geometry on which the equation is solved - e.g. a tube.

Now if you want to solve these equations there is a method called Finite Element Method. And this method requires a grid of your geometry. In most cases these grids contain quadrilaterals or triangles.

For this code-golf we will use a very simple grid:

(0,1)                     (1,1)
  x-----x-----x-----x-----x
  |     |     |     |     |
  |  1  |  2  |  3  |  4  |
  |     |     |     |     |
  x-----x-----x-----x-----x
  |     |     |     |     |
  |  5  |  6  |  7  |  8  |
  |     |     |     |     |
  x-----x-----x-----x-----x
  |     |     |     |     |
  |  9  | 10  | 11  | 12  |
  |     |     |     |     |
  x-----x-----x-----x-----x
  |     |     |     |     |
  | 13  | 14  | 15  | 16  |
  |     |     |     |     |
  x-----x-----x-----x-----x
(0,0)                     (1,0)

This 2D-grid consists of 5x5 points in (2D) unit cube [0,1]×[0,1]⊂ℝ². Therefore we have 16 cells. The four Cartesian coordinates and the numbers in the cells are not part of the grid. They are just to explain the Input/Output.

There is a connection between the grid-size and the accuracy of the solution - the finer the grid the higher the accuracy. (Actually that is not always true.) But a finer grid also has a draw-back: The finer the grid the higher the computation cost (RAM and CPU). So you only want to refine your grid at some locations. This idea is called adaptive refinement and is usually based on the behaviour of the solution - e.g. thinking about the flow problem above: refine that part of the grid, where the solution is turbulent, don't refine if the solution is boring.

Task

The task is to implement this adaptive refinement in a general way. Since we don't solve any PDE in this code-golf the criteria to refine grid cells is based on a circle disk. This circle disk is simply defined by the midpoint p=[p0,p1]∈[0,1]² and the radius r ∈ [0,1].

Every cell intersecting with that disk (including boundaries - see Example 1) will be refined.

The output is the 5x5 grid above with the refined cells.

Asked Questions

What is the purpose of 'x'?

'x' represents nodes/vertices, '-' and '|' edges.

Refinement of a cell means, that you split one cell into 4:

  x-----x       x--x--x
  |     |       |  |  |
  |     |   >   x--x--x
  |     |       |  |  |
  x-----x       x--x--x

Examples

Input: p=[0,0] r=0.5
Output:
  x-----x-----x-----x-----x
  |     |     |     |     |
  |     |     |     |     |
  |     |     |     |     |
  x--x--x-----x-----x-----x
  |  |  |     |     |     |
  x--x--x     |     |     |
  |  |  |     |     |     |
  x--x--x--x--x-----x-----x
  |  |  |  |  |     |     |
  x--x--x--x--x     |     |
  |  |  |  |  |     |     |
  x--x--x--x--x--x--x-----x
  |  |  |  |  |  |  |     |
  x--x--x--x--x--x--x     |
  |  |  |  |  |  |  |     |
  x--x--x--x--x--x--x-----x

The midpoint is located in (0,0) with radius 0.5.

Cell 13: Completely inside the cell.
Cell 9 : Intersects, since lower left corner has coords (0,0.25).  
Cell 14: Intersects, since lower left corner has coords (0.25,0). 
Cell 5 : Intersects, since lower left corner has the coordinates (0, 0.5). 
Cell 15: Intersects, since lower left corner has the coordinates (0.5, 0). 
Cell 10: Intersects, since lower left corner has the coordinates (0.25, 0.25).
The distance from (0,0) to that corner is √(0.25²+0.25²) < 0.36 < 0.5.

Cell 11:  Does not intersect, since the closest point is the lower left
corner with coordinate (0.5,0.25), so the distance is 
√(0.5² + 0.25²) > √(0.5²) = 0.5


Input: p=[0.5,0.5] r=0.1
Output:
  x-----x-----x-----x-----x
  |     |     |     |     |
  |     |     |     |     |
  |     |     |     |     |
  x-----x--x--x--x--x-----x
  |     |  |  |  |  |     |
  |     x--x--|--x--x     |
  |     |  |  |  |  |     |
  x-----x--x--x--x--x-----x
  |     |  |  |  |  |     |
  |     x--x--x--x--x     |
  |     |  |  |  |  |     |
  x-----x--x--x--x--x-----x
  |     |     |     |     |
  |     |     |     |     |
  |     |     |     |     |
  x-----x-----x-----x-----x

The midpoint is located in (0.5,0.5) with radius 0.1. 
Therefore the circle is completely inside the union of cells 6,7,10 and 11.
It does not touch any 'outer' boundaries of these four cells.
So the only refined cells are these four. 


Input: p=[0.35,0.9] r=0.05
Output:
  x-----x--x--x-----x-----x
  |     |  |  |     |     |
  |     x--x--x     |     |
  |     |  |  |     |     |
  x-----x--x--x-----x-----x
  |     |     |     |     |
  |     |     |     |     |
  |     |     |     |     |
  x-----x-----x-----x-----x
  |     |     |     |     |
  |     |     |     |     |
  |     |     |     |     |
  x-----x-----x-----x-----x
  |     |     |     |     |
  |     |     |     |     |
  |     |     |     |     |
  x-----x-----x-----x-----x

Cell 2: Intersecting with the circle.
Cell 1: Not refined, since the right edge has x-coordinate 0.25 < 0.35-0.05 = 0.3.
Cell 3: Not refined, since the left edge has x-coordinate 0.5 > 0.35+0.05 = 0.4.
Cell 6: Not refined, since the top edge has y-coordinate 0.75 < 0.9 - 0.05 = 0.85. 

Rules

Since this is my first puzzle / golf help is appreciated.

• code-golf: Smallest byte size wins.
• Trailing / Leading whitespaces are allowed.
• The Cartesian coordinates are not part of the grid, and should not be seen in the output.
• Only allowed chars are '-', '|', 'x' and ' '
• Input: All three numbers will be floats. It does not matter if your input is a tuple (p0,p1) and a number r, or three numbers, or one array - just be reasonable.

Answer 1

Charcoal, 107 105 106 bytes

Ｆ²«x⁵↷²x³↷»Ｆ³«Ｃ⁰±⁴Ｃ⁶¦⁰»Ｆ⁴«Ａ⁻×⁴ＩθιεＦ⁴«Ａ⁻×⁴Ｉηκ먪›⁺Ｘ⎇›ε¹⁻ε¹∧‹ε⁰ε²Ｘ⎇›δ¹⁻δ¹∧‹δ⁰δ²Ｘ×⁴Ｉ沫Ｊ⁺³×⁶ι⁻²×⁴κＰ|x|xＰ-x--x

Try it online! Link is to verbose version of code, not that it helps. Edit: Saved 2 bytes by handling the reversed sense of the Y-axis in a different way, but added a byte to handle a clarification in the question. Explanation:

Ｆ²«x⁵↷²x³↷»

Prints a cell. It does this by printing an x, then printing 5 (which expands to ----- because the default cursor direction is right), then it rotates downwards, prints another x, prints 3 (which now expands to three |s downwards), then rotates left. Doing all that twice completes the cell.

Ｆ³«Ｃ⁰±⁴Ｃ⁶¦⁰»

There are four cells horizontally and vertically, so the cell needs to be copied horizontally and vertically three times. The vertical copy is done upwards to simplify the calculation below.

Ｆ⁴«Ａ⁻×⁴ＩθιεＦ⁴«Ａ⁻×⁴Ｉηκδ

The 16 cells are now looped over using a four by four nested loop. The coordinates of the midpoint are multiplied by 4, scaling them from 0 to 4, which corresponds to our loop indices which are subtracted, so the resulting variables are now relative to the cell's bottom left corner.

¿¬›⁺Ｘ⎇›ε¹⁻ε¹∧‹ε⁰ε²Ｘ⎇›δ¹⁻δ¹∧‹δ⁰δ²Ｘ×⁴Ｉ沫

The variables are now compared to the range 0 to 1 that represents the relative quadrupled cell coordinates. If they lie outside this range it means that the midpoint lies outside the cell, so the distance to the range is squared and the sum of the squares compared to the square of the quadrupled radius. If it is not greater, then the cell needs to be refined.

Ｊ⁺³×⁶ι⁻²×⁴κＰ|x|xＰ-x--x

The cursor is moved to the centre of the cell to be refined. The string x|x is printed vertically (both up and down), while the string x--x is printed horizontally (both left and right). (The middle xs overlap.)