7
\$\begingroup\$

I have a library with a lot of duplicate code to accommodate different collection types, and its starting to get a bit tedious, is there a better way to do this to reduce the amount of duplication going on ? Its only going to get worse the more functions i add...

This is my current library script:

using System.Collections.Generic;
using UnityEngine;

namespace Math {
    public static class Geometry
    {
        public static float Area(List<Vector2> points)
        {
            float a = 0;
            for (int i = 0; i < points.Count; i++)
            {
                var p1 = points[i];
                var p2 = points[(i + 1) % points.Count];

                a += p1.x * p2.y - p2.x * p1.y;
            }

            return a * 0.5f;
        }

        public static float Area(List<Vector3> points)
        {
            float a = 0;
            for (int i = 0; i < points.Count; i++)
            {
                var p1 = points[i];
                var p2 = points[(i + 1) % points.Count];

                a += p1.x * p2.z - p2.x * p1.z;
            }
            return a * 0.5f;
        }

        public static float Area(Vector3[] points)
        {
            float a = 0;
            for (int i = 0; i < points.Length; i++)
            {
                var p1 = points[i];
                var p2 = points[(i + 1) % points.Length];

                a += p1.x * p2.z - p2.x * p1.z;
            }
            return a * 0.5f;
        }

        public static float Area(Vector2[] points)
        {
            float a = 0;
            for (int i = 0; i < points.Length; i++)
            {
                var p1 = points[i];
                var p2 = points[(i + 1) % points.Length];

                a += p1.x * p2.y - p2.x * p1.y;
            }
            return a * 0.5f;
        }

        public static bool IsClockwise(List<Vector3> points)
        {
            float sum = 0;

            for (int i = 0; i < points.Count - 1; i++)
            {
                var point1 = points[i];
                var point2 = points[i + 1];

                sum += (point2.x - point1.x) * (point2.z + point1.z);
            }

            return sum > 0;
        }
        public static bool IsClockwise(Vector3[] points)
        {
            float sum = 0;

            for (int i = 0; i < points.Length - 1; i++)
            {
                var point1 = points[i];
                var point2 = points[i + 1];

                sum += (point2.x - point1.x) * (point2.z + point1.z);
            }

            return sum > 0;
        }
        public static bool IsClockwise(List<Vector2> points)
        {
            float sum = 0;

            for (int i = 0; i < points.Count - 1; i++)
            {
                var point1 = points[i];
                var point2 = points[i + 1];

                sum += (point2.x - point1.x) * (point2.y + point1.y);
            }
            return sum > 0;
        }
        public static bool IsClockwise(Vector2[] points)
        {
            float sum = 0;

            for (int i = 0; i < points.Length - 1; i++)
            {
                var point1 = points[i];
                var point2 = points[i + 1];

                sum += (point2.x - point1.x) * (point2.y + point1.y);
            }

            return sum > 0;
        }
    }
}
\$\endgroup\$
4
\$\begingroup\$

Depending on how many points you'll be dealing with, you could go one step further. Since you're only using 2 points from the Vector3, it's fairly simple to cast the Vector3's into Vector2's.

public static float Area(List<Vector2> points)
{
    float a = 0;
    for (int i = 0; i < points.Count; i++)
    {
        var p1 = points[i];
        var p2 = points[(i + 1) % points.Count];

        a += p1.x * p2.y - p2.x * p1.y;
    }

    return a * 0.5f;
}

public static float Area(List<Vector3> points)
{

    return Area(points.Select(x => new Vector2(x.x,x.z)).ToList());
}

public static float Area(Vector3[] points)
{
    return Area(points.ToList());
}

public static float Area(Vector2[] points)
{
    return Area(points.ToList());
}

Upon further reflection the code reduction can be taken a step further by using IEnumerable<T>. Now it becomes:

public static float Area(IEnumerable<Vector2> points)
{
    float a = 0;
    var first = points.First();
    var prev = first;
    foreach (var curr in points.Skip(1))
    {
        a += prev.x * curr.y - curr.x * prev.y;
        prev = curr;

    }
    a += prev.x * first.y - first.x * prev.y;
    return a * 0.5;
}

