Class Centroid

1
2	/*
3	* Copyright (c) 2016 Vivid Solutions.
4	*
5	* All rights reserved. This program and the accompanying materials
6	* are made available under the terms of the Eclipse Public License 2.0
7	* and Eclipse Distribution License v. 1.0 which accompanies this distribution.
8	* The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
9	* and the Eclipse Distribution License is available at
10	*
11	* http://www.eclipse.org/org/documents/edl-v10.php.
12	*/
13	package org.locationtech.jts.algorithm;
14
15	import org.locationtech.jts.geom.Coordinate;
16	import org.locationtech.jts.geom.Geometry;
17	import org.locationtech.jts.geom.GeometryCollection;
18	import org.locationtech.jts.geom.LineString;
19	import org.locationtech.jts.geom.Point;
20	import org.locationtech.jts.geom.Polygon;
21
22	/**
23	* Computes the centroid of a {@link Geometry} of any dimension.
24	* If the geometry is nominally of higher dimension,
25	* but has lower <i>effective</i> dimension
26	* (i.e. contains only components
27	* having zero length or area),
28	* the centroid will be computed as for the equivalent lower-dimension geometry.
29	* If the input geometry is empty, a
30	* <code>null</code> Coordinate is returned.
31	*
32	* <h2>Algorithm</h2>
33	* <ul>
34	* <li><b>Dimension 2</b> - the centroid is computed
35	* as the weighted sum of the centroids
36	* of a decomposition of the area into (possibly overlapping) triangles.
37	* Holes and multipolygons are handled correctly.
38	* See <code>http://www.faqs.org/faqs/graphics/algorithms-faq/</code>
39	* for further details of the basic approach.
40	*
41	* <li><b>Dimension 1</b> - Computes the average of the midpoints
42	* of all line segments weighted by the segment length.
43	* Zero-length lines are treated as points.
44	*
45	* <li><b>Dimension 0</b> - Compute the average coordinate for all points.
46	* Repeated points are all included in the average.
47	* </ul>
48	*
49	* @version 1.7
50	*/
51	public class Centroid
52	{
53	/**
54	* Computes the centroid point of a geometry.
55	*
56	* @param geom the geometry to use
57	* @return the centroid point, or null if the geometry is empty
58	*/
59	public static Coordinate getCentroid(Geometry geom)
60	{
61	Centroid cent = new Centroid(geom);
62	return cent.getCentroid();
63	}
64
65	private Coordinate areaBasePt = null;// the point all triangles are based at
66	private Coordinate triangleCent3 = new Coordinate();// temporary variable to hold centroid of triangle
67	private double areasum2 = 0; /* Partial area sum */
68	private Coordinate cg3 = new Coordinate(); // partial centroid sum
69
70	// data for linear centroid computation, if needed
71	private Coordinate lineCentSum = new Coordinate();
72	private double totalLength = 0.0;
73
74	private int ptCount = 0;
75	private Coordinate ptCentSum = new Coordinate();
76
77	/**
78	* Creates a new instance for computing the centroid of a geometry
79	*/
80	public Centroid(Geometry geom)
81	{
82	areaBasePt = null;
83	add(geom);
84	}
85
86	/**
87	* Adds a Geometry to the centroid total.
88	*
89	* @param geom the geometry to add
90	*/
91	private void add(Geometry geom)
92	{
93	if (geom.isEmpty())
94	return;
95	if (geom instanceof Point) {
96	addPoint(geom.getCoordinate());
97	}
98	else if (geom instanceof LineString) {
99	addLineSegments(geom.getCoordinates());
100	}
101	else if (geom instanceof Polygon) {
102	Polygon poly = (Polygon) geom;
103	add(poly);
104	}
105	else if (geom instanceof GeometryCollection) {
106	GeometryCollection gc = (GeometryCollection) geom;
107	for (int i = 0; i < gc.getNumGeometries(); i++) {
108	add(gc.getGeometryN(i));
109	}
110	}
111	}
112
113	/**
114	* Gets the computed centroid.
115	*
116	* @return the computed centroid, or null if the input is empty
117	*/
118	public Coordinate getCentroid()
119	{
120	/**
121	* The centroid is computed from the highest dimension components present in the input.
122	* I.e. areas dominate lineal geometry, which dominates points.
123	* Degenerate geometry are computed using their effective dimension
124	* (e.g. areas may degenerate to lines or points)
125	*/
126	Coordinate cent = new Coordinate();
127	if (Math.abs(areasum2) > 0.0) {
128	/**
129	* Input contains areal geometry
130	*/
131	cent.x = cg3.x / 3 / areasum2;
132	cent.y = cg3.y / 3 / areasum2;
133	}
134	else if (totalLength > 0.0) {
135	/**
136	* Input contains lineal geometry
137	*/
138	cent.x = lineCentSum.x / totalLength;
139	cent.y = lineCentSum.y / totalLength;
140	}
141	else if (ptCount > 0){
142	/**
143	* Input contains puntal geometry only
144	*/
145	cent.x = ptCentSum.x / ptCount;
146	cent.y = ptCentSum.y / ptCount;
147	}
148	else {
149	return null;
150	}
151	return cent;
152	}
153
154	private void setAreaBasePoint(Coordinate basePt)
155	{
156	this.areaBasePt = basePt;
157	}
158
159	private void add(Polygon poly)
160	{
161	addShell(poly.getExteriorRing().getCoordinates());
162	for (int i = 0; i < poly.getNumInteriorRing(); i++) {
163	addHole(poly.getInteriorRingN(i).getCoordinates());
164	}
165	}
166
167	private void addShell(Coordinate[] pts)
168	{
169	if (pts.length > 0)
170	setAreaBasePoint(pts[0]);
171	boolean isPositiveArea = ! Orientation.isCCW(pts);
172	for (int i = 0; i < pts.length - 1; i++) {
173	addTriangle(areaBasePt, pts[i], pts[i+1], isPositiveArea);
174	}
175	addLineSegments(pts);
176	}
177
178	private void addHole(Coordinate[] pts)
179	{
180	boolean isPositiveArea = Orientation.isCCW(pts);
181	for (int i = 0; i < pts.length - 1; i++) {
182	addTriangle(areaBasePt, pts[i], pts[i+1], isPositiveArea);
183	}
184	addLineSegments(pts);
185	}
186	private void addTriangle(Coordinate p0, Coordinate p1, Coordinate p2, boolean isPositiveArea)
187	{
188	double sign = (isPositiveArea) ? 1.0 : -1.0;
189	centroid3( p0, p1, p2, triangleCent3 );
190	double area2 = area2( p0, p1, p2 );
191	cg3.x += sign * area2 * triangleCent3.x;
192	cg3.y += sign * area2 * triangleCent3.y;
193	areasum2 += sign * area2;
194	}
195	/**
196	* Computes three times the centroid of the triangle p1-p2-p3.
197	* The factor of 3 is
198	* left in to permit division to be avoided until later.
199	*/
200	private static void centroid3( Coordinate p1, Coordinate p2, Coordinate p3, Coordinate c )
201	{
202	c.x = p1.x + p2.x + p3.x;
203	c.y = p1.y + p2.y + p3.y;
204	return;
205	}
206
207	/**
208	* Returns twice the signed area of the triangle p1-p2-p3.
209	* The area is positive if the triangle is oriented CCW, and negative if CW.
210	*/
211	private static double area2( Coordinate p1, Coordinate p2, Coordinate p3 )
212	{
213	return
214	(p2.x - p1.x) * (p3.y - p1.y) -
215	(p3.x - p1.x) * (p2.y - p1.y);
216	}
217
218	/**
219	* Adds the line segments defined by an array of coordinates
220	* to the linear centroid accumulators.
221	*
222	* @param pts an array of {@link Coordinate}s
223	*/
224	private void addLineSegments(Coordinate[] pts)
225	{
226	double lineLen = 0.0;
227	for (int i = 0; i < pts.length - 1; i++) {
228	double segmentLen = pts[i].distance(pts[i + 1]);
229	if (segmentLen == 0.0)
230	continue;
231
232	lineLen += segmentLen;
233
234	double midx = (pts[i].x + pts[i + 1].x) / 2;
235	lineCentSum.x += segmentLen * midx;
236	double midy = (pts[i].y + pts[i + 1].y) / 2;
237	lineCentSum.y += segmentLen * midy;
238	}
239	totalLength += lineLen;
240	if (lineLen == 0.0 && pts.length > 0)
241	addPoint(pts[0]);
242	}
243
244	/**
245	* Adds a point to the point centroid accumulator.
246	* @param pt a {@link Coordinate}
247	*/
248	private void addPoint(Coordinate pt)
249	{
250	ptCount += 1;
251	ptCentSum.x += pt.x;
252	ptCentSum.y += pt.y;
253	}
254
255
256	}
257