CN119359926B - Method and equipment for generating area of irregular polygonal plane in geometric engine - Google Patents
Method and equipment for generating area of irregular polygonal plane in geometric engine Download PDFInfo
- Publication number
- CN119359926B CN119359926B CN202411901820.8A CN202411901820A CN119359926B CN 119359926 B CN119359926 B CN 119359926B CN 202411901820 A CN202411901820 A CN 202411901820A CN 119359926 B CN119359926 B CN 119359926B
- Authority
- CN
- China
- Prior art keywords
- polygon
- area
- edge
- geometric
- plane
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T17/00—Three dimensional [3D] modelling, e.g. data description of 3D objects
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T7/00—Image analysis
- G06T7/60—Analysis of geometric attributes
- G06T7/62—Analysis of geometric attributes of area, perimeter, diameter or volume
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T2207/00—Indexing scheme for image analysis or image enhancement
- G06T2207/10—Image acquisition modality
- G06T2207/10004—Still image; Photographic image
- G06T2207/10012—Stereo images
Landscapes
- Physics & Mathematics (AREA)
- Engineering & Computer Science (AREA)
- Geometry (AREA)
- General Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Computer Vision & Pattern Recognition (AREA)
- Computer Graphics (AREA)
- Software Systems (AREA)
- Image Generation (AREA)
Abstract
The application provides a method and equipment for generating the area of an irregular polygonal plane in a geometric engine, which provide the area generating capability for the complex shape of the geometric engine, namely, the irregular polygonal plane, are not limited by the influence of circular arc edges in the irregular polygonal plane any more, so that the irregular polygonal plane with the circular arc edges can be accurately processed, and the accuracy of the generated area is ensured.
Description
Technical Field
The present application relates to the technical field of geometric modeling, and in particular, to a method for generating an area of an irregular polygonal plane in a geometric engine, a computer device, a computer program product, and a computer readable storage medium.
Background
The creation of models in geometric engines often involves various complex shapes, particularly irregular polygonal planes containing curved edges, such as rounded edges. The area generation involved in the geometric engine processing of the irregular polygonal plane containing the circular arc edges is generally not realized by simple formula calculation, and various traditional operations are not directly applicable, so that more complex geometric processing and more complex algorithm support are required.
For example, in some geometric engines, the area calculation is further refined by detecting the distribution pattern of the circular arc edges, such as the start angle, the end angle, and the like, and the area calculation is corrected according to the distribution of the circular arc edges.
Therefore, the geometric engine is influenced by the circular arc edge to carry out complex operation on the processing of the irregular polygon plane, and accurate area processing is difficult to realize.
Disclosure of Invention
The application aims to solve the technical problem that a geometric engine cannot accurately and rapidly generate an area for an irregular polygonal plane with a circular arc edge.
According to an aspect of an embodiment of the present application, there is disclosed a method for generating an area of an irregular polygonal plane in a geometric engine, a framework of the geometric engine including a data input interface, an edge type recognition service, and an area calculation service, and performing geometric operations through data transfer and collaboration with each other, the method comprising:
Loading geometric data through the data input interface, wherein the geometric data is a geometric description file for constructing a geometric model, and the geometric data provides an irregular polygonal plane covered on the surface for the constructed geometric model;
the edge type identification service responds to the loading of geometric data, and identifies the included arc edge to the obtained irregular polygon plane, wherein the geometric engine is used for executing geometric operation to the irregular polygon plane, and the geometric operation comprises geometric attribute calculation of the irregular polygon plane;
Performing arc chord processing operation, taking chords corresponding to the arc edges as edges, and generating polygons through the obtained edge sets to obtain polygons mapped by the irregular polygon planes;
Calculating the area of the polygon to obtain the polygonal area of the polygon formed by chords corresponding to the arc edges;
And processing the polygonal area according to the circular arc distribution on the irregular polygonal plane to obtain the area of the irregular polygonal plane.
According to one aspect of an embodiment of the present application, the irregular polygonal plane includes at least one rounded edge.
According to an aspect of the embodiment of the present application, the performing the chord-wise processing operation of the circular arc uses a chord corresponding to the circular arc edge as an edge, and generates a polygon through the obtained edge set to obtain the polygon mapped by the irregular polygon plane, including:
Pulling a chord identifying the obtained arc edge, wherein the chord is connected with the arc edge at the end point of the adjacent edge of the irregular polygonal plane;
And forming continuous edges by the strings and edges formed by line segments on the irregular polygonal plane, wherein the obtained edges are gathered to form a closed interval, and the closed interval is a polygon mapped by the irregular polygonal plane.
According to an aspect of the embodiment of the present application, the calling the area calculation service to calculate the area of the polygon to obtain the polygon area of the polygon formed by the chords corresponding to the circular arc edge includes:
calling an area calculation service to split the polygon into a plurality of sub-convex polygons, wherein the sub-convex polygons are formed into the polygon without overlapping and gaps;
And respectively calculating the area of each sub-convex polygon and polymerizing to obtain the polygon area of the polygon.
According to an aspect of the embodiment of the present application, the calculating the area of each sub-convex polygon and aggregating to obtain the polygon area of the polygon includes:
Taking any vertex for each sub-convex polygon, and constructing at least one triangle with each side of the sub-convex polygon which does not contain the vertex;
And calculating the areas of all triangles, and converging the areas of all triangles to obtain the areas of the sub-convex polygons.
According to an aspect of the embodiment of the present application, the processing the polygonal area according to the circular arc distribution on the irregular polygonal plane to obtain the area of the irregular polygonal plane includes:
Identifying the direction of the arc edge on the plane of the irregular polygon;
And processing the arc area corresponding to the arc edge according to the orientation to obtain the area of the irregular polygonal plane.
According to one aspect of an embodiment of the application, the orientation includes inward and outward recessions toward the interior of the polygon to which the irregular polygon plane is mapped.
According to one aspect of an embodiment of the present application, a computer device is disclosed comprising a memory, a processor and a computer program stored on the memory, the processor executing the computer program to carry out the steps of the method as described above.
According to one aspect of an embodiment of the application, a computer program product is disclosed, comprising a computer program which, when executed by a processor, implements the steps of the method as described above.
According to one aspect of an embodiment of the present application, a computer-readable storage medium is disclosed, on which a computer program is stored which, when being executed by a processor, implements the steps of the method as described above.
According to one aspect of an embodiment of the present application, a computer device is disclosed comprising a memory, a processor and a computer program stored on the memory, the processor executing the computer program to carry out the steps of the method as described above.
According to one aspect of an embodiment of the application, a computer program product is disclosed, comprising a computer program which, when executed by a processor, implements the steps of the method as described above.
According to one aspect of an embodiment of the present application, a computer-readable storage medium is disclosed, on which a computer program is stored which, when being executed by a processor, implements the steps of the method as described above.
The embodiment of the application is configured for the geometric engine in architecture, the geometric engine is provided with the geometric attribute computing functions such as the area in modeling capacity by the data input interface, the edge type recognition service and the area computing service which execute geometric operation through mutual data transmission and cooperation, so that the area generation of the irregular polygon plane covered on the geometric model is implemented for the geometric model loaded in the geometric engine, and the area of the irregular polygon plane is accurately and quickly generated in quick modeling.
Specifically, in the embodiment of the application, an irregular polygon plane in a geometric engine is obtained by loading geometric data through a data input interface, for the irregular polygon plane, an edge type identification service firstly identifies the existence of an arc edge on the irregular polygon plane in response to the loading of the geometric data so as to acquire that the irregular polygon plane contains the arc edge, the irregular polygon plane with the arc edge needs to be processed, in the process of processing the irregular polygon plane with the arc edge, the chord corresponding to the arc edge is used as an edge in the arc chord processing operation, the obtained edge set is used for generating a polygon to be mapped by the irregular polygon plane, the area calculation service is invoked for carrying out the area calculation of the polygon to obtain the polygon area corresponding to the arc edge, and finally the area of the irregular polygon plane can be finally obtained according to the arc distribution processing on the irregular polygon plane, so that the irregular polygon plane with the arc edge is not limited by the influence of the arc edge any more, the generated area is accurately processed, and the accuracy of the generated area is ensured.
Other features and advantages of the application will be apparent from the following detailed description, or may be learned by the practice of the application.
It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory only and are not restrictive of the application as claimed.
Drawings
The above and other objects, features and advantages of the present application will become more apparent by describing in detail exemplary embodiments thereof with reference to the attached drawings.
FIG. 1 illustrates a flow chart of a method of generating an area of an irregular polygon plane in a geometry engine according to one embodiment of the present application.
Fig. 2 is a flowchart of a method for describing a polygon step of performing a chordization processing operation of the circular arc according to the corresponding embodiment of fig. 1, wherein chords corresponding to the circular arc edges are taken as edges, and a polygon is generated through the obtained edge set to obtain an irregular polygon plane map.
Fig. 3 is a flowchart of a method for describing the steps of obtaining the polygonal area of the polygon formed by the chords corresponding to the circular arc edges by performing the area calculation of the polygon for the call area calculation service according to the corresponding embodiment of fig. 1.
Fig. 4 is a flowchart describing a method for calculating the area of each sub-convex polygon and aggregating the areas of the polygons to obtain the polygons, respectively, according to the corresponding embodiment of fig. 3.
Fig. 5 is a flow chart of a method for describing the steps of processing the polygonal area to obtain the area of the irregular polygonal plane according to the circular arc distribution on the irregular polygonal plane, according to the corresponding embodiment of fig. 1.
FIG. 6 is a schematic diagram illustrating the type of orientation that a polygon mapped to an irregular polygon plane protrudes outward, according to one embodiment.
FIG. 7 is a schematic diagram illustrating the type of orientation that is concave inward toward the interior of a polygon to which an irregular polygon plane is mapped, according to one embodiment.
Fig. 8 is a schematic diagram of the direction determination of the circular arc edge according to the embodiment shown in fig. 6.
Fig. 9 is a schematic diagram illustrating the determination of the direction of the circular arc edge according to the embodiment shown in fig. 7.
Detailed Description
Example embodiments will now be described more fully with reference to the accompanying drawings. However, the exemplary embodiments may be embodied in many different forms and should not be construed as limited to the examples set forth herein, but rather, the exemplary embodiments are provided so that the description of the present application will be more complete and thorough, and will fully convey the concept of the exemplary embodiments to those skilled in the art. The drawings are merely schematic illustrations of the present application and are not necessarily drawn to scale. The same reference numerals in the drawings denote the same or similar parts, and thus a repetitive description thereof will be omitted.
Furthermore, the described features, structures, or characteristics may be combined in any suitable manner in one or more example embodiments. In the following description, numerous specific details are provided to give a thorough understanding of example embodiments of the application. One skilled in the relevant art will recognize, however, that the application may be practiced without one or more of the specific details, or with other methods, components, steps, etc. In other instances, well-known structures, methods, implementations, or operations are not shown or described in detail to avoid obscuring aspects of the application.
Some of the block diagrams shown in the figures are functional entities and do not necessarily correspond to physically or logically separate entities. These functional entities may be implemented in software or in one or more hardware modules or integrated circuits or in different networks and/or processor devices and/or microcontroller devices.
The method and the device are used for realizing the area generation of the irregular polygonal plane on the model created by the geometric engine, so that the geometric engine can quickly and accurately generate the area of the irregular polygonal plane on the created model or the model which is modified and adjusted currently, and further, when the geometric engine processes a large number of complex graphs, the area can be efficiently generated and the calculation accuracy can be ensured.
Based on the method, the processing capacity of a plane constructed by a complex image in the geometric engine and a three-dimensional model can be enhanced, and the method is not limited by the interference of curve edges.
The geometry engine provides modeling capabilities and in the modeling performed provides computational capabilities of the geometric properties for the built geometric model, as well as for the imported geometric model. The geometric engine architecture constructed for this purpose includes a data input interface, an edge type recognition service, and an area calculation service, and performs geometric operations through data transfer and collaboration with each other.
Referring to fig. 1, fig. 1 illustrates a flow chart of a method for generating an area of an irregular polygonal plane in a geometry engine according to one embodiment of the present application. The embodiment of the application provides a method for generating the area of an irregular polygonal plane in a geometric engine, which comprises the following steps:
step S110, loading geometric data through a data input interface, wherein the geometric data is a geometric description file for constructing a geometric model, and the geometric data provides an irregular polygonal plane covered on the surface for the constructed geometric model;
step S120, the edge type recognition service responds to the loading of geometric data, and recognizes the arc edge contained in the obtained irregular polygon plane, and the geometric engine is used for executing geometric operations on the irregular polygon plane, wherein the geometric operations comprise geometric attribute calculation of the irregular polygon plane;
Step S130, performing arc chord processing operation, taking a chord corresponding to the arc edge as an edge, and generating a polygon through the obtained edge set to obtain an irregular polygon plane mapped polygon;
Step S140, calling an area calculation service to calculate the area of the polygon to obtain the polygon area of the polygon formed by chords corresponding to the arc edges;
And step S150, processing the polygonal area according to the circular arc distribution on the irregular polygonal plane to obtain the area of the irregular polygonal plane.
These steps are described in detail below.
As indicated previously, the geometry engine focuses on the area generation of irregular polygon planes in the implementation of the present application, and in particular how to accurately handle complex shapes with rounded edges in the geometry engine.
For the created model, when a plane on the model is accurately identified to be a complex graph with an arc edge, the geometric engine can achieve accurate operation on the complex graph through the implementation of the geometric engine, and can effectively divide and aggregate to obtain corresponding areas, so that efficient operation and accuracy are guaranteed.
The geometric model is a entity or shape rendered in three-dimensional space, and in an embodiment of the application, at least one surface of the geometric model is covered by an irregular polygonal plane, thereby generating its area by means of the geometric property computing capability of the geometric engine.
The geometric model and the irregular polygonal plane covered by the surface of the geometric model have corresponding geometric data, and the geometric model and the irregular polygonal plane covered by the surface of the geometric model are loaded through the creation and/or the import of the geometric data in a geometric engine.
Specifically, the geometric engine loads corresponding geometric data through the configured data input interface, that is, as executed in step S110, so as to obtain a geometric description file for constructing the geometric model, and further provide an irregular polygonal plane covered on the surface for the constructed geometric model, where the irregular polygonal plane is an object with a required generation area.
For example, the geometry engine is configured with uploadGeometry (data) as an interface function, wherein data is the geometry data to be loaded, uploadGeometry (data) is used as the interface function of the geometry engine, and corresponding geometry data is loaded in response to the initiated model import or shape editing.
That is, in the geometry engine, no matter how the geometric model is created, the geometric model is imported, the shape on the geometric model is edited, etc., the generated geometric data is loaded by the data input interface function, so that the corresponding model and the shape on the constituent model are obtained through the loaded data, and thus the area is generated for the existing irregular polygon plane.
In order to implement the area generation of the irregular polygon plane, geometric attribute calculation related to the area is implemented on the irregular polygon plane, firstly, in the execution of step S120, the edge type recognition service performs recognition of the plane included in the model in the geometric engine, so as to recognize that the plane is a complex graph including a curved edge, that is, the irregular polygon plane with a circular arc edge.
In one exemplary embodiment, the edge type recognition service of the geometry engine recognizes whether a plane on the model contains rounded edges by performing curve fitting or curvature analysis to recognize an irregular polygonal plane containing rounded edges from the model, and generates an area for the irregular polygonal plane by performing the steps of the present application.
Specifically, on the plane of the irregular polygon, the curve fitting can be performed to obtain an equation of a circle for the points on the edge through least square fitting, namely, the equation is shown as follows:
Wherein, In order to fit the center of the circle,Is a radius;
Calculating fitting errors:
obtaining fitting error in edge-to-edge operation Then, the fitting error is judgedWhether or not it is smaller than a set threshold, if the fitting errorIf the calculated edge is smaller than the set threshold value, the calculated edge is judged to be an arc edge.
Alternatively, edges on the plane of the irregular polygon may be identified by curvature analysis. Exemplary, the curvature corresponding to points distributed on the edge is calculatedNamely, the following formula:
based on the calculation, the curvature of each point on the edge is obtained, and if the curvature is close to a constant on the whole edge, the edge is directly judged to be an arc edge.
The irregular polygonal plane defined by the application can comprise edges which can be line segments (straight line segments) or circular arcs. The irregular polygonal plane is a closed section formed by a plurality of continuous sides, and all the sides have no intersection except for the end points, so that the irregular polygonal plane does not have an area overlapping part.
In addition to determining whether an edge is a circular arc by curve fitting or curvature analysis, in another exemplary embodiment, the geometric attribute of the edge may be identified by describing parameters, functions, etc. of the edge, and if one edge has circular arc parameters, such as circle center, radius, etc. of the circular arc, or is described by a curve function, the edge is directly classified as a circular arc edge.
Of course, the type identification of the edge on the plane is not limited thereto, and in other exemplary embodiments, it may also be determined whether it is likely to be a straight line segment by performing the edge length calculation. Specifically, the opposite side calculates the actual length and the euclidean distance between the endpoints, if the actual length calculated by the opposite side is equal to the euclidean distance between the endpoints, the edge is a straight line, and if the actual length calculated by the opposite side is not equal to the euclidean distance between the endpoints, the edge is an arc edge.
For example, the edge type recognition service may be implemented by a IDENTIFYEDGETYPE (EDGE) function, where the edge input value is an edge for which recognition and judgment is performed by the input, and IDENTIFYEDGETYPE (EDGE) is used to recognize which type the input edge belongs to, so as to support subsequent operations.
After recognizing that a plane in the geometry engine is an irregular polygon plane including circular arc edges by the execution of step S120, an area can be generated for this irregular polygon plane by the execution of the subsequent steps.
It should be appreciated that the geometry engine is used to process and analyze geometric data, including objects such as points, lines, planes, etc., and that generating an area for the created graphic is one of the fundamental functions of the geometry engine. The area generating capability related to the geometric engine must include two-dimensional plane geometry for the object, namely, the irregular polygon plane identified by the application, and the size of the irregular polygon plane is described by generating the area for the irregular polygon plane identified by the application, so that the irregular polygon plane can be applied to functions such as shape optimization required later, and the like, thereby providing accurate support for area division, topography measurement and the like in an application layer, such as a GIS (Geographic Information System, geographic information) system.
The area generation of the irregular polygonal plane realized by the method is used as a basic function of the built geometric engine, so that area data is provided for the two-dimensional and three-dimensional geometric modeling, and the method is combined with other functions such as volume operation, gravity center analysis and the like, and finally, real-time calculation such as the rapid, efficient and accurate area calculation capability required in graphic rendering is realized by the method, so that the capability of the real-time geometric engine is built.
In step S130, for the irregular polygon plane including the circular arc edge identified in step S120 through the edge type identification service, the circular arc chording processing operation is performed on the circular arc edge included in the irregular polygon plane, that is, all the corresponding chords are taken as edges, and then the formed edge set is used to construct the polygon mapped by the irregular polygon plane. That is, the present application recognizes that an irregular polygon for area generation includes at least one circular arc edge.
The complex polygon, i.e. the plane of the irregular polygon containing the circular arc edges, performs chord processing on the circular arc edges, and performs preliminary operation, thereby simplifying the generated calculation amount.
Step S130 is a simplified and approximate calculation of the irregular polygon plane, and the complex boundary form is converted into a polygon form which is easy to process under the action of step S130, so as to facilitate geometric operations such as area generation and the like required by implementing the present application.
For the irregular polygon plane containing the circular arc edge in the geometric engine, the description is carried out through corresponding parameter information and functions, for example, corresponding boundary information exists for the contained straight line edge, namely the line segment as the above, and the circular arc edge, for example, for the circular arc edge, the parameters used for describing the circular arc edge comprise a circular arc starting point and an ending point, a circle center, a radius, an arc range and the like.
And pulling the corresponding strings of the arc edges obtained by recognition, wherein the pulled strings are straight line segments connecting two end points of the arc edges. And replacing the drawn chord with an arc edge to construct a closed interval which is completely formed by straight line edges, wherein the closed interval is a polygon mapped by an irregular polygon plane.
The execution of step S130 will significantly reduce the computational complexity in the geometry engine, which is the underlying basis for this geometry operation of area generation, and the significant reduction in computational complexity will be applicable to real-time applications supported by the geometry engine, such as graphics rendering, physics simulation.
Specifically, in the execution process of step S130, the execution process of the arc chording operation includes constructing a straight line segment for the start point and the end point of each arc edge, where the straight line segment is a chord pulled from the arc edge, and the constructed straight line segment is shown in the following formula:
Wherein, Namely a straight-line segment which is constructed,Is the starting point of the circular arc edge,Is the end point of the arc edge.
And replacing the drawn strings with arc edges, and so on, executing the operation on a plurality of arc edges contained in the irregular polygon plane one by one, and finally combining all replaced straight line segments, namely the straight line edges and strings generated by new drawing to form an edge set, wherein the edge set forms a closed section.
Referring also to fig. 2, fig. 2 is a flowchart of a method for describing a polygon step of performing a chordization processing operation by using a chord corresponding to a circular arc edge as an edge and generating a polygon from the obtained edge set to obtain an irregular polygon plane map according to the corresponding embodiment of fig. 1.
The step S130 of performing the chord processing operation of the circular arc provided in the embodiment of the present application uses the chord corresponding to the circular arc edge as an edge, and generates a polygon through the obtained edge set to obtain a polygon mapped by an irregular polygon plane, including:
Step S131, pulling a chord of the arc edge obtained by identification, wherein the chord is connected with the arc edge at the end point of the adjacent edge of the irregular polygonal plane;
In step S132, the strings and the edges formed by the line segments on the irregular polygon plane form continuous edges, and the obtained edges are assembled to form a closed section, and the closed section is a polygon mapped by the irregular polygon plane.
As described above, by pulling the corresponding chord from the identified arc edge, the chord is the two end points of the arc edge, i.e. the straight line segment between the start point and the end point of the arc edge.
Thus, for an irregular polygonal plane, the continuous edge thereon is replaced with a pulled chord as the rounded edge, the replaced chord connecting with the adjacent edge end points, thereby forming a closed area.
After the polygon mapped by the irregular polygon plane is obtained through the execution of step S130, the corresponding polygon area can be calculated under the action of step S140.
In step S140, it should be clear first that the initial polygon, that is, the irregular polygon plane, is a continuous edge composed of straight line segments and circular arcs, but all circular arc edges have been pulled and replaced with corresponding chords in step S130, so that the new polygon, that is, the polygon mapped by the irregular polygon plane, only includes straight line segment edges.
The graphics in the geometry engine are described by parameters and/or functions. Based on this, the resulting irregular polygon plane mapped polygon is illustratively described by its set of vertex coordinates, such that each straight line segment edge is also defined by the coordinates of the two vertices, i.e., endpoints, thereon.
Therefore, based on the vertex coordinate set, the area calculation service can be called to execute a geometric algorithm to calculate the area, so that the polygonal area is obtained. For example, the area calculation service may be implemented by a calculatePolygonArea (vertices) function, where vertices is each vertex in the vertex coordinate set. The calculatePolygonArea function will perform area calculations based on the coordinates of each vertex.
In the area calculation performed by the area calculation service, the polygon is first split to obtain a plurality of sub-convex polygons, that is, the polygon convex decomposition is performed, whereby a plurality of sub-polygons are output to the polygon, and each sub-polygon is a convex polygon. The sum of the areas of all sub-polygons, i.e. sub-convex polygons, is equal to the polygon area of the polygon to which the plane of the irregular polygon maps.
After the polygon mapped to the irregular polygon plane is split to obtain a plurality of sub-convex polygons, the area of each sub-convex polygon can be calculated and finally aggregated to obtain the polygon area.
The rule for judging the convex polygon formed by the straight line segments is that any one side and other polygon vertexes (without vertexes on the side) are on the same side of the side (including an extension line), and the polygon is the convex polygon.
The geometry engine implemented by embodiments of the present application will utilize this rule to split the polygon. Further, the polygon mapped by the irregular polygon plane is split by utilizing the rule that all vertexes are on the same side of any one side, so that a plurality of sub-convex polygons are obtained.
Specifically, firstly, a vertex coordinate set describing the polygon is marked with pits, then a feasible diagonal line is searched for each marked pit, so that the polygon is segmented by the found diagonal line, and the process is repeatedly executed until all the sub-polygons are convex, namely, a plurality of sub-convex polygons can be obtained by splitting the polygon mapped by the irregular polygon plane, and the sub-convex polygons are mutually non-overlapped and non-void to form the polygon.
Referring to fig. 3, fig. 3 is a flowchart of a method for describing the steps of obtaining the polygonal area of the polygon formed by the chords corresponding to the circular arc edges by performing the area calculation of the polygon for the call area calculation service according to the corresponding embodiment of fig. 1.
The step S140 of calculating the area of the polygon to obtain the polygonal area of the polygon formed by the chords corresponding to the circular arc edge according to the embodiment of the present application includes:
Step S141, calling area calculation service to split the polygon into a plurality of sub-convex polygons, wherein the sub-convex polygons are formed into polygons without overlapping and gaps;
in step S142, the area of each sub-convex polygon is calculated and aggregated to obtain the polygon area of the polygon.
This step is described in detail below.
In step S141, as the polygon is obtained, the area calculation service is invoked, and the invoked area calculation service splits a complex polygon into a plurality of sub-convex polygons, where the sub-convex polygons are convex for the plurality of sub-polygons obtained by splitting the complex polygon, and each sub-polygon is a convex polygon.
All vertices of the convex polygon must be located on the same side of any straight line that forms the edge. That is, the vertices of a convex polygon are "homolateral" in that if all of the vertices are on the same side of an edge, it is indicated that the edge does not partition the polygon, and that the vertices will form a split sub-convex edge.
In the computation performed by the geometry engine, the pits in the polygon, i.e. vertices with internal angles greater than 180 degrees, may first be marked by a proper amount of cross-product computation. Specifically, for each vertex, a vector between the vertex and two adjacent vertices is calculated, a cross product is calculated for the vector, if the obtained cross product is negative, the vertex is a concave point, otherwise, the vertex is a convex point, and the process realizes the marking of the concave point in the polygon.
One feasible diagonal is then found for each marked pit. Specifically, for each marked concave point, selecting the non-adjacent vertex in the polygon, wherein the line segment formed by the concave point and the selected vertex cannot pass through the edge of the polygon, and verifying whether other vertexes are positioned on the same side of the line segment formed by the concave point and the selected vertex, and if so, the concave point and the selected vertex form an effective diagonal line.
The effective diagonal line found by the polygon edge is cut into two sub-polygons, and the execution process is repeatedly executed on the basis of the effective diagonal line until all the sub-polygons are convex polygons.
In step S142, the geometric engine calculates the area of each sub-convex polygon, and finally aggregates the areas of all sub-convex polygons to obtain the polygon area of the polygon mapped by the irregular polygon plane.
Each sub-convex polygon is an independent convex polygon, and is not overlapped with each other and has no gap, so that the area of each sub-convex polygon can be obtained by performing area calculation of the polygon through the vertex of the sub-convex polygon.
In one exemplary embodiment, the area calculations respectively performed on the sub-convex polygons may be implemented by traversing the vertex coordinates on the sub-convex polygons, based on a directed area formula of the vertex coordinates.
In another exemplary embodiment, at least one triangle may be constructed for each sub-convex polygon, and the area of each triangle may be determined and aggregated to obtain the area of the sub-convex polygon.
Specifically, referring also to fig. 4, fig. 4 is a flowchart describing a method for calculating the area of each sub-convex polygon and aggregating the areas of the polygons to obtain the polygon, respectively, according to the corresponding embodiment of fig. 3.
The step S142 of calculating the area of each sub-convex polygon and aggregating to obtain the polygon area of the polygon provided in the embodiment of the present application includes:
Step S1421, for each sub-convex polygon, taking any vertex and constructing at least one triangle with each side of the sub-convex polygon without the vertex;
In step S1422, the areas of all triangles are calculated, and the areas of all triangles are aggregated to obtain the areas of the sub-convex polygons.
These two steps are described in detail below.
Specifically, at any one vertex of each sub-convex polygon, it forms a triangle with two vertices on one side without the vertex, and so on, at least one triangle can be obtained by dividing the sub-convex polygon.
Area calculation of the triangle obtained by division by vertex coordinates is exemplified by that for a triangle ABC, vertex coordinates corresponding to three vertexes of A, B and C are known respectively,BAndThe length of each side is first calculated to obtain the length a of side BC, the length b of side AC and the length c of side AB in triangle ABC.
After the length of each side of the triangle is calculated, the area of the triangle can be directly calculated, namely, the area is shown in the following formula:
wherein S is the area of the triangle obtained by calculation, Is half perimeter of triangle。
The area of each triangle in the sub-convex polygon is calculated, and then the areas of all triangles in the sub-convex polygon are accumulated to obtain the area of the sub-convex polygon.
Similarly, after obtaining the areas of all sub-convex polygons, all areas are aggregated to obtain a polygon area.
The polygonal area obtained by the operation in the step S140 is a rough expression of the area of the irregular polygonal plane, and the polygonal area needs to be processed by the execution in the step S150, so that the finally obtained area can be ensured to be infinitely close to a true value, and further higher precision is obtained.
As described above, the area calculation polygon is constructed by pulling the corresponding strings from the circular arc edges distributed on the plane of the irregular polygon and replacing the circular arc edges with the corresponding strings.
Thus, in the execution process of step S150, the direction of the circular arc edge on the irregular polygon plane is identified, and the circular arc area corresponding to the circular arc edge is processed for the polygon area according to the identified direction, so as to obtain the area of the irregular polygon plane.
Referring also to fig. 5, fig. 5 is a flowchart of a method for describing the steps of processing a polygonal area to obtain an area of an irregular polygonal plane according to an arc distribution on the irregular polygonal plane according to the corresponding embodiment of fig. 1.
The step S140 of processing a polygonal area according to the circular arc distribution on the irregular polygonal plane to obtain the area of the irregular polygonal plane provided by the embodiment of the present application includes:
step S151, identifying the direction of the arc edge on the plane of the irregular polygon;
Step S152, obtaining the area of the irregular polygon plane according to the arc area corresponding to the arc edge processed for the polygon area.
These two steps are described in detail below.
It should be clearly defined at first that the orientation of the circular arc edges includes both inward and outward types of polygons mapped toward the plane of the irregular polygon.
Illustratively, FIG. 6 is a schematic diagram illustrating the type of orientation of the projected polygon outward toward the plane of the irregular polygon, according to one embodiment;
FIG. 7 is a schematic diagram illustrating the type of orientation that is concave inward toward the interior of a polygon to which an irregular polygon plane is mapped, according to one embodiment.
The orientation is identified for each circular arc edge on the plane of the irregular polygon. Specifically, as previously described, each arcuate edge has a corresponding chord. Thus, for each arc edge, the midpoint on the chord corresponds toConnect a point on the arc edgeAnd constructing a ray, calculating whether an intersection point exists between the ray and other sides of the polygon, if the intersection point exists, determining that the direction of the circular arc side is concave towards the inside of the polygon, and if the intersection point does not exist, determining that the direction of the circular arc side is convex outwards.
The intersection of the computing rays and the polygon edges in the geometric engine is basic operation, the existing algorithm support of the geometric engine can be obtained, the need of complex concave-convex computation of additional design is avoided, the orientation judgment can be realized only based on a small amount of logic judgment, the local error risk is reduced, and the robustness is enhanced.
Further, even if the edge intersecting the ray is a circular arc edge, the present orientation recognition can be applied to the present orientation recognition, and therefore, the orientation recognition applied to the complex polygon has high reliability.
In order to facilitate the intersection calculation, the chord of the replaced circular arc edge can be directly carried out, so that the calculated amount is further reduced, the algorithm is easy to realize, the calculation cost is low, and the implementation can be supported by the existing geometric engine.
Fig. 8 is a schematic diagram of the direction determination of the circular arc edge according to the embodiment shown in fig. 6. In the circular arc edge shown in fig. 8, a ray is constructed in the direction of the point on the circular arc edge with the midpoint of the corresponding chord, and at this time, the ray does not intersect with the other edges of the polygon, and therefore, it can be determined that the direction of the circular arc edge is convex outward toward the irregular polygon.
Fig. 9 is a schematic diagram illustrating the determination of the direction of the circular arc edge according to the embodiment shown in fig. 7. In the circular arc edge shown in fig. 9, a ray is constructed with the midpoint of the corresponding chord in the direction of the point on the circular arc edge, and at this time, the ray intersects with the other edges of the polygon, and therefore, it can be determined that the direction of the circular arc edge is concave inward toward the irregular polygon.
Further, the geometry engine performs intersection computation on the ray to determine that there is a point that is located on both the ray and a polygon edge, and then determines that the ray intersects other edges of the polygon.
Specifically, first, chord midpoint D is calculated for two endpoints of the arc edge, namely a and B, that is, the chord midpoint D is calculated according to the following formula:
wherein the coordinates of the chord midpoint D are 。
The intersection point of the ray constructed by the point D and the point C and the straight line where the polygon edge EF is positioned is Q, namely the coordinate of the intersection point isThe calculation process involved is as follows
First calculate the required parameters、、、、AndWherein:
The Q point coordinates are:
at this time, if If so, the two straight lines are parallel and have no intersection point.
In the calculation of the Q point coordinates, i.eThen, at this time, whether the intersection point Q is within the line segment EF is determined, only whether the coordinate of the point Q is between the two coordinates of the point EF is required, and whether the intersection point Q is on the ray DC is determined only by determining whether the point D is on the line segment QC.
Through the calculation process, the geometric engine calculates whether the ray DC intersects other sides of the polygon or not so as to identify the orientation of the arc side, and then the geometric engine can adapt to the orientation to process the area of the polygon.
The polygon area processing includes calculation of the arc area, and it should be understood that the arc area is the area surrounded by the arc edge and the corresponding chord. That is, for the circular arc edges existing on the irregular polygon plane, the calculation of the corresponding circular arc area will also be performed for each circular arc edge.
Illustratively, a circular arc edge is represented by two endpoints at which it exists, and a point on the circular arc edge.
For example, a circular arc edge with two end pointsAndOne point on the arc edge。
The graph corresponding to the circular arc is a part of a circumscribing circle corresponding to a triangle formed by three points, and the circle center of the circumscribing circle isThe area of triangle OAB is calculated by the following formulaThe method comprises the following steps:
First, the length of each side is calculated to obtain the length of the side OA, the length of the side OB and the length of the side AB in the triangle OAB.
After the length of each side of the triangle is calculated, the area of the triangle can be directly calculated, namely, the area is shown in the following formula:
Wherein, In order to calculate the area of the resulting triangle,Is half perimeter of triangle。
Except for calculating the area of triangle OABThe calculation of the circle center of the circumscribing circle is needed, namely, firstly, the required parameters are calculated, namely:
The center coordinates are: ;
calculating the radius R=of the circumscribed circle Calculate +_acb =Then the arc radian alpha=2pi-2 < ACB, the sector area corresponding to the arc edge is:
S Sector shape =
if ACB is an acute angle, the arc area is S Arc of a circle =S Sector shape +S∆OAB;
If the ACB is an obtuse angle, the arc area is S Arc of a circle =S Sector shape -S∆OAB;
If the angle ACB is a right angle, the arc area is S Arc of a circle =S Sector shape = 。
The area of the irregular polygonal plane is obtained by adding the circular arc area to the polygonal area in the processing of the circular arc edge facing outwards, and the area of the irregular polygonal plane is obtained by subtracting the circular arc area from the polygonal area of the circular arc edge facing inwards.
Therefore, the obtained polygonal area is processed by identifying the direction of the circular arc edge, the real area of the irregular polygonal plane can be accurately obtained, and the area computing capability of the geometric engine is greatly enhanced compared with an algorithm of approaching a real value through segmentation and the like.
Furthermore, the direction of the circular arc edge on the plane of the irregular polygon is identified, so that the judgment by only using local parameters such as the circle center, the starting point, the end point, the radius and the like is avoided by means of the geometric characteristics of the polygon, the occurrence of single local misjudgment is effectively avoided, and the misjudgment probability is reduced.
Therefore, the situation that the direction of the arc edge of the irregular polygonal plane is difficult to judge when the arc edge is in arc state is caused, whether the constructed rays intersect with other edges or not is judged to achieve direction identification, existing basic operation of the geometric engine is effectively utilized, efficient algorithm support in the geometric engine can be obtained, and the need of additionally carrying out complex concave-convex calculation is avoided.
Further, in an exemplary embodiment, in the process of identifying the direction of the arc edge, a plurality of rays can be constructed from the midpoint of the chord to the arc, whether the number of rays intersected with other edges exceeds a set threshold value is judged, if the number of rays intersected with other edges exceeds the set threshold value, intersection is confirmed to exist, so that intersection point detection is performed, reliability of an obtained result is enhanced, direction judgment and stability are improved, and misjudgment caused by existence of a complex polygon is avoided.
Further, in another exemplary embodiment, to implement large-scale real-time processing of a large number of complex polygons in a geometry engine, intersection detection with a constructed ray and an edge will use a spatial index to filter out edges that are unlikely to intersect the ray, and then calculate in the area of possible intersection to finally determine whether the constructed ray and edge intersect.
The calculation is only needed in the possibly intersected area, so that the complexity can be obviously reduced, and the time complexity is obviously reduced for the situation that the number of sides of the polygon is large, and the method is suitable for processing a large-scale irregular polygon plane in a geometric engine in real time.
In summary, in the area calculation performed by the geometric engine, the area of each sub-convex polygon is obtained by aggregating the areas of all triangles in the sub-convex polygon, and then the polygonal area of the polygon mapped by the irregular polygon plane can be obtained by aggregating the areas of all sub-convex polygons, and the polygonal area is equivalent to the approximate area obtained after simplifying the irregular polygon plane, so that the circular arc area corresponding to each circular arc edge is processed for the polygonal area by identifying the orientation of each circular arc edge on the irregular polygon plane, thereby obtaining the accurate area of the irregular polygon plane.
By the process, the area generating capability in the real-time geometric engine is provided, the dynamic complex polygonal shape can be rapidly processed, further complex graph analysis is realized, and the geometric analysis task of the complex graph is realized efficiently and reliably.
In an exemplary embodiment, the application also provides a computer device comprising a memory, a processor and a computer program stored on the memory, the processor executing the computer program to carry out the steps of the method as described above.
In an exemplary embodiment, the application also provides a computer program product comprising a computer program which, when executed by a processor, implements the steps of the method as described above.
In an exemplary embodiment, the application also provides a computer-readable storage medium, on which a computer program is stored which, when being executed by a processor, implements the steps of the method as described above.
From the above description of embodiments, those skilled in the art will readily appreciate that the example embodiments described herein may be implemented in software, or may be implemented in software in combination with the necessary hardware. Thus, the technical solution according to the embodiments of the present application may be embodied in the form of a software product, which may be stored in a non-volatile storage medium (may be a CD-ROM, a U-disk, a mobile hard disk, etc.) or on a network, and includes several instructions to cause a computing device (may be a personal computer, a server, a terminal device, or a network device, etc.) to perform the method according to the embodiments of the present application.
In an exemplary embodiment of the application, a computer program medium is also provided, on which computer readable instructions are stored which, when executed by a processor of a computer, cause the computer to perform the method described in the method embodiments section above.
According to an embodiment of the present application, there is also provided a program product for implementing the method in the above method embodiment, which may employ a portable compact disc read only memory (CD-ROM) and comprise program code and may be run on a terminal device, such as a personal computer. However, the program product of the present application is not limited thereto, and in this document, a readable storage medium may be any tangible medium that can contain, or store a program for use by or in connection with an instruction execution system, apparatus, or device.
The program product may employ any combination of one or more readable media. The readable medium may be a readable signal medium or a readable storage medium. The readable storage medium can be, for example, but is not limited to, an electronic, magnetic, optical, electromagnetic, infrared, or semiconductor system, apparatus, or device, or a combination of any of the foregoing. More specific examples (a non-exhaustive list) of a readable storage medium include an electrical connection having one or more wires, a portable disk, a hard disk, a Random Access Memory (RAM), a read-only memory (ROM), an erasable programmable read-only memory (EPROM or flash memory), an optical fiber, a portable compact disc read-only memory (CD-ROM), an optical storage device, a magnetic storage device, or any suitable combination of the foregoing.
The computer readable signal medium may include a data signal propagated in baseband or as part of a carrier wave with readable program code embodied therein. Such a propagated data signal may take any of a variety of forms, including, but not limited to, electro-magnetic, optical, or any suitable combination of the foregoing. A readable signal medium may also be any readable medium that is not a readable storage medium and that can communicate, propagate, or transport a program for use by or in connection with an instruction execution system, apparatus, or device.
Program code embodied on a readable medium may be transmitted using any appropriate medium, including but not limited to wireless, wireline, optical fiber cable, RF, etc., or any suitable combination of the foregoing.
Program code for carrying out operations of the present invention may be written in any combination of one or more programming languages, including an object oriented programming language such as Java, C++ or the like and conventional procedural programming languages, such as the "C" programming language or similar programming languages. The program code may execute entirely on the user's computing device, partly on the user's device, as a stand-alone software package, partly on the user's computing device, partly on a remote computing device, or entirely on the remote computing device or server. In the case of remote computing devices, the remote computing device may be connected to the user computing device through any kind of network, including a Local Area Network (LAN) or a Wide Area Network (WAN), or may be connected to an external computing device (e.g., connected via the Internet using an Internet service provider).
It should be noted that although in the above detailed description several modules or units of a device for action execution are mentioned, such a division is not mandatory. Indeed, the features and functions of two or more modules or units described above may be embodied in one module or unit in accordance with embodiments of the application. Conversely, the features and functions of one module or unit described above may be further divided into a plurality of modules or units to be embodied.
Furthermore, although the steps of the methods of the present application are depicted in the accompanying drawings in a particular order, this is not required to or suggested that the steps must be performed in this particular order or that all of the steps shown be performed in order to achieve desirable results. Additionally or alternatively, certain steps may be omitted, multiple steps combined into one step to perform, and/or one step decomposed into multiple steps to perform, etc.
From the above description of embodiments, those skilled in the art will readily appreciate that the example embodiments described herein may be implemented in software, or may be implemented in software in combination with the necessary hardware. Thus, the technical solution according to the embodiments of the present application may be embodied in the form of a software product, which may be stored in a non-volatile storage medium (may be a CD-ROM, a U-disk, a mobile hard disk, etc.) or on a network, and includes several instructions to cause a computing device (may be a personal computer, a server, a mobile terminal, or a network device, etc.) to perform the method according to the embodiments of the present application.
Other embodiments of the application will be apparent to those skilled in the art from consideration of the specification and practice of the application disclosed herein. This application is intended to cover any variations, uses, or adaptations of the application following, in general, the principles of the application and including such departures from the present disclosure as come within known or customary practice within the art to which the application pertains. It is intended that the specification and examples be considered as exemplary only, with a true scope and spirit of the application being indicated by the following claims.
Claims (9)
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202411901820.8A CN119359926B (en) | 2024-12-23 | 2024-12-23 | Method and equipment for generating area of irregular polygonal plane in geometric engine |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202411901820.8A CN119359926B (en) | 2024-12-23 | 2024-12-23 | Method and equipment for generating area of irregular polygonal plane in geometric engine |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN119359926A CN119359926A (en) | 2025-01-24 |
| CN119359926B true CN119359926B (en) | 2025-05-13 |
Family
ID=94312823
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202411901820.8A Active CN119359926B (en) | 2024-12-23 | 2024-12-23 | Method and equipment for generating area of irregular polygonal plane in geometric engine |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN119359926B (en) |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN109712235A (en) * | 2018-11-28 | 2019-05-03 | 佛山市测绘地理信息研究院 | A kind of construction method of Digital Cadastral Block Map |
| CN110990925A (en) * | 2019-11-29 | 2020-04-10 | 广联达科技股份有限公司 | Template area calculation method and device based on geometric model processing and electronic equipment |
Family Cites Families (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US8269764B2 (en) * | 2007-10-03 | 2012-09-18 | Oracle International Corporation | Three dimensional spatial engine in a relational database management system |
| US20220156438A1 (en) * | 2020-11-13 | 2022-05-19 | Autodesk, Inc. | Building performance analysis (bpa) machine: machine learning to accelerate building energy analysis |
| CN117635800A (en) * | 2023-12-07 | 2024-03-01 | 浙江理工大学 | A method and device for generating geometric texture based on quasi-regular patterns |
| CN118864234B (en) * | 2024-09-26 | 2025-03-14 | 八维通科技有限公司 | Method, apparatus and program product for generating three-dimensional curved surface in geometric engine, and medium |
-
2024
- 2024-12-23 CN CN202411901820.8A patent/CN119359926B/en active Active
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN109712235A (en) * | 2018-11-28 | 2019-05-03 | 佛山市测绘地理信息研究院 | A kind of construction method of Digital Cadastral Block Map |
| CN110990925A (en) * | 2019-11-29 | 2020-04-10 | 广联达科技股份有限公司 | Template area calculation method and device based on geometric model processing and electronic equipment |
Also Published As
| Publication number | Publication date |
|---|---|
| CN119359926A (en) | 2025-01-24 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US8988420B2 (en) | Visual file representation | |
| Ortega et al. | Generating 3D city models from open LiDAR point clouds: Advancing towards smart city applications | |
| US20160180588A1 (en) | Identifying features in polygonal meshes | |
| Wu et al. | Piecewise Linear Approximation of Signed Distance Fields. | |
| CN114283441B (en) | Two-dimensional drawing recognition modeling method and device suitable for railway passenger stations | |
| Sandim et al. | Boundary Detection in Particle‐based Fluids | |
| Chen | Digital Functions and Data Reconstruction | |
| Qin et al. | Research and application of Boolean operation for triangular mesh model of underground space engineering—Boolean operation for triangular mesh model | |
| CN110135043B (en) | City street contour space form classification method and system | |
| Jiang et al. | Structure-aware surface reconstruction via primitive assembly | |
| CN119359926B (en) | Method and equipment for generating area of irregular polygonal plane in geometric engine | |
| Su et al. | Discrete calabi flow: A unified conformal parameterization method | |
| CN117235824B (en) | Coplanar fitting method, device, equipment and computer-readable storage medium | |
| CN118967902A (en) | Method and device for rendering virtual objects | |
| Vančo et al. | Surface reconstruction from unorganized point data with quadrics | |
| CN117974887A (en) | Tunnel wall modeling method and system based on three-dimensional laser point cloud | |
| US9122924B2 (en) | Object identification | |
| Fujimori et al. | Contouring medial surface of thin plate structure using local marching cubes | |
| CN119992026B (en) | Simplified expression method for geometric data in digital twin city field | |
| Li et al. | Multi-resolution representation of digital terrain models with terrain features preservation | |
| CN113901914A (en) | Image recognition method, device, electronic device, and readable storage medium | |
| CN118657743B (en) | Industrial parts detection method and system based on tensor voting | |
| Singh et al. | A pre-processing algorithm for faster convex hull computation | |
| CN117649530B (en) | Point cloud feature extraction method, system and equipment based on semantic level topological structure | |
| CN118094672A (en) | Method for constructing hierarchical bounding volume executed by electronic device |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |