/********************************************************************************
*  This file is part of CinoLib                                                 *
*  Copyright(C) 2016: Marco Livesu                                              *
*                                                                               *
*  The MIT License                                                              *
*                                                                               *
*  Permission is hereby granted, free of charge, to any person obtaining a      *
*  copy of this software and associated documentation files (the "Software"),   *
*  to deal in the Software without restriction, including without limitation    *
*  the rights to use, copy, modify, merge, publish, distribute, sublicense,     *
*  and/or sell copies of the Software, and to permit persons to whom the        *
*  Software is furnished to do so, subject to the following conditions:         *
*                                                                               *
*  The above copyright notice and this permission notice shall be included in   *
*  all copies or substantial portions of the Software.                          *
*                                                                               *
*  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR   *
*  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,     *
*  FITNESS FOR A PARTICULAR PURPOSE AND NON INFRINGEMENT. IN NO EVENT SHALL THE *
*  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER       *
*  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING      *
*  FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS *
*  IN THE SOFTWARE.                                                             *
*                                                                               *
*  Author(s):                                                                   *
*                                                                               *
*     Marco Livesu (marco.livesu@gmail.com)                                     *
*     http://pers.ge.imati.cnr.it/livesu/                                       *
*                                                                               *
*     Italian National Research Council (CNR)                                   *
*     Institute for Applied Mathematics and Information Technologies (IMATI)    *
*     Via de Marini, 6                                                          *
*     16149 Genoa,                                                              *
*     Italy                                                                     *
*********************************************************************************/
#ifndef CINO_SMALLEST_ENCLOSING_DISK_H
#define CINO_SMALLEST_ENCLOSING_DISK_H

#include <vector>
#include <cinolib/cino_inline.h>
#include <cinolib/geometry/vec_mat.h>

namespace cinolib
{

// Solve the smallest-circle problem (or minimum covering circle problem)
// using a recirsive implementation of the Welzl's algorithm. References:
//
//    1) https://en.wikipedia.org/wiki/Smallest-circle_problem
//
//    2) Smallest Enclosing Disks (Balls and Ellipsoids)
//       Emo Welzl
//       New Results and Trends in Computer Science
//       Lecture Notes in Computer Science, 555 (1991), pp359-370
//
CINO_INLINE
void smallest_enclosing_disk(const std::vector<vec2d> & points,
                                   vec2d              & center,
                                   double             & radius);


//::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::

CINO_INLINE
void smallest_enclosing_disk(const std::vector<vec3d> & points,  // will drop z component
                                   vec3d              & center,  // will have z=0
                                   double             & radius);
}

#ifndef  CINO_STATIC_LIB
#include "smallest_enclosing_disk.cpp"
#endif

#endif // CINO_SMALLEST_ENCLOSING_DISK_H
