73 views

Skip to first unread message

Oct 24, 2006, 7:53:04 AM10/24/06

to

Hello Group,

I'm trying to implement an image segmentation process, and the paper

I'm working from says:

"Finally the smallest 4-sided polygon surrounding the segmented code [

a convex polygon ] is evaluated. 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 the

vertices of a general polygon surrounding the code".

And I can't find an algorithm for that, perhaps because I'm using all

the wrong words.

I believe I'm looking for the minimal enclosing (convex) quadrilateral

(The segments were originally printed as (broken) squares, but

depending on the perspective they were photographed at, they will have

turned into a quadrilateral).

So far I've found

-minimum enclosing rectangle, both axis aligned ( trivial ) and

non-axis aligned (using rotating calipers)

-smallest enclosing paralellogram

-smallest enclosing triangle

-smallest enclosing circle

-somebody else asking roughly the same question (

http://groups.google.com/group/comp.graphics.algorithms/browse_thread/thread/4f75b8190a9bf5ff/0cc38373fa0c1527?lnk=gst&q=quadrilateral&rnum=65#0cc38373fa0c1527

) 13 years ago (without final answer, of course ;) )

So my questions is: does anybody know such an algorithm, or at least

what the problem is really called?

I appreciate your answers,

So long,

Tyberius Prime

Oct 30, 2006, 2:34:20 PM10/30/06

to

Hello,

I found there's an algorithm claiming to do solve my problem

in O ( n^2 log k log n):

@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"

}

Now all I need to do is understand it and turn it into code;)

So long,

Tyberius Prime

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu