Skip to main content
Share Your Experience: Take the 2024 Developer Survey
12 votes

How can I determine if two vertices on a polygon are consecutive?

As the polygon is convex, it is simple! Two vertices are consecutive if all other vertices are located on the same side of the line that goes through these two points. This means that the cross ...
OmG's user avatar
  • 3,572
5 votes

How can I determine if two vertices on a polygon are consecutive?

Given that the polygon is convex, its centroid $C$ is in its interior. Test the gradients of the lines $CV$ for each vertex $V$. This gives a linear time test.
Peter Taylor's user avatar
  • 2,082
4 votes

How can I determine if two vertices on a polygon are consecutive?

An alternative to OmG's answer (which is great) would be to sort your points into an ordered array where you can find any points neighbors by looking at the points on either side. This method would be ...
Tim Andrews's user avatar
4 votes
Accepted

Check if intersection of several 2D half-planes is empty

Your problem can be solved in linear time. This paper describes a method to solve a system of $n$ linear inequalities with at most two variables per inequality and $m$ distinct variables in total in $...
Steven's user avatar
  • 29.5k
3 votes

Merging rectangles into rectilinear polygon

Form a list of the $4n$ edges making up the $n$ rectangles. Delete every edge that appears twice. The edges that remain describe the outside of the polygon. If you want to list these edges in ...
j_random_hacker's user avatar
3 votes
Accepted

How to efficiently find line-segment intersections between two sets?

The problem you describe is known as the red-blue intersection problem. Here, we have a red set of $n_1$ segments and a blue set of $n_2$ segments and we know that there are only intersections between ...
Discrete lizard's user avatar
  • 8,248
3 votes
Accepted

Compute visible vertices of a polygon

