最小圆覆盖,并限制圆的渲染范围

2019-09-25 20:36栏目:网络编程
TAG:

主题材料链接:戳作者

叁个小小的圆覆盖的模板题吗。。。

细微圆覆盖如何是好??

便是枚举多个点,第二个点做圆心,第二、多个点和第贰个点同步起来鲜明三个圆。

看起来是的是还是不是?但是事实上均摊时间复杂度是的。具体怎么本身也不会证,不过大家得以通晓,若是枚举前面包车型大巴点一度在前头明确好的圆里面就没有须要再总结了是吧qwqwq

对于四个点,,,和茫然的圆心

对此多个点,,,和不解的圆心

(begin{cases}^2+^2=r^2\^2+^2=r^2\^2+^2=r^2end{cases})

(begin{cases}x0+y0=frac{(x2^2-x3^2)+(y2^2-y3^2)}{2}\x0+y0=frac{(x1^2-x2^2)+(y1^2-y2^2)}{2}end{cases})

(begin{cases}a*x0+b*y0=e\c*x0+d*y0=fend{cases})

(begin{cases}x=frac{de-bf}{ad-bc};\y=frac{ce-af}{bc-ad};end{cases})

代码如下:

#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>#include<ctime>#define eps 1e-15#define MAXN 500010using namespace std;int n;double r;struct Node{double x,y;}node[MAXN],o;inline double dist(Node a,Node b){return sqrt*+*;}inline void solve(Node A,Node B,Node C){    double a=*2;    double b=*2;    double c=*2;    double d=*2;    double e=(B.x*B.x-C.x*C.x)+(B.y*B.y-C.y*C.y);    double f=(A.x*A.x-B.x*B.x)+(A.y*A.y-B.y*B.y);    o.x=/;    o.y=/;    r=dist;}int main(){    #ifndef ONLINE_JUDGE    freopen("ce.in","r",stdin);    #endif    scanf("%d",&n);    for(int i=1;i<=n;i++)        scanf("%lf%lf",&node[i].x,&node[i].y);    random_shuffle(&node[1],&node[n+1]);    o=node[1]; r=0;    for(int i=2;i<=n;i++)        if(dist(node[i],o)>r+eps)        {            o=node[i];r=0;            for(int j=1;j<i;j++)            {                if(dist(node[j],o)>r+eps)                {                    o.x=(node[i].x+node[j].x)/2;                    o.y=(node[i].y+node[j].y)/2;                    r=dist(o,node[j]);                    for(int k=1;k<j;k++)                        if(dist(node[k],o)>r+eps)                            solve(node[i],node[j],node[k]);                }            }        }    printf("%.3lfn",r);}
  1. 因而四个点的坐标可规定一条双曲线。
  1. 透过五个点的坐标可明确一条双曲线。

  公式:

  公式:

      1)y=ax^2+bx+c;

      1)y=ax^2+bx+c;

      2) y=a(x-k)+h;

      2) y=a(x-k)+h;

      通过已知三点可明确a,b,c,h,k

      通过已知三点可分明a,b,c,h,k

  2.通过圆心坐标(a,b)和半径r可分明贰个圆,和已知的x坐标:

  2.通过圆心坐标(a,b)和半径r可明确多少个圆,和已知的x坐标:

  公式:

  公式:

      1)r^2=(x-a)^2+(y-b)^2

      1)r^2=(x-a)^2+(y-b)^2

  3.圆是否相交,可经过求得圆心距G鲜明,圆心(x1,y1)和(x2,y2):

  3.圆是不是相交,可经过求得圆心距G分明,圆心(x1,y1)和(x2,y2):

      1) G^2=(x1-x2)^2+(y1-y2)^2

      1) G^2=(x1-x2)^2+(y1-y2)^2

  4.规定圆上的点的x坐标是或不是在曲线内点(x,y),第11中学求得的a,h,k;算出当前y值时的大街小巷的曲线x值得范围:

  4.规定圆上的点的x坐标是还是不是在曲线内点(x,y),第11中学求得的a,h,k;算出当前y值时的随地的曲线x值得范围:

      1)  x1 =Math.sqrt((y -h) / a) + k, x2 =k - Math.sqrt((y - h) / a);

      1)  x1 =Math.sqrt((y -h) / a) + k, x2 =k - Math.sqrt((y - h) / a);

  以下为源码:

  以下为源码:

    

    

图片 1图片 2

