System and method for determining alpha values for alpha shapes

Patent metadata

Field	Value
Publication number	US-11532126-B2
Application number	US-202117378480-A
Country	US
Kind code	B2
Filing date	Jul 16, 2021
Priority date	Apr 3, 2018
Publication date	Dec 20, 2022
Grant date	Dec 20, 2022

Abstract

Some embodiments provide a non-transitory machine-readable medium that stores a program. The program receives, from a client device, a percentage value for a set of points. The program further determines a triangulation based on the set of points. The program also determines an alpha value based on the triangulation and the percentage value. The program further determines an alpha shape based on the alpha value. The program also provides the client device the alpha shape.

First claim

What is claimed is:

1. A non-transitory machine-readable medium storing a program executable by at least one processing unit of a device, the program comprising sets of instructions for:
receiving, from a client device, a request for an alpha shape formed from a set of points;
determining a triangulation based on the set of points;
determining a percentage value based on a number of points in the set of points;
determining an alpha value based on the triangulation and the percentage value;
determining an alpha shape based on the alpha value; and
providing the client device the alpha shape.

2. The non-transitory machine-readable medium of claim 1 , wherein determining the alpha value comprises:
determining a list of edges comprising each edge in the triangulation;
determining a length for each edge in the list of edges; and
sorting the list of edges from shortest length to longest length.

3. The non-transitory machine-readable medium of claim 2 , wherein determining the alpha value further comprises:
calculating a value based on the percentage value and a total number of edges in the list of edges;
identifying an edge in the list of edges having an nth shortest length, wherein n equals the value; and
determining the alpha value by dividing the length of the identified edge by a defined value.

4. The non-transitory machine-readable medium of claim 3 , wherein calculating the value comprises determining an integer closest to the product of the percentage value and the total number of edges in the list of edges.

5. The non-transitory machine-readable medium of claim 1 , wherein determining the alpha value comprises:
determining a list of triangles comprising each triangle in the triangulation;
determining an area for each triangle in the list of triangles;
determining a circumcircle for each triangle in the list of triangles;
determining a radius of the circumcircle for each triangle in the list of triangles; and
sorting the list of triangles from shortest radius to longest radius.

6. The non-transitory machine-readable medium of claim 5 , wherein determining the alpha shape value further comprises:
determining a total area of the triangles in the list of triangles;
calculating a value based on the percentage value and the total area; and
determining the alpha value by iterating through the list of triangles from shortest radius to longest radius; while iterating through the list of triangles, adding the area of each triangle to an aggregate area value until the aggregate area value is greater than or equal to the value; and selecting the radius of the last triangle whose area is added to the aggregate area value as the alpha value.

7. The non-transitory machine-readable medium of claim 1 , wherein determining the alpha shape based on the alpha value comprises:
generating a circle having a radius equal to the alpha value; and
iterating through each pair of points in the set of points to identify a set of edges configured to define the alpha shape by including in the set of edges each edge formed by a pair of points in the set of points where the circle can be positioned to touch the pair of points without the circle enclosing any other points in the set of points.

8. For a device, a method comprising:
receiving, from a client device, a request for an alpha shape formed from a set of points;
determining a triangulation based on the set of points;
determining a percentage value based on a number of points in the set of points determining an alpha value based on the triangulation and the percentage value;
determining an alpha shape based on the alpha value; and
providing the client device the alpha shape.

9. The method of claim 8 , wherein determining the alpha value comprises:
determining a list of edges comprising each edge in the triangulation;
determining a length for each edge in the list of edges; and
sorting the list of edges from shortest length to longest length.

10. The method of claim 9 , wherein determining the alpha value further comprises:
calculating a value based on the percentage value and a total number of edges in the list of edges;
identifying an edge in the list of edges having an n th shortest length, wherein n equals the value; and
determining the alpha value by dividing the length of the identified edge by a defined value.

11. The method of claim 10 , wherein calculating the value comprises determining an integer closest to the product of the percentage value and the total number of edges in the list of edges.

12. The method of claim 8 , wherein determining the alpha value comprises:
determining a list of triangles comprising each triangle in the triangulation;
determining an area for each triangle in the list of triangles;
determining a circumcircle for each triangle in the list of triangles;
determining a radius of the circumcircle for each triangle in the list of triangles; and
sorting the list of triangles from shortest radius to longest radius.

13. The method of claim 12 , wherein determining the alpha shape value further comprises:
determining a total area of the triangles in the list of triangles;
calculating a value based on the percentage value and the total area; and
determining the alpha value by iterating through the list of triangles from shortest radius to longest radius; while iterating through the list of triangles, adding the area of each triangle to an aggregate area value until the aggregate area value is greater than or equal to the value; and selecting the radius of the last triangle whose area is added to the aggregate area value as the alpha value.

14. The method of claim 8 , wherein determining the alpha shape based on the alpha value comprises:
generating a circle having a radius equal to the alpha value; and
iterating through each pair of points in the set of points to identify a set of edges configured to define the alpha shape by including in the set of edges each edge formed by a pair of points in the set of points where the circle can be positioned to touch the pair of points without the circle enclosing any other points in the set of points.

15. A system comprising:
a set of processing units; and
a non-transitory machine-readable medium storing instructions that when executed by at least one processing unit in the set of processing units cause the at least one processing unit to:
receive, from a client device, a request for an alpha shape formed from a set of points;
determine a triangulation based on the set of points;
determining a percentage value based on a number of points in the set of points determine an alpha value based on the triangulation and the percentage value;
determine an alpha shape based on the alpha value; and
provide the client device the alpha shape.

16. The system of claim 15 , wherein determining the alpha value comprises:
determining a list of edges comprising each edge in the triangulation;
determining a length for each edge in the list of edges; and
sorting the list of edges from shortest length to longest length.

17. The system of claim 16 , wherein determining the alpha value further comprises:
calculating a value based on the percentage value and a total number of edges in the list of edges;
identifying an edge in the list of edges having an n th shortest length, wherein n equals the value; and
determining the alpha value by dividing the length of the identified edge by a defined value.

18. The system of claim 17 , wherein calculating the value comprises determining an integer closest

Assignees

• Sap Se

Inventors

• Bastian Kai-Niklas
• Gildhoff Hinnerk
• Grouisborn Tim
• Jung Michael

Classifications

• G06T2210/56

  Particle system, point based geometry or rendering · CPC title

• G06T17/20 Primary

  Finite element generation, e.g. wire-frame surface description, {tesselation} · CPC title

• G06T17/205

  Re-meshing · CPC title

• G06T17/10 Primary

  Constructive solid geometry [CSG] using solid primitives, e.g. cylinders, cubes · CPC title

• G06F7/08

  Sorting, i.e. grouping record carriers in numerical or other ordered sequence according to the classification of at least some of the information they carry (by merging two or more sets of carriers in ordered sequence G06F7/16) · CPC title