In [1]:

```
class Polygon:
def __init__(self,list_of_nodes):
self.nodes=list_of_nodes
def compare(self,p):
return set(self.nodes)==set(p.nodes)
```

In [15]:

```
def create_classes(polygones):
classes = []
for p in polygones:
test = False
for classe in classes:
if classe[0].compare(p):
classe.append(p)
test=True
break
if not test:
classes.append([p])
return classes
```

In [16]:

```
polygones = [Polygon([1,2,3]),Polygon([2,5]),Polygon([2,6]),Polygon([5,2])]
create_classes(polygones)
```

Out[16]:

The worst case cost is $O(n^2)$ (in number of comparisons).

The idea is here to create a hash table with key the number of nodes in each polygon and value the list of polygons with this number of nodes. Then create classes by filtering over the hash table.

In [17]:

```
def create_hash_table(polygones):
hash_table={}
for p in polygones:
key = len(p.nodes)
if key in hash_table:
hash_table[key].append(p)
else:
hash_table[key] = [p]
return hash_table
def create_classes_improved(hash_table_of_polygones):
classes=[]
for key in hash_table_of_polygones:
classes += create_classes(hash_table_of_polygones[key])
return classes
```

In [18]:

```
ht=create_hash_table(polygones)
create_classes_improved(ht)
```

Out[18]:

Note that overlapping segments must be aligned: a hash-table can thus be designed based on a couple (angle,intersect).

We can also use a hash-table collecting all extremum points (its keys) and the corresponding value of $c(p)$.

In [19]:

```
def compute_store_c(S):
c = {}
for b,e in S:
if not (b in c):
c[b] = 0
c[b]+=1
if not(e in c):
c[e] = 0
c[e]-=1
return c
```

In [20]:

```
S = [[0,3],[1,2],[2,8],[5,7],[1,3]]
compute_store_c(S)
```

Out[20]:

In [8]:

```
def print_segments(S):
for b,e in S:
#print(" "*b,"="*(e-b),"\n")
print((b,e),":\t","{}x{}x\n".format(" "*b,"="*(e-b-1)))
```

In [9]:

```
print_segments(S)
```

The strategy is the following:

we first show that, sorting the $c(p)$'s in the order on the line of the points $p\in P$ made of the extremeties of the segments of $S$, $$C(p)\equiv \sum_{i\in P}^p c(i)$$ corresponds to the number of segments of the type $[p_1,p_2)$ on which $p$ stays. The variable $C(p)$ will be iterated over in the code, and will be named

`counter`

.*Prove it!**(Hint: by recursion; be careful that if $s = [p_1,p_2]\in S$, then $p_2\notin [p_1,p_2)$)*

- as a consequence, a segment in the final list of segments (without overlaps) must necessarily start at a $p$ with $C(p)=1$:
*this is when only one segment starts at $p$*. - when a point $p'$ immediately follows $p$, the segment must be cut if $C(p')\neq 1$:
*which is always the case unless the unique segment starting at $p$ stops at $p'$ and another one starts at $p'$*.

In [21]:

```
def discard_overlaps(S):
Sout = []
# get the values of c(p) for all p extremeties of segments of S
c = compute_store_c(S)
# take the opportunity to collect the extremeties in 'points' and sort them
points = [key for key in c]
points.sort()
# identifier to know whether we have a current beginning for the next segment (so 'None' initially)
segment_beginning = None
# counter counts the number of segments of the form '[p1,p2)' on which the current point 'p' lies
counter = 0
for p in points:
counter += c[p]
if counter != 1:
# if counter != 1, break the segment, output it, and wait for new segment
if segment_beginning != None:
Sout.append([segment_beginning,p])
segment_beginning = None
else:
# initiate a new segment if counter==1
if segment_beginning==None:
segment_beginning = p
return Sout
```

The algorithm complexity is in the worst case $O(|S|\log(|S|))$ dominated by the first sorting operation. The core of the algorithm has linear complexity in $|S|$.

In [22]:

```
print("Original segments:",S)
print("\nOutput segments:",discard_overlaps(S))
```

In [23]:

```
print("Original segments:\n")
print_segments(S)
print("\nAfter removing overlaps:\n")
print_segments(discard_overlaps(S))
```

In [ ]:

```
```

In [ ]:

```
```