Permalink
Cannot retrieve contributors at this time
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?
compgeoproject/main/CompGeo.pde
Go to fileThis commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
161 lines (145 sloc)
5.59 KB
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public static class CompGeo { | |
public static int CCW(Point a, Point b, Point c) { | |
// Return 1 if turn abc is ccw -1 if turn abc is cw 0 if no turn | |
float f = (b.getX() - a.getX())*(c.getY() - a.getY()) - (c.getX() - a.getX())*(b.getY()-a.getY()); | |
if (f < 0) { return 1; } | |
if (f > 0) { return -1; } | |
return 0; | |
} | |
public static int immediateCCW(Point parent, Point child, Point v1, Point v2) { | |
// returns 1 if v1 is more immediate CCW of parent, child than v2 | |
// returns -1 if v2 is more immediate CCW of parent, child than v1 | |
if (CCW(parent, child, v1) > CCW(parent, child, v2)) { return 1; } | |
if (CCW(parent, child, v1) < CCW(parent, child, v2)) { return -1; } | |
return CCW(parent, v1, v2); | |
} | |
private static boolean between(Point a, Point b, Point c) { | |
if (a.getX() > c.getX()) { return ((b.getX() > c.getX()) && (b.getX() < a.getX())); } | |
if (a.getX() < c.getX()) { return ((b.getX() < c.getX()) && (b.getX() > a.getX())); } | |
if (a.getY() > c.getY()) { return ((b.getY() > c.getY()) && (b.getY() < a.getY())); } | |
if (a.getY() < c.getY()) { return ((b.getY() < c.getY()) && (b.getY() > a.getY())); } | |
return false; | |
} | |
public static int intersect(Point a, Point b, Point c, Point d) { | |
if ((CCW(a,b,c) != CCW(a,b,d)) && ((CCW(c,d,a) != CCW(c,d,b)))) { | |
return 1; | |
} | |
if ((CCW(a,b,c) == 0) & (CCW(a,b,d) == 0)) { | |
if (between(a,c,b) || between(a,d,b) || between(c,a,d) || between(c,b,d)) { | |
return 1; | |
} | |
} | |
return 0; | |
} | |
public static boolean inside(HalfEdge h, Point p, Point q) { | |
HalfEdge temp = h.getnext(); | |
Point e1 = h.getOrigin(); | |
Point e2 = h.gettwin().getOrigin(); | |
int nis = intersect(e1, e2, p, q); | |
while (temp != h) { | |
e1 = temp.getOrigin(); | |
e2 = temp.gettwin().getOrigin(); | |
nis += intersect(e1, e2, p, q); | |
temp = temp.getnext(); | |
} | |
if ((nis % 2) == 0) { return false; } | |
else { return true; } | |
} | |
public static float signedArea(HalfEdge h) { | |
return signedArea(h.getPointsNext()); | |
} | |
public static float signedArea(ArrayList<Point> points) { | |
int num = points.size(); | |
Point p = null; | |
Point q = null; | |
float sum = 0; | |
for (int i = 0; i < num; i++) { | |
p = points.get(i); | |
q = points.get((i+1)%num); | |
sum += (p.getX()*q.getY() - q.getX()*p.getY()); | |
} | |
return sum; | |
} | |
public static boolean isContained(HalfEdge inner, HalfEdge outer, Point far) { | |
Point inHandle = inner.getOrigin(); | |
return inside(outer, inHandle, far); | |
} | |
public static ArrayList<HalfEdge> findFriends(HalfEdge outer, PointList points) { | |
ArrayList<HalfEdge> handles = points.getAllStructures(); | |
ArrayList<HalfEdge> friends = new ArrayList<HalfEdge>(); | |
int num = handles.size(); | |
HalfEdge out = null; | |
for (int i = 0; i < num; i++) { | |
//if (inner.canReach(handles.get(i))) { friends.add(inner); continue; } | |
out = findTightOuterBoundary(handles.get(i), points); | |
if (out == outer) { | |
//if (signedArea(handles.get(i)) <= 0) { friends.add(handles.get(i).gettwin()); continue; } | |
//else { friends.add(handles.get(i)); continue; } | |
friends.add(findCWR(handles.get(i))); continue; | |
} | |
if ((out != null) && (outer != null)) { | |
if (out.canReachNext(outer)) { | |
//if (signedArea(handles.get(i)) <= 0) { friends.add(handles.get(i).gettwin()); continue; } | |
//else { friends.add(handles.get(i)); continue; } | |
friends.add(findCWR(handles.get(i))); continue; | |
} | |
} | |
} | |
return friends; | |
} | |
public static HalfEdge findTightOuterBoundary(HalfEdge inner, PointList points) { | |
Point far = points.getFar(); | |
ArrayList<HalfEdge> handles = points.getAllStructures(); | |
int num = handles.size(); | |
HalfEdge temp; | |
HalfEdge tightest = null; | |
for (int i = 0; i < num; i++) { | |
temp = handles.get(i); | |
if (inner.canReach(temp)) { continue; } // MAKE SURE DONT CHECK AGAINST ITSELF | |
if (isContained(inner, temp, far)) { | |
if (tightest == null) { | |
tightest = temp; | |
} else { | |
if (isContained(temp, tightest, far)) { | |
tightest = temp; | |
} | |
} | |
} | |
} | |
tightest = findSuperTightBoundary(inner, tightest, far); | |
if (tightest != null) { tightest.reset(); } | |
return tightest; | |
} | |
public static HalfEdge findSuperTightBoundary(HalfEdge inner, HalfEdge outer, Point far) { | |
if (outer == null) { return null; } | |
if ((isContained(inner, outer, far)) && (signedArea(outer) < 0)) { return outer; } | |
if (outer.getCounted() == false) { | |
outer.setCounted(true); | |
HalfEdge temp = findSuperTightBoundary(inner, outer.getnext(), far); | |
if (temp != null) { return temp; } | |
temp = findSuperTightBoundary(inner, outer.getprevious(), far); | |
if (temp != null) { return temp; } | |
temp = findSuperTightBoundary(inner, outer.gettwin(), far); | |
if (temp != null) { return temp; } | |
} | |
return null; | |
} | |
public static HalfEdge findCWR(HalfEdge ref) { | |
HalfEdge out = findClockWiseRepresentation(ref); | |
ref.reset(); | |
return out; | |
} | |
private static HalfEdge findClockWiseRepresentation(HalfEdge ref) { | |
if (signedArea(ref) >= 0) { return ref; } | |
if (ref.getCounted() == false) { | |
ref.setCounted(true); | |
HalfEdge temp = findClockWiseRepresentation(ref.getnext()); | |
if (temp != null) { return temp; } | |
temp = findClockWiseRepresentation(ref.getprevious()); | |
if (temp != null) { return temp; } | |
temp = findClockWiseRepresentation(ref.gettwin()); | |
if (temp != null) { return temp; } | |
} | |
return null; | |
} | |
} |