Skip to main content
Filter by
Sorted by
Tagged with
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 ...
Merlin1896's user avatar
  • 1,801
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. #...
Bruno Santos's user avatar
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 ...
Paul Jurczak's user avatar
  • 7,940
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 ...
user3748950's user avatar
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 ...
Gianmarco's user avatar
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 ...
makeyourownmaker's user avatar
-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. ...
Alexandre Vitor's user avatar
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 ...
jonewa's user avatar
  • 31
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 '...
Bruno Santos's user avatar
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. ...
Konstantinos's user avatar
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 ...
Artyom Ionash's user avatar
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 ...
Szyszka947's user avatar
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 ...
JB2's user avatar
  • 103
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 ...
nickponline's user avatar
  • 25.8k
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 ...
Paul Jurczak's user avatar
  • 7,940
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 ...
Andrey's user avatar
  • 13
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 ...
Konchog's user avatar
  • 2,106
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 = ...
pcace's user avatar
  • 560
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 ...
Peter Hsu's user avatar
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 ...
josima's user avatar
  • 21
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 ...
ricolxwz's user avatar
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 ...
Harsh's user avatar
  • 198
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::...
Peter F's user avatar
  • 11
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 ...
MaxS14's user avatar
  • 5
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 ...
zebat's user avatar
  • 1
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 ...
Meowing's user avatar
  • 47
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 ...
etzabo's user avatar
  • 21
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 ...
Helloexcel's user avatar
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 ...
Prakhar's user avatar
  • 61
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 ...
ricolxwz's user avatar
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 ...
user362461's user avatar
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 ...
Tony Wu's user avatar
  • 19
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. ...
matteogost's user avatar
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 ...
Egor's user avatar
  • 147
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 ...
Lryan's user avatar
  • 11
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 ...
swiss_knight's user avatar
  • 7,403
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-...
Bruno Ferreto Fiorillo's user avatar
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 ...
ricolxwz's user avatar
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)....
juan zaragoza's user avatar
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 ...
J.Tmr's user avatar
  • 137
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 ...
Alf's user avatar
  • 1,949
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 ...
Rowing0914's user avatar
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 ...
user716881's user avatar
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(...
SRobertJames's user avatar
  • 8,999
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) ...
SRobertJames's user avatar
  • 8,999
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 ...
qgius's user avatar
  • 33
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 ...
granular_bastard's user avatar
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 ...
uk2797's user avatar
  • 81
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 ...
Neremintos's user avatar
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 ...
Martin Ždila's user avatar

1
2 3 4 5
56