All Questions
Tagged with algorithms plane-geometry
11 questions
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
4
votes
2
answers
4k
views
Curves similarity metric [closed]
I am working on an optical character recognition algorithm that takes vector data (i.e. polylines) as input rather than raster picture. E.g., we have N polyline samples, and when certain polyline is ...
- 151
4
votes
2
answers
213
views
Algorithm for reporting all triangles with unique interior point
What is known about the complexity of and/or practical algorithms for reporting all triplets of points from finite set of at least four points of which no three are collinear in the Euclidean plane, ...
- 13.2k
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
1
answer
288
views
Generalization of notion of convexity
I am searching for the correct term for the following, if it exists.
A set $X\subset \mathbb{R}^2$ is called $r$-convex if for any two points $x_1, x_2\in X$ such that there exists an arc of radius $...
3
votes
1
answer
140
views
Find the smallest circumference of a figure containing n squares [closed]
So there's a figure which contains n squares of 1 x 1, and I have to find the smallest circumference possible. I don't know if there's an algorithm behind this, I've been stuck on this for two hours ...
- 31
2
votes
1
answer
69
views
Maximal opening angle of a polygon from a point [closed]
I'm looking for an algorithm that given a 2D convex polygon and point outside it, returns the two points of the polygon which are the two extremities of the polygon when viewed from that point.
One ...
- 121
2
votes
1
answer
1k
views
Finding integer points inside of a parallelogram
Suppose $P = \{p_1,\ldots,p_4\} \in \mathbb{R}^2$ defines a quadrilateral (here, specifically, a parallelogram). In the particular case I'm dealing with, I know that there exists at least one point ...
- 1,318
1
vote
1
answer
264
views
Could somebody suggest a way to determine if a parallelogram contains another parallelogram?
I thought of one way to do this.
Using the algorithm which determines if a point is inside a parallelogram,
one can determine if the polygon contains the point within $2N$ steps ($N=2$ for ...
- 19
0
votes
3
answers
115
views
Calculating radii allowing for circular placement of polygonal linkage's joints
Given a planar polygonal linkage defined by a sequence of $n$ hinge joints $(j_0,\,\cdots,\,j_{n-1},j_n = j_0)$ with links of fixed lengths $\lbrace\|j_{k+1}-j_k\|=d_k\ |\ 0\le k\lt n\rbrace$ between ...
- 13.2k
0
votes
1
answer
1k
views
Fast way to generate random points in 2D according to a density function
I'm looking for a fast way to generate random points in 2D according to a given 2D density function.
For instance something like this:
Right now I'm using a modified version of "Poisson disc&...
- 121