Skip to content
Permalink
194239db76
Switch branches/tags

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?
Go to file
 
 
Cannot retrieve contributors at this time
511 lines (391 sloc) 20.1 KB
/////////////////////////////////////////////////////////////
class HalfEdge {
Node origin;
HalfEdge next;
HalfEdge prev;
HalfEdge twin;
Face face;
public HalfEdge(){}
public HalfEdge(Node o, HalfEdge n, HalfEdge p, HalfEdge t, Face f){
this.origin = o;
this.next = n;
this.prev = p;
this.twin = t;
this.face = f;
}
public HalfEdge(Node o, HalfEdge n, HalfEdge t, Face f){
this.origin = o;
this.next = n;
this.twin = t;
this.face = f;
}
public void setAll(Node o, HalfEdge n, HalfEdge p, HalfEdge t, Face f){
this.origin = o;
this.next = n;
this.prev = p;
this.twin = t;
this.face = f;
}
public void setLess(Node o, HalfEdge n, HalfEdge t, Face f){
this.origin = o;
this.next = n;
this.twin = t;
this.face = f;
}
}
///////////////////////////////////////////////////
class Node{
int x_coord;
int y_coord;
HalfEdge arbitrary_outgoing;
public Node(int x, int y, HalfEdge a_o){
x_coord = x;
y_coord = y;
arbitrary_outgoing = a_o;
}
public Node(int x, int y){
x_coord = x;
y_coord = y;
}
public void setOutgoing(HalfEdge out){
arbitrary_outgoing = out;
}
}
//////////////////////////////////////////////////
class Face{
HalfEdge inc_edge;
public Face(){}
public Face(HalfEdge he){
inc_edge = he;
}
public void set_he(HalfEdge he){
inc_edge = he;
}
}
////////////////////////////////////////////////////
int num_lines = int(random(4, 8));
int[][] list_of_lines = new int[num_lines][4];
ArrayList<HalfEdge> half_edges_list = new ArrayList<HalfEdge>();
ArrayList<Node> node_list = new ArrayList<Node>();
ArrayList<Face> face_list = new ArrayList<Face>();
void setup(){
size(800, 800);
frameRate(60);
background(0, 0, 0);
//createBoundingBox Nodes
Node topleft = new Node( 0, 0);
Node topright = new Node( 800, 0);
Node botleft = new Node( 0, 800);
Node botright = new Node( 800, 800);
//add to node list
node_list.add(topleft);
node_list.add(topright);
node_list.add(botleft);
node_list.add(botright);
//Initialize Half Edges of Bouding Box
HalfEdge top_i = new HalfEdge();
HalfEdge top_o = new HalfEdge();
HalfEdge bot_i = new HalfEdge();
HalfEdge bot_o = new HalfEdge();
HalfEdge right_i = new HalfEdge();
HalfEdge right_o = new HalfEdge();
HalfEdge left_i = new HalfEdge();
HalfEdge left_o = new HalfEdge();
//add to halfedge list
half_edges_list.add(top_i);
half_edges_list.add(top_o);
half_edges_list.add(bot_i);
half_edges_list.add(bot_o);
half_edges_list.add(right_i);
half_edges_list.add(right_o);
half_edges_list.add(left_i);
half_edges_list.add(left_o);
//Construct First Faces, interior and exterior faces of the bounding box
Face unbounded = new Face(top_o);
Face original = new Face(top_i);
//add to faces list
face_list.add(unbounded);
face_list.add(original);
//setup HalfEdges of Bounding Box
top_i.setAll(topright, left_i, right_i, top_o, original);
left_i.setAll(topleft, bot_i, top_i, left_o, original);
bot_i.setAll(botleft, right_i, left_i, bot_o, original);
right_i.setAll(botright, top_i, bot_i, right_o, original);
top_o.setAll(topleft, right_o, left_o, top_i, unbounded);
right_o.setAll(topright, bot_o, top_o, right_i, unbounded);
bot_o.setAll(botright, left_o, right_o, bot_i, unbounded);
left_o.setAll(botleft, top_o, bot_o, left_i, unbounded);
//setup nodes of Bounding box
topleft.setOutgoing(left_i);
botleft.setOutgoing(bot_i);
botright.setOutgoing(right_i);
topright.setOutgoing(top_i);
//Create Random Arrangement
for(int i = 0; i < num_lines; i++){
stroke(255, 255, 255);
int side1 = int(random(1,5));
int side2 = side1;
while ( side2 == side1){
side2 = int(random(1,5));
}
int x1 = int(random(0, width + 1));
int y1 = int(random(0, height + 1));
int x2 = int(random(0, width + 1));
int y2 = int(random(0, height + 1));
if (side1 == 1)
y1 = 0;
if (side1 == 2)
x1 = width;
if (side1 == 3)
y1 = height;
if (side1 == 4)
x1 = 0;
///////////////////
if (side2 == 1)
y2 = 0;
if (side2 == 2)
x2 = width;
if (side2 == 3)
y2 = height;
if (side2 == 4)
x2 = 0;
if( i == 0 ){ //for the first line we do not need to check for intersection, this line is always added
//do line
line(x1, y1, x2, y2);
list_of_lines[i][0] = x1;
list_of_lines[i][1] = y1;
list_of_lines[i][2] = x2;
list_of_lines[i][3] = y2;
//do half edge
node_list.add(new Node(x1, y1));
node_list.add(new Node(x2, y2));
face_list.add(new Face());
Face newface = face_list.get(face_list.size()-1);
HalfEdge startHE = top_i;
HalfEdge currentHE = top_i;
Node collinear1 = null;
Node collinear2 = null;
HalfEdge inner1 = null; //save the two "inner" halfedges so that they may be used to initialize the newline halfedges
HalfEdge inner2 = null;
do{
if(checkLineIntersect(x1, y1, x2, y2, currentHE.origin.x_coord, currentHE.origin.y_coord, currentHE.next.origin.x_coord, currentHE.next.origin.y_coord)){
//when we find that currentHE is intersected by the new line
//determine which node is intersecting our current HE
if(ccw(currentHE.origin.x_coord, currentHE.origin.y_coord, x1, y1, currentHE.next.origin.x_coord, currentHE.next.origin.y_coord) == 0){
collinear1 = node_list.get(node_list.size() - 2);
}else if(ccw(currentHE.origin.x_coord, currentHE.origin.y_coord, x2, y2, currentHE.next.origin.x_coord, currentHE.next.origin.y_coord) == 0){
collinear1 = node_list.get(node_list.size() - 1);
}else{
collinear1 = null;
System.out.println("error when finding node collinear with intersected bounding box edge");
}
//add new half edges
half_edges_list.add( new HalfEdge());//inner half edge
half_edges_list.add( new HalfEdge());//outer halfedge
inner1 = half_edges_list.get(half_edges_list.size() - 2);
HalfEdge outer = half_edges_list.get(half_edges_list.size() - 1);
inner1.setLess(collinear1, currentHE.next, outer, newface);
collinear1.setOutgoing(inner1);
newface.set_he(inner1);
outer.setLess(currentHE.next.origin, currentHE.twin, inner1, unbounded);
currentHE.twin.origin = collinear1;
currentHE.twin.prev = outer;
currentHE.next = inner1;
stroke(255, 0 , 0);
line(inner1.origin.x_coord, inner1.origin.y_coord, inner1.next.origin.x_coord, inner1.next.origin.y_coord);
currentHE = inner1.next; //move to the newly created next half edge so that the next edge will be set to be the next edge on the bounding box
break;
}else{
currentHE = currentHE.next;
}
}while(currentHE != top_i);
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//search for where to add second vertex
do{
if(checkLineIntersect(x1, y1, x2, y2, currentHE.origin.x_coord, currentHE.origin.y_coord, currentHE.next.origin.x_coord, currentHE.next.origin.y_coord)){
if(ccw(currentHE.origin.x_coord, currentHE.origin.y_coord, x1, y1, currentHE.next.origin.x_coord, currentHE.next.origin.y_coord) == 0){
collinear2 = node_list.get(node_list.size() - 2);
}else if(ccw(currentHE.origin.x_coord, currentHE.origin.y_coord, x2, y2, currentHE.next.origin.x_coord, currentHE.next.origin.y_coord) == 0){
collinear2 = node_list.get(node_list.size() - 1);
}else{
collinear2 = null;
System.out.println("error when finding node collinear with intersected bounding box edge");
}
half_edges_list.add( new HalfEdge());//inner half edge
half_edges_list.add( new HalfEdge());//outer halfedge
inner2 = half_edges_list.get(half_edges_list.size() - 2);
HalfEdge outer = half_edges_list.get(half_edges_list.size() - 1);
inner2.setLess(collinear2, currentHE.next, outer, original);
collinear2.setOutgoing(inner2);
outer.setLess(currentHE.next.origin, currentHE.twin, inner2, unbounded );
currentHE.twin.origin = collinear2;
currentHE.twin.prev = outer;
currentHE.next = inner2;//change to newline
currentHE.face = newface;
//add half edges for the new line crossing this face, one on old face and one on the newly created face
half_edges_list.add( new HalfEdge());//half edge on new face
half_edges_list.add( new HalfEdge());//half edge on preexisting face
HalfEdge newface_edge = half_edges_list.get(half_edges_list.size() - 2);
HalfEdge oldface_edge = half_edges_list.get(half_edges_list.size() - 1);
newface_edge.setLess(collinear2, inner1, oldface_edge, newface);
oldface_edge.setLess(collinear1, inner2, newface_edge, original);
inner1.twin.next.twin.next = oldface_edge;
inner2.twin.next.twin.next = newface_edge;
break;
}else{
currentHE.face = newface;
currentHE = currentHE.next;
}
}while(currentHE != top_i);
}
else{ //for any line following the first line we check all lines added and see if this new line intersects at least one, if it does the new line is added
int hasIntersect = 0;
for (int k = 0; k < i; k++){
if (checkLineIntersect(x1, y1, x2, y2, list_of_lines[k][0], list_of_lines[k][1], list_of_lines[k][2], list_of_lines[k][3]) == true){
hasIntersect = 1;
break;
}
}
if (hasIntersect == 1){
//do line
line(x1, y1, x2, y2); //<>//
list_of_lines[i][0] = x1;
list_of_lines[i][1] = y1;
list_of_lines[i][2] = x2;
list_of_lines[i][3] = y2;
/////////////////////////////////////////////////////////////////////////////////////////////////////WIP///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
HalfEdge startHE = top_i;
HalfEdge currentHE = top_i;
Node leftmost = null;
Node rightmost = null;
if ( x1 < x2 ){
leftmost = new Node(x1,y1);
rightmost = new Node(x2, y2);
node_list.add(leftmost);
node_list.add(rightmost);
}else if( x2 < x1 ){
leftmost = new Node(x2, y2);
rightmost = new Node(x1, y1);
node_list.add(leftmost);
node_list.add(rightmost);
}else{
System.out.println("Neither points in the line are leftmost, line may be vertical or there may be an error");
leftmost = new Node(x1,y1);
rightmost = new Node(x2, y2);
node_list.add(leftmost);
node_list.add(rightmost);
}
//We have found which intersection point of the line is the leftmost point and then placed a node there at that point
//Now we search the bounding box for the edge that both intersects the new line and is also collinear with the leftmost point
//This intersection point will be the beginning of our walk
do{
if((checkLineIntersect(x1, y1, x2, y2, currentHE.origin.x_coord, currentHE.origin.y_coord, currentHE.next.origin.x_coord, currentHE.next.origin.y_coord)) //<>//
&& (ccw(currentHE.origin.x_coord, currentHE.origin.y_coord, leftmost.x_coord, leftmost.y_coord, currentHE.next.origin.x_coord, currentHE.next.origin.y_coord) == 0)){
//when we find that currentHE is intersected by the new line
//split half edge intersected by leftmost point
face_list.add( new Face());
Face newface = face_list.get(face_list.size()-1);
half_edges_list.add( new HalfEdge());//inner half edge
half_edges_list.add( new HalfEdge());//outer halfedge
HalfEdge inner = half_edges_list.get(half_edges_list.size() - 2);
HalfEdge outer = half_edges_list.get(half_edges_list.size() - 1);
inner.setLess(leftmost, currentHE.next, outer, newface);
outer.setLess(currentHE.next.origin, currentHE.twin, inner, unbounded);
currentHE.twin.origin = leftmost;
currentHE.twin.prev = outer; //this stuff must be changed later once the face is traversed and the exit point of the new line is found. At this point these values will take their finalized values (eg: currentHE.next will be equal to a HE on new line)
currentHE.next = inner;
currentHE = inner;
HalfEdge first_of_face = currentHE;
//do walk to set up new edges and faces
boolean right_end_found = false;
//////////////////////////////////////Walk Block//////////////////////////////////////////////
do{
if(checkLineIntersect(leftmost.x_coord, leftmost.y_coord, rightmost.x_coord, rightmost.y_coord, currentHE.origin.x_coord, currentHE.origin.y_coord, currentHE.next.origin.x_coord, currentHE.next.origin.y_coord)){
if(ccw(currentHE.origin.x_coord, currentHE.origin.y_coord, rightmost.x_coord, rightmost.y_coord, currentHE.next.origin.x_coord, currentHE.next.origin.y_coord) == 0){
right_end_found = true;
}
int a1 = rightmost.x_coord - leftmost.x_coord;
int b1 = leftmost.x_coord - rightmost.x_coord;
int c1 = a1*(leftmost.x_coord) + b1*(rightmost.y_coord);
int a2 = currentHE.next.origin.y_coord - currentHE.origin.y_coord;
int b2 = currentHE.origin.x_coord - currentHE.next.origin.x_coord;
int c2 = a2*(currentHE.origin.x_coord) + b2*(currentHE.origin.y_coord);
int det = a1*b2 - a2*b1;
if(det == 0){
System.out.println("parallel");
}else{
int pointx = (b2*c1 - b1*c2)/det;
int pointy = (b2*c1 - b1*c2)/det;
node_list.add( new Node(pointx, pointy));
}
Node intercept_node = node_list.get(node_list.size()-1);
half_edges_list.add(new HalfEdge());
half_edges_list.add(new HalfEdge());
HalfEdge inner_on_walk = half_edges_list.get(half_edges_list.size() - 2);
HalfEdge outer_on_walk = half_edges_list.get(half_edges_list.size() - 1);
inner_on_walk.setLess(intercept_node, currentHE.next, outer_on_walk, currentHE.next.face);
intercept_node.setOutgoing(inner_on_walk);
outer_on_walk.setLess(currentHE.next.origin, currentHE.twin, inner_on_walk, currentHE.twin.face);
currentHE.twin.origin = intercept_node;
currentHE.twin.prev = outer_on_walk;
currentHE.next = inner_on_walk;
currentHE.face = face_list.get(face_list.size() - 1);
//add halfedges for newline intersecting this face
half_edges_list.add( new HalfEdge()); //oldface
half_edges_list.add( new HalfEdge()); //newface
HalfEdge oldface_nl_walk = half_edges_list.get(half_edges_list.size() - 2);
HalfEdge newface_nl_walk = half_edges_list.get(half_edges_list.size() - 1);
oldface_nl_walk.setLess( node_list.get(node_list.size() - 2), inner_on_walk, newface_nl_walk, inner_on_walk.face);
newface_nl_walk.setLess( intercept_node, first_of_face, oldface_nl_walk, currentHE.face);
currentHE = currentHE.twin;
first_of_face = currentHE;
}else{
currentHE.face = face_list.get(face_list.size() - 1);
currentHE = currentHE.next;
}
}while(right_end_found == false);
////////////////////////////////////////////////////////////////////////////////////
//currentHE = currentHE.next; //move to the newly created next half edge so that the next edge will be set to be the next edge on the bounding box
break;
}else{
if(currentHE.next.twin.face == unbounded){
currentHE = currentHE.next;
}else if(currentHE.next.twin.next.twin.face == unbounded){
currentHE = currentHE.next.twin.next;
}else{
System.out.println("error finding next bounding box halfedge");
}
}
}while(currentHE != top_i);
///////////////////////////////////////////////////////////////////////////////////////////WIP end////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
}else{
i--; //try again
}
}
}
}
boolean checkLineIntersect(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4){
int orientation1 = ccw( x1, y1, x2, y2, x3, y3);
int orientation2 = ccw( x1, y1, x2, y2, x4, y4);
int orientation3 = ccw( x3, y3, x4, y4, x1, y1);
int orientation4 = ccw( x3, y3, x4, y4, x2, y2);
if((orientation1 != orientation2) && (orientation3 != orientation4)){
return true;
}else{
return false;
}
}
int ccw(int point1_x, int point1_y, int point2_x, int point2_y, int point3_x, int point3_y){
float returnVal = 0;
returnVal = (point2_y - point1_y) * (point3_x - point2_x) - (point2_x - point1_x) * (point3_y - point2_y);
if (returnVal > 0)
return 1;
else if (returnVal == 0)
return 0;
else if (returnVal < 0)
return -1;
else
return 2; //error code
}
void draw(){
}