首页 > ACM题库 > HDU-杭电 > hdu 2436 Collision Detection[解题报告]C++
2014
01-26

hdu 2436 Collision Detection[解题报告]C++

Collision Detection

问题描述 :

      In physical simulations, video games and computational geometry, collision detection involves algorithms for checking for collision, i.e. intersection, of two given objects. Collision detection algorithms are a basic component of 3D video games. Without them, characters could go through walls and other obstacles.
      Here comes an interesting problem, given a ball and a cuboid, you need to detect whether they collide. We say that two objects collide if and only if they share at least one point.

输入:

      The first line of input is the number of test cases.
      Each test case contains two lines, the first line contains 24 integers X1, Y1, Z1, …, X8, Y8, Z8, representing the 8 vertexes of the cuboid. Vertexes are given in random order and you can make sure that all edges of the cuboid are parallel to coordinate axes; the second line contains 4 integers X,Y,Z,R representing the central point of the ball and its radius. All integers given are non-negative and will be less than 100000.

输出:

      The first line of input is the number of test cases.
      Each test case contains two lines, the first line contains 24 integers X1, Y1, Z1, …, X8, Y8, Z8, representing the 8 vertexes of the cuboid. Vertexes are given in random order and you can make sure that all edges of the cuboid are parallel to coordinate axes; the second line contains 4 integers X,Y,Z,R representing the central point of the ball and its radius. All integers given are non-negative and will be less than 100000.

样例输入:

2
0 0 0 0 0 1 0 1 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 1
2 2 2 2
0 0 0 0 0 1 0 1 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 1
2 2 2 1

样例输出:

Yes
No

判断一个长方体和一个球是否相交

 

找到一个离求最近的点,然后算这个点到这个球圆心的距离,就能判断出是否相交

 

代码:

#include <cstdio>
 #include <cmath>
 #include <iostream>
 
 using namespace std;
 
 typedef struct point
 {
     double x,y,z;
 }point;
 
 point a[10];
 
 double judge(double x,double y,double z,point q)
 {
     double sum = (x-q.x)*(x-q.x) + (y-q.y)*(y-q.y) +(z-q.z)*(z-q.z);
     sum = sqrt(sum);
     return sum;
 }
 
 int main()
 {
     int T;
     scanf("%d",&T);
     while(T--)
     {
         int i = 0;
         for(i = 0; i < 8; i++)
             scanf("%lf%lf%lf",&a[i].x,&a[i].y,&a[i].z);
         point b;
         double r1;
         scanf("%lf%lf%lf%lf",&b.x,&b.y,&b.z,&r1);
         double flag = 0;
         double kk;
         double xmin,xmax,ymin,ymax,zmin,zmax;
         double x,y,z;
 
         xmin = a[0].x;xmax = a[0].x;
         ymin = a[0].y;ymax = a[0].y;
         zmin = a[0].z;zmax = a[0].z;
 
         for(i = 1; i < 8; i++)
         {
             if(a[i].x < xmin) xmin = a[i].x;
             if(a[i].x > xmax) xmax = a[i].x;
             if(a[i].y < ymin) ymin = a[i].y;
             if(a[i].y > ymax) ymax = a[i].y;
             if(a[i].z < zmin) zmin = a[i].z;
             if(a[i].z > zmax) zmax = a[i].z;
 
         }
         if(b.x < xmin) x = xmin;
         else if(b.x > xmax) x= xmax;
         else x = b.x;
 
         if(b.y < ymin) y = ymin;
         else if(b.y > ymax) y= ymax;
         else y = b.y;
 
         if(b.z < zmin) z = zmin;
         else if(b.z > zmax) z= zmax;
         else z = b.z;
 
     if( judge(x,y,z,b) > r1)
         printf("No\n");
     else
         printf("Yes\n");
     }
     return 0;
 }

 

解题转自:http://www.cnblogs.com/yyroom/archive/2013/04/10/3011613.html


  1. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience