Topic: Smallest Quadrilateral around polygon

Hello,

I'm looking for an algorithm to find the smallest 4 sided polygon ( ie. a quadrilateral ) around a given
(convex) polygon.

I'm specifically not looking for the minimum enclosing rectangle.

I'm pretty certain there is an algorithmus somewhere out there, at least the paper I'm working with says "Finally the smalest 4-sided polygon surrounding the segmented code is evaluated [segmented code in question is a convex polygon]. This is a special case of convex hull evaluation, in which the hull is constrained to have exactly four sides. The output consists in a list of four points which are vertices of a general polygon surrounding the code",
alas it seems I'm using all the wrong words for google ( again )

Thanks for your input,
so long,

->Tyberius Prime

I'm unclear on what you're looking for. You said you are not looking for the minimum enclosing rectangle. Is that because you don't care if the angles of the enclosing polygon are ninety degrees? Is there something else I'm missing here?

.



-- not necessarily stoned... just beautiful.

Yes, the are not required to be 90 degrees.

I'm segmenting regions that once where rectangular ( square actually), but might have been shot at any angle.
So a rectangle might turn into any quadrilateral, and I need that quadrilateral to turn it back into a square.
(There's a nice proof java apllet out there on the web showing that any (convex) quadrilateral is a project
of a rectangle).

so long

->Tyberius Prime

Have you seen an implemetation or a other mentions of such algorithm ?

If the minimum enclosed quad of a convex polygon share some edges with the initial polygon that should simplify greatly the work and allow for a brute force approach that would test the cost ( in term of area ) deleting various edges ofthe convex hull.

Otherwise, well I don't know how to approach the problem. My gut feelings says to fiddle around with voronoi diagrams and eventually delaunay triangulation ... but that might be a dead end.

Well, the only mention I have is in this 2d barcode paper I found.
That's the paragraph I quoted. they don't cite anything surrounding that.
They cited a book for convex hull computation earlier, ( Preparata, "Computional Geometry")
which I looked into. It contained a basic Grahams' scan, but no cake for 'smallest 4-sided polygon surrounding' a polygon.

So far I have found algorithms (or at least references for them) for :
-smallest enclosing (bounding) rectangle, both axis aligned (trivial) and non axis alligned
-smallest enclosing paralellogram ( haven't read that yet. Ghostscript is still downloading...)
-smallest enclosing triangle
-circles

And of course somebody else asking roughly the same question without receiving a useful answer more than a decade ago .

Argh.

Well, now I have posted in comp.graphics.algorithms.
More Spam for me .

Let's see if those guys have any idea.

Okay, correct me if I get this wrong, but I think that you may be on the right track with the smallest enclosing parallelogram. A square, if photographed from a different perspective, will always turn into a parallelogram, because of vanishing points and perspectives and so on. So, since all your barcode grids have a solid bar across the top, then that sequence of black white black white and so on squares just under that, can't you find the bounds of the grid in that image from those reference points, and virtually draw a perspective-shifted grid around the entire barcode from that?

I don't know if I'm explaining this at all clearly, but... image the final grid to be what you'd get if you took a stock standard 2D grid of squares, and pinched one of the sides in, to give it a look of perspective.


Justice 4 Pat Richard

And, yes, on further thought I realised I was wrong with this one. Oh, well... so it goes.

(Edited by Skaarjj on 10-24-2006 15:59)

quote:

---

Skaarjj said:
A square, if photographed from a different perspective, will always turn into a parallelogram, because of vanishing points and perspectives

---

While I don't know anything about the question at hand, it needs to be pointed out that this is a contradictory statement. Perspective and vanishing points preclude the possiblity of a paralellagram by definition.

FWIW.

Indeed, that was what I believe Skaarjj meant when he said he was 'wrong about this one'.

They form a (convex) quadrilateral.

I see. I assumed that the part he thought he was wrong about was...you know...edited...during the edit

Yep, it's my faulty geometric memory. Quadlilateral is what I meant, not parallelogram. Ah, well. As I said, so it goes. I manage to be wrong about much bigger things than this


Justice 4 Pat Richard

quote:

---

I'm segmenting regions that once where rectangular ( square actually), but might have been shot at any angle.

---

I just want to make sure that you know the "Z-near" plane of projection doesn't pass through the square? If so, the projected shape could be an open polygon extending to infinity.

Here's an idea I'll throw out there - there's probably something wrong with it, and it's probably not optimal. What if you start with the convex hull of the polygon, and then:

While the number of sides of the polygon is greater than 4, find the side which, when "removed", causes the smallest increase in area of the polygon and "remove" it.

"Removing" a side of the polygon means taking the two sides adjacent to it and extending them towards each other until they intersect, eliminating the side in question. (This can't be done when the two adjacent sides point away from each other.)

-----

If the original polygon is a triangle, the smallest quadrilateral that encloses it is undefined (as it approaches a triangle shape enclosing the triangle, it gets smaller but if you actually make it into the triangle it's not a quadrilateral anymore).

Hope that helps...

[edit: no, this has flaws, because it can only generate a quadrilateral where each side shares a side with the original convex hull; there are cases where this doesn't represent the best case.]



(Edited by Slime on 10-25-2006 10:22)

If it's an open polygon extending to infinity, I won't be able to decode the datamatrix code embedded in it no matter what.

Triangles are a degenerate case - and I can reject them before hand in my application ( same reason. When one side is shrinked to 0 width,
how would I ever decode it?)

Your approach doesn't sound that bad, at least it would work with the few test cases I have in mind right now.
I could always restrict it to edges with appropriate angles... hm. Gotta think about it, it at least will be an approximation.

Thanks!


Edit: the first paper on this search looks just like what I need. To bad I can't find it online.

(Edited by Tyberius Prime on 10-25-2006 11:23)

Degenerating the convex hull is what I proposed in the 2nd paragraph of my previous post. With a bad wording apparently
But yep that's a very restrictive case.

TP: may I ask what you want to do with the smallest enclosing quad ? how is it related to your data matrix problem ?

From the picture you had in your other thread, it looked fairly easy to segment and decode the DM. It might need a first pass of lens correction to cancel the slight fish eye effect but from what I've seen I doubt you need more.

Well, what I'm trying to do is follow the 'ultimate paper' on decoding these things.

Unfortunatly, it's a bit sketchy as for the details

Here's the basic run down, the part I'm working on right now is marked ( Not that I have the others running as outlined in the paper... but I gotta start somewhere, and I have my own (slow) made up methods ).

1. Scan for regions of interest. ( Using Sobel mask and gradients showing directional characteristics.
2. Locate likely code positions in the regions of interest. ( Ie. The points where the orthogonal bars meet, and points on the far end of the bars). If you have multiple such points, assign a likelyhood value (longest bars, I guess), take maximum one.
3. Segment the code from the rest of the image. To do this, you start with the triangle from the previous step, and grow the region. Then take the complex hull of that grown mess. Repeat growing & complex hull till it's stable ( 2-4 times according to the paper ) . Now take the smallest surrounding 4-sided polygon. Use that to undistort, resample and binarize the code, evaluate bit pattern,
4. Decode bitpattern.

I'm all up on the complex hull computation, and I have a poor man's region growing that will get replaced by a scan line algorithm later on, but I'm absolutly stuck on 'smallest 4-sided polygon surrounding the segmented code'.


If anyone wants to have a look at that paper ( Q me ) , I'd appreciate it .

So long,
and thanks for all your feedback so far!,
->Tyberius Prime

Edit: Correct UBB makes the Asylum Happy!

(Edited by Tyberius Prime on 10-25-2006 13:35)

I believe this paper would have what I need
@article{acy-macp-85
, author = "A. Aggarwal and J. S. Chang and C. K. Yap"
, title = "Minimum area circumscribing polygons"
, journal = "Visual Comput."
, volume = 1
, year = 1985
, pages = "112--117"
, keywords = "extremal figures, polygons"

}

But I'm not going to shell out 30 euros just to check.

Instead I've deceided to fake it. I can easily find out which are the two vertices closest to my original 'bar intersection point'.
Then I'll simply get the next vertices for each one, and elongate that till they meet.
It should work just as well, since they will be already parallel to the alternating borders after region growing * convex hull computation, just not
long enough.


Thanks
and so long,

->Tyberius Prime

Well, my fake algorithm doesn't work. D'oh . ( Turns out my marker bars aren't necessary turned into just one line. Depending on how the thresholded pixels fall, they might be triangular ;( ).

Anyhow, I was able to get the paper I referenced in my last post, but it's a load of mathematical gibberish to me.
So if anybody is up to speed on understanding sentences that start with 'let i and j denote any two distinct edges of P...',
and willing to help me translate this into code,
I'd be more than happy

so long,

->Tyberius Prime

This paper is driving me even more insane than I've already been...

Is there a mathematican in the house??!

Hi TP,

I might be able to help you with that paper. I used to readmathematical papers from time to time. Let me know what I can do to help.

.



-- not necessarily stoned... just beautiful.

Do you need a fast and analytically correct solution? There's always the brute force approximation approach.

For every set of four vertices, consider "all" (for an approximation, "many") lines that pass through them without intersecting the polygon at any other point, to create many sets of four lines. If a set of four lines forms a closed quadrilateral which has a smaller area than any previously found quadrilateral, store it as the best.

Optionally, take the best one you find (or a few of the best ones), and try similar ones to refine the approximation.

Well, it needs to be fast, and correct always beats approximate ( though approximate probably would do just as well )...
As far as I understand the algorithm, it's pretty 'brute force' already. It exploits the fact, that the minimum k-gon always
has (k-1) sides 'flush' with the polygon, and the center of all k-gon sides actually touching the polygon, then calculates
all possible 'chains' of 'one side optimal' and 'one side flushed', and their 'extra area', and that calculating is just about
where I loose it.

I think I've finally grasped why I can't figure out how to calculate this from the paper. It's not actually in there.
The paper is just a proof of the O(n^2 * log n * log k ) runtime!
Maybe it's still in there, but it's not in 'plain formular' .

Hyperbole: I'd appricate your help . Are you on ICQ? Either way, drop me a line ( see my profile for both Q number and (slightly obfuscated ) e-mail address ), and I'll get the paper to you.

Thanks to all of you,
so long,

->Tyberius Prime

Well, it needs to be fast, and correct always beats approximate ( though approximate probably would do just as well )...
As far as I understand the algorithm, it's pretty 'brute force' already. It exploits the fact, that the minimum k-gon always
has (k-1) sides 'flush' with the polygon, and the center of all k-gon sides actually touching the polygon, then calculates
all possible 'chains' of 'one side optimal' and 'one side flushed', and their 'extra area', and that calculating is just about
where I loose it.

I think I've finally grasped why I can't figure out how to calculate this from the paper. It's not actually in there.
The paper is just a proof of the O(n^2 * log n * log k ) runtime!
Maybe it's still in there, but it's not in 'plain formular' .

Hyperbole: I'd appricate your help . Are you on ICQ? Either way, drop me a line ( see my profile for both Q number and (slightly obfuscated ) e-mail address ), and I'll get the paper to you.

Thanks to all of you,
so long,

->Tyberius Prime

Hyperbole: Are you around?

Tyberius Prime,

I sent an e-mail yesterday. Have you sent a response yet?

.



-- not necessarily stoned... just beautiful.

Minkowski Sums ...is a good search phrase..

And this phrase I typed into Google

algorithm for complex polyhedron

Most of the web sites are Pay for Information but there were several that
seemed willing to share a bit of knowledge. One site was about using triangulation to find that dimension.. There were many sites..there may be something useful there
This seems to be a ..test..type question

(Edited by skyetyger on 11-09-2006 23:15)