public static float Area(IEnumerable<Vector3> points)
{

    return Area(points.Select(x => new Vector2(x.x,x.z)));
}
\$\endgroup\$
3
  • \$\begingroup\$ That's gonna be quite inefficient. \$\endgroup\$
    – slepic
    Jan 9 '20 at 6:30
  • \$\begingroup\$ Specifically, the call to Last() is O(a*n) which turns the O(b*n) algorithm to O((a+b)*n). Check my answer to see how to avoid this both with and without linq and also squeeze a bit more flexibility out of all this. \$\endgroup\$
    – slepic
    Jan 9 '20 at 11:54
  • \$\begingroup\$ @slepic - The inefficiency is corrected. \$\endgroup\$
    – user33306
    Jan 10 '20 at 1:57
2
\$\begingroup\$

your non-common code is the line with the formula, so this is what you have to move to the outside, and pass as a parameter.

    public static float Area<T>(IReadOnlyCollection<T> points, Func<T, T, float> func)
    {
        float a = 0;
        for (int i = 0; i < points.Count; i++)
        {
            var p1 = points[i];
            var p2 = points[(i + 1) % points.Count];
            a += func(p1, p2);
        }

        return a * 0.5f;
    }

And this you can call with

   Area(yourpointVector2list, (p1, p2) => p1.x * p2.y - p2.x * p1.y)  
   Area(yourpointVector3list, (p1, p2) => p1.x * p2.z - p2.x * p1.z)

And since I changed it to ICollection, you can use it with lists and arrays, witout having the code twice.
Using the readonly version documents, the method is not changing the collection. (Works with .NET 4.5 and above)

For your "IsClockwise" you can apply this pattern yourself.

It will perform a little slower, the delegate call is a little costly, depending on how often you use it, you will not notice it.

I give you the performance back, at another place

    public static float Area<T>(IReadOnlyCollection<T> points, Func<T, T, float> func)
    {
        float a = 0;
        for (int i = 1; i < points.Count; i++)
        {
            a += func(points[i-1], points[i]);
        }
        a += func(points[points.Count-1], points[0]);

        return a * 0.5f;
    }

This save the 'mod' operation in each iteration.

\$\endgroup\$
4
  • \$\begingroup\$ OK, I make a hint in the answer. After one has made copy&paste, it's always hard to find for others, if something really is a copy, or not. \$\endgroup\$
    – Holger
    Jan 8 '20 at 17:52
  • 1
    \$\begingroup\$ When you move the computation out as parameter you probably dont want it to be called Area anymore. Because you have to provide a specific callback in order for it to provide the area of polygon. \$\endgroup\$
    – slepic
    Jan 9 '20 at 6:33
  • \$\begingroup\$ Anyway i would instead make it return enumerable of pairs of points instead of having to pass callback acceptin such pair. That's gonna be yet more flexible because you can do more then sums. \$\endgroup\$
    – slepic
    Jan 9 '20 at 6:36
  • \$\begingroup\$ It would basically turn the polygon representation as list of points into a list of consecutive line segments which might be easier to work with. \$\endgroup\$
    – slepic
    Jan 9 '20 at 6:38
2
\$\begingroup\$

Extension methods

Notice that I add this to the first arguments of all the functions to allow calling them like points.Area() instead of Area(points).

Polygon Vertices vs. Edges

The biggest problem I see is that you represent the polygon as a list/array (generaly an enumerable) of points. Well that's not bad on it's own. But the fact that all your functions need to treat the polygon as a list of edges rather than vertices makes you repeat the complexity of "converting the representations" in every function again.

And so the first thing I would do, would be to generalize to IEnumerable and create a function that converts the vertices representation into an edges representation. And use yielding to avoid triplication of memory.

Maybe you could do this with linq but it is not necessary. There is a low level interface called IEnumerator. Thats how every IEnumerable achieve the "foreachability", they simply provide an enumerator through the GetEnumerator() method. It is useful whenever you need different code for some items and different for other items. Only when all items are processed the same you fall back to standard foreach (which uses the enumerator for you). The enumerator is probably used directly by linq as well. But true is, sometimes, if you use it directly yourself, you can get the best fit for your case.

And because such function no longer depends on the "point type" it can be made generic.

public static IEnumerable<Tuple<T, T>> GetCircularPairs<T>(this IEnumerable<T> items)
{
    var enumerator = items.GetEnumerator();
    if (enumerator.MoveNext())
    {
        T first = enumerator.Current;
        if (enumerator.MoveNext())
        {
            T previous = first;
            do
            {
                T current = enumerator.Current;
                yield return new Tuple<T, T>(previous, current);
                previous = current;
            } while (enumerator.MoveNext());
            yield return new Tuple<T, T>(previous, first);
        }
    }
}

