Find smallest irregular polygon from combination of vertices (Performance Critical)

I need to find an irregular polygon with the smallest surface area out of several vertices on a 2D plane.

No this isn't homework. Although I wish I was back in school right now.

There are some requirements on how the polygon can be constructed. Let's say I have 3 different types of vertices (red, green, blue) plotted out on a 8x8 grid. I need to scan all vertices in this grid satisfying the red, green, blue combination requirement and pick the one with the smallest surface area.

Getting the surface area of an irregular polygon is simple enough. I'm mainly concerned about the performance of scanning all possible combinations efficiently.

See the below image for an example. All three types are used to make the polygons however the one circled has the smallest surface area and is my objective.

This scenario is simplified compared to what I'm trying to prototype. The polygons will be constructed of tens if not hundreds of vertices and the grid will be much larger. Also, this will be a process ran 24/7.

I was thinking that maybe I should organize开发者_C百科 the vertices by type and break them into individual arrays. Then just iterate over the arrays in a tiered fashion to compute the surface area of all combinations. This approach however seems wasteful.

---

Here is a version based on branch and bound, with some flourishes.

1) Break the grid down into a Quadtree, with annotations in the nodes as needed for the rest.

2) Find the lowest node in the quad tree that has one of each type of node. This gives you a starting solution, which should be at least good enough to speed up the rest of the search.

3) Do a recursive search which takes all possible branches where I say guess, choosing the most promising candidates first where applicable:

3a) Guess a vertex of the least common type.

3b) Using the relative location of points in the quad tree to order your guesses, guess a vertex of the next least common type, so as to guess them in increasing order of distance form the original point...

3z) you have a complete set of vertices.

At each step 3? you have a partial set of vertices, which I presume gives you a lower bound on the area of any complete solution including those vertices (is it the area inside the convex hull of the vertices?). You can discard any partial solutions that are already at least as large as the largest solutions so far. If you can live with an answer that is X% inaccurate, you can discard any partial solutions that are within X% of the largest solution so far. Hopefully this prunes the tree of possibilies you are navigating in (3) far enough to make it tractable.

---

How about picking the color with the least number of vertices, and checking for each one the immediate neighborhood, if none has the other colors within this neighborhood, increase the stencil size (select next ring around the vertex), and check again. Until at least one of the vertices, has all other colors within the current stencil. If there are more than one, you just need to compare those (simple min reduction) to find the smallest one.

---

Here's how to find the smallest triangle in time O(n² log n). Perhaps it will be useful to you.

The high-level idea is to use a rotating sweep-line. At all times we maintain the order of the blue points along the axis perpendicular to the sweep-line, in a binary search tree. When the sweep-line is parallel with the line passing through a red-green pair, we use the BST to find the blue point closest to the red-green line.

As always, we use an event-driven simulation of the sweep-line. For each red-green pair, make one kind of event for its angle. For each pair of blue points, make O(1) of another kind of event for when their relative order changes. Sort all of the events and turn the crank.

---

If we already have found an area A, we can narrow the search.

The area of a triangle is B*h (base times height).

If you find two points, then B is the distance between them.

Then we can search for a point which is at most A/B (B*h < A => h < A/B) distance from that line. This is the same as searching between two lines parallel to the two points we already have, which are displaced A/B and -A/B.

This should give a complexity of O(n^2*k) where k is the width or height of your grid.

If you don't extract the coordinates you have to do a O(k^5) search, which at least is better than O(k^6) you had to do earlier.

Some more analysis: if p is the probability that a cell contains a vertex then the complexity is: O(k^2p(k^2p(kp))) = O(k^5p^3). If p=n/k^2, where n is the number of nodes we then get O(n^3/k).