# Cutting Concave Polygons

Geschrieben von am 11. March 2012

Remember my last post on how to turn concave polygons into convex ones so that you can actually use them in Box2D? Well, turns out my solution didn't quite work out that well. The thing is, if you mess up the order of vertices in the polygon (Box2D requires them to be in counter-clockwise order), the results are really weird and the collision starts bugging out. So I looked around for some better solution that would work more reliably.

On the blog of Emanuele Feronato I found a great algorithm which is a lot more mathematical and less "lets try until it (maybe) works". It uses ray-casting to split up the polygons and I just had to port it to Java and clean it up a bit. So first of all the polygon needs to be simplified (meaning removing unnecessary vertices) and the order of the vertices must be counter clockwise (if you want to know how to do that, have a look at the source code here and some explanation here). First of all here is some source code (which might not actually work since I pasted it together for this blog post, for a definitely working version see the repository):

  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 // Use this list for finished convex polygon results ArrayList result = new ArrayList(); // Queue used for recursively handling polygons ArrayDeque> queue = new ArrayDeque>(); queue.clear(); // Make sure there are no uncessecary vertices as the algorithm might // not work otherwise poly = simplify(poly); // Make sure the vertices are in counter-clockwise order if (!isCCW(poly)) { poly = flip(poly); } // Start off with the given polygon queue.add(makeVectors(poly)); while (queue.size() > 0) { // See if the polygon needs splitting and do it poly = handlePolygon(queue.remove()); int last_vertex = vectors.size() - 1; boolean is_convex = true; // Walk through all vertices until we find a concave one for (int current_idx = 0; current_idx < vectors.size(); current_idx++) { // Grab a triplet of vertices int last_idx = current_idx == 0 ? last_vertex : current_idx - 1; int next_idx = current_idx == last_vertex ? 0 : current_idx + 1; Vec2 last = vectors.get(last_idx); Vec2 current = vectors.get(current_idx); Vec2 next = vectors.get(next_idx); // Use the cross product to determine if the current vertex is at a // concave position. If cross product is negative, the vertex is not // convex, so we need to split here if (Vec2.cross(current.sub(last), next.sub(current)) < 0) { is_convex = false; Segment ray = new Segment(last, current); int split_idx = current_idx; // To use the closest segment for ray intersection order them by // distance. Using the closest prevents the cut to go through any // unwanted segments. float min_distance = Float.MAX_VALUE; int hit_start = -1; int hit_end = -1; Vec2 hit_point = null; // For each segment in the polygon for (int start_idx = 0; start_idx < vectors.size(); start_idx++) { // Calculate the index of the end vertex int end_idx = start_idx == last_vertex ? 0 : start_idx + 1; // Ignore the ray segment and the one after it if (start_idx == split_idx || start_idx == last_idx) { continue; } Segment segment = new Segment(vectors.get(start_idx), vectors.get(end_idx)); // Try casting a ray along the problematic segment which if // successful can be used to split up the polygon along it Vec2 res = hitRay(ray, segment); if (res != null) { // Hit another segment, so check if it's the closest one float distance = res.sub(ray.end).lengthSquared(); // This one is closer to the original if (distance < min_distance) { hit_point = res; min_distance = distance; hit_start = start_idx; hit_end = end_idx; } } } // Yay! Lets cut it up! if (hit_start != -1) { // Prepare the parts Vector part_a = new Vector(); Vector part_b = new Vector(); // Only add the new points if they are to far from the end/start of // the associated segment if (!deltaEquals(vectors.get(hit_end), hit_point)) { part_a.add(hit_point); } if (!deltaEquals(vectors.get(hit_start), hit_point)) { part_b.add(hit_point); } // Build the parts which both contain the new found cut as an edge for (int j = hit_end; j != split_idx; j = (j == last_vertex) ? 0 : j + 1) { part_a.add(vectors.get(j)); } for (int j = split_idx; j != hit_end; j = (j == last_vertex) ? 0 : j + 1) { part_b.add(vectors.get(j)); } // And check those new parts for convexity queue.add(part_a); queue.add(part_b); break; } else { throw new Error("Invalid polygon - polygons must not overlap!"); } } } // The polygon was convex so we simply add it if (is_convex) { result.add(makePolygon(poly)); } } 

So let me try and explain how this algorithm works. First of all it uses a queue to recursively process all polygons - so if we cut one polygon in half we get two new ones that need checking. The algorithm runs through all corners of the polygon checking if they are all convex (in the picture to the right all but #4 are convex). If they are all convex, that's great and the polygon can just be kept as is. Otherwise we have to split it up at the given corner (from line 41).

That is where the ray-casting comes in as we basically follow the last segment's direction until we hit another segment of the polygon. This ray (red in the picture) is the line we will use to cut the polygon in half. This is done by checking each segment individually and using the one with the shortest distance (line 81). The new found hit point is then inserted into both new polygons. Now the most interesting part is the actual ray and seeing if it hits anything. The math for that comes from Graphics Algorithms FAQ (Subject 1.03):

 1

private static Vec2 hitRay(Segment ray, Segment segment)
{
// See http://www.faqs.org/faqs/graphics/algorithms-faq/
float ray_numerator = Vec2.cross(segment.delta, ray.start.sub(segment.start));
float segement_numerator = Vec2.cross(ray.delta, ray.start.sub(segment.start));

float denominator = Vec2.cross(ray.delta, segment.delta);

// Segment and ray are parallel
if (denominator == 0)
{
return null;
}

float ray_pos = ray_numerator / denominator;
float segement_pos = segement_numerator / denominator;

// The potential hit point is not actually on the segment
if (segement_pos < 0 || segement_pos > 1)
{
return null;
}

// The hit point would be in opposite direction of the ray
if (ray_pos <= 0) { return null; } // Calculate the hit point return ray.start.add(ray.delta.mul(ray_pos)); }[/pygmentize] You can determin the offset ob both the ray and the segment using the formula: $\text{rayoff} = \frac{(\mathbf{segend} - \mathbf{segstart}) \times (\mathbf{raystart} - \mathbf{segstart})}{(\mathbf{rayend} - \mathbf{raystart}) \times (\mathbf{segend} - \mathbf{segstart})} \\ \text{segoff} = \frac{(\mathbf{rayend} - \mathbf{raystart}) \times (\mathbf{raystart} - \mathbf{segstart})}{(\mathbf{rayend} - \mathbf{raystart}) \times (\mathbf{segend} - \mathbf{segstart})}$ Here if segoff is inbetween 0 and 1 the hit point is on the segment and if rayoff is positive then the ray hits it from the right direction as well so we have found ourselves a hit. All that is left to do here is calculating the actual hit point which is simple: $\mathbf{hitpoint} = \mathbf{raystart} + \text{rayoff} \cdot (\mathbf{rayend} - \mathbf{raystart})$ All that is left to do then is splitting the polygons up by adding the new diagonal. That is done in to first code from line 94 by splitting the list of vertices up using the two indices (the one of the ray segment and the one of the hit segment). Noteworthy is that the initial corner (the one that was concave) is left out in one polygon as it lies on the ray and is therefor redundant. So in the above example part A would contain the points #2 and #3 as well as the hit point and part B would have #4, #5, #1 and the hit point. In the next steps both parts would be checked for convexity as well - which they are, so that's the final result. I hope I could help you guys if you're wondering how to make those stupid polygons convex... Feel free to leave some comments, suggestions or whatever. And you can use the code for pretty much anything you want. Grab it from the repository as that probably is the cleaner and ready-to-use version. Cheers :)