In this paper, we introduce a novel approach for efficiently computing the connected orthogonal convex hull COCH (P) of a finite set P of points in the 2D plane. By using a (4k + 4)-sided orthogonal convex polygon (4k+4)P constructed from 2k extremum directions, we can significantly reduce the input size by eliminating unnecessary interior points. This preprocessing step decreases the input size by up to 95% when k = 16, leading to substantial improvements in computation time. Our method further enhances efficiency by partitioning the remaining points into 4k subsets, classifying these subsets into four groups to identify type-t extreme points for t = 1, 2, 3, 4, which allows for rapid identification of the extreme points of COCH (P). Additionally, the algorithm is easily parallelizable and can scale up to 4k parallel threads, resulting in remarkable speedups. Experimental results demonstrate that our algorithm outperforms state-of-the-art algorithms such as OQuickhull (introduced by Linh et al. (Appl. Math. Comput. 429, 127183, 2022)) and O-Graham (introduced by An et al. (Appl. Math. Comput. 397, 125889, 2021)). For instance, with a dataset of 100, 000, 000 randomly generated points within a disc, our method achieved speedups of up to 16.23 times over O-Graham and 12.44 times over O-Quickhull. When parallelized, these speedup ratios increased significantly to 96.12 times over O-Graham and 73.68 times over O-Quickhull, highlighting the efficiency and scalability of our approach for high-demand computational applications.