Questions tagged [computational-geometry]

Question 1

The algorithm in question is from this webpage. The complete algorithm from this webpage is as follows: ...

Question 2

This question is related to my previous posts about overlapping circles, like this one. Another way of overlapping 3 circles looks like this: Once again, my question is, "How can these 3 circles ...

Question 3

I have a set of $n$ points in the plane and I want to find the smallest circumscribed circle that contains them. By circumscribed I mean that the circle must pass through $3$ of the points. Brute ...

Question 4

I'm mainly a programmer, not a mathematician, so please bear with me. I have a sequence of rectangles in 3D space. Each one has a specified pose: position, an orientation (rotation in 3D), and a width ...

Question 5

Let $D\subset\mathbb{R}^{2}$ be a bounded, open, connected polygonal domain whose boundary decomposes (unknown to the observer) as a disjoint union $$ \partial D \;=\; U \,\sqcup\, W $$ where $U$ is ...

Question 6

Given a set of $n$ rectangles $[a, b] × [c, d]$ in a cartesian coordinate plane, calculate the area of their union. My first thought of this problem is by using a simple sweep line algorithm plus a ...

Question 7

I am working on some problem on toric arrangements at the crossroad between topology, combinatorics and algebraic geometry. $\textbf{Setting}$ Let $m,n\geq1$ and let \begin{equation*}\mathcal{S}=\left\...

Question 8

I need to calculate the volume (and centroid, but techniques for both seem to be fairly similar) of the intersection between the unit cube defined by $0 \leq x,y,z \leq 1$ and the halfspace defined by ...

Question 9

I am looking for a way to divide a 2D polygon (possibly with a complex shape, like an "H". These are actually floor layouts of buildings) into several connected sub-regions, where each ...

Question 10

Theorem in question: I understood the first part, I don't understand the converse. Why can we assume that for all $v \in V_{ij}$ point $w_i$ is the nearest neighbor? Can't we say that $w_i$ or $w_j$ ...

Question 11

When a polygon is convex, its medial axis a.k.a. topological skeleton is particularly simple: there are no curved parts; it looks like an undirected tree whose internal nodes are all those points in ...

Question 12

I have discovered two quantities that are very easily computable from the vertex coordinates of a plane quadrilateral which allow to check directly if the quadrilateral is convex, concave, or self-...

Question 13

Given a cubic Bézier curve with control points P0, P1, P2, P3, is there a way to determine whether it approximates a circular arc using only those four points — without evaluating the curve at ...

Question 14

I know the conic combination is A set $C \subseteq \mathbb{R}^n$ is a cone if: $$x \in C \Rightarrow \lambda x \in C \quad \text{for all } \lambda \geq 0$$ Let's take two non-zero, non-colinear ...

Question 15

I have four 3D points A , B , C , D that define a quadrilateral (assumed to be convex) on the surface of a unit sphere (i.e., all points lie on the sphere centered at the origin). These points define ...

Stack Exchange Network

Questions tagged [computational-geometry]

I need help to understand the algorithm that tests if a point lies inside or outside a general 2D polygon

Smallest overlapping circles containing unit circles in each section - Fifth arrangement

Is there an efficient algorithm to find the smallest circumscribed circle to a set of points?

How do I find the straightest path through 3D rectangles?

Is the adaptive jamming complexity for aperture identification $O(m \log m + \log N)$?

Calculate the area of the union of rectangles in a plane

Toric arrangements and system of polynomial equations

Volume/centroid of unit cube cut by plane

How to partition a polygon into contiguous regions with given area ratios?

How does the existence of a second order Voronoi polyhedron imply corresponding first order Voronoi polyhedra to be adjacent?

Simple medial axis algorithm for convex polygons gets unexpectedly tangled up

Found simple quantities to check if a plane quadrilateral is convex, concave or self-intersecting [closed]

How to test if a cubic Bézier approximates a circular arc using only its control points?

Why does the conic combination of two points in two dimension does not contain points outside the rays formed from origin to the two points?

How to test if a point lies inside a spherical quadrilateral?

Hot Network Questions