Menu
▾
▴
[reprap-commits] SF.net SVN: reprap:[3960] trunk/old_files/miscellaneous/CarapaceCopier/src/ org/reprap/scanning
|
From: <ree...@us...> - 2010-12-22 02:08:26
|
Revision: 3960
http://reprap.svn.sourceforge.net/reprap/?rev=3960&view=rev
Author: reece-arnott
Date: 2010-12-22 02:08:19 +0000 (Wed, 22 Dec 2010)
Log Message:
-----------
CarapaceCopier: 2D Dewall triangulation tested and is now working. Still need to add into BoundingPolygon etc.
Modified Paths:
--------------
trunk/old_files/miscellaneous/CarapaceCopier/src/org/reprap/scanning/DataStructures/OrderedListLineSegment2dIndices.java
trunk/old_files/miscellaneous/CarapaceCopier/src/org/reprap/scanning/DataStructures/OrderedListTriangule3D.java
trunk/old_files/miscellaneous/CarapaceCopier/src/org/reprap/scanning/DataStructures/QuickSortPoints2D.java
trunk/old_files/miscellaneous/CarapaceCopier/src/org/reprap/scanning/DataStructures/Uniform2DGrid.java
trunk/old_files/miscellaneous/CarapaceCopier/src/org/reprap/scanning/DataStructures/Uniform3DGrid.java
trunk/old_files/miscellaneous/CarapaceCopier/src/org/reprap/scanning/FeatureExtraction/DeWall2D.java
trunk/old_files/miscellaneous/CarapaceCopier/src/org/reprap/scanning/FeatureExtraction/DeWall3D.java
trunk/old_files/miscellaneous/CarapaceCopier/src/org/reprap/scanning/GUI/Testing.java
trunk/old_files/miscellaneous/CarapaceCopier/src/org/reprap/scanning/Geometry/LineSegment2D.java
trunk/old_files/miscellaneous/CarapaceCopier/src/org/reprap/scanning/Geometry/LineSegment2DIndices.java
trunk/old_files/miscellaneous/CarapaceCopier/src/org/reprap/scanning/Geometry/Triangle2D.java
Modified: trunk/old_files/miscellaneous/CarapaceCopier/src/org/reprap/scanning/DataStructures/OrderedListLineSegment2dIndices.java
===================================================================
--- trunk/old_files/miscellaneous/CarapaceCopier/src/org/reprap/scanning/DataStructures/OrderedListLineSegment2dIndices.java 2010-12-21 22:29:36 UTC (rev 3959)
+++ trunk/old_files/miscellaneous/CarapaceCopier/src/org/reprap/scanning/DataStructures/OrderedListLineSegment2dIndices.java 2010-12-22 02:08:19 UTC (rev 3960)
@@ -24,7 +24,7 @@
*
* Reece Arnott ree...@gm...
*
-* Last modified by Reece Arnott 21st December 2010
+* Last modified by Reece Arnott 22nd December 2010
*
* This class stores an array of line segments which can be accessed in an ordered way (ordered by a hashvalue)
* This was a copy of the OrderedListTriangle3D as at 21st Decemeber with the only changes a search and replace from Triangle3D to LineSegment2DIndices
@@ -155,15 +155,8 @@
}
- public LineSegment2DIndices GetTetrahedron(LineSegment2DIndices candidate){
- LineSegment2DIndices returnvalue=candidate.clone();
- candidate.SetHash(n);
- int index=Find(candidate.hashvalue);
- if (index!=-1) returnvalue=list[index].clone();
- return returnvalue;
- }
+
-
public LineSegment2DIndices[] GetFullUnorderedList(){
return list;
}
@@ -203,16 +196,18 @@
return returnvalue;
}
+ // Note that this doesn't sanity check to see that the index is in range.
private void DeleteEntry(int index, boolean changeinsertionorderarray){
// First go through the insertionorder array and take out the entry if requested
if (changeinsertionorderarray){
int numberofmatches=0;
- for (int i=0;i<insertionorder.length;i++)if (insertionorder[i]==index) numberofmatches++;
+ long hashtomatch=list[index].hashvalue;
+ for (int i=0;i<insertionorder.length;i++)if (insertionorder[i]==hashtomatch) numberofmatches++;
if (numberofmatches!=0){
long[] newinsertionarray=new long[insertionorder.length-numberofmatches];
int j=0;
for (int i=0;i<insertionorder.length;i++){
- if (insertionorder[i]!=index){
+ if (insertionorder[i]!=hashtomatch){
newinsertionarray[j]=insertionorder[i];
j++;
} // end if
@@ -229,4 +224,26 @@
}
list=returnvalue.clone();
}
+
+ public void PrintFIFO(){
+ if (insertionorder.length!=0)
+ {
+ int i=0;
+ int index=-1;
+ while (i<insertionorder.length) {
+ index=Exists(insertionorder[i]);
+ if (index!=-1){
+ // There is a valid hash in the array
+ LineSegment2DIndices f=list[index].clone();
+ System.out.print(i+" "+insertionorder[i]+": ");
+ f.print();
+ } // end if
+ else System.out.print(i+" "+insertionorder[i]+" ");
+ if (nextFIFO==i) System.out.print(" <=====");
+ System.out.println();
+ i++;
+ } // end while
+ } // end if
+ }
+
} // end of class
Modified: trunk/old_files/miscellaneous/CarapaceCopier/src/org/reprap/scanning/DataStructures/OrderedListTriangule3D.java
===================================================================
--- trunk/old_files/miscellaneous/CarapaceCopier/src/org/reprap/scanning/DataStructures/OrderedListTriangule3D.java 2010-12-21 22:29:36 UTC (rev 3959)
+++ trunk/old_files/miscellaneous/CarapaceCopier/src/org/reprap/scanning/DataStructures/OrderedListTriangule3D.java 2010-12-22 02:08:19 UTC (rev 3960)
@@ -24,7 +24,7 @@
*
* Reece Arnott ree...@gm...
*
-* Last modified by Reece Arnott 21st December 2010
+* Last modified by Reece Arnott 22nd December 2010
*
* This class stores an array of triangluar faces which can be accessed in an ordered way (ordered by a hashvalue)
* A triangular face is 3 vertices a,b,c. These are stored as simple indexes to a Point3d array.
@@ -32,6 +32,7 @@
* TODO - This class may benefit from using unconstrained ArrayList rather than fixed length array.
*
***********************************************************************************/
+
import org.reprap.scanning.Geometry.Triangle3D;
public class OrderedListTriangule3D {
@@ -202,16 +203,18 @@
return returnvalue;
}
+// Note that this doesn't sanity check to see that the index is in range.
private void DeleteEntry(int index, boolean changeinsertionorderarray){
// First go through the insertionorder array and take out the entry if requested
if (changeinsertionorderarray){
int numberofmatches=0;
- for (int i=0;i<insertionorder.length;i++)if (insertionorder[i]==index) numberofmatches++;
+ long hashtomatch=list[index].hashvalue;
+ for (int i=0;i<insertionorder.length;i++)if (insertionorder[i]==hashtomatch) numberofmatches++;
if (numberofmatches!=0){
long[] newinsertionarray=new long[insertionorder.length-numberofmatches];
int j=0;
for (int i=0;i<insertionorder.length;i++){
- if (insertionorder[i]!=index){
+ if (insertionorder[i]!=hashtomatch){
newinsertionarray[j]=insertionorder[i];
j++;
} // end if
Modified: trunk/old_files/miscellaneous/CarapaceCopier/src/org/reprap/scanning/DataStructures/QuickSortPoints2D.java
===================================================================
--- trunk/old_files/miscellaneous/CarapaceCopier/src/org/reprap/scanning/DataStructures/QuickSortPoints2D.java 2010-12-21 22:29:36 UTC (rev 3959)
+++ trunk/old_files/miscellaneous/CarapaceCopier/src/org/reprap/scanning/DataStructures/QuickSortPoints2D.java 2010-12-22 02:08:19 UTC (rev 3960)
@@ -41,14 +41,14 @@
public int[] Sortby(char coordinate,int[] subsetofindexes){
- boolean Y=((coordinate==new String("y").charAt(0)) || (coordinate==new String("Y").charAt(0)));
- return Sort(subsetofindexes,Y);
+ boolean X=((coordinate==new String("x").charAt(0)) || (coordinate==new String("X").charAt(0)));
+ return Sort(subsetofindexes,X);
}
public int[] SortbyX(int[] subsetofindexes){
- return Sort(subsetofindexes,false);
+ return Sort(subsetofindexes,true);
}
public int[] SortbyY(int[] subsetofindexes){
- return Sort(subsetofindexes,true);
+ return Sort(subsetofindexes,false);
}
public int[] SortbyX(){
indexarray=new int[pointsarray.length];
Modified: trunk/old_files/miscellaneous/CarapaceCopier/src/org/reprap/scanning/DataStructures/Uniform2DGrid.java
===================================================================
--- trunk/old_files/miscellaneous/CarapaceCopier/src/org/reprap/scanning/DataStructures/Uniform2DGrid.java 2010-12-21 22:29:36 UTC (rev 3959)
+++ trunk/old_files/miscellaneous/CarapaceCopier/src/org/reprap/scanning/DataStructures/Uniform2DGrid.java 2010-12-22 02:08:19 UTC (rev 3960)
@@ -34,8 +34,6 @@
import org.reprap.scanning.Geometry.Point2d;
import org.reprap.scanning.Geometry.AxisAlignedBoundingBox;
-import org.reprap.scanning.Geometry.Point3d;
-import org.reprap.scanning.Geometry.Triangle3D;
public class Uniform2DGrid{
public Uniform2DGridCell[][] Grid;
@@ -63,7 +61,7 @@
Grid[0][0].pointslist=new int[p.length];
marked=new boolean[1][1];
marked[0][0]=(Grid[0][0].GetLength()==0);
- for (int i=0;i<p.length;i++) Grid[0][0].pointslist[i]=i;
+ Grid[0][0].pointslist=subsetindexes.clone();
}
else {
@@ -75,10 +73,10 @@
boundary.miny=p[subsetindexes[0]].y;
boundary.minz=0;
boundary.maxx=p[subsetindexes[0]].x;
- boundary.maxy=p[subsetindexes[i]].y;
+ boundary.maxy=p[subsetindexes[0]].y;
boundary.maxz=0;
}
- else boundary.Expand2DBoundingBox(p[i]);if (p[i].x<boundary.minx) boundary.minx=p[i].x;
+ else boundary.Expand2DBoundingBox(p[subsetindexes[i]]);
}
// Now divide up the space into 2d cells
@@ -103,7 +101,7 @@
for (int i=0;i<subsetindexes.length;i++){
int x=(int)((p[subsetindexes[i]].x-boundary.minx)/side);
int y=(int)((p[subsetindexes[i]].y-boundary.miny)/side);
- Grid[x][y].Add(i);
+ Grid[x][y].Add(subsetindexes[i]);
}
// Create and set the marked array
marked=new boolean[arraysizex][arraysizey];
Modified: trunk/old_files/miscellaneous/CarapaceCopier/src/org/reprap/scanning/DataStructures/Uniform3DGrid.java
===================================================================
--- trunk/old_files/miscellaneous/CarapaceCopier/src/org/reprap/scanning/DataStructures/Uniform3DGrid.java 2010-12-21 22:29:36 UTC (rev 3959)
+++ trunk/old_files/miscellaneous/CarapaceCopier/src/org/reprap/scanning/DataStructures/Uniform3DGrid.java 2010-12-22 02:08:19 UTC (rev 3960)
@@ -66,14 +66,7 @@
boundary.maxy=p[subsetindexes[0]].y;
boundary.maxz=p[subsetindexes[0]].z;
}
- else {
- if (p[subsetindexes[i]].x<boundary.minx) boundary.minx=p[subsetindexes[i]].x;
- if (p[subsetindexes[i]].y<boundary.miny) boundary.miny=p[subsetindexes[i]].y;
- if (p[subsetindexes[i]].z<boundary.minz) boundary.minz=p[subsetindexes[i]].z;
- if (p[subsetindexes[i]].x>boundary.maxx) boundary.maxx=p[subsetindexes[i]].x;
- if (p[subsetindexes[i]].y>boundary.maxy) boundary.maxy=p[subsetindexes[i]].y;
- if (p[subsetindexes[i]].z>boundary.maxz) boundary.maxz=p[subsetindexes[i]].z;
- }
+ else boundary.Expand3DBoundingBox(p[subsetindexes[i]]);
}
// Now divide up the space into 3d cells
double volume=(boundary.maxx-boundary.minx)*(boundary.maxy-boundary.miny)*(boundary.maxz-boundary.minz);
Modified: trunk/old_files/miscellaneous/CarapaceCopier/src/org/reprap/scanning/FeatureExtraction/DeWall2D.java
===================================================================
--- trunk/old_files/miscellaneous/CarapaceCopier/src/org/reprap/scanning/FeatureExtraction/DeWall2D.java 2010-12-21 22:29:36 UTC (rev 3959)
+++ trunk/old_files/miscellaneous/CarapaceCopier/src/org/reprap/scanning/FeatureExtraction/DeWall2D.java 2010-12-22 02:08:19 UTC (rev 3960)
@@ -25,7 +25,7 @@
*
* Reece Arnott ree...@gm...
*
-* Last modified by Reece Arnott 21st December 2010
+* Last modified by Reece Arnott 22nd December 2010
*
* This was originally a copy of the DeWall3D class as at 21st Decemeber 2010 and is changed to find 2d line segments and triangles rather than 3d triangles and tetrahedrons
*
@@ -64,20 +64,17 @@
import org.reprap.scanning.DataStructures.OrderedListLineSegment2dIndices;
import org.reprap.scanning.Geometry.AxisAlignedBoundingBox;
import org.reprap.scanning.Geometry.LineSegment2D;
-import org.reprap.scanning.Geometry.Plane;
import org.reprap.scanning.Geometry.Point2d;
-import org.reprap.scanning.Geometry.Tetrahedron;
import org.reprap.scanning.Geometry.Triangle2D;
import org.reprap.scanning.Geometry.LineSegment2DIndices;
-import org.reprap.scanning.Geometry.Triangle3D;
public class DeWall2D {
public enum planeslice {x,y};
public enum searching {oneradius,tworadii,currentminimumradius,all,exit}; // just for readability in the MakeSimplex method
// These just for testing
+ public static boolean printdebugging=false;
public static boolean printverbose=false;
public static boolean print=false;
- public static boolean test=false;
public int maxrecurse=21; // Once the maximum recursion level is reached the recursion stops and the algorithm reverts to a sequential form by having the Categorise method always returning 0. Given that is assumed a maximum of 2^21 points will be used (due to the way the TriangularFace hashvalue is calculated) it doesn't make sense to set a recursion level greater than 21.
public int minpoints=100; // If the number of points to be processed by DeWall is less than this, recursion stops by having the recursionlevel set to maxrecurse
@@ -130,7 +127,7 @@
}
if (printverbose){
for (int i=0;i<FinalTriangles.length;i++){
- System.out.print(i);
+ System.out.print(i+" ");
FinalTriangles[i].print();
System.out.println();
} // end for
@@ -153,15 +150,17 @@
private void dewall(int[] P, OrderedListLineSegment2dIndices AFL, planeslice currentplaneslice,JProgressBar bar, long lastprogressupdate,int recursionlevel){
recursionlevel++;
if (P.length<minpoints) recursionlevel=maxrecurse;
+
//Initialise the arrays we'll be using to be empty and calculate a splitting plane for the point array P
OrderedListLineSegment2dIndices AFLalpha=new OrderedListLineSegment2dIndices(PointsList.length);
OrderedListLineSegment2dIndices AFL1=new OrderedListLineSegment2dIndices(PointsList.length);
OrderedListLineSegment2dIndices AFL2=new OrderedListLineSegment2dIndices(PointsList.length);
+
// Set up the Uniform Grid
Uniform2DGrid UG=new Uniform2DGrid(PointsList, P, (int)(UGScale*P.length));
+
// Sort the list based on the direction of the currentplaneslice
P=qsort.Sortby(currentplaneslice.toString().charAt(0),P);
-
// Partition the point array P into two other point arrays based on the splitting plane
// Note that in the case where there is an odd number of elements the right hand array (P2) will be one larger than the left (P1)
// Because of the way the rest of this works there shouldn't be only a couple of elements in the array so don't need to test for midpoint-1<0
@@ -178,23 +177,36 @@
if (i<midpoint) P1[i]=P[i];
else P2[i-midpoint]=P[i];
} // end for
+ if (printdebugging) {System.out.println("Recursion level "+recursionlevel+". Splitting points array of length "+P.length+" into arrays of length "+P1.length+" and "+P2.length);
+ System.out.println("Split plane "+currentplaneslice.toString()+" "+splitplanecoordinate);
+ System.out.println("P1");
+ for (int i=0;i<P1.length;i++) {System.out.print(i+" "+P1[i]+" ");PointsList[P1[i]].print();System.out.println();}
+ System.out.println("P2");
+ for (int i=0;i<P2.length;i++) {System.out.print(i+" "+P2[i]+" ");PointsList[P2[i]].print();System.out.println();}
+ System.out.println("P");
+ for (int i=0;i<P.length;i++) {System.out.print(i+" "+P[i]+" ");PointsList[P[i]].print();System.out.println();}
+ }
// Wall Construction
- if ((AFL.getLength()==0) && (recursionlevel==1)){
+ if (AFL.getLength()==0){
// Make the first simplex using as one point the closest point to the midpoint split, and as another a point on the other side.
Triangle2D tri=MakeFirstSimplex(P);
if (!tri.isNull()) {
LineSegment2DIndices[] temp=tri.GetFaces(PointsList);
for (int i=0;i<temp.length;i++) {
- if (i==0){ // Reverse the first line segment
- int[] v=temp[i].GetFace();
- LineSegment2DIndices t=new LineSegment2DIndices(v[1],v[0],PointsList);
- int[] oppositevertices=tri.GetVertices();
- t.CalculateNormalAwayFromPoint(PointsList,PointsList[oppositevertices[i]]);
- t.SetHash(PointsList.length);
- AFL.InsertIfNotExist(t);
- }
- else AFL.InsertIfNotExist(temp[i]);
+ temp[i].SetHash(PointsList.length);
+ //if (i==0){ // Reverse the first line segment normal
+ //temp[0].FlipNormal(PointsList);
+ //int[] v=temp[0].GetFace();
+ //LineSegment2DIndices t=new LineSegment2DIndices(v[1],v[0],PointsList);
+ //int[] oppositevertices=tri.GetVertices();
+ //t.CalculateNormalAwayFromPoint(PointsList,PointsList[oppositevertices[0]]);
+ //t.SetHash(PointsList.length);
+ //AFL.InsertIfNotExist(t);
+ // AFL.InsertIfNotExist(temp[0]);
+ //}
+ //else
+ AFL.InsertIfNotExist(temp[i]);
}
FinalTriangles=new Triangle2D[1];
FinalTriangles[0]=tri.clone();
@@ -205,11 +217,13 @@
}
}
+
// Split the Active Face List into the correct sub lists
LineSegment2DIndices f=AFL.GetFirstFIFO();
+
while (!f.IsNull()){
- int category=Categorise(f,splitplanecoordinate,currentplaneslice,recursionlevel);
- switch(category){
+ int category=Categorise(f,splitplanecoordinate,currentplaneslice,recursionlevel);
+ switch(category){
case 0:AFLalpha.InsertIfNotExist(f);break;
case 1:AFL1.InsertIfNotExist(f);break;
case 2:AFL2.InsertIfNotExist(f);break;
@@ -218,22 +232,22 @@
}
-
// Main loop
f=AFLalpha.ExtractFIFO();
while (!f.IsNull()){
-
Triangle2D t=new Triangle2D();
- t=MakeSimplex(f,UG);
+ t=MakeSimplex(f,UG);
// Test to make sure the tetrahedron constructed is a valid one
boolean valid=!t.isNull();
if (valid)
{
FinalTriangles=Insert(FinalTriangles,t); // Note that this will mean we end up with a list of TriangularFaces each attached to a single tetrahedron only.
LineSegment2DIndices[] fdash=t.GetFaces(PointsList);
- for (int i=0;i<fdash.length;i++){
+ for (int i=0;i<fdash.length;i++){
if (!fdash[i].LineSegmentEqual(f)){
// Update the correct Active Face list
+ fdash[i].SetHash(PointsList.length);
+
int category=Categorise(fdash[i],splitplanecoordinate,currentplaneslice,recursionlevel);
switch(category){
case 0:AFLalpha=Update(AFLalpha,fdash[i]);break;
@@ -244,7 +258,6 @@
} // end for
// DecimalFormat format = new DecimalFormat("0.000000");
// System.out.println(" "+format.format(splitplanecoordinate));
-
} // end if valid
// Once every second update the progress bar and tidy up the lists
if ((System.currentTimeMillis()-lastprogressupdate)>1000) {
@@ -254,44 +267,44 @@
bar.setValue(value);
lastprogressupdate=System.currentTimeMillis();
}
+ if (printdebugging) {
+ System.out.println("AFLalpha "+AFLalpha.getLength());AFLalpha.PrintFIFO();
+ //System.out.println("AFL1 "+AFL1.getLength());//AFL1.PrintFIFO();
+ //System.out.println("AFL2 "+AFL2.getLength());//AFL2.PrintFIFO();
+ }
f=AFLalpha.ExtractFIFO();
+
if (CyclicTriangle2DCreation){
+ if (print) System.out.println("CTC error");
f=new LineSegment2DIndices(); // exit while loop
}
}//end while
-
-// recurse and change the orientation of the plane slice
+ // recurse and change the orientation of the plane slice
planeslice nextplaneslice=planeslice.values()[(currentplaneslice.ordinal()+1)%planeslice.values().length];
// Only recurse if need to i.e. there is at least one face in the Active face list that needs processed and a cyclic tetrahedron creation hasn't been flagged.
if ((!CyclicTriangle2DCreation) && (AFL1.getLength()!=0)) dewall(P1,AFL1,nextplaneslice,bar, lastprogressupdate,recursionlevel);
if ((!CyclicTriangle2DCreation) && (AFL2.getLength()!=0)) dewall(P2,AFL2,nextplaneslice,bar,lastprogressupdate,recursionlevel);
} // end of method dewall (recursive)
-// returns 0 if the slice-plane intersects the face and is to go into AFLalpha
- // returns 1 if the plane is on one side of the face (to go into AFL1)
- // returns 2 if the plane is on the other side of the face (to go into AFL2)
+// returns 0 if the slice-line intersects the line segment and is to go into AFLalpha
+ // returns 1 if the line is on one side of the face (to go into AFL1)
+ // returns 2 if the line is on the other side of the face (to go into AFL2)
// If the maximum recursion level has been reached it will also return 0 which essentially turns it into an iterative approach
private int Categorise(LineSegment2DIndices f,double coordinate,planeslice currentplaneslice,int recursionlevel){
if (recursionlevel>=maxrecurse) return 0;
else{
- int[] indexes=f.GetFace();
- double a,b,c;
- a=Coordinate(currentplaneslice,indexes[0]);
- b=Coordinate(currentplaneslice,indexes[1]);
- c=Coordinate(currentplaneslice,indexes[2]);
-
- boolean v1,v2,v3;
- v1=(a<coordinate);
- v2=(b<coordinate);
+ int[] indexes=f.GetStartAndEndPointIndices();
+ double start,end;
+ start=Coordinate(currentplaneslice,indexes[0]);
+ end=Coordinate(currentplaneslice,indexes[1]);
+ boolean v1,v2;
+ v1=(start<coordinate);
+ v2=(end<coordinate);
if (v1!=v2) return 0;
else{
- v3=(c<coordinate);
- if (v1!=v3) {return 0;}
- else {
- if (v1) return 1;
+ if (v1) return 1;
else return 2;
- }
} // end else
}
} // end Categorise
@@ -311,7 +324,12 @@
Triangle2D[] returnvalue=new Triangle2D[original.length+1];
for (int i=0;i<original.length;i++){
returnvalue[i]=original[i].clone();
- if (original[i].isEquivalent(addition)) CyclicTriangle2DCreation=true;
+ if (original[i].isEquivalent(addition)) {
+ CyclicTriangle2DCreation=true;
+ System.out.print("CTC error adding triangle ");
+ addition.print();
+ System.out.println();
+ }
}
returnvalue[original.length]=addition.clone();
return returnvalue;
@@ -322,7 +340,7 @@
private OrderedListLineSegment2dIndices Update(OrderedListLineSegment2dIndices AFL, LineSegment2DIndices f){
boolean deleted=AFL.DeleteIfExist(f);
if (!deleted) AFL.InsertIfNotExist(f);
- int[] indexes=f.GetFace();
+ int[] indexes=f.GetStartAndEndPointIndices();
for (int i=0;i<indexes.length;i++)
if (deleted) decrement(indexes[i]);
else increment(indexes[i]);
@@ -336,9 +354,9 @@
// It is also assumed that the P index array is ordered corectly.
private Triangle2D MakeFirstSimplex(int[] P){
+
Triangle2D returnvalue=new Triangle2D();
int midpoint=(int)Math.floor((double)P.length/2);
-
int a=P[midpoint-1];
int b=-1;
double mindistancesquared=Double.MAX_VALUE;
@@ -349,6 +367,7 @@
mindistancesquared=distancesquared;
}
}
+
if (b!=-1){
// Now find the third point from the array that means the circumcircle has the smallest radius
@@ -364,7 +383,7 @@
if ((a!=P[i]) && (b!=P[i])){
// Calculate the centre of the circumcircle using this point and from this calculate the radiussquared
// Find the bisecting line of the two points we currently have
- LineSegment2DIndices AC=new LineSegment2DIndices(a,c,PointsList);
+ LineSegment2DIndices AC=new LineSegment2DIndices(a,P[i],PointsList);
bisectpoint=AC.GetPointOnLine(PointsList,0.5);
LineSegment2D ACbisectline=new LineSegment2D(bisectpoint,bisectpoint.plusEquals(AC.normal));
@@ -389,23 +408,29 @@
} // end for
// If there wasn't a 3rd point we drop the whole thing
if (c==-1) returnvalue=new Triangle2D();
- else
+ else {
// Find out whether point c is on the same side of the mid line between a and b as point b and if it isn't swap point a and b around.
- // So the normals calculated by ABxAC on all but the first face will point outwards. Note that this means that for the first face to have a normal pointing outwards a and b will have to be swapped around once the face list has been extracted.
- if (AB.InsideHalfspace(PointsList[c])!=AB.InsideHalfspace(PointsList[b])) returnvalue=new Triangle2D(new LineSegment2DIndices(b,a,PointsList),c,PointsList);
- else returnvalue=new Triangle2D(new LineSegment2DIndices(a,b,PointsList),c,PointsList);
-
+ // Point the normal away from c
+ LineSegment2DIndices line=new LineSegment2DIndices(a,b,PointsList);
+ line.SetHash(PointsList.length);
+ if (AB.InsideHalfspace(PointsList[c])!=AB.InsideHalfspace(PointsList[b])){
+ line=new LineSegment2DIndices(b,a,PointsList);
+ line.SetHash(PointsList.length);
+ }
+ returnvalue=new Triangle2D(line,c,PointsList);
+ }
} // end if b!=-1
return returnvalue;
} // end of MakeFirstSimplex method
private Triangle2D MakeSimplex(LineSegment2DIndices f,Uniform2DGrid UG){
- //TriangularFaceOf3DTriangle2Ds returnvalue;
Triangle2D returnvalue;
int currentnextpointindex=-1;
- int[] ab=f.GetFace();
+ int[] ab=f.GetStartAndEndPointIndices();
decrement(ab[0]);
decrement(ab[1]);
+ if (printverbose) System.out.println("Attempting Make Simplex with "+ab[0]+" and "+ab[1]);
+
// The centre of a circumcircle in 2d can be found as the intersection point of lines that bisect neighbouring edges at right angles
@@ -428,6 +453,7 @@
UG.resetMarked();
while (state!=searching.valueOf("exit")){
AxisAlignedBoundingBox box=new AxisAlignedBoundingBox();
+ if (printverbose) System.out.println(state.toString());
switch(state) {
case oneradius:
@@ -461,13 +487,12 @@
break;
}
- if (printverbose) System.out.println(state.toString());
for (int x=(int)box.minx;x<=(int)box.maxx;x++){
for (int y=(int)box.miny;y<=(int)box.maxy;y++){
- for (int z=(int)box.minz;z<=(int)box.maxz;z++){
if (UG.ExaminableCell(x,y)){
int i=UG.GetFirst(x,y);
+
while (i!=-1){
boolean valid=((i!=ab[0]) && (i!=ab[1])); // make sure it isn't one the vertices we already have
if (valid) valid=(!f.InsideHalfspace(PointsList[i])); // it is in the correct halfspace
@@ -530,10 +555,9 @@
else state=searching.valueOf("tworadii"); // No candidate was found so expand the search
break;
}
- } // end while
- } // end if p1,p2,p3 intersect
+ } // end while
// If there wasn't a 4th point or it is to be ignored we drop the whole thing
if ((currentnextpointindex==-1))
Modified: trunk/old_files/miscellaneous/CarapaceCopier/src/org/reprap/scanning/FeatureExtraction/DeWall3D.java
===================================================================
--- trunk/old_files/miscellaneous/CarapaceCopier/src/org/reprap/scanning/FeatureExtraction/DeWall3D.java 2010-12-21 22:29:36 UTC (rev 3959)
+++ trunk/old_files/miscellaneous/CarapaceCopier/src/org/reprap/scanning/FeatureExtraction/DeWall3D.java 2010-12-22 02:08:19 UTC (rev 3960)
@@ -25,7 +25,7 @@
*
* Reece Arnott ree...@gm...
*
-* Last modified by Reece Arnott 21st December 2010
+* Last modified by Reece Arnott 22nd December 2010
*
* Note that this breaks down if the first simplex made is made from 4 points in a plane or there are 5 points that are co-circular including the initial point so when this is called
* from the Main class the original simplex seed point is chosen as the midpoint in the array first by ordering the list based on x values, then if that doesn't work, by y and finally z.
@@ -73,7 +73,6 @@
// These just for testing
public static boolean printverbose=false;
public static boolean print=false;
- public static boolean test=false;
public int maxrecurse=21; // Once the maximum recursion level is reached the recursion stops and the algorithm reverts to a sequential form by having the Categorise method always returning 0. Given that is assumed a maximum of 2^21 points will be used (due to the way the TriangularFace hashvalue is calculated) it doesn't make sense to set a recursion level greater than 21.
public int minpoints=100; // If the number of points to be processed by DeWall is less than this, recursion stops by having the recursionlevel set to maxrecurse
@@ -175,7 +174,7 @@
} // end for
// Wall Construction
- if ((AFL.getLength()==0) && (recursionlevel==1)){
+ if (AFL.getLength()==0){
// Make the first simplex using as one point the closest point to the midpoint split, and as another a point on the other side.
Tetrahedron tetra=MakeFirstSimplex(P);
if (!tetra.isNull()) {
Modified: trunk/old_files/miscellaneous/CarapaceCopier/src/org/reprap/scanning/GUI/Testing.java
===================================================================
--- trunk/old_files/miscellaneous/CarapaceCopier/src/org/reprap/scanning/GUI/Testing.java 2010-12-21 22:29:36 UTC (rev 3959)
+++ trunk/old_files/miscellaneous/CarapaceCopier/src/org/reprap/scanning/GUI/Testing.java 2010-12-22 02:08:19 UTC (rev 3960)
@@ -23,7 +23,7 @@
*
* Reece Arnott ree...@gm...
*
- * Last modified by Reece Arnott 17th December 2010
+ * Last modified by Reece Arnott 22nd December 2010
*
* This is test code used to test the success of the combinatorial approach to point matching on different combinations/permutations of found points on a calibration sheet
*
@@ -48,10 +48,9 @@
*
*
*******************************************************************************/
-import java.io.File;
import org.reprap.scanning.Calibration.CalibrateImage;
-import org.reprap.scanning.FeatureExtraction.PointPairMatch;
+import org.reprap.scanning.FeatureExtraction.*;
import org.reprap.scanning.Geometry.*;
import org.reprap.scanning.DataStructures.*;
import javax.swing.JProgressBar;
@@ -84,6 +83,64 @@
}
public void TemporaryTestMethod(){
+
+ Point2d[] points=new Point2d[1000];
+
+for (int i=0;i<points.length;i++) {
+ points[i]=new Point2d(Math.random()*1000,Math.random()*1000);
+
+ }
+ //*/
+ //Adjust points to be image points
+ Point2d[] imagepoints=new Point2d[points.length];
+ for (int i=0;i<points.length;i++){
+ imagepoints[i]=points[i].clone();
+ //imagepoints[i].minus(new Point2d(-1,-1)); // reset origin
+ //imagepoints[i].scale(50); // scale
+ }
+
+ DeWall2D dewall=new DeWall2D(points);
+ Triangle2D[] triangles=dewall.Triangularisation(new JProgressBar(0,1), true,"x");
+
+ if ((dewall.IsCyclicTriangle2DCreationError()) || (triangles.length==0)) {System.out.println("Error in recursive x start, trying recursive y");triangles=dewall.Triangularisation(new JProgressBar(0,1), true,"y");}
+ if ((dewall.IsCyclicTriangle2DCreationError()) || (triangles.length==0)) {System.out.println("Error in recursive y start, trying sequential x");triangles=dewall.Triangularisation(new JProgressBar(0,1), false,"x");}
+ if ((dewall.IsCyclicTriangle2DCreationError()) || (triangles.length==0)) {System.out.println("Error in sequential x start, trying sequential y");triangles=dewall.Triangularisation(new JProgressBar(0,1), false,"y");}
+ if ((dewall.IsCyclicTriangle2DCreationError()) || (triangles.length==0)) {System.out.println("Pathological points?");}
+ else {
+ int size=1000;
+ PixelColour[][] colour=new PixelColour[size][size];
+ for (int i=0;i<size;i++)
+ for (int j=0;j<size;j++)
+ colour[i][j]=new PixelColour(PixelColour.StandardColours.White);
+ GraphicsFeedback graphics=new GraphicsFeedback(true);
+ graphics.ShowPixelColourArray(colour,size,size);
+ for (int i=0;i<triangles.length;i++){
+ LineSegment2D[] lines=triangles[i].GetLineSegmentFaces(imagepoints);
+ for (int j=0;j<lines.length;j++)graphics.PrintLineSegment(lines[j],new PixelColour(PixelColour.StandardColours.Blue));
+ }
+ // Points
+ for (int i=0;i<imagepoints.length;i++){
+ PixelColour col=new PixelColour(PixelColour.StandardColours.Red);
+ graphics.PrintPoint(imagepoints[i].x,imagepoints[i].y,col);
+ }
+ // Seed triangle
+ for (int i=0;i<1;i++){
+ LineSegment2D[] lines=triangles[i].GetLineSegmentFaces(imagepoints);
+ for (int j=0;j<lines.length;j++)graphics.PrintLineSegment(lines[j],new PixelColour(PixelColour.StandardColours.Red));
+ }
+ String filename="/home/cshome/r/rarnott/Desktop/images/test.jpg";
+ graphics.SaveImage(filename);
+ // Now do the sanity checks
+ boolean fail=TestIntersectionofLineSegments(triangles, points);
+ fail=fail || (TestEmptyTriangles(triangles, points));
+ fail=fail || (TestPointInclusion(triangles, points.length));
+ if (fail) for (int i=0;i<points.length;i++) System.out.println("points["+i+"]=new Point2d("+points[i].x+","+points[i].y+");");
+
+ } // end else
+ // } // end loop
+
+
+ /*
Point2d[] points=new Point2d[11];
points[0]=new Point2d(34.97812500000012,-2.723437499999962);
points[1]=new Point2d(34.67812500000012,-2.723437499999962);
@@ -97,7 +154,6 @@
points[9]=new Point2d(22.37812500000012,3.576562500000037);
points[10]=new Point2d(21.47812500000012,3.8765625000000368);
BoundingPolygon2D poly=new BoundingPolygon2D(points);
-
int size=1000;
PixelColour[][] colour=new PixelColour[size][size];
for (int i=0;i<size;i++)
@@ -402,4 +458,76 @@
Point2d imagepoint=new Point2d(H.times(newpoint));
return imagepoint;
}
+ private static boolean TestIntersectionofLineSegments(Triangle2D[] triangles, Point2d[] PointsList){
+ boolean fail=false;
+ for (int i=0;i<triangles.length;i++){
+ LineSegment2DIndices[] lines=triangles[i].GetFaces(PointsList);
+ for (int j=0;j<lines.length;j++){
+ LineSegment2D line1=lines[j].ConvertToLineSegment(PointsList);
+ int[] line1indices=lines[j].GetStartAndEndPointIndices();
+ // For each other triangle
+ for (int k=0;k<triangles.length;k++)if (i!=k) {
+ LineSegment2DIndices[] lines2=triangles[k].GetFaces(PointsList);
+
+ // For each of its lines test whether the 2 line segments intersect (aside from the end points) and aside from where one of the points is the start or end of the other line segment (in case of rounding errors
+ for (int l=0;l<lines2.length;l++){
+ if (!((lines2[l].IncludesPoint(line1indices[0])) || (lines2[l].IncludesPoint(line1indices[1])))){
+ Point2d intersect=line1.SingleIntersectionPointBetweenStartAndEndExclusive(lines2[l].ConvertToLineSegment(PointsList));
+ if (!intersect.isEqual(line1.start)){
+ fail=true;
+ System.out.println("Intersecting line segments for triangles "+j+" and "+k);
+ } // end if intersection
+ } // end if not include end points
+ }// end for l
+ } // end for k
+ } // end for j
+ } // end for i
+ return fail;
+ }
+
+ private static boolean TestEmptyTriangles(Triangle2D[] triangles,Point2d[] PointsList){
+ boolean fail=false;
+ // This is to be called once the points have been turned into triangles and is just used to test whether the result is valid
+ // which in this case means that no points are inside any triangles
+ // Its not efficient but is written so can be easily checked for bugs
+ for (int i=0;i<triangles.length;i++){
+ // Get the vertices of the triangle
+ int[] vertices=triangles[i].GetVertices();
+ Point2d[] vertexpoints=new Point2d[3];
+ for (int j=0;j<3;j++) vertexpoints[j]=PointsList[vertices[j]].clone();
+ Coordinates test=new Coordinates(3);
+ // Test all points not in the triangle vertices
+ for (int j=0;j<PointsList.length;j++){
+ if ((j!=vertices[0]) && (j!=vertices[1]) && (j!=vertices[2])){
+ test.pixel=PointsList[j].clone();
+ test.calculatebary(vertexpoints);
+ if (!test.isOutside()){
+ fail=true;
+ System.out.println("Point "+j+" is inside triangle "+i);
+ }
+ }
+ } // end for j
+ } // end for i
+ return fail;
+ } // end method
+
+ private static boolean TestPointInclusion(Triangle2D[] triangles, int numberofpoints){
+ // Test all points have been included in at least one triangle
+ // Could use boolean but using an int count in case want to expand to output how often a point is used as a vertex etc.
+ // Its not efficient but is written so can be easily checked for bugs
+
+ boolean fail=false;
+ int[] PointUsageCount=new int[numberofpoints];
+ for (int i=0;i<PointUsageCount.length;i++) PointUsageCount[i]=0;
+ for (int i=0;i<triangles.length;i++){
+ int[] vertices=triangles[i].GetVertices();
+ for (int j=0;j<vertices.length;j++) PointUsageCount[vertices[j]]++;
+ }
+ for (int i=0;i<PointUsageCount.length;i++)
+ if (PointUsageCount[i]==0) {System.out.println("Point "+i+" not included in any tetrahedron"); fail=true;}
+ return fail;
+ } // end of method
+
+
+
}
Modified: trunk/old_files/miscellaneous/CarapaceCopier/src/org/reprap/scanning/Geometry/LineSegment2D.java
===================================================================
--- trunk/old_files/miscellaneous/CarapaceCopier/src/org/reprap/scanning/Geometry/LineSegment2D.java 2010-12-21 22:29:36 UTC (rev 3959)
+++ trunk/old_files/miscellaneous/CarapaceCopier/src/org/reprap/scanning/Geometry/LineSegment2D.java 2010-12-22 02:08:19 UTC (rev 3960)
@@ -24,7 +24,7 @@
*
* Reece Arnott ree...@gm...
*
- * Last modified by Reece Arnott 21st December 2010
+ * Last modified by Reece Arnott 22nd December 2010
*
*****************************************************************************/
@@ -109,8 +109,8 @@
double denominator=((other.end.y-other.start.y)*(end.x-start.x))-((other.end.x-other.start.x)*(end.y-start.y));
if (denominator!=0){ //if the denominator is zero the two lines are parallel
double numeratora=((other.end.x-other.start.x)*(start.y-other.start.y))-((other.end.y-other.start.y)*(start.x-other.start.x));
- double numeratorb=((end.x-start.x)*(start.y-other.start.y))-((end.y-start.y)*(start.x-other.start.x));
double ua=numeratora/denominator;
+ //double numeratorb=((end.x-start.x)*(start.y-other.start.y))-((end.y-start.y)*(start.x-other.start.x));
//double ub=numeratorb/denominator;
returnvalue=GetPointOnLine(ua);
}
Modified: trunk/old_files/miscellaneous/CarapaceCopier/src/org/reprap/scanning/Geometry/LineSegment2DIndices.java
===================================================================
--- trunk/old_files/miscellaneous/CarapaceCopier/src/org/reprap/scanning/Geometry/LineSegment2DIndices.java 2010-12-21 22:29:36 UTC (rev 3959)
+++ trunk/old_files/miscellaneous/CarapaceCopier/src/org/reprap/scanning/Geometry/LineSegment2DIndices.java 2010-12-22 02:08:19 UTC (rev 3960)
@@ -24,7 +24,7 @@
*
* Reece Arnott ree...@gm...
*
-* Last modified by Reece Arnott 21st December 2010
+* Last modified by Reece Arnott 22nd December 2010
*
* This class stores a 2d line segment face which may be part of 0,1 or 2 triangles.
* with the start and end points simple indexes to a Point2d array.
@@ -100,8 +100,8 @@
}
- public int[] GetFace(){
- int[] returnvalue=new int[3];
+ public int[] GetStartAndEndPointIndices(){
+ int[] returnvalue=new int[2];
returnvalue[0]=a;
returnvalue[1]=b;
return returnvalue;
@@ -129,6 +129,13 @@
}
}
+ public void FlipNormal(Point2d[] p){
+ // flip the normal
+ normal.scale(-1);
+ normaldota=normal.dot(p[a]);
+
+ }
+
public void print(){
System.out.print(" ["+a+" "+b+"] hashvalue="+hashvalue);
}
Modified: trunk/old_files/miscellaneous/CarapaceCopier/src/org/reprap/scanning/Geometry/Triangle2D.java
===================================================================
--- trunk/old_files/miscellaneous/CarapaceCopier/src/org/reprap/scanning/Geometry/Triangle2D.java 2010-12-21 22:29:36 UTC (rev 3959)
+++ trunk/old_files/miscellaneous/CarapaceCopier/src/org/reprap/scanning/Geometry/Triangle2D.java 2010-12-22 02:08:19 UTC (rev 3960)
@@ -23,7 +23,7 @@
*
* Reece Arnott ree...@gm...
*
-* Last modified by Reece Arnott 21st December 2010
+* Last modified by Reece Arnott 22nd December 2010
*
* This class stores a single triangle where the points a,b,c are simple indexes to a Point2d array.
*
@@ -55,7 +55,7 @@
public LineSegment2DIndices[] GetFaces(Point2d[] p){
LineSegment2DIndices[] returnvalue=new LineSegment2DIndices[3];
- int[] ab=linesegment.GetFace();
+ int[] ab=linesegment.GetStartAndEndPointIndices();
int a=ab[0];
int b=ab[1];
@@ -64,17 +64,24 @@
returnvalue[0]=new LineSegment2DIndices(a,b,p); returnvalue[0].CalculateNormalAwayFromPoint(p, p[c]);
// This returns faces so that a normal calculated for each face will all point out of original triangle
returnvalue[1]=new LineSegment2DIndices(a,c,p);returnvalue[1].CalculateNormalAwayFromPoint(p, p[b]);
- returnvalue[3]=new LineSegment2DIndices(b,c,p);returnvalue[3].CalculateNormalAwayFromPoint(p, p[a]);
+ returnvalue[2]=new LineSegment2DIndices(b,c,p);returnvalue[2].CalculateNormalAwayFromPoint(p, p[a]);
}
else returnvalue=new LineSegment2DIndices[0];
return returnvalue;
}
+ public LineSegment2D[] GetLineSegmentFaces(Point2d[] p){
+ LineSegment2DIndices[] lines=GetFaces(p);
+ LineSegment2D[] returnvalue=new LineSegment2D[lines.length];
+ for (int i=0;i<lines.length;i++) returnvalue[i]=lines[i].ConvertToLineSegment(p);
+
+ return returnvalue;
+ }
public int[] GetVertices(){
// Note that the order of the vertices is such that each vertex returned is the one not used in triangle returned by the GetFaces method for the same array index
int[] returnvalue=new int[3];
if (c>=0) {
- int[] abc=linesegment.GetFace();
+ int[] abc=linesegment.GetStartAndEndPointIndices();
int a=abc[0];
int b=abc[1];
returnvalue[0]=c;
@@ -97,7 +104,7 @@
boolean returnvalue=true;
for (int j=0;j<othervertices.length;j++) if (returnvalue){
int i=othervertices[j];
- returnvalue=((thisvertices[0]==i) || (thisvertices[1]==i) || (thisvertices[2]==i) || (thisvertices[3]==i));
+ returnvalue=((thisvertices[0]==i) || (thisvertices[1]==i) || (thisvertices[2]==i));
}
return returnvalue;
}
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|