source: 2013/30/MiskaK/MW2(My Warfare 2)/Paranneltu Jypeli/AdvanceMath/Geometry2D/BoundingPolygon.cs @ 4507

Revision 4507, 19.9 KB checked in by anlakane, 6 years ago (diff)

Talletus.

Line 
1#region MIT License
2/*
3 * Copyright (c) 2005-2008 Jonathan Mark Porter. http://physics2d.googlepages.com/
4 *
5 * Permission is hereby granted, free of charge, to any person obtaining a copy
6 * of this software and associated documentation files (the "Software"), to deal
7 * in the Software without restriction, including without limitation the rights to
8 * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
9 * the Software, and to permit persons to whom the Software is furnished to do so,
10 * subject to the following conditions:
11 *
12 * The above copyright notice and this permission notice shall be
13 * included in all copies or substantial portions of the Software.
14 *
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
16 * INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
17 * PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
18 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
19 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
20 * OTHER DEALINGS IN THE SOFTWARE.
21 */
22#endregion
23
24
25
26
27#if UseDouble
28using Scalar = System.Double;
29#else
30using Scalar = System.Single;
31#endif
32using System;
33namespace AdvanceMath.Geometry2D
34{
35#if !(WINDOWS_PHONE || XBOX)
36    [Serializable]
37#endif
38    public sealed class BoundingPolygon
39    {
40        public static ContainmentType ContainsExclusive(Vector2D[] vertexes, Vector2D point)
41        {
42            ContainmentType result;
43            ContainsExclusive(vertexes, ref point, out result);
44            return result;
45        }
46        public static void ContainsExclusive(Vector2D[] vertexes, ref Vector2D point, out ContainmentType result)
47        {
48            if (vertexes == null) { throw new ArgumentNullException("vertexes"); }
49            if (vertexes.Length < 3) { throw new ArgumentOutOfRangeException("vertexes"); }
50            int count = 0; //intersection count
51            bool t1;
52            Vector2D v1, v2;
53            Scalar temp;
54            v1 = vertexes[vertexes.Length - 1];
55            for (int index = 0; index < vertexes.Length; ++index, v1 = v2)
56            {
57                v2 = vertexes[index];
58                t1 = (v1.Y <= point.Y);
59                if (t1 ^ (v2.Y <= point.Y))
60                {
61                    temp = ((point.Y - v1.Y) * (v2.X - v1.X) - (point.X - v1.X) * (v2.Y - v1.Y));
62                    if (t1) { if (temp > 0) { count++; } }
63                    else { if (temp < 0) { count--; } }
64                }
65            }
66            result = (count != 0) ? (ContainmentType.Contains) : (ContainmentType.Disjoint);
67        }
68
69        public static ContainmentType ContainsInclusive(Vector2D[] vertexes, Vector2D point)
70        {
71            ContainmentType result;
72            ContainsInclusive(vertexes, ref point, out result);
73            return result;
74        }
75        public static void ContainsInclusive(Vector2D[] vertexes, ref Vector2D point, out ContainmentType result)
76        {
77            if (vertexes == null) { throw new ArgumentNullException("vertexes"); }
78            if (vertexes.Length < 3) { throw new ArgumentOutOfRangeException("vertexes"); }
79            int count = 0;    // the crossing count
80            Vector2D v1 = vertexes[vertexes.Length - 1];
81            Vector2D v2;
82            for (int index = 0; index < vertexes.Length; index++, v1 = v2)
83            {
84                v2 = vertexes[index];
85                if (((v1.Y <= point.Y) ^ (v2.Y <= point.Y)) ||
86                    (v1.Y == point.Y) || (v2.Y == point.Y))
87                {
88                    Scalar xIntersection = (v1.X + ((point.Y - v1.Y) / (v2.Y - v1.Y)) * (v2.X - v1.X));
89                    if (point.X < xIntersection) // P.X < intersect
90                    {
91                        ++count;
92                    }
93                    else if (xIntersection == point.X)
94                    {
95                        result = ContainmentType.Contains;
96                        return;
97                    }
98                }
99            }
100            result = ((count & 1) != 0) ? (ContainmentType.Contains) : (ContainmentType.Disjoint); //true if odd.
101        }
102
103        public static bool Intersects(Vector2D[] vertexes1, Vector2D[] vertexes2)
104        {
105            bool result;
106            Intersects(vertexes1, vertexes2, out result);
107            return result;
108        }
109        public static void Intersects(Vector2D[] vertexes1, Vector2D[] vertexes2, out bool result)
110        {
111            if (vertexes1 == null) { throw new ArgumentNullException("vertexes1"); }
112            if (vertexes2 == null) { throw new ArgumentNullException("vertexes2"); }
113            if (vertexes1.Length < 2) { throw new ArgumentOutOfRangeException("vertexes1"); }
114            if (vertexes2.Length < 2) { throw new ArgumentOutOfRangeException("vertexes2"); }
115
116            Vector2D v1, v2, v3, v4;
117            v1 = vertexes1[vertexes1.Length - 1];
118            v3 = vertexes2[vertexes2.Length - 1];
119            result = false;
120            for (int index1 = 0; index1 < vertexes1.Length; ++index1, v1 = v2)
121            {
122                v2 = vertexes1[index1];
123                for (int index2 = 0; index2 < vertexes2.Length; ++index2, v3 = v4)
124                {
125                    v4 = vertexes2[index2];
126                    LineSegment.Intersects(ref v1, ref v2, ref v3, ref v4, out result);
127                    if (result) { return; }
128                }
129            }
130        }
131
132        public static Scalar GetDistance(Vector2D[] vertexes, Vector2D point)
133        {
134            Scalar result;
135            GetDistance(vertexes, ref point, out result);
136            return result;
137        }
138        /*public static void GetDistance(Vector2D[] vertexes, ref Vector2D point, out Scalar result)
139        {
140            if (vertexes == null) { throw new ArgumentNullException("vertexes"); }
141            if (vertexes.Length < 3) { throw new ArgumentOutOfRangeException("vertexes"); }
142            Scalar distance1, distance2;
143            int nearestIndex = 0;
144            Vector2D.DistanceSq(ref point, ref vertexes[0], out distance1);
145            for (int index = 1; index < vertexes.Length; ++index)
146            {
147                Vector2D.DistanceSq(ref point, ref vertexes[index], out distance2);
148                if (distance1 > distance2)
149                {
150                    nearestIndex = index;
151                    distance1 = distance2;
152                }
153            }
154            Vector2D prev = vertexes[(nearestIndex - 1 + vertexes.Length) % vertexes.Length];
155            Vector2D good = vertexes[nearestIndex];
156            Vector2D next = vertexes[(nearestIndex + 1) % vertexes.Length];
157            LineSegment.GetDistance(ref prev, ref good, ref point, out distance1);
158            LineSegment.GetDistance(ref good, ref next, ref point, out distance2);
159            result = Math.Min(distance1, distance2);
160            ContainmentType contains;
161            ContainsExclusive(vertexes, ref point, out contains);
162            if (contains == ContainmentType.Contains) { result = -result; }
163        }*/
164        public static void GetDistance(Vector2D[] vertexes, ref Vector2D point, out Scalar result)
165        {
166            if (vertexes == null) { throw new ArgumentNullException("vertexes"); }
167            if (vertexes.Length < 3) { throw new ArgumentOutOfRangeException("vertexes"); }
168            int count = 0; //intersection count
169            Vector2D v1 = vertexes[vertexes.Length - 1];
170            Vector2D v2;
171            Scalar goodDistance = Scalar.PositiveInfinity;
172            for (int index = 0; index < vertexes.Length; ++index, v1 = v2)
173            {
174                v2 = vertexes[index];
175                bool t1 = (v1.Y <= point.Y);
176                if (t1 ^ (v2.Y <= point.Y))
177                {
178                    Scalar temp = ((point.Y - v1.Y) * (v2.X - v1.X) - (point.X - v1.X) * (v2.Y - v1.Y));
179                    if (t1) { if (temp > 0) { count++; } }
180                    else { if (temp < 0) { count--; } }
181                }
182                Scalar distance;
183                LineSegment.GetDistanceSq(ref v1, ref v2, ref point, out distance);
184                if (distance < goodDistance) { goodDistance = distance; }
185            }
186            result = MathHelper.Sqrt(goodDistance);
187            if (count != 0)
188            {
189                result = -result;
190            }
191        }
192
193
194        /// <summary>
195        /// Calculates the Centroid of a polygon.
196        /// </summary>
197        /// <param name="vertexes">The vertexes of the polygon.</param>
198        /// <returns>The Centroid of a polygon.</returns>
199        /// <remarks>
200        /// This is Also known as Center of Gravity/Mass.
201        /// </remarks>
202        public static Vector2D GetCentroid(Vector2D[] vertexes)
203        {
204            Vector2D result;
205            GetCentroid(vertexes, out result);
206            return result;
207        }
208        /// <summary>
209        /// Calculates the Centroid of a polygon.
210        /// </summary>
211        /// <param name="vertexes">The vertexes of the polygon.</param>
212        /// <param name="centroid">The Centroid of a polygon.</param>
213        /// <remarks>
214        /// This is Also known as Center of Gravity/Mass.
215        /// </remarks>
216        public static void GetCentroid(Vector2D[] vertexes, out Vector2D centroid)
217        {
218            if (vertexes == null) { throw new ArgumentNullException("vertexes"); }
219            if (vertexes.Length < 3) { throw new ArgumentOutOfRangeException("vertexes", "There must be at least 3 vertexes"); }
220            centroid = Vector2D.Zero;
221            Scalar temp;
222            Scalar area = 0;
223            Vector2D v1 = vertexes[vertexes.Length - 1];
224            Vector2D v2;
225            for (int index = 0; index < vertexes.Length; ++index, v1 = v2)
226            {
227                v2 = vertexes[index];
228                Vector2D.ZCross(ref v1, ref v2, out temp);
229                area += temp;
230                centroid.X += ((v1.X + v2.X) * temp);
231                centroid.Y += ((v1.Y + v2.Y) * temp);
232            }
233            temp = 1 / (Math.Abs(area) * 3);
234            centroid.X *= temp;
235            centroid.Y *= temp;
236        }
237        /// <summary>
238        /// Calculates the area of a polygon.
239        /// </summary>
240        /// <param name="vertexes">The vertexes of the polygon.</param>
241        /// <returns>the area.</returns>
242        public static Scalar GetArea(Vector2D[] vertexes)
243        {
244            Scalar result;
245            GetArea(vertexes, out result);
246            return result;
247        }
248        /// <summary>
249        /// Calculates the area of a polygon.
250        /// </summary>
251        /// <param name="vertexes">The vertexes of the polygon.</param>
252        /// <param name="result">the area.</param>
253        public static void GetArea(Vector2D[] vertexes, out Scalar result)
254        {
255            if (vertexes == null) { throw new ArgumentNullException("vertexes"); }
256            if (vertexes.Length < 3) { throw new ArgumentOutOfRangeException("vertexes", "There must be at least 3 vertexes"); }
257            Scalar area = 0;
258            Scalar temp;
259            Vector2D v1 = vertexes[vertexes.Length - 1];
260            Vector2D v2;
261            for (int index = 0; index < vertexes.Length; ++index, v1 = v2)
262            {
263                v2 = vertexes[index];
264                Vector2D.ZCross(ref v1, ref v2, out temp);
265                area += temp;
266            }
267            result = Math.Abs(area * .5f);
268        }
269
270        public static Scalar GetPerimeter(Vector2D[] vertexes)
271        {
272            Scalar result;
273            GetPerimeter(vertexes, out result);
274            return result;
275        }
276        public static void GetPerimeter(Vector2D[] vertexes, out Scalar result)
277        {
278            if (vertexes == null) { throw new ArgumentNullException("vertexes"); }
279            if (vertexes.Length < 3) { throw new ArgumentOutOfRangeException("vertexes", "There must be at least 3 vertexes"); }
280            Vector2D v1 = vertexes[vertexes.Length - 1];
281            Vector2D v2;
282            Scalar dist;
283            result = 0;
284            for (int index = 0; index < vertexes.Length; ++index, v1 = v2)
285            {
286                v2 = vertexes[index];
287                Vector2D.Distance(ref v1, ref v2, out dist);
288                result += dist;
289            }
290        }
291
292        public static Scalar GetInertia(Vector2D[] vertexes)
293        {
294            Scalar result;
295            GetInertia(vertexes, out result);
296            return result;
297        }
298        public static void GetInertia(Vector2D[] vertexes, out Scalar result)
299        {
300            if (vertexes == null) { throw new ArgumentNullException("vertexes"); }
301            if (vertexes.Length == 0) { throw new ArgumentOutOfRangeException("vertexes"); }
302            if (vertexes.Length == 1)
303            {
304                result = 0;
305                return;
306            }
307
308            Scalar denom = 0;
309            Scalar numer = 0;
310            Scalar a, b, c, d;
311            Vector2D v1, v2;
312            v1 = vertexes[vertexes.Length - 1];
313            for (int index = 0; index < vertexes.Length; index++, v1 = v2)
314            {
315                v2 = vertexes[index];
316                Vector2D.Dot(ref v2, ref v2, out a);
317                Vector2D.Dot(ref v2, ref v1, out b);
318                Vector2D.Dot(ref v1, ref v1, out c);
319                Vector2D.ZCross(ref v1, ref v2, out d);
320                d = Math.Abs(d);
321                numer += d;
322                denom += (a + b + c) * d;
323            }
324            result = denom / (numer * 6);
325        }
326
327        Vector2D[] vertexes;
328        public BoundingPolygon(Vector2D[] vertexes)
329        {
330            if (vertexes == null) { throw new ArgumentNullException("vertexes"); }
331            if (vertexes.Length < 3) { throw new ArgumentOutOfRangeException("vertexes"); }
332            this.vertexes = vertexes;
333        }
334        public Vector2D[] Vertexes
335        {
336            get { return vertexes; }
337        }
338
339        public Scalar Area
340        {
341            get
342            {
343                Scalar result;
344                GetArea(vertexes, out result);
345                return result;
346            }
347        }
348        public Scalar Perimeter
349        {
350            get
351            {
352                Scalar result;
353                GetPerimeter(vertexes, out result);
354                return result;
355            }
356        }
357
358        public Scalar GetDistance(Vector2D point)
359        {
360            Scalar result;
361            GetDistance(vertexes, ref point, out result);
362            return result;
363        }
364        public void GetDistance(ref Vector2D point, out Scalar result)
365        {
366            GetDistance(vertexes, ref point, out result);
367        }
368
369        public ContainmentType Contains(Vector2D point)
370        {
371            ContainmentType result;
372            Contains(ref point, out result);
373            return result;
374        }
375        public void Contains(ref Vector2D point, out ContainmentType result)
376        {
377            ContainsInclusive(vertexes, ref point, out result);
378        }
379
380        public ContainmentType Contains(BoundingCircle circle)
381        {
382            ContainmentType result;
383            Contains(ref circle, out result);
384            return result;
385        }
386        public void Contains(ref BoundingCircle circle, out ContainmentType result)
387        {
388            Scalar distance;
389            GetDistance(ref circle.Position, out distance);
390            distance += circle.Radius;
391            if (distance <= 0)
392            {
393                result = ContainmentType.Contains;
394            }
395            else if (distance <= circle.Radius)
396            {
397                result = ContainmentType.Intersects;
398            }
399            else
400            {
401                result = ContainmentType.Disjoint;
402            }
403        }
404
405        public ContainmentType Contains(BoundingRectangle rect)
406        {
407            ContainmentType result;
408            Contains(ref rect, out result);
409            return result;
410        }
411        public void Contains(ref BoundingRectangle rect, out ContainmentType result)
412        {
413            Contains(rect.Corners(), out result);
414        }
415
416        public ContainmentType Contains(BoundingPolygon polygon)
417        {
418            ContainmentType result;
419            Contains(ref polygon, out result);
420            return result;
421        }
422        public void Contains(ref BoundingPolygon polygon, out ContainmentType result)
423        {
424            if (polygon == null) { throw new ArgumentNullException("polygon"); }
425            Contains(polygon.vertexes, out result);
426        }
427        private void Contains(Vector2D[] otherVertexes, out ContainmentType result)
428        {
429            ContainmentType contains;
430            result = ContainmentType.Unknown;
431            for (int index = 0; index < vertexes.Length; ++index)
432            {
433                ContainsExclusive(otherVertexes, ref vertexes[index], out contains);
434                if (contains == ContainmentType.Contains) { result = ContainmentType.Intersects; return; }
435            }
436            for (int index = 0; index < otherVertexes.Length && result != ContainmentType.Intersects; ++index)
437            {
438                ContainsInclusive(vertexes, ref otherVertexes[index], out contains);
439                result |= contains;
440            }
441            if (result == ContainmentType.Disjoint)
442            {
443                bool test;
444                Intersects(this.vertexes, otherVertexes, out test);
445                if (test) { result = ContainmentType.Intersects; }
446            }
447        }
448
449        public Scalar Intersects(Ray ray)
450        {
451            Scalar result;
452            Intersects(ref ray, out result);
453            return result;
454        }
455        public bool Intersects(BoundingRectangle rect)
456        {
457            bool result;
458            Intersects(ref rect, out result);
459            return result;
460        }
461        public bool Intersects(BoundingCircle circle)
462        {
463            bool result;
464            Intersects(ref circle, out result);
465            return result;
466        }
467        public bool Intersects(BoundingPolygon polygon)
468        {
469            bool result;
470            Intersects(ref polygon, out result);
471            return result;
472        }
473
474        public void Intersects(ref Ray ray, out Scalar result)
475        {
476            result = -1;
477            for (int index = 0; index < vertexes.Length; ++index)
478            {
479                int index2 = (index + 1) % vertexes.Length;
480                Scalar temp;
481                LineSegment.Intersects(ref vertexes[index], ref vertexes[index2], ref ray, out temp);
482                if (temp >= 0 && (result == -1 || temp < result))
483                {
484                    result = temp;
485                }
486            }
487        }
488        public void Intersects(ref BoundingRectangle rect, out bool result)
489        {
490            Intersects(this.vertexes, rect.Corners(), out result);
491        }
492        public void Intersects(ref BoundingCircle circle, out bool result)
493        {
494            result = false;
495            for (int index = 0; index < vertexes.Length; ++index)
496            {
497                int index2 = (index + 1) % vertexes.Length;
498                Scalar temp;
499                LineSegment.GetDistance(ref vertexes[index], ref vertexes[index2], ref circle.Position, out temp);
500                if (temp <= circle.Radius)
501                {
502                    result = true;
503                    break;
504                }
505            }
506        }
507        public void Intersects(ref BoundingPolygon polygon, out bool result)
508        {
509            if (polygon == null) { throw new ArgumentNullException("polygon"); }
510            Intersects(this.vertexes, polygon.vertexes, out result);
511        }
512    }
513}
Note: See TracBrowser for help on using the repository browser.