Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
?
Solved

Largest Inscribed Circle in a Closed Polygon

Posted on 2004-04-12
3
Medium Priority
?
702 Views
Last Modified: 2007-12-19
Hi Experts,

Given a set of points that form a closed polygon, how do I determine the largest inscribed rectangle of that polygon?

I've seen examples online for how to determine the inscribed rectangle of a circle or triangle, but I'm

dealing with shapes that aren't necessarily circles or triangles. Is this even possible?

Thanks!

-Me
0
Comment
Question by:CPOsosky
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
3 Comments
 
LVL 27

Expert Comment

by:aburr
ID: 10807451
Your title asks for a circle, your body asks for a rectangle.
-
I think the question as asked will be impossible to answer in general with a finite number of words. The first problem is to draw the polygon. The answer will depend on the order in which the points are connected.
0
 

Author Comment

by:CPOsosky
ID: 10807735
Sorry. Typo in the title.

I'm looking for the largest inscribed RECTANGLE of a polygon.

Here's an example:

Given points A, B, C, D, E

Drawing order goes from

A to B
B to C
C to D
D to E
E to A

The points can have varying distances between them.

Line segments only intersect at the end points.

-Me












0
 
LVL 45

Accepted Solution

by:
sunnycoder earned 1000 total points
ID: 10810586
this is a special case for largest empty rectangle algorithms ... It is still an active research topic

http://portal.acm.org/citation.cfm?id=41988&dl=ACM&coll=portal
http://portal.acm.org/citation.cfm?id=767364&dl=ACM&coll=portal

I had worked on largest empty isothetic rectangles but not on largest empty rectangles ... but it is possible and the above links have the algorithms too ... I think you will have to register to view the paper
0

Featured Post

On Demand Webinar - Networking for the Cloud Era

This webinar discusses:
-Common barriers companies experience when moving to the cloud
-How SD-WAN changes the way we look at networks
-Best practices customers should employ moving forward with cloud migration
-What happens behind the scenes of SteelConnect’s one-click button

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

A Guide to the PMT, FV, IPMT and PPMT Functions In MS Excel we have the PMT, FV, IPMT and PPMT functions, which do a fantastic job for interest rate calculations.  But what if you don't have Excel ? This article is for programmers looking to re…
Lithium-ion batteries area cornerstone of today's portable electronic devices, and even though they are relied upon heavily, their chemistry and origin are not of common knowledge. This article is about a device on which every smartphone, laptop, an…
Finds all prime numbers in a range requested and places them in a public primes() array. I've demostrated a template size of 30 (2 * 3 * 5) but larger templates can be built such 210  (2 * 3 * 5 * 7) or 2310  (2 * 3 * 5 * 7 * 11). The larger templa…
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201…
Suggested Courses

715 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question