برش میانی

برش میانه ای (به انگلیسی: median cut) الگوریتمی برای یافتن نماینده هایی مناسب از یک مجموعه عناصر چند بعدی است که توسط پاول هکبرت (Paul Heckbert) در سال ۱۹۷۹ میلادی ابداع شد. این روش یک الگوریتم بازگشتی است و در هر مرحله داده ها را به دو دسته حول میانه بُعد با بزرگ ترین دامنه تغییرات تقسیم می کند و در پایان برای هر دسته نماینده ای مشخص می کند. برش میانی در حال حاضر پر استفاده ترین الگوریتم برای گسسته سازی رنگ است.
پیچیدگی زمانی
توابع بازگشتی
بیت مپ
فضای رنگ
الگوریتم های همروند
این الگوریتم به این شکل عمل می کند که در هر دسته ابتدا مولفه ای که دامنه تغییرات عناصر در آن از بقیه بزرگ تر است را پیدا کرده و داده ها را برحسب مقادیر در آن بُعد مرتب می کند. سپس با پیدا کردن میانه داده ها را به دو دسته قبل و بعد میانه تقسیم می کند. اگر هنوز تعداد دسته های ایجاد شده از تعداد مورد نظر کمتر بود این عملیات را بر روی هر دو دسته ایجاد شده تکرار می کند. در پایان معمولاً میانگین عناصر هر دسته را به عنوان نماینده آن دسته انتخاب می کنند.
معمولاً عناصر مجموعه را به شکل یک بردار در نظر می گیرند. در این صورت شبه کد الگوریتم به این شکل خواهد بود:
def median_cut (array, reprsnt_num, step): if (2 ^ step >= reprsnt_num or array.length <= 1 ): return # max_range_dim finds the dimension with max "range" idx = max_range_dim(array) # sort_by_nth_comp sorts array by comparing nth component in elements sorted_array = sort_by_nth_comp(array, idx) # merge two arrays return median_cut(array, reprsnt_num, step + 1) + median_cut(array, reprsnt_num, step + 1)مرحله ۰ - نمودار داده های دو بعدیمرحله ۱ - داده ها حول میانه به دو دسته تقسیم شده اندمرحله ۲ - هر دسته خود به دو دسته دیگر تقسیم شده است      تحلیل الگوریتمویرایشاگر n {\displaystyle n}  داده در فضای m {\displaystyle m}  بعدی داشته باشیم، درصورتی که در پیاده سازی این الگوریتم از مرتب سازی هرمی (از O ( n l o g ( n ) ) {\displaystyle O(nlog(n))}  )استفاده کنیم و در هر مرحله برای پیدا کردن مولفه با بیشتربن بازه، کمینه و بیشینه را برای هر مولفه بیابیم (از O ( m n ) {\displaystyle O(mn)}  ) و ادغام لیست ها را در O ( n ) {\displaystyle O(n)}  انجام دهیم، داریم: