1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
|
package editor;
import java.lang.Math;
import java.util.ArrayList;
public class PointInPolyhedron
{
/**
* Class Variables declaration
*/
ArrayList<Polygon> Polyhedron = new ArrayList<Polygon>();
Point3D TestPoint = new Point3D();
//**********************************************************************************************
/**
* The constructor of the class
*/
public PointInPolyhedron(ArrayList<Polygon> PolyhedronPolygons, Point3D point_to_test)
{
Polyhedron = PolyhedronPolygons;
TestPoint = point_to_test;
}
//***********************General methods***************************************
/**
* Set and get methods
*/
public ArrayList<Polygon> getPolyhedronPolygons()
{
return Polyhedron;
}
public Point3D getTestPoint()
{
return TestPoint;
}
public void setPolyhedronPolygons(ArrayList<Polygon> PolyhedronPolygons)
{
Polyhedron = PolyhedronPolygons;
}
public void setTestPoint(Point3D point)
{
TestPoint = point;
}
//****************** Geometric method********************************
/**
* This method checks if the test point is in the bounding box of the polyhedron
*/
//**********************************************************************************************
public boolean isItInTheBoundingBox()
{
double minX=0, minY=0, minZ=0;
double maxX=0, maxY=0, maxZ=0;
for(int i=0; i<Polyhedron.size();i++)
{
for(int j=0;j<Polyhedron.get(i).getPointsNumber();j++)
{
minX = (Polyhedron.get(i).getPointAt(j).getX()<minX)?Polyhedron.get(i).getPointAt(j).getX():minX;
minY = (Polyhedron.get(i).getPointAt(j).getY()<minY)?Polyhedron.get(i).getPointAt(j).getY():minY;
minZ = (Polyhedron.get(i).getPointAt(j).getZ()<minZ)?Polyhedron.get(i).getPointAt(j).getZ():minZ;
maxX = (Polyhedron.get(i).getPointAt(j).getX()>maxX)?Polyhedron.get(i).getPointAt(j).getX():maxX;
maxY = (Polyhedron.get(i).getPointAt(j).getY()>maxY)?Polyhedron.get(i).getPointAt(j).getY():maxY;
maxZ = (Polyhedron.get(i).getPointAt(j).getZ()>maxZ)?Polyhedron.get(i).getPointAt(j).getZ():maxZ;
}
}
return (TestPoint.getX()>=minX && TestPoint.getY()>=minY && TestPoint.getZ()>=minZ &&
TestPoint.getX()<=maxX && TestPoint.getY()<=maxY && TestPoint.getZ()<=maxZ)? true:false;
}
//**********************************************************************************************
/**
* This method calculates a vector between 2 points
*/
public Vect makeVect(Point3D point1, Point3D point2)
{
return new Vect(
point2.getX() - point1.getX(),
point2.getY() - point1.getY(),
point2.getZ() - point1.getZ());
}
/**
* This method calculates the product vector of two vectors
*/
public Vect productVect(Vect v1, Vect v2)
{
Vect resultVect = new Vect();
resultVect.setX(v1.getY()*v2.getZ() - v1.getZ()*v2.getY());// Y1*Z2-Z1*Y2
resultVect.setY(v1.getZ()*v2.getX() - v1.getX()*v2.getZ());// Z1*X2-X1*Z2
resultVect.setZ(v1.getX()*v2.getY() - v1.getY()*v2.getX());// X1*Y2-Y1*X2
return resultVect;
}
//**********************************************************************************************
/**
* This method calculates the normal vector of a given polygon
*/
public Vect NormalVector(Polygon polygon)
{
// The first vector corresponding to points P1 and P2
Vect v1 = new Vect();
// // The second vector corresponding to points P1 and P3
Vect v2 = new Vect();
// The result vector
Vect resultVect = new Vect();
// The first vector corresponding to the first and the second points of the surface
v1 = makeVect(polygon.getPointAt(1),polygon.getPointAt(0)); // X1, Y1, Z1
//The second vector corresponding to the second and the third points of the surface
v2 = makeVect(polygon.getPointAt(2),polygon.getPointAt(0));// X2, Y2, Z2
// We calculate the vector V : vector product of v1 and v2
resultVect = productVect(v1, v2);
// We normalize the vector V
double var = Math.sqrt(Math.pow(resultVect.getX(), 2)+
Math.pow(resultVect.getY(), 2)+
Math.pow(resultVect.getZ(), 2));
if(var!=0)
{
resultVect.setX(resultVect.getX()/var);//v[0]=-v[0]/var;
resultVect.setY(resultVect.getY()/var);//v[1]=-v[1]/var;
resultVect.setZ(resultVect.getZ()/var);//v[2]=-v[2]/var;
}
return resultVect;
}
//**********************************************************************************************
/**
* This method calculates the scalar product of two vectors
*/
public double scalarProduct(Vect v1, Vect v2)
{
return v1.getX()*v2.getX()+
v1.getY()*v2.getY()+
v1.getZ()*v2.getZ();
}
//**********************************************************************************************
/**
* This method checks if the test point is inside the polyhedron
*/
public boolean pointInPolyhedron()
{
if(this.isItInTheBoundingBox()==false)
{
System.out.println("the test point is not in the bounding box of the polyhedron");
return false;
}
else
{
double signNum0 = 0; //0: if num = 0, 1 if num>0, -1 if num<0
/**
* Test the first polygon
*/
//Calculate the normal vector of the polygon
Vect normal0 = NormalVector(Polyhedron.get(0));
//System.out.println("****"+normal0.getX()+","+normal0.getY()+","+normal0.getZ()+"****");
//Calculate a vector between the test point and a point of the polygon (the first point)
Vect tmp0 = makeVect(TestPoint, Polyhedron.get(0).getPointAt(0));
//Calculate the scalar product between these 2 vectors.
double scalar0 = scalarProduct(normal0, tmp0);
signNum0 = Math.signum(scalar0);
/**
* Test the other polygons
*/
for(int i=1; i<Polyhedron.size();i++)
{
//Calculate the normal vector of the polygon
Vect normal1 = NormalVector(Polyhedron.get(i));
//System.out.println("****"+normal1.getX()+","+normal1.getY()+","+normal1.getZ()+"****");
//Calculate a vector between the test point and a point of the polygon (the first vertex of the polygon)
Vect tmp1 = makeVect(TestPoint, Polyhedron.get(i).getPointAt(0));
//Calculate the scalar product between these 2 vectors.
double scalar1 = scalarProduct(normal1, tmp1);
double signNum1 = Math.signum(scalar1);
System.out.println("------>"+scalar1);
if(signNum1 != signNum0 && signNum1 != 0)
{
return false;
}
}
return true;
}
}
//**********************************************************************************************
//**********************************************************************************************
//**********************************************************************************************
public static void main(String args[])
{
Point3D p1 = new Point3D(100,100,100);
Point3D p2 = new Point3D(0,100,100);
Point3D p3 = new Point3D(0,0,100);
Point3D p4 = new Point3D(100,0,100);
Point3D p5 = new Point3D(100,0,0);
Point3D p6 = new Point3D(100,100,0);
Point3D p7 = new Point3D(0,100,0);
Point3D p8 = new Point3D(0,0,0);
Point3D p9 = new Point3D(50,150,100);
Point3D p10 = new Point3D(50,150,0);
/*Point3D p1 = new Point3D(150,0,150);
Point3D p2 = new Point3D(150,0,50);
Point3D p3 = new Point3D(50,0,50);
Point3D p4 = new Point3D(50,0,150);
Point3D p5 = new Point3D(100,100,100);*/
Point3D testPoint = new Point3D(50,150,50);
ArrayList<Polygon> PolygonList = new ArrayList<Polygon>();
Polygon pl1 = new Polygon();
Polygon pl2 = new Polygon();
Polygon pl3 = new Polygon();
Polygon pl4 = new Polygon();
Polygon pl5 = new Polygon();
Polygon pl6 = new Polygon();
Polygon pl7 = new Polygon();
Polygon pl8 = new Polygon();
Polygon pl9 = new Polygon();
Polygon pl10 = new Polygon();
//Facades
pl1.addPoint(p1);pl1.addPoint(p2);pl1.addPoint(p3);pl1.addPoint(p4);
pl2.addPoint(p6);pl2.addPoint(p1);pl2.addPoint(p4);pl2.addPoint(p5);
pl3.addPoint(p7);pl3.addPoint(p6);pl3.addPoint(p5);pl3.addPoint(p8);
pl4.addPoint(p2);pl4.addPoint(p7);pl4.addPoint(p8);pl4.addPoint(p3);
pl5.addPoint(p4);pl5.addPoint(p3);pl5.addPoint(p8);pl5.addPoint(p5);
pl6.addPoint(p6);pl6.addPoint(p7);pl6.addPoint(p2);pl6.addPoint(p1);
//Roof
pl7.addPoint(p9);pl7.addPoint(p2);pl7.addPoint(p1);
pl8.addPoint(p10);pl8.addPoint(p9);pl8.addPoint(p1);pl8.addPoint(p6);
pl9.addPoint(p10);pl9.addPoint(p6);pl9.addPoint(p7);
pl10.addPoint(p9);pl10.addPoint(p10);pl10.addPoint(p7);pl10.addPoint(p2);
/*pl1.addPoint(p1);pl1.addPoint(p2);pl1.addPoint(p3);pl1.addPoint(p4);
pl2.addPoint(p1);pl2.addPoint(p5);pl2.addPoint(p4);
pl3.addPoint(p2);pl3.addPoint(p5);pl3.addPoint(p1);
pl4.addPoint(p3);pl4.addPoint(p5);pl4.addPoint(p2);
pl5.addPoint(p4);pl5.addPoint(p5);pl5.addPoint(p3);*/
PolygonList.add(pl1);
PolygonList.add(pl2);
PolygonList.add(pl3);
PolygonList.add(pl4);
PolygonList.add(pl5);
//PolygonList.add(pl6);
PolygonList.add(pl7);
PolygonList.add(pl8);
PolygonList.add(pl9);
PolygonList.add(pl10);
PointInPolyhedron test = new PointInPolyhedron(PolygonList, testPoint);
System.out.println(test.pointInPolyhedron());
}
//**********************************************************************************************
} |
Question sur la géométrie
Envoyé par Frifron
. Mais, l'inconvénient majeur de cet algorithme et que les vertex des toutes les faces du polyèdere doivent être ordonnées de la même manière (sens des aiguilles de la montre ou le sens inverse). Sinon, les vecteurs normals n'auront pas le même sens (quelques uns seront orientés vers l'intérieur du polyèdre et les autres seront orientés vers l'extèrieur).
Répondre avec citation
Partager