All your functions could then rely on the edges representation simplifying them a lot. And because we generalized to IEnumerable, you dont need any overloads for lists, arrays, etc...

public static float Area(this IEnumerable<Vector2> points)
{
  float area = 0.0;
  foreach (var (p1, p2) in points.GetCircularPairs()) {
    area += p1.x * p2.y - p2.x * p1.y;
  }
  return area;
}

public static bool IsClockwise(this IEnumerable<Vector2> points)
{
  float sum = 0.0;
  foreach (var (p1, p2) in points.GetCircularPairs()) {
    sum += (p2.x - p1.x) * (p2.y + p1.y);
  }
  return sum > 0;
}

The same in linq:

public static float Area(this IEnumerable<Vector2> points)
{
  return points.GetCircularPairs().Aggregate(0.0, (a, x) => a + x.Item1.x * x.Item2.y - x.Item2.x * x.Item1.y);
}

public static bool IsClockwise(this IEnumerable<Vector2> points)
{
  return 0 < points.GetCircularPairs().Aggregate(0.0, (a, x) => a +(x.Item2.x - x.Item1.x) * (x.Item2.y + x.Item1.y));
}

3D Wrappers may not be necessary

Similarly to @tinstaafl linq solution for Vector3, but extract the select to separate function because that also repeats:

public static IEnumerable<Vector2> OmitY(this IEnumerable<Vector3> points)
{
  return points.Select(p => new Vector2(p.x,p.z));
}

public static float Area(this IEnumerable<Vector3> points)
{
    return points.OmitY().Area();
}

public static bool IsClockwise(this IEnumerable<Vector3> points)
{
    return points.OmitY().IsClockwise();
}

you can solve without linq this way:

public static IEnumerable<Vector2> OmitY(this IEnumerable<Vector3> points)
{
  foreach (var p in points) {
    yield return new Vector2(p.x,p.z);
  }
}

You see that maybe you will want to also define OmitX and OmitZ, and then maybe the 3D wrappers would need variants for that too (ie AreaXOmitted, etc.), so it becomes disuptable whether they are needed at all or rather let the consumer choose which axis to omit by calling OmitX|Y|Z himself before calling Area and/or IsClockwise on it. But by all means, if you feel that omitting y is the best fit for most cases, go for it and add this y-omitting overload :)

Linq or No Linq?

As you can see with Linq the code gets a bit shorter in height and longer in width :). Also depends on you if you wanna make it dependent on Linq. I wouldn't see any problem with it as Linq is commonly used anyway. On other hand, in the code you needed Select and Aggregate functions from linq. And these actually encapsulate a very trivial using such wrappers may cause some performance drop. To show how trivial they are here is a possible implementation:

public static IEnumerable<R> Select<R,T>(this IEnumerable<T> items, Func<T,R> f)
{
    foreach (var item in items)
    {
        yield return f(item);
    }
}

public static R Aggregate<R,T>(this IEnumerable<T> items, R acc, Func<R,T,R> f)
{
    foreach (var item in items)
    {
        acc = f(acc, item);
    }
    return acc;
}

Some More Abstraction?

If the expression p1.x * p2.y - p2.x * p1.y make any "Sense" separately you can also create a function for it (depends how far you wanna go :)):

public static float AreaSense(this Tuple<Vector2, Vector2> edge)
{
  return edge.Item1.x * edge.Item2.y - edge.Item2.x * edge.Item1.y
}

public static float ClockwiseSense(this Tuple<Vector2, Vector2> edge)
{
  return (edge.Item2.x - edge.Item1.x) * (edge.Item2.y + edge.Item1.y);
}

public static float Area(this IEnumerable<Vector2> points)
{
  return points.GetCircularPairs().Select(p => p.AreaSense()).Sum();
  // supposing Sum() is the obvious Aggregate(0.0, (a,x) => a+x)
}

// or aggregate directly
public static float IsClockwise(this IEnumerable<Vector2> points)
{
  return points.GetCircularPairs().Aggregate(0.0, (a,p) => a + p.ClockwiseSense());
}

Increased performance without linq

You can increase performance by bypassing linq and merging everything possible together, and you get something similar to what @Holger suggests in his answer, but it is generalized for anything enumerable, not just read only collections.

