All Questions
Tagged with computational-geometry polygons
21 questions
20
votes
2
answers
25k
views
Partitioning a polygon into convex parts
I'm looking for an algorithm to partition any simple closed polygon into convex sub-polygons--preferably as few as possible.
I know almost nothing about this subject, so I've been searching on Google ...
- 201
15
votes
1
answer
616
views
Acute triangles in "obtuse" polygons?
Let $P$ be a convex polygon. Suppose every interior angle of $P$ is obtuse. Is it always the case that there exist three vertices $p, q, r$ of $P$ such that $\triangle pqr$ is acute?
I conjecture ...
- 173
10
votes
1
answer
9k
views
Get Largest Inscribed Rectangle of a Concave Polygon
I'm looking for an algorithm to find a set of largest inscribed rectangles of a concave polygon where each rectangle must be collinear with one of the edges of the polygon.
In other words, I want to ...
- 325
9
votes
5
answers
13k
views
Get a point inside a polygon
I have a 2D polygon of arbitrary geometry. I need to find any point that is inside of that polygon. Taking the center won't work, because the polygon might not be convex. Is there a way to quickly ...
- 201
8
votes
2
answers
339
views
Angle subtended by the shortest segment that bisects the area of a convex polygon
Let $C$ be a convex polygon in the plane and let $s$ be the shortest line segment (I believe this is called a "chord") that divides the area of $C$ in half. What is the smallest angle that $s$ could ...
- 113
8
votes
1
answer
231
views
Counting polygons in arrangements
For an arrangement of lines $\cal{A}$ in the plane, an
inducing polygon $P$ is a simple polygon satisfying:
(a) every edge $e$ of $P$ lies on some line $\ell$ of $\cal{A}$, and
(b) every line $\ell \...
- 151k
6
votes
1
answer
2k
views
Given a set of 2D vertices, how to create a minimum-area polygon which contains all the given vertices?
Not sure whether this question belongs here or math.stackexchange.
You can assume that all the vertices are unique. The given vertices can be the vertices of the polygon, thus they do NOT have to be ...
- 163
5
votes
1
answer
234
views
Generalizations of the "Curious Tiger" Polygon
I actually don't know, whether the polygon I describe here already has name, but let me explain the problem, that is solved by the polygon, with a little story:
Imagine a flat terrain with bushes of ...
- 13.2k
4
votes
2
answers
805
views
Fitting one Polygon in another
I have two Polygons A and B and I want to find the position, rotation and scale of B, so it fits into A and has the maximum Area possible. Also both can be concave.
I did some research but couldn't ...
- 41
4
votes
2
answers
390
views
Construct polygon/polyhedron containing all points not externally visible w.r.t given polygon/polyhedron?
Is there an algorithm to construct a polyhedron containing all points in space for which there exists no ray to infinite not intersecting a given polyhedron?
In 2D, we could consider polygons. For ...
- 723
4
votes
1
answer
2k
views
Algorithms for covering a rectilinear polygon using the same multiple rectangles
Sorry for the crossing-posting: original post is here
All angles of the polygon (representing a room) are right. It may be convex or concave. Use rectangles of the same size (representing a sensor ...
- 143
3
votes
3
answers
2k
views
Is there a simple criterion to determine if two parallelograms intersect?
Assume we are given two parallelograms in the plane. How can I check if their intersection is nonempty?
Note that I do not need to actually find the intersection.
- 979
3
votes
0
answers
58
views
Find shift direction for min overlap area of 2 polygons
I have 2 arbitrary polygons (concave or convex) with certain overlap.
Now there is some relative shift between these 2 polygons (vector s with a constant length).
I want to find the direction of s ...
- 31
2
votes
1
answer
173
views
Calculating the "Belvedere Hull" of a Simple Planar Polygon
As an informal motivation the problem, imagine a tower with polygonal footprint, that is located in a beautiful landscape, the "Belvedere Hull" is then related to the directions, in which one would ...
- 13.2k
2
votes
1
answer
441
views
Build reversed No-Fit-Polygon
I need some robust algorithm to optimally fit one non-convex polygon into another. The destination one can contain holes.
Recently I found scholarly articles on this subject:
One of them describes ...
2
votes
0
answers
58
views
Complexity of existence of simple polygonalization with prescribed area?
This is a followup on my previous question. Fekete proved the NP-completeness of deciding the existence of simple polygonalization with minimum (or maximum) enclosed area (simple polygonalization is ...
- 2,993
1
vote
1
answer
51
views
On triangulations and "coverage" of circumcircles
Let $P$ be a convex quadrilateral defined by four vertices $a$, $b$, $c$, and $d$. Suppose that the circumcircle of $\triangle abd$ contains $c$.* Let $D(\triangle abc)$ to denote the area enclosed by ...
- 173
1
vote
0
answers
66
views
Non-Convex Polygons with "Antipodal Visibility"
by "antipodal visibility" of planar, simple polygons I mean the following property:
if two points $p$ and $q$ on the polygon's boundary divide the polygon's boundary into two polylines of equal length,...
- 13.2k
0
votes
2
answers
3k
views
Determine the boundary points of a set of points [closed]
I have a set of points $S=\{(x_1,y_1),(x_2,y_2),\ldots,(x_n,y_n)\}$. Then how to find the boundary points (which is a subset of $S$) of $S$?
There are methods like convex hull, concave hull and $\...
- 17
0
votes
1
answer
51
views
What is the most dense sample for which the Crust algorithm returns an incorrect polygonal reconstruction?
The Crust algorithm by Amenta, Bern, and Eppstein computes a polygonal reconstruction of a smooth curve $C$ without boundary from a discrete set of sample points $S$. It is known that if $S$ is an a $\...
- 413
0
votes
1
answer
575
views
Detect perimetral edges of a polygon [closed]
I'm developing a building editor. Users can draw rooms by adding angles (vertices of the room) with a left click. Clicking on an existing angle closes the room and fills the floor by using the ...
