1
$\begingroup$

I have a set of n random points on a 2D plane, and its convex hull boundary. Some points lie interior to the convex hull boundary. I want to triangulate this in a non-delaunay random fashion, such that it conforms to the points interior to the convex hull boundary (the points inside are vertices of the triangulation) and the convex hull boundary itself. Any ideas would be appreciated.

$\endgroup$
0

1 Answer 1

0
$\begingroup$

I think I might have found a solution.

Given the convex-hull boundary, I can find out all the points that are purely inside the convex-hull boundary. Next, I find the points on the convex hull boundary with the maximum and minimum x-coordinates. Next, I sort all the internal points by their x-coordinates. If these points exist in an appropriate data structure, such as a Doubly Connected Edge List, I add edges between consecutive points in the x-coordinated sorted order. Further I connect the left most point of the convex hull boundary to the left most point of the internal set, and the right most point of the convex hull boundary to the right most point of the internal set. This forms 2 monotone polygons that each can be triangulated in O(n).

$\endgroup$
1
  • $\begingroup$ This site is based on dialog : please react to my answer about median line. $\endgroup$
    – Jean Marie
    May 13, 2023 at 17:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .