Search code examples
javaalgorithmmathgeometryjts

Determining best start and end points for line segment on polygon

I'm having trouble figuring out the best way to solve the following problem. I've tried out multiple methods of solving them but I'm always running into some corner cases.

The problem is the following:

  1. You have a List of coordinates (x and y points) forming a closed polygon. This list is guaranteed to form a polygon with points ordered in a clockwise direction.
  2. You are given a Set of coordinates (x and y points) which are from the above List of coordinates.
  3. You must figure out the start and end points of the line formed using all points in the above Set.

The issue I'm having is that I can't figure out the method of finding the 'best' start and end points. For many scenarios, you can pick the first and last point (using the indices of the List) to form the start and end points, however this could result in a line which is longer than it has to be.

For example, let's say we have the following polygon: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 0 And the following Set of coordinates our line segment must contain: 0, 7, 3.

If we find the min and max indices, we get index(0), index(7), so we can form the line 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7, which is a valid line but it is longer than it needs to be. The best line segment would be 7 -> 0 -> 1 -> 2 -> 3.

How can I find the best (shortest which contains all points in Set) line segment in an efficient manner?

For context: I'm working on an application which using JTS Geometries to draw shapes. The drawn shapes are smoothed using Bezier curves to result in 'curved edges'. After drawing the shapes (by dropping points), users can edit the shape. We want to figure out the start and end points using the points they modify (forms the Set above) so we can 'smooth' only the affected area.

Solution

  • Transform your set into sorted list, concatenate this list with it's copy, where every element is added with number of polygon vertices N, then find the longest empty run (neighbor difference) in this doubled list. Then get sublist of needed length, transform it to continuous range (but take elements modulo N)

    (0,3,7) + (0+8,3+8,7+8) = (0,3,7,8,11,15)

    max difference is 7-3, so the best case sublist starts with 7, it is 

     (7%8 .. 11%8) = (7,0,1,2,3)