2,800
questions
1
vote
2
answers
115
views
Parallel Convex Hull Algorithm for 2D Convex Hull of a Simple Polygon
I have a list (with lets say 600) of simple polygons (i.e. no self-intersections) with at least 4 and at max 3000 points.
I want to compute the convex hulls for each of these polygons on the GPU. That ...
0
votes
1
answer
68
views
About Boolean operation Difference
I'm facing a issue about difference boolean operation (Polygon A / Polygon B). When a polygon is not simple, the CGAL::difference() function has a crash. Look the example of a question that I facing.
#...
1
vote
4
answers
128
views
Calculating an average of multiple polygons
I would like to "average" several polygons having a substantial intersection, e.g. these three:
Preferably using a Python library, e.g. Shapely. I don't see a suitable function there, which ...
0
votes
0
answers
25
views
Python-OCC BRepBuilderAPI_Transform causing vertex distribution to change
I am currently developing a geometric application that utilizes 3D Zernike moments to identify similar shapes. While these moments are designed to be rotationally invariant, I have observed an issue ...
3
votes
1
answer
229
views
Compute minimum area convex k-gon in 2d
I am trying to solve the following problem: given a set of points P and a value k, find the area of the smallest convex k-gon defined by a subset of points S of P with |P| = n and |S| = k.
I found ...
2
votes
4
answers
221
views
How do I find the smallest circle that can enclose a polygon?
Using python, how do I find the smallest circle that can enclose a polygon?
A polygon is defined as a set of coordinates that map the vertices inside a 2D plane.
Guidelines:
Input: A list of tuples ...
-1
votes
1
answer
55
views
How to get the upper line of a polygon
I am trying to create an application to automate the workflow of dam analysis for the geotechnical sector I work in. The app takes as input a DXF file that contains the geometry of the dam section. ...
3
votes
0
answers
109
views
Is there a curve-triangle intersection algorithm?
The problem of calculating the intersection between a ray and a triangle is well-known. For this there exists e.g. the Möller-Trumbore intersection algorithm.
For my application I need an algorithm ...
0
votes
1
answer
33
views
Duplicated Points in Polygon_with_holes_2 result of a Minkowski_sum_2
When using CGAL to operate 'Minkwoski_sum_2' and produce 'no-fit-polygons', some polygons resulted with duplicate points. For example, taken from the terminal output (result of the '...
0
votes
0
answers
42
views
Find visibility polyhedron from a point inside it
I have some 3d model meshes from .obj files, which means I have all the vertices and triangles of the mesh at my disposal. I want to find the visibility polyhedron from a point of view inside my mesh.
...
2
votes
2
answers
120
views
How to locate the most sparse point within a defined 2D region?
The core of the problem is to algorithmically determine the coordinates of the point E that maximizes the distance to the nearest other point in the bounded 2D space.
For example, in the space defined ...
0
votes
1
answer
92
views
While finding count of points inside some shape using KD-Tree, do we need to check areas intersection, or just compare depth-appropriate properties?
Let's say we have to find count of points inside some shape in 2D plane.
We can use KD-Tree to solve this. The KD-Tree will partition 2D plane into rectangles, and then we can check intersections ...
0
votes
1
answer
39
views
In solidworks, is there a way to get the direction cosines of a surface normal?
I have a system with an assortment of planes and lines. In order to compare to other models, it would be a lot easier if I could deal with the directions (or direction cosines) of the normals to ...
1
vote
0
answers
42
views
Find all consensus locations of 2D line segment intersections
I have a set of line segments, subsets of which all intersect at some locations. The line segments are noisy though so the intersections points aren't exact and there are some erroneous line segments ...
1
vote
2
answers
77
views
Ovalness of a polygon measure or a classifier
I'm looking for a computationally not very expensive algorithm or a library function to measure ovalness of a polygon or a binary classifier: an oval or not an oval. Here are a few examples of oval ...
0
votes
1
answer
71
views
Compensate IMU pan/tilt
I am building quadcopter with IMU to get orientation in 3D and ultrasound range finder to measure distance to the ground. For some mechanical reasons, IMU is not aligned with quadcopter axis. Range ...
3
votes
2
answers
98
views
derive (approximate) rotation transform matrix (numpy) on a unit sphere given a mapping of vectors (n=12)
While I am aware of vaguely similar questions, I seem to be stuck on this.
Buckminster Fuller introduced a spherical mapping of the world onto an icosahedron - it's known as the Dymaxion Map
A common ...
0
votes
2
answers
55
views
find xyz coordinate inside 3d polygon
I am trying to find a way to get a point definitive inside a 3d polygon (planar)
currently I am trying to do that like this:
let sumX = 0
let sumY = 0
let sumZ = 0
const numPoints = ...
0
votes
1
answer
29
views
How to processing points' attributes(like uv coordinates or normals) in CGAL library?
As known, the cgal library only process the 3d model without points' attributes. But, I have specific models with those attributes(like uv coordinates or normals or colors). I want to find a effective ...
2
votes
0
answers
71
views
Are there effective any-angle pathfinding algorithms for infinite weighted grids?
I am developing a game that involves pathfinding on terrain where different surfaces have different movement costs (e.g., snow, mud, etc.). I need an any-angle pathfinding algorithm that works ...
2
votes
3
answers
89
views
Find two furthest points in a point set in linear time (2-approximation algorithm)
Given a set of n points, find two points which is furthest from each other. We need to use 2-approximation algorithm which means actually, we do not need to accurately find these two points, we just ...
3
votes
2
answers
91
views
Closest edge to a rectangle in a plane of rectangles
I have a 2D plane (with discrete points) that contains arbitrary-sized rectangles and all rectangles are axis aligned. I have their coordinates (upper-left) and sizes (length and breadth).
Suppose I ...
1
vote
1
answer
64
views
How to convert spherical geometry to ellipsoid geometry c++ vertex generation
I have a question on how to generate ellipsoid vertex geometry in c++. I have the following code:
Sphere::Sphere(const LengthT radius, const LengthT a, const LengthT b, const LengthT c, , std::...
0
votes
1
answer
128
views
How to find overlapping area of convex coplanar polygons in 3D?
I have two convex polygons in 3D. They are always flat and vertically aligned. There only in the shapes of squares, pentagons, and a 4-sided polygon where two sides are parallel and the other two ...
0
votes
1
answer
38
views
Check whether the vertices of a triangle are collinear
It's getting a bit complicated.
Unfortunately, our professor uses his own library. Maybe someone can still help me. It's generally about geometry and homogeneous coordinates. The task was to construct ...
0
votes
1
answer
41
views
Calculate the outline of an abstract shape with holes
I want to code a room builder that creates a room out of selected cells. For example, here's a shape I drew:
To create the room, I believe I'd need to calculate the outline of this shape, including ...
1
vote
1
answer
117
views
Implementing arc-length parameterization and adaptive subdivision for Bézier curves
I'm attempting to determine multiple aspects about a Bézier curve programmatically. I want to be able to find the arc length of the curve, points positioned along the curve with higher density at ...
0
votes
0
answers
44
views
Algorithm of projecting nurbs/curves on to cylinder and sphere
I am looking for the algorithm to project nurbs(or other curves)onto cylinder and sphere?related books or articles will also help, thanks!!
I find some method like first project start point onto the ...
0
votes
0
answers
15
views
How to morph enclosing mesh according to the enclosed mesh?
I am quite new to meshing and mesh manipulation. I am working on a problem consiting of meshes A, B, and C. The mesh C completely encloses the meshes A and B as shown in the attached figure. I applied ...
1
vote
1
answer
63
views
How to solve this question using a range tree?
Question:
we’re given n treasures t1, ..., tn in the plane. Each treasure ti has an associated value vi. Your task is to design an
algorithm that returns the location of an axis-aligned k × k square
...
0
votes
1
answer
154
views
How to calculate sharp corners for polygons with rounded corners?
Basically this question, but in reverse: How to calculate rounded corners for a polygon?
I have (at least) a polygon made up of edges which has round corners in it and I would like to completely ...
1
vote
1
answer
37
views
How to find all possible new positions with a given distance to one or more given 3D coordinates?
Suppose we have a set of 3D coordinates (x, y, z) in a cubic box, just like a molecule or a unit of crystal lattice in chemistry. Now I want to place a new “atom” inside the box, and I want it to be ...
3
votes
1
answer
99
views
Fast footpoint computation over polygonal lines in MATLAB
Problem definition
Consider a 2xm dataset matrix D encoding m 2-dimensional noisy observations. I want to project the dataset D over a 2xN open polygonal line V encoded by N 2-dimensional vertices. ...
3
votes
1
answer
91
views
Remove leftmost point from convex hull
I have a set of N 2d points sorted by x coordinate and upper convex hull for this set. I'm trying to update current convex hull after I've deleted the leftmost point from set or inserted new point to ...
1
vote
0
answers
60
views
How can I speed up CGAL::compute_intersection_points() without changing kernel into EPICK?
I want to calculate the intersection points between several polygons (including their vertices), more precisely the intersection points between their edges. I wrote the following pseudocode for doing ...
0
votes
1
answer
169
views
Sweep shape along 3D path in Python
Using Python (3.10.14 at the time of writing), how could one build a 3D mesh object (which can be saved in either STL, PLY or GLB/GLTF format) using:
a 3D path as the sweep axis,
a 2D rectangular ...
0
votes
0
answers
18
views
'plotAtlas' function in Morpho package
I am trying to plot my mesh with its respective landmarks and semi-landmarks. I provided all matrices but when I plotted the mesh it appeared completely empty. For some reason my LMs and semi-...
0
votes
2
answers
72
views
Encounter problem at different speed/start point algorithm design
Riding jet skis is popular again, so let’s have a race! Unfortunately not all jet skis are equally fast, so to make the race more fair, the jet skis don’t all start at the same position (i.e., there’s ...
0
votes
0
answers
48
views
Selecting suitable triangles to intersect with a line
Allow me to describe the situation. I have a 3D triangular mesh with N triangles (approx. 1e5 triangles) and M lines (in the same order of magnitude as the triangles but not necessary the same number)....
1
vote
1
answer
72
views
Merging Geodataframe Polygons to Meet Population Threshold in Python
I have a geodataframe in Python containing polygons representing various regions, with each region having its respective population count. My goal is to merge these polygons in a way that ensures each ...
0
votes
1
answer
67
views
Rotating a 3D body in python results in holes in the body
I have a 3D body, let's say a cuboid, which I want to rotate. For simplicity, let's assume it's just rotation around the x-axis. So I use the corresponding rotation matrix R and multiply it with the ...
0
votes
0
answers
19
views
SageMath: Create a triangle with specific angles in Hyperbolic space, eg., Upper Halfspace Plane
I'm trying to create a triangle in hyperbolic space, specifically in the Upper Halfspace Plane, using SageMath. I would like to specify the angles of the triangle and generate its corresponding ...
1
vote
1
answer
148
views
Implementing Jarvis Binary Search in Chan's algorithm
Both Wikipedia and Chan's paper state that once Graham's scan has been done to the $n//m$ subsets of our original set $P$, since each subhull is ordered from least to most CCW rotation from its lowest ...
1
vote
1
answer
47
views
How to find centroid snapped to grid via Shapely?
When I use shapely to find a centroid, it gets me fractional values, even if I set the precision:
bbox = shapely.Polygon(coords)
shapely.set_precision(bbox, grid_size=1)
centroid = bbox.centroid
print(...
2
votes
1
answer
111
views
Find the largest rectangle that doesn't intersect any given polygon
I'm given an image with several (not necessarily convex) polygons defined, as well as a single point of interest.
I need to find the largest rectangle (parallel to the axes of the image - not rotated) ...
3
votes
2
answers
148
views
Generate P random N-dimensional points from list of ALL possible pairwise distances
I would like to generate random N-dimensional points with the constraint of having precise Euclidean distances (known) between each other.
Number of points P = 100
Number of dimensions of the ...
1
vote
2
answers
218
views
Fast way to find closest line segment for a large set of planar points [Python]
Problem
Given are n=10000 points and m=1000 line segments in a plane. The task is to determine the closest segment to each point. A fast solution in Python is preferred.
Specifications
Line segments ...
1
vote
2
answers
386
views
how to check if all the faces face outward
Situation: I am using Open3D python,The mesh generation algorithm ( like ball pivot, poisson reconstruction ) are dependent on normal direction. I used estimate_normals and ...
2
votes
1
answer
120
views
Counting the number of polygons containing origin in 2D
Suppose we have n points in 2D space in convex position. There are precisely choose(n, k) different convex k-gons (non-degenerate). Is there any existing algorithm that runs in O(n log n) time (for a ...
2
votes
0
answers
133
views
Seeking Algorithm for Generating Non-Overlapping Polygons from Path Segments for Pattern Filling
I'm in search of an algorithm that can accept a series of vertices (e.g., v1, v2, v3, ...) defining a path, along with a specified line width, and generate a polygon for each path segment (like v1 to ...