<commit_before><meta charset="utf-8" />

<address>Mar 2017</address>

<style>
svg { pointer-events: none; }
text { font-family: helvetica; font-size: 16px; text-anchor: middle; }
line { fill: none; stroke: black; }
.dashed { stroke-dasharray: 4,3; }
.draggable { pointer-events: visible; cursor: move; }
.draggable:hover { filter:url(#drop-shadow); }
</style>



# Problem statement

Show the problem being solved with an interactive diagram

## Path

Show a path. It will be alternating "surfing" and "hugging" edges.

# A\* Algorithm

Review A\*, emphasizing that it works on graphs. We'll want to represent the surfing and hugging edges, as well as the nodes, in this graph. A\* is versatile and does not need to be modified for this problem (is this true?). 

# Graph

Show the graph corresponding to the initial diagram, with surfing and hugging edges. Simplications: player is a point instead of a circle, and the obstacles don't intersect.

Every node is on a circle (or is the start/end point), and every edge is either a hugging edge between two points on the same circle, or a surfing edge between two points on different circles

## Generating surfing edges

The surfing edges between a pair of circles are the line segments
which just kiss the circles; these segments are known as bitangents,
and in general, there are four of them for each pair of circles.

- Given two circles, generate the nodes and edges for the graph
- bitangents, biarcs
- pulley problem, belt problem

<svg id="belt-problem" width="600" height="300">
  <circle id="belt-circle-1" class="draggable" :cx="A.x" :cy="A.y" :r="A.r" fill="hsl(240,10%,90%)"/>
  <circle id="belt-circle-2" class="draggable" :cx="B.x" :cy="B.y" :r="B.r" fill="hsl(240,10%,90%)"/>
  <circle :cx="A.x" :cy="A.y" :r="A.r" fill="none" stroke="black"/>
  <circle :cx="B.x" :cy="B.y" :r="B.r" fill="none" stroke="black"/>
  <line class="dashed" :x1="A.x" :y1="A.y" :x2="B.x" :y2="B.y"/>
  <belt-label :at="A" :opposite="B" label="A"/>
  <belt-label :at="B" :opposite="A" label="B"/>
  <template v-if="non_overlapping">
    <line class="dashed" :x1="A.x" :y1="A.y" :x2="C.x" :y2="C.y"/>
    <line class="dashed" :x1="A.x" :y1="A.y" :x2="D.x" :y2="D.y"/>
    <line class="dashed" :x1="B.x" :y1="B.y" :x2="E.x" :y2="E.y"/>
    <line class="dashed" :x1="B.x" :y1="B.y" :x2="F.x" :y2="F.y"/>
    <line :x1="C.x" :y1="C.y" :x2="F.x" :y2="F.y" stroke-width="2" style="stroke:hsl(240,50%,50%)"/>
    <line :x1="D.x" :y1="D.y" :x2="E.x" :y2="E.y" stroke-width="2" style="stroke:hsl(240,50%,50%)"/>
    <belt-label :at="C" :opposite="A" label="C"/>
    <belt-label :at="D" :opposite="A" label="D"/>
    <belt-label :at="E" :opposite="B" label="E"/>
    <belt-label :at="F" :opposite="B" label="F"/>
    <belt-label :at="theta_AC" :opposite="A" label="θ"/>
    <belt-label :at="theta_AD" :opposite="A" label="θ"/>
    <belt-label :at="theta_BE" :opposite="B" label="θ"/>
    <belt-label :at="theta_BF" :opposite="B" label="θ"/>
  </template>
  <template v-else>
    <text x="300" y="15">Overlapping circles have no bitangents</text>
  </template>
</svg>


<svg id="pulley-problem" width="600" height="300">
  <circle id="pulley-circle-1" class="draggable" :cx="A.x" :cy="A.y" :r="A.r" fill="hsl(240,10%,90%)"/>
  <circle id="pulley-circle-2" class="draggable" :cx="B.x" :cy="B.y" :r="B.r" fill="hsl(240,10%,90%)"/>
  <circle :cx="A.x" :cy="A.y" :r="A.r" fill="none" stroke="black"/>
  <circle :cx="B.x" :cy="B.y" :r="B.r" fill="none" stroke="black"/>
  <line class="dashed" :x1="A.x" :y1="A.y" :x2="B.x" :y2="B.y"/>
  <belt-label :at="A" :opposite="B" label="A"/>
  <belt-label :at="B" :opposite="A" label="B"/>
  <template v-if="non_containing">
    <line class="dashed" :x1="A.x" :y1="A.y" :x2="C.x" :y2="C.y"/>
    <line class="dashed" :x1="A.x" :y1="A.y" :x2="D.x" :y2="D.y"/>
    <line class="dashed" :x1="B.x" :y1="B.y" :x2="E.x" :y2="E.y"/>
    <line class="dashed" :x1="B.x" :y1="B.y" :x2="F.x" :y2="F.y"/>
    <line :x1="C.x" :y1="C.y" :x2="F.x" :y2="F.y" stroke-width="2" style="stroke:hsl(240,50%,50%)"/>
    <line :x1="D.x" :y1="D.y" :x2="E.x" :y2="E.y" stroke-width="2" style="stroke:hsl(240,50%,50%)"/>
    <belt-label :at="C" :opposite="A" label="C"/>
    <belt-label :at="D" :opposite="A" label="D"/>
    <belt-label :at="E" :opposite="B" label="E"/>
    <belt-label :at="F" :opposite="B" label="F"/>
    <belt-label :at="theta_AC" :opposite="A" label="θ"/>
    <belt-label :at="theta_AD" :opposite="A" label="θ"/>
    <belt-label :at="theta_BE" :opposite="B" label="θ"/>
    <belt-label :at="theta_BF" :opposite="B" label="θ"/>
  </template>
  <template v-else>
    <text x="300" y="15">Smaller circle entirely contained in larger one</text>
  </template>
</svg>

## Generating hugging edges


## Line of sight

Diagram with three circles shows that some of the surfing edges don't actually work because they're blocked. Implement line of sight here<commit_msg>Add some text<commit_after><meta charset="utf-8" />

<address>Mar 2017</address>

<style>
svg { pointer-events: none; }
text { font-family: helvetica; font-size: 16px; text-anchor: middle; }
line { fill: none; stroke: black; }
.dashed { stroke-dasharray: 4,3; }
.draggable { pointer-events: visible; cursor: move; }
.draggable:hover { filter:url(#drop-shadow); }
</style>



# Problem statement

Show the problem being solved with an interactive diagram

## Path

Show a path. It will be alternating "surfing" and "hugging" edges.

# A\* Algorithm

Review A\*, emphasizing that it works on graphs. We'll want to represent the surfing and hugging edges, as well as the nodes, in this graph. A\* is versatile and does not need to be modified for this problem (is this true?). 

# Graph

Show the graph corresponding to the initial diagram, with surfing and hugging edges. Simplications: player is a point instead of a circle, and the obstacles don't intersect.

Every node is on a circle (or is the start/end point), and every edge is either a hugging edge between two points on the same circle, or a surfing edge between two points on different circles

## Generating surfing edges

- Given two circles, generate the nodes and edges for the graph
- bitangents, biarcs
- pulley problem, belt problem

The surfing edges between a pair of circles are the line segments
which just kiss the circles; these segments are known as bitangents,
and in general, there are four of them for each pair of circles. The
bitangents which cross between the circles are the internal
bitangents, while the ones which go along the outside are the external
bitangents.

### Internal bitangents

Historically, internal bitangents were important for calculating the
length of a belt which crosses over two different sized pulleys, and
the problem of constructing internal bitangents is known as the belt
problem.  To find the internal bitangents, calculate the angle theta
in the diagram below.

<svg id="belt-problem" width="600" height="300">
  <circle id="belt-circle-1" class="draggable" :cx="A.x" :cy="A.y" :r="A.r" fill="hsl(240,10%,90%)"/>
  <circle id="belt-circle-2" class="draggable" :cx="B.x" :cy="B.y" :r="B.r" fill="hsl(240,10%,90%)"/>
  <circle :cx="A.x" :cy="A.y" :r="A.r" fill="none" stroke="black"/>
  <circle :cx="B.x" :cy="B.y" :r="B.r" fill="none" stroke="black"/>
  <line class="dashed" :x1="A.x" :y1="A.y" :x2="B.x" :y2="B.y"/>
  <belt-label :at="A" :opposite="B" label="A"/>
  <belt-label :at="B" :opposite="A" label="B"/>
  <template v-if="non_overlapping">
    <line class="dashed" :x1="A.x" :y1="A.y" :x2="C.x" :y2="C.y"/>
    <line class="dashed" :x1="A.x" :y1="A.y" :x2="D.x" :y2="D.y"/>
    <line class="dashed" :x1="B.x" :y1="B.y" :x2="E.x" :y2="E.y"/>
    <line class="dashed" :x1="B.x" :y1="B.y" :x2="F.x" :y2="F.y"/>
    <line :x1="C.x" :y1="C.y" :x2="F.x" :y2="F.y" stroke-width="2" style="stroke:hsl(240,50%,50%)"/>
    <line :x1="D.x" :y1="D.y" :x2="E.x" :y2="E.y" stroke-width="2" style="stroke:hsl(240,50%,50%)"/>
    <belt-label :at="C" :opposite="A" label="C"/>
    <belt-label :at="D" :opposite="A" label="D"/>
    <belt-label :at="E" :opposite="B" label="E"/>
    <belt-label :at="F" :opposite="B" label="F"/>
    <belt-label :at="theta_AC" :opposite="A" label="θ"/>
    <belt-label :at="theta_AD" :opposite="A" label="θ"/>
    <belt-label :at="theta_BE" :opposite="B" label="θ"/>
    <belt-label :at="theta_BF" :opposite="B" label="θ"/>
  </template>
  <template v-else>
    <text x="300" y="15">Overlapping circles have no bitangents</text>
  </template>
</svg>

Given circles A and B with radii r1 and r2, with centers separated by distance
P, theta = acos((r1 + r2) / P). Note that when the two circles
overlap, (r1 + r2) is greater than P, and their ratio is greater than
1. Arccosine is not defined for values outside the range [-1 .. 1],
and therefore there are no internal bitangents between overlapping
circles.

### External bitangents

Finding external bitangents is also easy (the "pully problem").

<svg id="pulley-problem" width="600" height="300">
  <circle id="pulley-circle-1" class="draggable" :cx="A.x" :cy="A.y" :r="A.r" fill="hsl(240,10%,90%)"/>
  <circle id="pulley-circle-2" class="draggable" :cx="B.x" :cy="B.y" :r="B.r" fill="hsl(240,10%,90%)"/>
  <circle :cx="A.x" :cy="A.y" :r="A.r" fill="none" stroke="black"/>
  <circle :cx="B.x" :cy="B.y" :r="B.r" fill="none" stroke="black"/>
  <line class="dashed" :x1="A.x" :y1="A.y" :x2="B.x" :y2="B.y"/>
  <belt-label :at="A" :opposite="B" label="A"/>
  <belt-label :at="B" :opposite="A" label="B"/>
  <template v-if="non_containing">
    <line class="dashed" :x1="A.x" :y1="A.y" :x2="C.x" :y2="C.y"/>
    <line class="dashed" :x1="A.x" :y1="A.y" :x2="D.x" :y2="D.y"/>
    <line class="dashed" :x1="B.x" :y1="B.y" :x2="E.x" :y2="E.y"/>
    <line class="dashed" :x1="B.x" :y1="B.y" :x2="F.x" :y2="F.y"/>
    <line :x1="C.x" :y1="C.y" :x2="F.x" :y2="F.y" stroke-width="2" style="stroke:hsl(240,50%,50%)"/>
    <line :x1="D.x" :y1="D.y" :x2="E.x" :y2="E.y" stroke-width="2" style="stroke:hsl(240,50%,50%)"/>
    <belt-label :at="C" :opposite="A" label="C"/>
    <belt-label :at="D" :opposite="A" label="D"/>
    <belt-label :at="E" :opposite="B" label="E"/>
    <belt-label :at="F" :opposite="B" label="F"/>
    <belt-label :at="theta_AC" :opposite="A" label="θ"/>
    <belt-label :at="theta_AD" :opposite="A" label="θ"/>
    <belt-label :at="theta_BE" :opposite="B" label="θ"/>
    <belt-label :at="theta_BF" :opposite="B" label="θ"/>
  </template>
  <template v-else>
    <text x="300" y="15">Smaller circle entirely contained in larger one</text>
  </template>
</svg>

For external bitangents, theta = acos((r1 - r2) / P). It doesn't
matter whether circle A or B is bigger, but as shown in the diagram,
theta appears on the side of A toward B, but on the side of B away
from A. But if the difference in size of the two circles is greater
than the separation of the centers, then acos((r1 - r2) / P) is
undefined. This mean one circle is completely inside the other, and
there are no external bitangents for the circles.

## Generating hugging edges


## Line of sight

Diagram with three circles shows that some of the surfing edges don't actually work because they're blocked. Implement line of sight here
{'fraction_non_alphanumeric': 0.21091590118612324, 'fraction_numerical': 0.028092392758405423, 'mean_word_length': 4.373263057019646, 'pattern_counts': {'":': 0, '<': 129, '<?xml version=': 0, '>': 129, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2576303', 'n_tokens_mistral': 4601, 'n_tokens_neox': 4354, 'n_words': 1232}