Yes, there are more algorithms to do so in $\mathcal O(n)$. The first is dated back to ElGindy and Avis in 1981, Lee 1983 and Joe & Simpson in 1985. The visibility algorithms use stack (the first ...
Evil's user avatar
  • 9,465
3 votes

Finding all faces in a wireframe mesh

After conducting more research I did find a solution, but first I will examine solutions suggested by posters and considered by myself and review why they didn't work. ...
hgs3's user avatar
  • 253
3 votes

An algorithm to find the area of intersection between a convex polygon and a 3D polyhedron?

You have a 2D convex polygon $G$, and a 3D polyhedron $H$. Let $P_G$ denote the plane that the polygon is contained in. The following should work: Their intersection is a 2D polygon. You can find ...
D.W.'s user avatar
  • 161k
2 votes
Accepted

Running time for Testing Polygonal Neighbours for Intersection or Inclusion

In the paper you reference, Theorem 5 is a claim about simple polygons, where Theorem 6 deals with convex polygons, which are a special kind of simple polygons. The 'As we have seen before, ...' ...
Discrete lizard's user avatar
  • 8,248
2 votes

Convex-hull of a star shaped polygon in O(n)

Graham scan for a convex hull works if you have an ordering of points $a_1,a_2,...a_N$ such that you have a sequence $p_1 < p_2 <...< p_k$ where your convex hull is $a_{p_1}, a_{p_2},...,a_{...
S. Pek's user avatar
  • 201
2 votes

Is there an efficient algorithm to extract the farthest ends of a thin contour?

Run Flood Fill from any point and the farthest points in the both directions are your result. If you find that the distance in one of the directions is zero it means that it was one of them. ...
Evil's user avatar
  • 9,465
2 votes
Accepted

Simplex Algorithm: Why must the optimal value of the LP lie on the face or vertex of a polyhedron?

Suppose $P = \lbrace x: Ax \leq b \rbrace$ is the polyhedra, where $x \in \mathbb{R}^n$. Further assume $P$ is full dimensional, then let $x_0$ be some interior point in P. Let $c \in \mathbb{R}^n$ (...
csTheoryBeginner's user avatar
2 votes
Accepted

Selecting a polygon within an array of complex polygons

I would use a winding number algorithm. There are a few, but the fastest goes like this:Imagine a line from your point along the positive x-axis. Now, for every edge of your polygon, determine if it ...
Gabriel Rohweder's user avatar
2 votes

Is Dual Graph of a Triangulation of a Polygon Tree?

Below is an example of a polygon with a single hole. The red area is the interior of the polygon, and the white triangle in the center is the hole (which lies outside the polygon). In the figure, I've ...
Discrete lizard's user avatar
  • 8,248
2 votes
Accepted

assign points to non-overlapping rectangles

Most spatial indexes should be good, especially if your rectangles are axis aligned. Spatial indexes typically have about $O(log{M})$ insertion time so you could build in index in $O(M * log{M})$. ...
TilmannZ's user avatar
  • 764
2 votes
Accepted

Finding the Point with Maximum Distance from the Boundary of a Closed Polygon in 2D Euclidean Space

The medial axis is the set of points in the interior of the shape that has two closest points on the boundary. Intuitively, the largest "incircle" in a polygon must touch the boundary at at ...
Pseudonym's user avatar
  • 22.2k
1 vote

How to find simple polygons in a complex polygon created by two lines

Please take a look at the DCEL data structure, which is normally used for representation and processing of polygonal subdivisions of the plane. This data structure usually stores three kinds of ...
HEKTO's user avatar
  • 3,098
1 vote

Euler polygon division algorithm

You can use the formula to count the number of division to generate them. Suppose you want to generate a division of a $n$-polygon whose vertices are $1, 2, …, n$. We know that there are $C_{n-2}$ ...
Nathaniel's user avatar
  • 15.7k
1 vote

Euler polygon division algorithm

See: Hurtado and Noy, Graph of triangulations of a convex polygon and tree of triangulations, Computational Geometry 13 (1999) pp179–188. Section 3 of that paper gives a relatively straightforward ...
Pseudonym's user avatar
  • 22.2k
1 vote
Accepted

Is there a computationally optimal point-in-polygon solution (for a dynamic scenario)?

I can list three candidate approaches. I'm not sure how to choose among them -- you might need to experiment among them to see which will work best in your situation. Approach #1: sweepline algorithm ...
D.W.'s user avatar
  • 161k
1 vote

Find an edge that is completely visible from point outside a polygon (Convex Hull)

It is not too hard. connect the point to the end-point of an edge. If none of these two segments has an intersection with convex-hull, it means you can see that edge completely (as you consider a ...
OmG's user avatar
  • 3,572
1 vote

Joining points of polygon in correct order

Start from the leftmost point $x_0$ (the one with minimum $x$-coordinate). If there are ties break them in favor of the point with minimum $y$ coordinate. Suppose for simplicity that there are no ...
Steven's user avatar
  • 29.5k
1 vote

Efficient rasterisation of vector image with polygons

The quad tree suggestion by D.W. is interesting. I want to expand on it here. The principle of it is to break the area into big (and then progressively smaller) squares and check whether these squares ...
Thanassis's user avatar
  • 121
1 vote

Efficient rasterisation of vector image with polygons

An alternative approach is to use a quad-tree. One approach is to store each polygon in the deepest node that corresponds to a region that wholly contains the polygon. Given a test point, you ...
D.W.'s user avatar
  • 161k
1 vote

Convert a polygon mesh into a b-spline surface

Without any assumptions on the input mesh, you cannot in general get a single b-spline surface that replicates an arbitrary polygon mesh. You would need the mesh to be connected, but you would also ...
Aaron Rotenberg's user avatar
1 vote
Accepted

Detecting rotational symmetries of spatial structures

Here is one approach to identify all rotational symmetries of the graph: Pick any three vertices, $v_1,\dots,v_3$. Loop over all possible combinations of three vertices $w_1,\dots,w_3$. For each ...
D.W.'s user avatar
  • 161k
1 vote

Using visible line segments to compute a visibility polygon

First, assume we already have a list $L$ with all segments in $P$ that are at least partially visible from $p$, ordered by the smallest angle $\theta$ such that a segment is visible from $p$ at angle $...
Discrete lizard's user avatar
  • 8,248
1 vote

Is there an efficient algorithm to extract the farthest ends of a thin contour?

Build a graph, with one vertex per black pixel, and an edge between two pixels if they are adjacent. Compute all-pairs shortest-path distances $d(x,y)$. For each vertex $x$, compute $$f(x) = \max \{...
D.W.'s user avatar
  • 161k

Only top scored, non community-wiki answers of a minimum length are eligible