CODEWITHSUNDEEP
pythonpython-3.xalgorithm
Raj
Raj

Reputation: 3001

Welzl's Algorithm for Minimum Enclosing Circle SupportPoints going beyond 3

I am implementing Welzl's algorithm recursively as explained in https://www.geeksforgeeks.org/minimum-enclosing-circle-set-2-welzls-algorithm/. But I am not able to understand how we are restricting the size of supportPoints max upto 3. As we are either adding or keeping supportPoints same, then its obvious that its size max exceed 3. Here, is my source code.

def Welzl(points, supportpoints):
    if points.size() == 0 or supportpoints.size() == 3:
        if supportpoints.isempty():
            return (0,0), 0

        if supportpoints.size() == 1:
            return points[0], 0

        if supportpoints.size() == 2:
            center = minimum enclosing circle with points[0], points[1]
            radius = half the distance
            return center, radius

        if supportpoints.size() == 3:
            minimum enclosing circle with different permutations if possible else
            center = minimum enclosing circle with points[0], points[1], points[2]
            radius = radius 
            return center, radius

    random point p from points
    remove p from points
    circle = Wezl(points, supportpoints)
    if p in circle:
        return circle
    else:
        add p in supportpoints 
        return welzl(points, supportpoints)
    

Welze(points, [])

It is not giving correct output on points = [[2,1], [4,2], [1,4], [-1,1], [3,-2], [-3,-3], [-1,-5]]. Can anyone please explain what point I am missing or what's the error in my implementation

Upvotes: 1

Views: 1940

Answers (2)

Kashyap gajera
Kashyap gajera

Reputation: 35

I believe you need to have an explicit condition like below

supportpoints ==3

Similar to

// Base case when all points processed or |R| = 3 
    if (n == 0 || R.size() == 3) { 
        return min_circle_trivial(R); 
    }

in the the link you provided

Upvotes: 0

Jack McKay Fletcher
Jack McKay Fletcher

Reputation: 169

The 3 support points are nicely visualised here: https://www.nayuki.io/page/smallest-enclosing-circle and there is some python code here which helps explain the algorithm: https://www.nayuki.io/res/smallest-enclosing-circle/smallestenclosingcircle.py

I would break your algorithm into smaller functions for ease of understanding.

Upvotes: 1

Related Questions