You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
333 lines
17 KiB
333 lines
17 KiB
import {
|
|
addBoundingSquareTo,
|
|
getDirectionSorter,
|
|
Graph,
|
|
GraphBoundary,
|
|
GraphDirection,
|
|
Point,
|
|
Segment,
|
|
SegmentWithIntersection, Triangle
|
|
} from "./pslg";
|
|
|
|
export function getFirstIntersectingSegmentInDirection(raySegment: Segment, boundary: GraphBoundary, graph: Graph, direction: GraphDirection, inclusive = false): [Segment, Point] {
|
|
const intersectingSegment = boundary.getBoundary(direction)
|
|
const intersectingPoint = raySegment.getIntersectionWith(intersectingSegment)
|
|
if ( !intersectingPoint ) {
|
|
console.log(
|
|
'getFirstIntersectingSegmentInDirection',
|
|
[raySegment.from.coordinate, raySegment.to.coordinate],
|
|
[intersectingSegment.from.coordinate, intersectingSegment.to.coordinate],
|
|
intersectingPoint
|
|
)
|
|
throw new RangeError('Ray segment does not extend to boundary in the given direction!')
|
|
}
|
|
|
|
// Now, collect all non-boundary segments that intersect with the ray segment
|
|
const intersections = (graph.segments
|
|
.map(segment => {
|
|
if ( boundary.isBoundarySegment(segment) ) return undefined
|
|
|
|
return {
|
|
segment,
|
|
intersect: segment[inclusive ? 'getIntersectionWith' : 'getIntersectionWithin'](raySegment)
|
|
}
|
|
})
|
|
.filter(x => x && x.intersect) as SegmentWithIntersection[])
|
|
.sort(getDirectionSorter(direction))
|
|
|
|
const intersection = intersections[0]
|
|
if ( intersection ) {
|
|
return [intersection.segment, intersection.intersect]
|
|
}
|
|
|
|
return [intersectingSegment, intersectingPoint]
|
|
}
|
|
|
|
export function triangulate(originalGraph: Graph): Graph {
|
|
const graph = originalGraph.clone()
|
|
const trapezoidSegments: Segment[] = [] //graph.segments.filter(segment => segment.isHorizontal())
|
|
|
|
const boundary = addBoundingSquareTo(graph)
|
|
const leftBound = boundary.getLeftBoundary()
|
|
const rightBound = boundary.getRightBoundary()
|
|
|
|
// trapezoidSegments.push(boundary.getLowerBoundary())
|
|
|
|
// For each vertex in the original graph, create a horizontal line that
|
|
// extends in both directions until it intersects with either (1) the boundary
|
|
// or (2) a segment in the graph.
|
|
const originalPoints = [...graph.points]
|
|
for ( const point of originalPoints ) {
|
|
if ( boundary.isBoundaryPoint(point) ) continue // skip boundary points
|
|
|
|
// First, check if there is a horizontal segment ending at this point
|
|
// extending toward the left
|
|
const hasLeftHorizon = graph.getSegmentsEndingAt(point)
|
|
.some(segment => segment.isHorizontal() && segment.getOtherPoint(point).isLeftOf(point))
|
|
|
|
let leftmostPoint: Point = point
|
|
let rightmostPoint: Point = point
|
|
let leftIntersectionRay: Segment
|
|
let rightIntersectionRay: Segment
|
|
|
|
if ( !hasLeftHorizon ) {
|
|
const leftRaySegment = new Segment(point, Point.from(boundary.getLeftBoundary().xmin, point.y))
|
|
const [leftIntersectingSegment, leftIntersectingPoint] = getFirstIntersectingSegmentInDirection(
|
|
leftRaySegment,
|
|
boundary,
|
|
graph,
|
|
GraphDirection.LEFT
|
|
)
|
|
|
|
leftmostPoint = leftIntersectingPoint
|
|
leftIntersectionRay = leftIntersectingSegment
|
|
}
|
|
|
|
// First, check if there is a horizontal segment ending at this point
|
|
// extending toward the left
|
|
const hasRightHorizon = graph.getSegmentsEndingAt(point)
|
|
.some(segment => segment.isHorizontal() && segment.getOtherPoint(point).isRightOf(point))
|
|
|
|
if ( !hasRightHorizon ) {
|
|
const rightRaySegment = new Segment(point, Point.from(boundary.getRightBoundary().xmin, point.y))
|
|
const [rightIntersectingSegment, rightIntersectingPoint] = getFirstIntersectingSegmentInDirection(
|
|
rightRaySegment,
|
|
boundary,
|
|
graph,
|
|
GraphDirection.RIGHT
|
|
)
|
|
|
|
rightmostPoint = rightIntersectingPoint
|
|
rightIntersectionRay = rightIntersectingSegment
|
|
}
|
|
|
|
if ( !leftmostPoint.is(rightmostPoint) ) {
|
|
// Check if this point has a line segment extending from both sides.
|
|
// If so, then the line segment will bisect a captive area to create 2 trapezoids,
|
|
// so we need to make 2 line segments.
|
|
|
|
let hasSegmentBelow = false
|
|
let hasSegmentAbove = false
|
|
graph.getSegmentsEndingAt(point)
|
|
.forEach(segment => {
|
|
const otherPoint = segment.getOtherPoint(point)
|
|
if ( otherPoint.y > point.y ) hasSegmentAbove = true
|
|
if ( otherPoint.y < point.y ) hasSegmentBelow = true
|
|
})
|
|
|
|
if ( hasSegmentAbove && hasSegmentBelow ) {
|
|
trapezoidSegments.push(graph.findExistingSegmentOrAdd(new Segment(leftmostPoint, point)))
|
|
trapezoidSegments.push(graph.findExistingSegmentOrAdd(new Segment(rightmostPoint, point)))
|
|
} else {
|
|
trapezoidSegments.push(graph.findExistingSegmentOrAdd(new Segment(leftmostPoint, rightmostPoint)))
|
|
}
|
|
}
|
|
}
|
|
|
|
// Any horizontal segments present in the original graph will also be used for form
|
|
// trapezoids, so push them onto the list of trapezoid base segments.
|
|
originalGraph.segments
|
|
.filter(segment => segment.isHorizontal())
|
|
.forEach(segment => trapezoidSegments.push(segment))
|
|
|
|
// Now, go through and identify trapezoids for all the horizontal segments we just added
|
|
for ( const segment of trapezoidSegments ) {
|
|
// Find the trapezoid formed with the segment as the bottom
|
|
// Create a vertical segment from the midpoint of the segment to the top boundary
|
|
const horizontalMidpoint = segment.getMidpoint()
|
|
let upperBoundaryPoint = Point.from(horizontalMidpoint.x, boundary.ymax)
|
|
let upperBoundaryVerticalSegment = new Segment(horizontalMidpoint, upperBoundaryPoint)
|
|
|
|
let [upperIntersectSegment, upperIntersectPoint] = getFirstIntersectingSegmentInDirection(
|
|
upperBoundaryVerticalSegment,
|
|
boundary,
|
|
graph,
|
|
GraphDirection.UP
|
|
)
|
|
|
|
upperBoundaryVerticalSegment = new Segment(horizontalMidpoint, upperIntersectPoint)
|
|
|
|
// Now we have the upper and lower boundaries of the trapezoid.
|
|
// So, we need to figure out the left and right boundaries next.
|
|
// Get the midpoint of the vertical segment
|
|
const verticalMidpoint = upperBoundaryVerticalSegment.getMidpoint()
|
|
let leftBoundaryPoint = Point.from(boundary.xmin, verticalMidpoint.y)
|
|
let leftBoundaryHorizontalSegment = new Segment(verticalMidpoint, leftBoundaryPoint)
|
|
|
|
const [leftIntersectSegment, leftIntersectPoint] = getFirstIntersectingSegmentInDirection(
|
|
leftBoundaryHorizontalSegment,
|
|
boundary,
|
|
graph,
|
|
GraphDirection.LEFT,
|
|
true
|
|
)
|
|
|
|
leftBoundaryHorizontalSegment = new Segment(verticalMidpoint, leftIntersectPoint)
|
|
|
|
// Repeat to get the right boundary
|
|
let rightBoundaryPoint = Point.from(boundary.xmax, verticalMidpoint.y)
|
|
let rightBoundaryHorizontalSegment = new Segment(verticalMidpoint, rightBoundaryPoint)
|
|
|
|
const [rightIntersectSegment, rightIntersectPoint] = getFirstIntersectingSegmentInDirection(
|
|
rightBoundaryHorizontalSegment,
|
|
boundary,
|
|
graph,
|
|
GraphDirection.RIGHT,
|
|
true
|
|
)
|
|
|
|
rightBoundaryHorizontalSegment = new Segment(verticalMidpoint, rightIntersectPoint)
|
|
|
|
// Check if the upper boundary segment extends beyond the x-range of the left- and right-boundary segments
|
|
// If so, we need to split it to fit within the bounds of the current trapezoid, starting with the right side
|
|
if ( upperIntersectSegment.xmax > rightIntersectSegment.xmax ) {
|
|
let [upperIntersectSplit1, upperIntersectSplit2] = upperIntersectSegment.splitAt(
|
|
Point.from(rightIntersectSegment.xmax, upperIntersectSegment.ymax)
|
|
)
|
|
|
|
graph.removeSegment(upperIntersectSegment)
|
|
upperIntersectSplit1 = graph.findExistingSegmentOrAdd(upperIntersectSplit1)
|
|
upperIntersectSplit2 = graph.findExistingSegmentOrAdd(upperIntersectSplit2)
|
|
|
|
upperIntersectSegment = upperIntersectSplit1.xmax === rightIntersectSegment.xmax ? upperIntersectSplit1 : upperIntersectSplit2
|
|
}
|
|
|
|
// Repeat for the left side
|
|
if ( upperIntersectSegment.xmin < leftIntersectSegment.xmin ) {
|
|
let [upperIntersectSplit1, upperIntersectSplit2] = upperIntersectSegment.splitAt(
|
|
Point.from(leftIntersectSegment.xmin, upperIntersectSegment.ymax)
|
|
)
|
|
|
|
graph.removeSegment(upperIntersectSegment)
|
|
upperIntersectSplit1 = graph.findExistingSegmentOrAdd(upperIntersectSplit1)
|
|
upperIntersectSplit2 = graph.findExistingSegmentOrAdd(upperIntersectSplit2)
|
|
|
|
upperIntersectSegment = upperIntersectSplit1.xmin === leftIntersectSegment.xmin ? upperIntersectSplit1 : upperIntersectSplit2
|
|
}
|
|
|
|
// Now, check if we actually have a 4-bound trapezoid, or if we have a triangle
|
|
const points = Point.distinct([
|
|
segment.from,
|
|
segment.to,
|
|
upperIntersectSegment.from,
|
|
upperIntersectSegment.to,
|
|
])
|
|
|
|
// Now, we have the 4 bounding segments of the trapezoid.
|
|
// Let's find the segments that make up the trapezoid
|
|
// We will do this by re-creating segments for the four sides of the trapezoid
|
|
// Split the left-side on the intersection point
|
|
const leftSegmentIntersectPoint = leftIntersectSegment.getIntersectionWith(segment)
|
|
if ( !leftSegmentIntersectPoint ) {
|
|
console.log('!leftSegmentIntersectPoint', segment.toQuickDisplay(), leftIntersectSegment.toQuickDisplay())
|
|
throw new Error('Unable to find trapezoid segment intersection')
|
|
}
|
|
|
|
// TODO Account for the case where we don't need to split the segment.
|
|
let trapezoidLeftBoundSegment = leftIntersectSegment
|
|
// let leftSegment1: Segment | undefined
|
|
// let leftSegment2: Segment | undefined
|
|
if ( !leftIntersectSegment.hasPoint(leftSegmentIntersectPoint) ) {
|
|
let [leftSegment1, leftSegment2] = leftIntersectSegment.splitAt(leftSegmentIntersectPoint)
|
|
graph.removeSegment(leftIntersectSegment)
|
|
leftSegment1 = graph.findExistingSegmentOrAdd(leftSegment1)
|
|
leftSegment2 = graph.findExistingSegmentOrAdd(leftSegment2)
|
|
|
|
// We care about the upper-segment from the split, as that is the bound of our trapezoid
|
|
trapezoidLeftBoundSegment = leftSegment1.ymin === leftSegmentIntersectPoint.y ? leftSegment1 : leftSegment2
|
|
|
|
// Now, we need to consider the case where the upper segment we split extends beyond the upper bound of
|
|
// the trapezoid we are working with now. If so, split the upper segment again.
|
|
if ( trapezoidLeftBoundSegment.ymax > upperIntersectPoint.y && points.length > 3 ) {
|
|
// The left bound extends beyond the top of this trapezoid. So, split it.
|
|
let localLeftUpperSplitPoint = Point.from(trapezoidLeftBoundSegment.xmin, upperIntersectPoint.y)
|
|
let [leftUpperSegment1, leftUpperSegment2] = trapezoidLeftBoundSegment.splitAt(localLeftUpperSplitPoint)
|
|
graph.removeSegment(trapezoidLeftBoundSegment)
|
|
leftUpperSegment1 = graph.findExistingSegmentOrAdd(leftUpperSegment1)
|
|
leftUpperSegment2 = graph.findExistingSegmentOrAdd(leftUpperSegment2)
|
|
|
|
trapezoidLeftBoundSegment = leftUpperSegment1.ymax === upperIntersectPoint.y ? leftUpperSegment1 : leftUpperSegment2
|
|
}
|
|
}
|
|
|
|
graph.findExistingSegmentOrAdd(trapezoidLeftBoundSegment)
|
|
|
|
// Repeat this process for the right-side segment
|
|
const rightSegmentIntersectPoint = rightIntersectSegment.getIntersectionWith(segment)
|
|
if ( !rightSegmentIntersectPoint ) throw new Error('Unable to find trapezoid segment intersection')
|
|
|
|
let trapezoidRightBoundSegment = rightIntersectSegment
|
|
if ( !rightIntersectSegment.hasPoint(rightSegmentIntersectPoint) ) {
|
|
let [rightSegment1, rightSegment2] = rightIntersectSegment.splitAt(rightSegmentIntersectPoint)
|
|
graph.removeSegment(rightIntersectSegment)
|
|
rightSegment1 = graph.findExistingSegmentOrAdd(rightSegment1)
|
|
rightSegment2 = graph.findExistingSegmentOrAdd(rightSegment2)
|
|
|
|
// We care about the upper-segment from the split, as that is the bound of our trapezoid
|
|
trapezoidRightBoundSegment = rightSegment1.ymin === rightSegmentIntersectPoint.y ? rightSegment1 : rightSegment2
|
|
|
|
// Now, we need to consider the case where the upper segment we split extends beyond the upper bound of
|
|
// the trapezoid we are working with now. If so, split the upper segment again.
|
|
if ( trapezoidRightBoundSegment.ymax > upperIntersectPoint.y && points.length > 3 ) {
|
|
// The left bound extends beyond the top of this trapezoid. So, split it.
|
|
let localRightUpperSplitPoint = Point.from(trapezoidRightBoundSegment.xmin, upperIntersectPoint.y)
|
|
let [rightUpperSegment1, rightUpperSegment2] = trapezoidRightBoundSegment.splitAt(localRightUpperSplitPoint)
|
|
graph.removeSegment(trapezoidRightBoundSegment)
|
|
rightUpperSegment1 = graph.findExistingSegmentOrAdd(rightUpperSegment1)
|
|
rightUpperSegment2 = graph.findExistingSegmentOrAdd(rightUpperSegment2)
|
|
|
|
trapezoidRightBoundSegment = rightUpperSegment1.ymax === upperIntersectPoint.y ? rightUpperSegment1 : rightUpperSegment2
|
|
}
|
|
}
|
|
|
|
// break;
|
|
|
|
if ( points.length === 3 ) {
|
|
// We found a triangle! Less work.
|
|
// Create the triangle and push it onto the graph
|
|
// const [p1, p2, p3] = points.map(x => graph.findExistingPointOrAdd(x))
|
|
// const s12 = graph.findExistingSegmentOrAdd(new Segment(p1, p2))
|
|
// const s23 = graph.findExistingSegmentOrAdd(new Segment(p2, p3))
|
|
// const s31 = graph.findExistingSegmentOrAdd(new Segment(p3, p1))
|
|
graph.findExistingTriangleOrAdd(new Triangle([trapezoidLeftBoundSegment, trapezoidRightBoundSegment, segment]))
|
|
continue // FIXME - remove to handle below-segment case
|
|
}
|
|
|
|
if ( points.length !== 4 ) {
|
|
throw new RangeError('Found shape with invalid number of distinct points!')
|
|
}
|
|
|
|
// Now we have all 4 bounding segments. We find the bisector that creates
|
|
// triangles with the largest minimum angle.
|
|
|
|
// First, try making triangles from bottom-left to top-right
|
|
const lowerLeftPoint = graph.findExistingPointOrAdd(Point.from(segment.xmin, segment.ymin))
|
|
const upperRightPoint = graph.findExistingPointOrAdd(Point.from(upperIntersectSegment.xmax, upperIntersectSegment.ymax))
|
|
|
|
const bottomLeftBisectorSegment = new Segment(lowerLeftPoint, upperRightPoint)
|
|
const bottomLeftBisectorUpperTriangle = new Triangle([bottomLeftBisectorSegment, upperIntersectSegment, trapezoidLeftBoundSegment])
|
|
const bottomLeftBisectorLowerTriangle = new Triangle([bottomLeftBisectorSegment, segment, trapezoidRightBoundSegment])
|
|
const bottomLeftBisectorMinAngle = Math.min(bottomLeftBisectorUpperTriangle.getMinimumAngle(), bottomLeftBisectorLowerTriangle.getMinimumAngle())
|
|
|
|
const upperLeftPoint = graph.findExistingPointOrAdd(Point.from(upperIntersectSegment.xmin, upperIntersectSegment.ymax))
|
|
const lowerRightPoint = graph.findExistingPointOrAdd(Point.from(segment.xmax, segment.ymin))
|
|
|
|
const topRightBisectorSegment = new Segment(upperLeftPoint, lowerRightPoint)
|
|
const upperRightBisectorUpperTriangle = new Triangle([topRightBisectorSegment, upperIntersectSegment, trapezoidRightBoundSegment])
|
|
const upperRightBisectorLowerTriangle = new Triangle([topRightBisectorSegment, trapezoidLeftBoundSegment, segment])
|
|
const upperRightBisectorMinAngle = Math.min(upperRightBisectorUpperTriangle.getMinimumAngle(), upperRightBisectorLowerTriangle.getMinimumAngle())
|
|
|
|
const optimalBisectorUpperTriangle = upperRightBisectorMinAngle > bottomLeftBisectorMinAngle ? upperRightBisectorUpperTriangle : bottomLeftBisectorUpperTriangle
|
|
const optimalBisectorLowerTriangle = upperRightBisectorMinAngle > bottomLeftBisectorMinAngle ? upperRightBisectorLowerTriangle : bottomLeftBisectorLowerTriangle
|
|
|
|
// Add the triangles to the graph
|
|
const upperTriangleSegments = optimalBisectorUpperTriangle.sides.map(side => graph.findExistingSegmentOrAdd(side))
|
|
graph.findExistingTriangleOrAdd(new Triangle(upperTriangleSegments as [Segment, Segment, Segment]))
|
|
|
|
const lowerTriangleSegments = optimalBisectorLowerTriangle.sides.map(side => graph.findExistingSegmentOrAdd(side))
|
|
graph.findExistingTriangleOrAdd(new Triangle(lowerTriangleSegments as [Segment, Segment, Segment]))
|
|
}
|
|
|
|
return graph
|
|
}
|