dan-masek

Quick reimplementation of OpenCV partition function in Python

May 3rd, 2021
736
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. from cv2_45 import cv2
  2. import numpy as np
  3.  
  4. points = [(522, 114),
  5.     (523, 114),
  6.     (524, 114),
  7.     (522, 115),
  8.     (523, 115),
  9.     (524, 115),
  10.     (522, 116),
  11.     (523, 116),
  12.     (524, 116),
  13.     (523, 117),
  14.     (191, 178),
  15.     (192, 178),
  16.     (193, 178)]
  17.  
  18. def partition(items, predicate):
  19.     N = len(items)
  20.        
  21.     # // The first O(N) pass: create N single-vertex trees
  22.     parents = [-1] * N
  23.     ranks = [0] * N
  24.  
  25.     # The main O(N^2) pass: merge connected components
  26.     for i in range(N):
  27.         # Find root
  28.         root = i
  29.         while parents[root] >= 0:
  30.             root = parents[root]
  31.            
  32.         for j in range(N):
  33.             if i == j or not predicate(items[i], items[j]):
  34.                 continue
  35.            
  36.             root2 = j
  37.             while parents[root2] >= 0:
  38.                 root2 = parents[root2]
  39.                
  40.             if root != root2:
  41.                 # Unite both trees
  42.                 rank, rank2 = ranks[root], ranks[root2]
  43.                 if rank > rank2:
  44.                     parents[root2] = root
  45.                 else:
  46.                     parents[root] = root2
  47.                     ranks[root2] += 1 if rank == rank2 else 0
  48.                     root = root2
  49.                 assert parents[root] < 0
  50.                
  51.                 # compress the path from node2 to root
  52.                 k = j
  53.                 while True:
  54.                     parent = parents[k]
  55.                     if parent < 0:
  56.                         break
  57.                     parents[k] = root
  58.                     k = parent
  59.                    
  60.                    
  61.                 #compress the path from node to root
  62.                 k = i
  63.                 while True:
  64.                     parent = parents[k]
  65.                     if parent < 0:
  66.                         break
  67.                     parents[k] = root
  68.                     k = parent
  69.                    
  70.     # Final O(N) pass: enumerate classes
  71.     labels = [0] * N
  72.     nclasses = 0
  73.  
  74.     for i in range(N):
  75.         root = i
  76.         while parents[root] >= 0:
  77.             root = parents[root]
  78.         # re-use the rank as the class label
  79.         if ranks[root] >= 0:
  80.             ranks[root] = ~nclasses
  81.             nclasses += 1
  82.         labels[i] = ~ranks[root]
  83.  
  84.     return nclasses, labels
  85.  
  86.  
  87. def predicate(point1, point2):
  88.     threshold = 10
  89.     return (abs(point1[0] - point2[0]) < threshold) and (abs(point1[1] - point2[1]) < threshold)
  90.    
  91. print(partition(points, predicate))
  92.  
  93.  
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×