public static float SumCircluarPairs<T>(this IEnumerable<T> points, Func<T, T, float> f)
{
    float sum = 0.0;
    var enumerator = items.GetEnumerator();
    if (enumerator.MoveNext())
    {
        T first = enumerator.Current;
        if (enumerator.MoveNext())
        {
            T previous = first;
            do
            {
                T current = enumerator.Current;
                sum += f(previous, current);
                previous = current;
            } while (enumerator.MoveNext());
            sum += f(previous, first);
        }
    }
    return sum;
} 

public static float Area(this IEnumerable<Vector2> points)
{
  return points.SumCircularPairs((p1, p2) => p1.x * p2.y - p2.x * p1.y);
}
\$\endgroup\$
6
  • \$\begingroup\$ Maybe you get the price for creativity and elegance, but for sure not for performance. So many function calls, Creation of enumerators, 3-level-member access, delegates and tons of object creations. If you run it once in a while it's nice, but not if you need to rotate some 10.000 vector grid-model with 25 frames/second. No use of Linq is only the weakest condition, extend it with no foreach(no enumerators), no object creation, stack limited to 10 items ;-) \$\endgroup\$
    – Holger
    Jan 9 '20 at 18:09
  • \$\begingroup\$ @Holger You can also merge the approach from GetCircularPairs with the expression AreaSense/ClockwiseSense, inlining the expression instead of the yields and making the aggregation inside that function. That way you avoid extra enumeration wrappers from Select and Aggregate while keeping it work for any enumerable, althoutgh you will have to repeat the GetCircularPairs logic in both Area() and IsClockwise(), unless you expose the expression logic as a callback argument like you did in your answer. But with the callback you still get many function calls against which you object. \$\endgroup\$
    – slepic
    Jan 9 '20 at 18:21
  • \$\begingroup\$ @Holger I have added a new section on the end showing the implementation as I descibed in previous comment using the callback... \$\endgroup\$
    – slepic
    Jan 9 '20 at 18:36
  • \$\begingroup\$ I just wanted to direct attention on all the GetEnumerator, MoveNext and Current, calls. This can all be avoided if you don' turn it down to IEnumerable and not use foreach. But I'm just combining the best of our ideas, we just demonstrate different techniques. for case T is a huge struct, you move quiet a lot of bytes. (btw: it's points.getenumerator, not items.getenumerator) \$\endgroup\$
    – Holger
    Jan 9 '20 at 21:36
  • \$\begingroup\$ if we do the sum over 3 points, like (p1, p2, p3) => (p1.x-p3.x)*p2.y - (p3.y-p1.y)*p2.x we have only 6 member accesses instead of 8, and 5 math operations instead of 7, and half the number of loops and delegate calls ;-) \$\endgroup\$
    – Holger
    Jan 9 '20 at 21:39
1
\$\begingroup\$

You could avoid a lot of duplicated code if you call one overloaded method from the other overloaded one.

An IList<T> can be easily changed to a [T] array by just calling the ToArray() method of that List. This would result in e.g public static float Area(List<Vector3> points) looking like so

public static float Area(IList<Vector3> points)
{
    return Area(points.ToArray());
}

public static float Area(Vector3[] points)
{
    float a = 0;
    for (int i = 0; i < points.Length; i++)
    {
        var p1 = points[i];
        var p2 = points[(i + 1) % points.Length];

        a += p1.x * p2.z - p2.x * p1.z;
    }
    return a * 0.5f;
}  
\$\endgroup\$
5
  • \$\begingroup\$ How about just having one method for IEnumerable<T>? That covers both List And Array And many more. \$\endgroup\$
    – slepic
    Jan 8 '20 at 6:15
  • \$\begingroup\$ @slepic and later on you will return it into an array again or what? The items are accessed by index hence a IEnumerable<T> won't fit. \$\endgroup\$
    – Heslacher
    Jan 8 '20 at 6:17
  • \$\begingroup\$ @Heslacher IList<T> then. \$\endgroup\$
    – JAD
    Jan 8 '20 at 7:37
  • \$\begingroup\$ @Heslacher Indeed they are. But is it necessary? Compute for first versus last. Set first as previous. Then loop from second to end comparing current to previous. Set current as previous on end of each iteration. \$\endgroup\$
    – slepic
    Jan 8 '20 at 8:12
  • \$\begingroup\$ Why do you need Area(Vector3[] points) when the first method with the IList<Vector3> argument can be called with an array of Vector3? An array implements IList<T> \$\endgroup\$
    – user73941
    Jan 8 '20 at 17:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.