图片 3图片 4

  1 <html>
  2 <head>
  3 
  4 </head>
  5 <body>
  6     <!--<div id="main">
  7 
  8     </div>-->
  9     <script>
 10         var mainDoc = document.getElementById("main");
 11         function _drawPoint(x, y) {
 12             var pe = document.createElement("div");
 13             pe.style.position = "absolute";
 14             pe.style.left = x;
 15             pe.style.top = y;
 16             pe.style.position
 17             pe.style.backgroundColor = "red";
 18             pe.style.width = 1;
 19             pe.style.height = 1;
 20             document.body.appendChild(pe);
 21         }
 22         var Circle = function (options) {
 23             this.center_x = options.center_x;
 24             this.center_y = options.center_y;
 25             this.radius = options.radius;
 26         }
 27         Circle.prototype = {
 28             draw: function () {
 29                 var sx = this.center_x - this.radius;
 30                 var ex = this.center_x + this.radius;
 31                 for (var i = sx; i <= ex; i += 0.1) {
 32                     var pos = this._pointCoordinate(i);
 33                     _drawPoint(pos[0].x, pos[0].y);
 34                     _drawPoint(pos[1].x, pos[1].y);
 35                 }
 36             },
 37             _pointCoordinate: function (x) {
 38                 var y = Math.sqrt(this.radius * this.radius - (x - this.center_x) * (x - this.center_x)) + this.center_y;
 39                 return [{ x: x, y: y }, {
 40                     x: x, y: this.center_y - (y - this.center_y)
 41                 }];
 42             }
 43         };
 44 
 45         var Hyperbola = function (options) {
 46             this.center_x = options.center_x;
 47             this.center_y = options.center_y;
 48             this.height = options.height;
 49             this.width = options.width;
 50             this.CircleList = [];
 51             this.k = 0;
 52             this.h = 0;
 53             this.a = 0;
 54             this._init();
 55         }
 56         Hyperbola.prototype = {
 57             draw: function () {
 58                 var sx = this.center_x - this.width / 2;
 59                 var ex = this.center_x + this.width / 2;
 60                 for (var i = sx; i <= this.center_x ; i += 0.1) {
 61                     var pos = this._pointCoordinate(i);
 62                     _drawPoint(pos[0].x, pos[0].y);
 63                     _drawPoint(pos[1].x, pos[1].y);
 64                 }
 65             },
 66             _init: function () {
 67                 var x1 = this.center_x - this.width / 2, y1 = this.center_y - this.height;
 68                 var x2 = this.center_x, y2 = this.center_y;
 69                 var x3 = this.center_x + this.width / 2, y3 = this.center_y - this.height;
 70                 var b = ((y1 - y2) * (x2 * x2 - x3 * x3) - (y2 - y3) * (x1 * x1 - x2 * x2)) / ((x1 - x2) * (x2 * x2 - x3 * x3) - (x2 - x3) * (x1 * x1 - x2 * x2));
 71                 var a = this.a = (y1 - y2 - b * x1 + b * x2) / (x1 * x1 - x2 * x2);
 72                 var c = y3 - a * x3 * x3 - b * x3;
 73                 var k = this.k = -b / (2 * a), h = this.h = (4 * a * c - b * b) / (4 * a);
 74             },
 75             _pointCoordinate: function (x) {
 76                 var y = this.a * (x - this.k) * (x - this.k) + this.h;
 77                 return [{ x: x, y: y }, {
 78                     x: this.center_x + Math.abs(this.center_x - x), y: y
 79                 }];
 80             },
 81             _randomCircle: function () {
 82                 var count = 1000;
 83                 while (count > 0) {
 84                     var x = this.center_x - this.width / 2 + Math.random() * this.width;
 85                     var y = this.center_y - Math.random() * this.height;
 86                     var radius = 3;
 87                     if (this.CheckTheBoundary(x - radius, y) && this.CheckTheBoundary(x + radius, y)
 88                         && this.CheckTheBoundary(x, y - radius) && this.CheckTheBoundary(x, y + radius)
 89                         && this.CheckTheCircle(x, y, radius)
 90                         ) {
 91                         var c = new Circle({ center_x: x, center_y: y, radius: radius });
 92                         c.draw();
 93                         this.CircleList.push(c);
 94                         count--;
 95                     }
 96                 }
 97             }
 98         ,
 99             move: function () {
100                 var speed = 5;
101                 for (var i = 0; i < this.CircleList.length; i++) {
102                     var c = this.CircleList[i];
103                     var x = this.center_x - this.width / 2 + Math.random() * this.width;
104                     var y = this.center_y - Math.random() * this.height;
105                     var radius = c.radius;
106                     if (this.CheckTheBoundary(x - radius, y) && this.CheckTheBoundary(x + radius, y)
107                           && this.CheckTheBoundary(x, y - radius) && this.CheckTheBoundary(x, y + radius)
108                           && this.CheckTheCircle(x, y, radius)
109                           ) {
110                         c.center_y = y;
111                         c.center_x = x;
112                         console.log(c.center_y);
113                         c.draw();
114                     }
115                 }
116             },
117             CheckTheBoundary: function (x, y) {
118                 if (y < (this.center_y - this.height)) return false;
119                 if (x < 0 || y < 0) return false;
120                 if (y > this.center_y) return false;
121                 var x1 = Math.sqrt((y - this.h) / this.a) + this.k, x2 = this.k - Math.sqrt((y - this.h) / this.a);
122                 var maxx = Math.max(x1, x2);
123                 var minx = Math.min(x1, x2);
124                 //if (isNaN(maxx) || isNaN(minx)) return false;
125                 if (x < minx || x > maxx) {
126                     return false;
127                 }
128                 return true;
129             },
130             CheckTheCircle: function (x, y, r) {
131                 for (var i = 0; i < this.CircleList.length; i++) {
132                     var g = Math.sqrt((x - this.CircleList[i].center_x) * (x - this.CircleList[i].center_x)
133                         + (y - this.CircleList[i].center_y) * (y - this.CircleList[i].center_y))
134                     if (g < (r + this.CircleList[i].radius))
135                         return false;
136                 }
137                 return true;
138             }
139         };
140         var h = new Hyperbola({ center_x: 700, center_y: 600, width: 800, height: 400 });
141         h.draw();
142         h._randomCircle();
143         //setInterval(function () {
144         //    h.move();
145         //}, 1000);
146     </script>
147 </body>
148 </html>
  1 <html>
  2 <head>
  3 
  4 </head>
  5 <body>
  6     <!--<div id="main">
  7 
  8     </div>-->
  9     <script>
 10         var mainDoc = document.getElementById("main");
 11         function _drawPoint(x, y) {
 12             var pe = document.createElement("div");
 13             pe.style.position = "absolute";
 14             pe.style.left = x;
 15             pe.style.top = y;
 16             pe.style.position
 17             pe.style.backgroundColor = "red";
 18             pe.style.width = 1;
 19             pe.style.height = 1;
 20             document.body.appendChild(pe);
 21         }
 22         var Circle = function (options) {
 23             this.center_x = options.center_x;
 24             this.center_y = options.center_y;
 25             this.radius = options.radius;
 26         }
 27         Circle.prototype = {
 28             draw: function () {
 29                 var sx = this.center_x - this.radius;
 30                 var ex = this.center_x + this.radius;
 31                 for (var i = sx; i <= ex; i += 0.1) {
 32                     var pos = this._pointCoordinate(i);
 33                     _drawPoint(pos[0].x, pos[0].y);
 34                     _drawPoint(pos[1].x, pos[1].y);
 35                 }
 36             },
 37             _pointCoordinate: function (x) {
 38                 var y = Math.sqrt(this.radius * this.radius - (x - this.center_x) * (x - this.center_x)) + this.center_y;
 39                 return [{ x: x, y: y }, {
 40                     x: x, y: this.center_y - (y - this.center_y)
 41                 }];
 42             }
 43         };
 44 
 45         var Hyperbola = function (options) {
 46             this.center_x = options.center_x;
 47             this.center_y = options.center_y;
 48             this.height = options.height;
 49             this.width = options.width;
 50             this.CircleList = [];
 51             this.k = 0;
 52             this.h = 0;
 53             this.a = 0;
 54             this._init();
 55         }
 56         Hyperbola.prototype = {
 57             draw: function () {
 58                 var sx = this.center_x - this.width / 2;
 59                 var ex = this.center_x + this.width / 2;
 60                 for (var i = sx; i <= this.center_x ; i += 0.1) {
 61                     var pos = this._pointCoordinate(i);
 62                     _drawPoint(pos[0].x, pos[0].y);
 63                     _drawPoint(pos[1].x, pos[1].y);
 64                 }
 65             },
 66             _init: function () {
 67                 var x1 = this.center_x - this.width / 2, y1 = this.center_y - this.height;
 68                 var x2 = this.center_x, y2 = this.center_y;
 69                 var x3 = this.center_x + this.width / 2, y3 = this.center_y - this.height;
 70                 var b = ((y1 - y2) * (x2 * x2 - x3 * x3) - (y2 - y3) * (x1 * x1 - x2 * x2)) / ((x1 - x2) * (x2 * x2 - x3 * x3) - (x2 - x3) * (x1 * x1 - x2 * x2));
 71                 var a = this.a = (y1 - y2 - b * x1 + b * x2) / (x1 * x1 - x2 * x2);
 72                 var c = y3 - a * x3 * x3 - b * x3;
 73                 var k = this.k = -b / (2 * a), h = this.h = (4 * a * c - b * b) / (4 * a);
 74             },
 75             _pointCoordinate: function (x) {
 76                 var y = this.a * (x - this.k) * (x - this.k) + this.h;
 77                 return [{ x: x, y: y }, {
 78                     x: this.center_x + Math.abs(this.center_x - x), y: y
 79                 }];
 80             },
 81             _randomCircle: function () {
 82                 var count = 1000;
 83                 while (count > 0) {
 84                     var x = this.center_x - this.width / 2 + Math.random() * this.width;
 85                     var y = this.center_y - Math.random() * this.height;
 86                     var radius = 3;
 87                     if (this.CheckTheBoundary(x - radius, y) && this.CheckTheBoundary(x + radius, y)
 88                         && this.CheckTheBoundary(x, y - radius) && this.CheckTheBoundary(x, y + radius)
 89                         && this.CheckTheCircle(x, y, radius)
 90                         ) {
 91                         var c = new Circle({ center_x: x, center_y: y, radius: radius });
 92                         c.draw();
 93                         this.CircleList.push(c);
 94                         count--;
 95                     }
 96                 }
 97             }
 98         ,
 99             move: function () {
100                 var speed = 5;
101                 for (var i = 0; i < this.CircleList.length; i++) {
102                     var c = this.CircleList[i];
103                     var x = this.center_x - this.width / 2 + Math.random() * this.width;
104                     var y = this.center_y - Math.random() * this.height;
105                     var radius = c.radius;
106                     if (this.CheckTheBoundary(x - radius, y) && this.CheckTheBoundary(x + radius, y)
107                           && this.CheckTheBoundary(x, y - radius) && this.CheckTheBoundary(x, y + radius)
108                           && this.CheckTheCircle(x, y, radius)
109                           ) {
110                         c.center_y = y;
111                         c.center_x = x;
112                         console.log(c.center_y);
113                         c.draw();
114                     }
115                 }
116             },
117             CheckTheBoundary: function (x, y) {
118                 if (y < (this.center_y - this.height)) return false;
119                 if (x < 0 || y < 0) return false;
120                 if (y > this.center_y) return false;
121                 var x1 = Math.sqrt((y - this.h) / this.a) + this.k, x2 = this.k - Math.sqrt((y - this.h) / this.a);
122                 var maxx = Math.max(x1, x2);
123                 var minx = Math.min(x1, x2);
124                 //if (isNaN(maxx) || isNaN(minx)) return false;
125                 if (x < minx || x > maxx) {
126                     return false;
127                 }
128                 return true;
129             },
130             CheckTheCircle: function (x, y, r) {
131                 for (var i = 0; i < this.CircleList.length; i++) {
132                     var g = Math.sqrt((x - this.CircleList[i].center_x) * (x - this.CircleList[i].center_x)
133                         + (y - this.CircleList[i].center_y) * (y - this.CircleList[i].center_y))
134                     if (g < (r + this.CircleList[i].radius))
135                         return false;
136                 }
137                 return true;
138             }
139         };
140         var h = new Hyperbola({ center_x: 700, center_y: 600, width: 800, height: 400 });
141         h.draw();
142         h._randomCircle();
143         //setInterval(function () {
144         //    h.move();
145         //}, 1000);
146     </script>
147 </body>
148 </html>

View Code

View Code

 

 

效果:

效果:

  

  

    图片 5

    图片 6

        

        

  

  

版权声明:本文由澳门新葡亰平台游戏发布于网络编程,转载请注明出处:最小圆覆盖,并限制圆的渲染范围